用Python实现快速排序(Quicksort)算法

蔚落 2022-05-06 14:57 643阅读 0赞

## 1.快速排序(Quicksort)算法介绍 ##

>     快速排序（Quicksort）是对冒泡排序的一种改进,但是不是稳定的排序算法

## 2.算法思想 ##

>     1）设置两个变量i、j，排序开始的时候：i=0，j=N-1；
>     2）以第一个数组元素作为关键数据，保存在key中，即key=A[0]；
>     3）从j开始向前搜索，即由后开始向前搜索(j--)，找到第一个小于key的值A[j]，用A[j]覆盖A[0],
>     4）从i开始向后搜索，即由前开始向后搜索(i++)，找到第一个大于key的A[i]，用A[i]覆盖A[j]  即每一次覆盖上一次的
>     5）重复第3、4步，直到i=j；找到符合条件的值，进行交换的时候i， j指针位置不变。另外，i==j这一过程一定正好是i+或j-完成的时候，此时令循环结束。
>     6) 将K还原
>     7) 第一遍快速排序不会直接得到最终结果，只会把比k大和比k小的数分到k的两边。为了得到最后结果，需要再次对下标2两边的数组分别执行此步骤，然后再分解数组，直到数组不能再分解为止（只有一个数据），才能得到正确结果。

## 3. 第一趟排序 举例如下 ##

>     key = 3
>     i-->                  <--j
>     3   7    6    2    4   5        j走
>     
>     i-->         <--j
>     2   7    6    2    4   5        i走
>     
>         i-->     <--j
>     2   7    6    7   4   5       j走
>     
>         i--><--j     
>     2   3    6    7   4   5       i走
>     
>      第一趟排序走完,key(key = 3)左边的值都比3小,key右边的值都比key大

##  4.用Python3实现 ##

###     方法1 ###

def quick_sort(list, low, high):
        """
        控制快速排序递归的主函数
        :param list:用户传入的待排序列表
        :param low:列表左下标
        :param high:列表右下标
        """
    
        if low < high:
            k_index = deal_list(list, low, high)
    
            # 递归分界值左边的一组
            quick_sort(list, low, k_index - 1)
            # 递归分界值右边的一组
            quick_sort(list, k_index + 1, high)
    
    
    def deal_list(list, low, high):
        """实现每趟排序,并找出分界值的下标k_index"""
    
        # 必须把low ,high保存起来,上面的主函数的left right始终不变
        left = low
        right = high
    
        # 将列表最左边的值赋值给k
        k = list[low]
    
        while left < right:  # 当左右"指针"未碰头时就一直比较移动下去
            # 从右边开始,如果比K大:right左移一位,继续比较
            while list[right] > k:
                right -= 1
    
            # 从左边开始,如果比K小: left右移一位,继续比较
            while list[left] <= k:
                left += 1
    
            # 若移动完，二者仍未相遇则交换下标对应的值
            if left < right:
                list[right], list[left] = list[left], list[right]
    
        # 若移动完，已经相遇，则交换right对应的值和k
        list[low] = list[right]
        list[right] = k
        return right
    
    if __name__ == '__main__':
    
        list = [6, 1, 2, 7, 9, 3, 4, 5, 10, 8]
        quick_sort(list, 0, len(list) - 1)
        print(list)

### 方法2 ###

import time, random
    
    
    def quick_sort(list, low, high):
        # 1)
        # 必须将low  high保存,因为下面的递归 还要固定着 最边界
        i = low
        j = high
        if i >= j:
            return list
    
        key = list[i]  # 2)
        while i < j:
            # 3)
            while i < j and list[j] >= key:
                j = j - 1
            list[i] = list[j]
    
            # 4)
            while i < j and list[i] <= key:
                i = i + 1
            list[j] = list[i]
    
        # 6)
        list[i] = key
    
        # 7)
        quick_sort(list, low, i - 1)
        quick_sort(list, j + 1, high)
        return list
    
    
    if __name__ == '__main__':
        list = [random.randint(1, 100) for i in range(100)]
        start_time = time.time()
        quick_sort(list, 0, len(list) - 1)
        # list = sorted(list)
        end_time = time.time()
        print("所用时间:", end_time - start_time)

## 5.结果如下![70][] ##

## 7.时间复杂度 空间复杂度分析 ##

>     在最优的情况下，快速排序算法的时间复杂度为O(nlogn)。
>     平均的情况 O(nlogn)。
>     
>     就空间复杂度来说，主要是递归造成的栈空间的使用，最好情况，递归树的深度为log2n，其空间复杂度也就为O(logn)，最坏情况，需要进行n‐1递归调用，其空间复杂度为O(n)，平均情况，空间复杂度也为O(logn)。
> 
>

**如果你和我有共同爱好,我们可以加个好友一起交流!**

**![1445380-20180903211901788-1752749014.png][]**

[70]: /images/20220506/ca8faca428604081992e1126f5332d9e.png
[1445380-20180903211901788-1752749014.png]: /images/20220506/d91e8dc483e14a918ff7eab8cdf90be1.png