算法学习：快速排序

1、基本思想

取待排序数组第一个数作为参照数，建立left和right数组，left存储小于参照数的数组集合，right存储大于参照数的数组集合，然后分别对left和right进行递归调用排序。

 

2、举例

[11,2,3,43,23,5,6,9,10]
取任意的一个数为基准数
temp = arr[0]
遍历数组，将比temp小的元素放在temp的左边，比temp大的元素放在temp的右边
left+【temp】+right
然后对左边和右边的元素分别进行quicksort
[3,21,1,999,9,2,2]
temp =3 
left = [1]
right = [21]

[1,3,21]

3、实现步骤

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

4、实现方法1

def quickSort(start_idx,end_idx,arr): 
    """start_idx和end_idx确定排序区间""" 
    if start_idx>=end_idx:
        return arr
    low,high = start_idx,end_idx#设定2个指针分别执行待排序数组的起始和结束位置 
    temp=arr[low]#设置基准数temp = arr[low]
    while low<high:
        while low< high and arr[high]>=temp:#从队尾向前扫描，如果队尾的数小于temp将队尾的数放在low的位置 
            high-=1
        arr[low] = arr[high]
        while low<high and arr[low]<temp:#从队首向后扫描，如果队首的数大于temp将队首的数放在high的位置
            low+=1 
        arr[high] = arr[low]
    arr[low] = temp 
    quickSort(start_idx,low,arr) 
    quickSort(low+1,end_idx,arr) 
    return arr

5、实现方法2

def quickSort02(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 quickSort02(left)+[temp]+quickSort02(right)


print(quickSort02([1,45,23,28,33,22,1,-1]))
#结果 [-1, 1, 1, 22, 23, 28, 33, 45]

 6、快速排序的时间复杂度和空间复杂度

• 时间复杂度:为O(nlogn)

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

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