排序算法 | 快速排序(含C++/Python代码实现)

导言

排序算法,就是使得序列按照一定要求排列的方法。排序算法有很多,本文将介绍面试中常常被问到的经典排序算法:快速排序,并分别利用C++和Python进行实现。

前戏

Amusi 作为一个2019年秋招大军中的一员,经历过数次面试。就个人经历而言,今天分享的快速排序算法属于常见问题排行榜中的前五

之前CVer推送了 排序算法 | 冒泡排序(含C++/Python代码实现),一些同学反映太简单了,想知道其它复杂的排序算法介绍,如Shell排序和桶排序等。原本想着慢慢推送过来,今天就破例一会儿,直接跳到面试高频算法:快速排序算法

注:想要了解更多的面试题和算法题,可以关注Amusi的github,欢迎star和fork

link:https://github.com/amusi/coding-note

排序

在介绍快速排序之前,先捋捋排序是个啥?常说的稳定性和复杂度又是个啥?

排序的定义

假设含有n个记录的序列为{r1,r2,...,rn},其相应的关键字分别是{k1,k2,...,kn},需要确定1,2,...,n的一种排列p1,p2,...,pn,使其相应的关键字满足kp1<=kp2<=...<=kpn 非递减(或非递增)的关系,即使得序列成为一个按关键字有序的序列{rp1,rp2,...,rpn},这样的操作就称为排序。

简单来说,排序就是使输入的序列变成符合一定规则(关键字)的有序序列(非递减或非递增)。大多数遇到的排序问题都是按数据元素值的大小规则进行排序的问题。所以本文为了方便起见,只讨论数据元素值大小比较的排序问题。

排序的稳定性

假设ki=kj(1<=i《=n,1<=j<=n,i!=j),且在排序前的序列中ri领先于rj(即i<j)。

  • 如果排序后ri仍领先于rj,则称所用的排序方法是稳定的;
  • 反之,若可能使得排序后的序列中rj领先于ri,则称所用的排序方法是不稳定的。

简单来概括稳定和不稳定:

  • 稳定:如果a原本在b前面,而a=b,排序之后a仍然在b前面;
  • 不稳定:如果a原本在b前面,而a=b,排序之后a可能在b的后面。

时间和空间复杂度

  • 时间复杂度:对排序数据的总的操作次数。反应当n变化时,操作次数呈现什么规律
  • 空间复杂度:算法在计算机内执行时所需要的存储空间的容量,它也是数据规模n的函数。

快速排序

基本思想

快速排序(quick sort):通过一趟排序将待排列表分隔成独立的两部分,其中一部分的所有元素均比另一部分的所有元素小,则可分别对这两部分继续重复进行此操作,以达到整个序列有序。(这个过程,我们可以使用递归快速实现)

步骤

快速排序使用分治法来把一个串(list)分为两个子串(sub-lists)。具体算法描述如下:

  • 从数列中挑出一个元素,称为 “基准”(pivot),这里我们通常都会选择第一个元素作为prvot;
  • 重新排序数列,将比基准值小的所有元素放在基准前面,比基准值大的所有元素放在基准的后面(相同的数可以到任一边)。这样操作完成后,该基准就处于新数列的中间位置,即将数列分成了两部分。这个操作称为分区(partition)操作;
  • 递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数按上述操作进行排序。这里的递归结束的条件是序列的大小为0或1。此时递归结束,排序就完成了。

复杂度分析

  • 时间复杂度:
    • 平均情况:O(nlogn)
    • 最好情况:O(nlong)
    • 最坏情况:O(n^2) 其实不难理解,快排的最坏情况就已经退化为冒泡排序了!所以大家深入理解就会发现各个排序算法是相通的,学习时间久了你就会发现它们的内在联系!是不是很神奇哈~
  • 空间复杂度:
    • 平均情况:O(logn)
    • 最好情况:O(logn)
    • 最坏情况:O(n)
  • 稳定性:不稳定 (由于关键字的比较和交换是跳跃进行的,所以快速排序是一种不稳定的排序方法~)

这里,Amusi 通过DIY 暴力手绘图来描述快速排序的一部分过程:

