排序算法-快速排序

向右看齐 2024-05-02 20:26 21阅读 0赞

## 一、快速排序 ##

快速排序也属于**交换排序**，通过元素之间的比较和交换位置来达到排序的目的。

冒泡排序在每一轮中只把1个元素冒泡到数列的一端。而快速排序则在每一轮挑选一个**基准元素**，并让其他比它大的元素移动到数列**一边**，比它小的元素移动到数列的**另一边**，从而把数列拆解成两个部分。

![8fd7deab42234322a155f7351c83ecf8.png][]

> 这种思路就叫作分治法。
> 
> 在分治法的思想下，原数列在每一轮都被拆分成两部分，每一部分在下一轮又分别被拆分成两部分，直到不可再分为止。 每一轮的比较和交换，需要把数组中的全部元素都遍历一遍，时间复杂度是O(n)。这样的遍历一共需要多少轮呢﹖假如元素个数是n，那么平均情况下需要logn轮，因此快速排序算法总体的平均时间复杂度是O ( nlogn)。

**基准元素，英文pivot，在分治过程中，以基准元素为中心，把其他元素移动到它的左右两边。**

> 1、双边循环法。
> 
> 2、单边循环法。

**1、双边循环法**

首先，选定基准元素pivot，并且设置两个指针left和right，指向数列的最左和最右两个元素。

![e3e376cb200a474991f0063e4bef3a4a.png][]

第1次循环，从right指针开始，让指针所指向的元素和基准元素做比较。如果right>=pivot，则指针向左移动(-1);如果right<pivot，则right指针停止移动(stop)，切换到left指针。

在当前数列中，1<4，所以right直接停止移动，换到left指针，进行下一步行动。轮到left指针行动，让指针所指向的元素和基准元素做比较。如果left<=pivot，则指针向右移动(+1);如果left>pivot，则left指针停止移动(stop)。

![a765f133128e4c1e84eeba9bb19ae0cd.png][]

由于left开始指向的是基准元素，判断肯定相等，所以left右移1位。

![7f3bed404fd146f6b4a951139dd52a93.png][]

由于7>4，left指针在元素7的位置停下。这时，让left指针和right指针所指向的元素进行交换。

![eb8b97d548654e919cda0b8615064b2d.png][]

![bc45b6943b0f404695b4988cb00f62ad.png][]

def partition(start,end,ll):
        '''
         比较交换过程
        :param start: 开始索引
        :param end: 结束索引
        :param ll:  数列
        :return:   左边索引
        '''
        #取第一个元素为基准元素，也可以随机
        pirot=ll[start]
        #左边元素索引
        left=start
        #右边元素索引
        right=end
        #循环
        while left!=right:
            #控制right指针比较，并左移
            while left<right and ll[right]>=pirot:
                right -=1
            # 控制left指针比较，并右移
            while left<right and ll[left]<=pirot:
                left+=1
            #交换left指针和right指针的元素
            if left<right:
                #交换
                ll[left],ll[right]=ll[right],ll[left]
        #pirot与left,right指针重合
        ll[start]=ll[left]
        ll[left]=pirot
        return left
    
    def quickSort(start,end,ll):
        #递归结束
        if start>=end:
            return
        #获取基准元素位置
        pirot=partition(start,end,ll)
        #根据基准元素，分成两部分递归排序
        quickSort(start,pirot-1,ll)
        quickSort(pirot+1,end,ll)
    
    if __name__ == '__main__':
         ll=[4,7,6,5,3,2,8,1]
         print('排序前：')
         print(ll)
         #调用方法排序
         quickSort(0,len(ll)-1,ll)
         print('排序后：')
         print(ll)

![de0548bb0a484816980e2824c70a9648.png][]

**2、单边循环法**

> 只从数组的一边对元素进行遍历和交换。

开始和双边循环法相似，首先选定基准元素pivot。同时，设置一个mark指针指向数列**起始位置**，这个mark指针代表小于基准元素的区域边界。接下来，从基准元素的**下一个位置开始**遍历数组。

![bb69d07f9a67473c93351cefd3895007.png][]

> 如果遍历到的元素**>**基准元素，就继续往后遍历。
> 
> 如果遍历到的元素**<**基准元素，则需要做两件事:
> 
> 第一，把mark指针右移1位，因为小于pivot的区域边界增大了1;
> 
> 第二，让最新遍历到的元素和mark指针所在位置的元素交换位置，因为最新遍历的元素归属于小于pivot的区域。

首先遍历到元素7，7>4，所以继续遍历。

![c772de5144da4c50a454fd4808a896e0.png][]

遍历到的元素是3，3<4，所以mark指针右移1位。

![cb5f7938eb484a5ebdf4c5c84a669ce8.png][]

随后，让元素3和mark指针所在位置的元素交换，因为元素3归属于小于pivot的区域。

![0bc89f3944ec4c15bc394182eb92a7c8.png][] ![64d819c9205d4c2e918a944913e07b35.png][]

def partitionSingle(start,end,ll):
        # 取第一个元素为基准元素，也可以随机
        pirot = ll[start]
        # 标记索引
        mark = start
        for i in range(start+1,end+1):
            #判断遍历的元素<基准元素
            if ll[i]<pirot:
                #右移1位
                mark+=1
                #交换
                p=ll[mark]
                ll[mark]=ll[i]
                ll[i]=p
    
        ll[start]=ll[mark]
        ll[mark]=pirot
        return mark
    
    
    def quickSort(start,end,ll):
        #递归结束
        if start>=end:
            return
        #获取基准元素位置
        pirot=partitionSingle(start,end,ll)
        #根据基准元素，分成两部分递归排序
        quickSort(start,pirot-1,ll)
        quickSort(pirot+1,end,ll)

> 很明显，partitionSingle方法只要一个循环就OK，的确比双边循环法简单多了。

[8fd7deab42234322a155f7351c83ecf8.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/02/cde3e8845a22459e8b7214ff5dcac2ad.png
[e3e376cb200a474991f0063e4bef3a4a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/02/66b9d3fd9349440a926c3dee364d75ce.png
[a765f133128e4c1e84eeba9bb19ae0cd.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/02/6552d0a7a40f430ca1960766e9cb1146.png
[7f3bed404fd146f6b4a951139dd52a93.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/02/c2e5528cda1940009a4aa3f3cde66178.png
[eb8b97d548654e919cda0b8615064b2d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/02/8a864cd69efe47a8bb91580ac6694d5b.png
[bc45b6943b0f404695b4988cb00f62ad.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/02/0b07dc437c594bdab613a273e46f1e26.png
[de0548bb0a484816980e2824c70a9648.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/02/52e6d52fe7b94c799dc6286f90d68e33.png
[bb69d07f9a67473c93351cefd3895007.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/02/60ee63c464c3441b870a4073b587fce5.png
[c772de5144da4c50a454fd4808a896e0.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/02/bf2dce0cc9874b6f8eab92132935ba96.png
[cb5f7938eb484a5ebdf4c5c84a669ce8.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/02/a58acd469f1e46beb32f05da9e47ae7a.png
[0bc89f3944ec4c15bc394182eb92a7c8.png]: https://img-blog.csdnimg.cn/direct/0bc89f3944ec4c15bc394182eb92a7c8.png
[64d819c9205d4c2e918a944913e07b35.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/02/689bf8ecba984274b2a0a0fc8dd7c460.png