python 排序（一）快速排序、原理以及代码实现、比较归并排序、时间复杂度推算

系统管理员 2023-08-17 15:26 115阅读 0赞

## **一、介绍** ##

快速排序（quick sort）采用了分治的策略（很多排序都应用到分治，比如归并排序）。

快速排序的基本思想就是：通过一趟排序将要排序的数据分隔成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据要小，然后再按此方法对两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

**1、原理以及思想：**

（1）、将数据分为两步分，先在原数组选取一个数据做为基准值

（2）、将数据中其余所有元素与基准值比较，比基准值小的放在左边，比基准值大的放在右边

（3）、基准值两边的子列做为新数剧，不断的重复第一步跟第二步，直到所有子集只剩下一个元素为止

**2、举例说明：**

数组：\[11, 99, 33 , 69, 77, 88, 55, 11, 33, 36, 39, 66, 44, 22\]

1、选取基准值66

2、将数组中除去66以外的所有值与66比较

11小于66，放在66的左分区，然后99大于66，放在66的右分区

第一轮结束：左分区：\[11，33，55，11,  33,  36,  39,  44,  22\]，右分区：\[99，69，77,  88\] 基准：66

3、将左右分区的数据分别进行第一二部的操作，直到分区数据数量为一

## **二、代码实现** ##

def quick_sort(lis):
        """
        quick sort
    
        return: sort list, mid, right list
        """
        if len(lis) < 2: #数组大小小于2就返回
            return lis
    
        mid = lis[len(lis) // 2] #取基准值
        left_list, right_list = [], [] 
        lis.remove(mid) #除去基准值
        for i in lis:
            if i >= mid:
                right_list.append(i)
            else:
                left_list.append(i)
        #print     right_list,     left_list
        return quick_sort(left_list) + [mid] + quick_sort(right_list) #递归实现快排
    
    if __name__ == '__main__':
        lis = [11, 99, 33 , 69, 77, 88, 55, 11, 33, 36, 39, 66, 44, 22]
        print quick_sort(lis)
    
    #[11, 11, 22, 33, 33, 36, 39, 44, 55, 66, 69, 77, 88, 99]

## **三、总结** ##

1、排序的稳定性：快速排序是一种时间复杂度不稳定的算法，跟数据的顺序有关

2、复杂度：时间复杂度**O(nlogn)，**空间复杂度**O(nlogn)**

3、比较归并排序：

（1）快速排序和归并的区别就在于它正好和递归的排序反过来。快速排序先排序再递归细分，排序是从上到下的。归并排序先递归细分再排序，排序是从下到上的。

（2）归并排序与快排两种排序思想都是**分而治之**，但是它们分解和合并的策略不一样：归并是从中间**直接**将数列分成两个，而快排是**比较后**将小的放左边大的放右边，所以在合并的时候归并排序还是需要将两个数列重新再次排序，而快排则是直接合并不再需要排序，**所以快排比归并排序更高效一些**，可以从示意图中比较二者之间的区别。

## **四、时间复杂度推算** ##

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNzcxNTY3_size_16_color_FFFFFF_t_70][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNzcxNTY3_size_16_color_FFFFFF_t_70]: /images/20230810/b54458cca0bd400cb04e0c88e5970936.png