20191209-八大排序之快速排序

baike 2019-12-09

1. 快速排序

算法核心思想

 取待排序数组第一个数作为参照数,建立left和right数组left存储小于参照数的数组集合,right存储大于参照数的数组集合,然后分别对left和right进行递归调用排序。具体算法逻辑如下:

  1. 先从数列中取出一个数作为基准数。
  2. 分区过程,将比这个数大的数全放到它的右边,小于或等于它的数全放到它的左边。
  3. 再对左右区间重复第二步,直到各区间只有一个数

代码实现01

#encoding=utf-8
def quickSort(arr,start,end):
    if start>=end:
        return arr
    low,high = start,end
    temp = arr[low]
    while low<high:
        while low < high and arr[high]>=temp:
            high-=1
        arr[low] = arr[high]
        while low < high and arr[low]<=temp:
            low+=1
        arr[high] = arr[low]
        print("low = %s,high=%s,arr=%s"%(low,high,arr))
    arr[low] = temp
    quickSort(arr,start,low)
    quickSort(arr,low+1,end)
    return arr
arr = [3,2,1,5,6,4,3,9]
print(quickSort(arr,0,len(arr)-1))

执行解析01

通过循环的从右向左比较和从左向右比较,最终low=high,此时将基准数据放置在low的位置,然后对start---low和low+1---end的数递归调用排序

  1. 取待排序的数组第一个数作为基准数,设两个指示标志:low指向起始位置,high指向末尾
  2. 从列表的high位置向前扫描,如果arr[high]>基准数,high-=1,如果arr[high]<基准数,将arr[high]赋值给arr[low],然后从low开始向后扫描
  3. 从low开始向后扫描如果arr[low]<基准数,low+=1,如果arr[low]>基准数,将arr[low]赋值给arr[high],然后从high开始向前扫描
  4. 重复上述步骤知道low=high,此时arr[low]的位置就是基准数的位置,然后对0-low,low-len(arr)的数进行快速排序

代码实现02

def PythonQuickSort(arr):
    if not arr:
        return arr
    temp = arr[0]
    left = [x for x in arr[1:] if x<=temp]
    right = [x for x in arr[1:] if x > temp]
    return PythonQuickSort(left)+[temp]+PythonQuickSort(right)
print(PythonQuickSort(arr))

执行解析02

PythonQuickSort的代码实现是基于Python的语言特性(列表长度可变来写的代码),主体思路同代码实现01一样

总结

时间复杂度:为O(nlogn)

空间复杂度:快速排序使用递归,递归使用栈,因此它的空间复杂度为O(logn)

稳定性:快速排序无法保证相等的元素的相对位置不变,因此它是不稳定的排序算法

相关推荐