5 篇笔记 写笔记

1. #0

   alisa_l_zhang

   187***[email protected]

   354

   参考内容:

   def quicksort(arr): 
    if len(arr) <= 1: 
    return arr 
    pivot = arr[len(arr) // 2] 
    left = [x for x in arr if x < pivot] 
    middle = [x for x in arr if x == pivot] 
    right = [x for x in arr if x > pivot] 
    return quicksort(left) + middle + quicksort(right)
   print(quicksort([3, 6, 8, 19, 1, 5])) # [1,3, 5, 6, 8, 19]
   

   alisa_l_zhang

   187***[email protected]

   7年前 (2019年10月08日)
2. #0

   LYLM

   109***[email protected]

   14

   考上面的笔记,综合了一下。(以最后列表最后一个元素作pivot)

   def quickSort(aList):
    if len(aList) <= 1:
    return aList
    pivot = aList[len(aList)-1]
    pivot = -1
    for index,item in enumerate(aList):
    if item < pivot:
    pivot += 1
    aList[pivot], aList[index] = aList[index], aList[pivot]
    pivot = pivot + 1
    aList[pivot], aList[index] = aList[index], aList[pivot]
    left = quickSort(aList[:pivot]) 
    middle = [aList[pivot]]
    right = quickSort(aList[pivot+1:])
    newList = left+middle+right
    return newList
    
   theList = [123,45,32,555,64,31,45,50,658,55,1,45]
   result = quickSort(theList)

   LYLM

   109***[email protected]

   7年前 (2020年01月03日)
3. #0

   hjklo

   123***[email protected]

   37

   使用递归、分治思想的快速排序:

   def quickSort(arr):
    if(len(arr)<2): #不用进行排序
    return arr
    else:
    pivot=arr[0]
    less=[i for i in arr[1:] if(i<=pivot)]
    great=[i for i in arr[1:] if(i>pivot)]
    return quickSort(less)+[pivot]+quickSort(great)
   arr=[1,4,5,2,41,4,24,5]
   print("原始数据:",arr)
   print("排序后的数据:",quickSort(arr))

   hjklo

   123***[email protected]

   6年前 (2020年04月27日)
4. #0

   风之语故乡

   272***[email protected]

   10

   内存消耗小,时间复杂度稳定,不改变原有元素类型(比如是numpy),速度也快.(1000000个数据大约5秒多)

   def quickSort(arr):
    len_ = len(arr)
    if len_ <= 1:
    return
    pivot = arr[len_//2] # 基准数为中间元素,中间元素位置空出来,一定要用中间元素为基准,
    # 若取第一或末尾,对排好顺序的序列,时间复杂度会变成指数O(n^2)
    arr[len_//2] = arr[0] # 中间空位放入第一个元素,此时第一元素的位置空出来
    left = 0 # 左边界(边界之外是已经处理好的元素,边界之内是未处理的元素)
    right = len_-1 # 右边界
    # 当左侧有空位时,从最右侧找出小于基准的元素放入空位,当右侧有空位时,从左侧找出大于基准的
    is_cell_left = True # 空位在左侧
    while (left < right):
    if is_cell_left: # 空位在左侧
    if(arr[right] >= pivot): # 如果右侧元素>=基准
    right -= 1 # 右边界缩小
    else:
    arr[left] = arr[right] # 右侧元素放入空位
    left += 1
    is_cell_left = False # 空位在右侧
    else: # 空位在右侧
    if(arr[left] <= pivot): # 如果左侧元素>=基准
    left += 1 # 左边界缩小
    else:
    arr[right] = arr[left] # 左侧元素放入空位
    right -= 1
    is_cell_left = True # 空位在左侧
    arr[left] = pivot
    quickSort(arr[:left])
    quickSort(arr[left+1:])

   风之语故乡

   272***[email protected]

   4年前 (2022年02月22日)
5. #0

   Gbosh

   ge1***[email protected]

   2

   参考方法:

   def quick_sort(alist, start, end):
    """快速排序"""
    if start >= end: # 递归的退出条件
    return
    mid = alist[start] # 设定起始的基准元素
    low = start # low为序列左边在开始位置的由左向右移动的游标
    high = end # high为序列右边末尾位置的由右向左移动的游标
    while low < high:
    # 如果low与high未重合,high(右边)指向的元素大于等于基准元素,则high向左移动
    while low < high and alist[high] >= mid:
    high -= 1
    alist[low] = alist[high] # 走到此位置时high指向一个比基准元素小的元素,将high指向的元素放到low的位置上,此时high指向的位置空着,接下来移动low找到符合条件的元素放在此处
    # 如果low与high未重合,low指向的元素比基准元素小,则low向右移动
    while low < high and alist[low] < mid:
    low += 1
    alist[high] = alist[low] # 此时low指向一个比基准元素大的元素,将low指向的元素放到high空着的位置上,此时low指向的位置空着,之后进行下一次循环,将high找到符合条件的元素填到此处
    # 退出循环后,low与high重合,此时所指位置为基准元素的正确位置,左边的元素都比基准元素小,右边的元素都比基准元素大
    alist[low] = mid # 将基准元素放到该位置,
    # 对基准元素左边的子序列进行快速排序
    quick_sort(alist, start, low - 1) # start :0 low -1 原基准元素靠左边一位
    # 对基准元素右边的子序列进行快速排序
    quick_sort(alist, low + 1, end) # low+1 : 原基准元素靠右一位 end: 最后
   alist = [3, 6, 8, 19, 1, 5]
   quick_sort(alist, 0, len(alist) - 1)
   print(alist) # 输出 [1, 3, 5, 6, 8, 19]

   Gbosh

   ge1***[email protected]

   4年前 (2022年09月14日)