快速排序算法__python实现

快速排序算法(quick sort):

一.基本思想(分治

先用一趟排序将原始数组分割成两个独立部分,其中一个部分都比另一个部分小,再继续对分成的两个部分分别进行快速排序,整个过程递归进行,最后整个数组成为有序序列。

二.基本步骤

1. 从数列中挑出一个元素,作为“基准”(pivot),[随机取三个数,再取这三个数中的中值]或者[取第一,最后,中间再取中值];

2. 分区操作:重排数列,比基准值小的全部放在基准值前面,比基准值大的全部放再基准值后面(相同的数放在任意一边),分区结束后该基准值就在该数列的中间位置。

3. 递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序。

递归的最底部情形是,数列的大小是0 or 1,也是最终别排序好了的。每次迭代中它至少会把一个元素摆到它的最后位置去。

三.时间复杂度和稳定性

1.时间复杂度:

 

若每次分裂都在列表*,将会重复分裂 log n 次。n个数都要与基准值比较大小,进行N次

所以最优时间复杂度是O(nlogn) ;

最坏的情况下,分成一个长度为 0 和(n-1)的两个数列,(n-1)数列分成 0 和(n-2),以次类推

最坏时间复杂度是O(n ^2)

2.稳定性:不稳定

 

四.python实现

def quick_sort(alist,start,end):
    #递归的退出条件
    if start >= end:
        return
    
    #设定起始元素为基准值
    mid = alist[start]

    #low为从左边开始移动的游标,high为从右边开始移动的游标
    low = start
    high = end

    while low < high:
        #两个游标不重合,high所指的数比基准值大,high往左移
        while low < high and alist[high] >= mid:
            high -= 1
        
         # 将high指向的元素放到low的位置上
        alist[low] = alist[high]
    
        # 如果low与high未重合,low指向的元素比基准元素小,则low向右移动
        while low < high and alist[low] < mid:
            low += 1
        # 将low指向的元素放到high的位置上
        alist[high] = alist[low]

    # 退出循环后,low与high重合,此时所指位置为基准元素的正确位置
    # 将基准元素放到该位置
    alist[low] = mid

    # 对基准元素左边的子序列进行快速排序
    quick_sort(alist, start, low-1)

    # 对基准元素右边的子序列进行快速排序
    quick_sort(alist, low+1, end)


alist = [54,26,93,17,77,31,44,55,20]
quick_sort(alist,0,len(alist)-1)
print(alist)
        

 

 

 

 

 

上一篇:排序算法之选择排序的python代码实现


下一篇:常用的排序算法与Python实现