导言
排序算法,就是使得序列按照一定要求排列的方法。排序算法有很多,本文将介绍面试中常常被问到的经典排序算法:快速排序,并分别利用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)。
简单来概括稳定和不稳定:
时间和空间复杂度
基本思想
快速排序(quick sort):通过一趟排序将待排列表分隔成独立的两部分,其中一部分的所有元素均比另一部分的所有元素小,则可分别对这两部分继续重复进行此操作,以达到整个序列有序。(这个过程,我们可以使用递归快速实现)
步骤
快速排序使用分治法来把一个串(list)分为两个子串(sub-lists)。具体算法描述如下:
复杂度分析
这里,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