这里Amusi可是花了很大的决心才将自制的图像po出来,因为画的实在...

好的,我们直接看代码吧

代码实现

注:下面都是利用递归法实现快速排序。

C++版本

 1/* Summary: 快速排序(Quick Sort)
 2* Author: Amusi
 3* Date:   2018-07-28
 4*
 5* Reference: 
 6*   https://en.wikipedia.org/wiki/Quicksort
 7*    
 8* 快速排序(quick sort):通过一趟排序将待排列表分隔成独立的两部分,其中一部分的所有元素均比另一部分的所有元素小,则可分别对这两部分继续重复进行此操作,以达到整个序列有序。(这个过程,我们可以使用递归快速实现)
 9*
10*/
11
12#include <iostream>
13
14// 快速排序函数(递归法)
15namespace alg{
16    template<typename T>
17    static void QuickSort(T list[], int start, int end)
18    {
19        int i = start;
20        int j = end;
21        // 结束排序(左右两索引值见面,即相等,或者左索引>右索引)
22        if (i >= j)
23            return;
24        // 保存首个数值(以首个数值作为基准)
25        // 这个位置很重要,一定要在if i >= j判断语句之后,否则就索引溢出了
26        T pivot = list[i];
27
28        // 一次排序,i和j的值不断的靠拢,然后最终停止,结束一次排序
29        while (i < j){
30            // 一层循环实现从左边起大于基准的值替换基准的位置,右边起小于基准的值位置替换从左起大于基准值的索引
31            //(从右往左)和最右边的比较,如果 >= pivot, 即满足要求,不需要交换,然后j - 1,慢慢左移,即拿基准值与前一个值比较; 如果值<pivot,那么就交换位置
32            while (i < j && pivot <= list[j])
33                --j;
34            list[i] = list[j];
35            // 交换位置后,(从左往右)然后在和最左边的值开始比较,如果 <= pivot, 然后i + 1,慢慢的和后一个值比较; 如果值>pivot,那么就交换位置
36            while (i < j && pivot >= list[i])
37                ++i;
38            list[j] = list[i];
39        }
40        // 列表中索引i的位置为基准值,i左边序列都是小于基准值的,i右边序列都是大于基准值的,当前基准值的索引为i,之后不变
41        list[i] = pivot;
42        // 左边排序
43        QuickSort(list, start, i-1);
44        // 右边排序
45        QuickSort(list, i+1, end);
46    }
47}
48
49using namespace std;
50using namespace alg;
51
52
53int main()
54{
55    int a[8] = { 5, 2, 5, 7, 1, -3, 99, 56 };
56    QuickSort<int>(a, 0, sizeof(a)/sizeof(a[0]) - 1);
57    for (auto e : a)
58        std::cout << e << " ";
59
60    return 0;
61}

Python版本

 1''' Summary: 快速排序(Quick Sort)
 2* Author: Amusi
 3* Date:   208-07-28
 4*
 5* Reference: 
 6*   https://en.wikipedia.org/wiki/Quicksort
 7*   https://www.cnblogs.com/wujingqiao/articles/8961890.html
 8*    https://github.com/apachecn/LeetCode/blob/master/src/py3.x/sort/QuickSort.py
 9*   快速排序(quick sort):通过一趟排序将待排列表分隔成独立的两部分,其中一部分的所有元素均比另一部分的所有元素小,则可分别对这两部分继续重复进行此操作,以达到整个序列有序。(这个过程,我们可以使用递归快速实现)
10*
11'''
12
13def QuickSort(array, start, end):
14    lengths = len(array)
15    i = start
16    j = end
17    # 结束排序(左右两索引值见面,即相等,或者左索引>右索引)
18    if i >= j:
19        return    # 返回空即可
20    # 保存首个数值(以首个数值作为基准)
21    # 这个位置很重要,一定要在if i>=j判断语句之后,否则就索引溢出了
22    pivot = array[i]
23    # 一次排序,i和j的值不断的靠拢,然后最终停止,结束一次排序
24    while i < j:
25        # (从右往左)和最右边的比较,如果>=pivot,即满足要求,不需要交换,然后j-1,慢慢左移,即拿基准值与前一个值比较; 如果值<pivot,那么就交换位置
26        while i < j and pivot <= array[j]:
27            # print(pivot, array[j], '*' * 30)
28            j -= 1
29        array[i] = array[j]
30        # 交换位置后,然后在和最左边的值开始比较,如果<=pivot,然后i+1,慢慢的和后一个值比较;如果值>pivot,那么就交换位置
31        while i < j and pivot >= array[i]:
32            # print(pivot, array[i], '*' * 30)
33            i += 1
34        array[j] = array[i]
35    # 列表中索引i的位置为基准值,i左边序列都是小于基准值的,i右边序列都是大于基准值的,当前基准值的索引为i,之后不变
36    array[i] = pivot
37    # 左边排序
38    QuickSort(array, start, i-1)
39    # 右边排序
40    QuickSort(array, i+1, end)
41
42    #return array
43
44if __name__ == "__main__":
45    array = [1,3,8,5,2,10,7,16,7,4,5]
46    print("Original array: ", array)
47    #array = QuickSort(array, 0, len(array)-1)
48    # 因为python中的list对象是可变对象,所以在函数做"形参"时,是相当于按引用传递
49    # 所以不写成返回值的形式,也是OK的
50    QuickSort(array, 0, len(array)-1)
51    print("QuickSort: ", array)

