排序算法(1) 快速排序 C++实现
快速排序基本特性
- 时间复杂度：O（n*lgn）
- 最坏：O（n^2）
- 空间复杂度：最好情况下：O（lgn），最坏情况：O(n)，平均情况：O(lgn)
- 不稳定。
关于快速排序的空间复杂度，谢谢@命运他爹 同学指正。详述一下。
快速排序由于每次递归的时候会占用一个空间返回中间数位置，所以一次递归的空间复杂度为O(1)。
最好情况和平均情况下的递归深度为O(lgn)，相应的空间复杂度就是O(lgn)
最坏情况下的递归深度为O(n)，空间复杂度为O(n)。
算法
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | QUICKSORT(A, p, r) if p < r then q ← PARTITION(A, p, r) //关键 QUICKSORT(A, p, q - 1) QUICKSORT(A, q + 1, r)PARTITION(A, p, r) x ← A[r] i ← p - 1 for j ← p to r - 1 do if A[j] ≤ x then i ← i + 1 exchange A[i] <-> A[j] exchange A[i + 1] <-> A[r] return i + 1 |
示例
待排序数组：7 3 5 9 8 5 1 10 4 6
一趟排序过程分析：
源码
类声明
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 | class BaseSort {public: BaseSort() { } virtual void sort() = 0;};class QuickSort : public BaseSort {public: QuickSort(int Array[], int len) : BaseSort() { this->Array = Array; this->len = len; } void sort();private: int partition(int Array[], int start, int end); void QuickSort(int Array[], int start, int end);private: int* Array; int len;}; |
相关成员函数实现
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 | void QuickSort::sort() { quicksort(Array, 0, len-1);}void QuickSort::quicksort(int Array[], int start, int end) { if ( start < end ) { int mid = this->partition(Array, start, end); if ( start < mid - 1 ) quicksort(Array, start, mid-1 ); if ( mid + 1 < end ) quicksort(Array, mid+1, end); }}int QuickSort::partition(int Array[], int start, int end) { int i, j, x, tmp; x = Array[end]; i = start -1; for ( j = start; j < end; j++ ) { if ( Array[j] <= x) { i++; tmp = Array[j]; Array[j] = Array[i]; Array[i] = tmp; } } tmp = Array[end]; Array[end] = Array[i+1]; Array[i+1] = tmp; if (DEBUG) { printArray(Array, len, "MidResult"); } return i+1;} |
测试：
1 2 3 4 5 6 | int a[10] = {7,3,2,9,8,5,1,10,4,6};int len = 10;QuickSort* quicksort= new QuickSort(a, len);quicksort->sort();printArray(a, len, "QuickSort"); |
运行截图：
------------------------------分割线------------------------------
将C语言梳理一下，分布在以下10个章节中：
- Linux-C成长之路（一）：Linux下C编程概要 http://www.linuxidc.com/Linux/2014-05/101242.htm
- Linux-C成长之路（二）：基本数据类型 http://www.linuxidc.com/Linux/2014-05/101242p2.htm
- Linux-C成长之路（三）：基本IO函数操作 http://www.linuxidc.com/Linux/2014-05/101242p3.htm
- Linux-C成长之路（四）：运算符 http://www.linuxidc.com/Linux/2014-05/101242p4.htm
- Linux-C成长之路（五）：控制流 http://www.linuxidc.com/Linux/2014-05/101242p5.htm
- Linux-C成长之路（六）：函数要义 http://www.linuxidc.com/Linux/2014-05/101242p6.htm
- Linux-C成长之路（七）：数组与指针 http://www.linuxidc.com/Linux/2014-05/101242p7.htm
- Linux-C成长之路（八）：存储类，动态内存 http://www.linuxidc.com/Linux/2014-05/101242p8.htm
- Linux-C成长之路（九）：复合数据类型 http://www.linuxidc.com/Linux/2014-05/101242p9.htm
- Linux-C成长之路（十）：其他高级议题
相关推荐
Masimaro 2020-06-21
清溪算法君老号 2020-06-01
Joymine 2020-06-06
GhostLWB 2020-04-20
田有朋 2020-04-19
sunjunior 2020-04-10
cmsmdn 2020-03-03
shenwenjie 2020-02-26
sunjunior 2020-02-15
hanyujianke 2020-01-13
路漫 2020-01-12
sunnyJam 2019-12-31
KilluaZoldyck 2019-12-15
yuanran0 2019-12-14
Happyunlimited 2019-12-10
baike 2019-12-09
yishujixiaoxiao 2019-12-02
YUAN 2019-11-19