注:点击阅读全文,即可访问Amusi的github,欢迎start和fork

原文发布于微信公众号 - CVer(CVerNews)

原文发表时间:2018-07-29

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏编程

详解 Python的enumerate 函数

你应该在何时何地,如何使用内置的 enumerate() 函数来写出更加简洁、更加具有 Python 范儿的循环结构呢? ? Python 的 enumerat...

24370
来自专栏机器学习算法与Python学习

“基数排序”展现Python的优雅与简洁

在这儿那桶排序为例目的不是向大家介绍基数排序这种排序方式,是想通过基数排序的实现来展现Python的简洁与优雅。在这儿先简单的介绍一下基数排序,至于具体的内容会...

37750
来自专栏开源优测

Python3快速排序

Python3快速排序 概述 快速排序(Quicksort)是对冒泡排序的一种改进。 快速排序由C. A. R. Hoare在1962年提出。 通过一趟排序将要...

43460
来自专栏编程

关于python字典类型最疯狂的表达方式

[译]关于python字典类型最疯狂的表达方式 一个Python字典表达式谜题 这个子字典是从哪里来的 Umm..好吧,可以得到什么结论呢? 一篇来自 Dan ...

227100
来自专栏程序员互动联盟

【编程基础】Java面向对象基础知识

前言: 前面一系列文章讲了Java的一些语法基础知识、Java中的数据类型和Java中的运算符,基本上都是学习Java语言的基础知识,从这一讲开始将会逐步介绍J...

35650
来自专栏猿人谷

常见排序算法分析

一.常见排序算法的实现 1.冒泡排序 冒泡排序是非常容易理解和实现,,以从小到大排序举例: 设数组长度为N。 1.比较相邻的前后二个数据,如果前面数据大于后面...

21080
来自专栏工科狗和生物喵

【计算机本科补全计划】《C++ Primer》:类型转换

正文之前 学习,不如爆文?反正晚上也不会学习,某个家伙也对我爱理不理的!!!!(这才是最骚的吧),刚好欠了 C++ Primer太多烂账了。不如赶紧还了! 对了...

31680
来自专栏追不上乌龟的兔子

介绍一些Python str类的方法

上面的代码正确的返回了'0.333333',但是当x = 1 / 2时,由于小数只有一位,这个方案的结果就是'0.5'了,而不是预期中的'0.500000'。

21540
来自专栏用户画像

迷语博士的难题

两面族是荒岛上的一个新民族,他们的特点是说话真一句假一句且真假交替。如果第一句为真,则第二句是假的;如果第一句为假的,则第二句就是真的,但是第一句是真是假没有规...

8310
来自专栏从流域到海域

Python 函数

Python的函数与其他语言的函数概念上是一致的,只是形式上有所不同。在面向过程的编程语言中(C语言),函数是代码的基本组成形式,是功能的基本模块;在面向...

22270

扫码关注云+社区

领取腾讯云代金券