排序算法(1) 快速排序 C++实现


快速排序基本特性

  1. 时间复杂度：O（n*lgn）
  2. 最坏：O（n^2）
  3. 空间复杂度：最好情况下：O（lgn），最坏情况：O(n)，平均情况：O(lgn)
  4. 不稳定。

关于快速排序的空间复杂度，谢谢@命运他爹 同学指正。详述一下。

快速排序由于每次递归的时候会占用一个空间返回中间数位置，所以一次递归的空间复杂度为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

 

clipboard

 

一趟排序过程分析：

 

1 quicksort一趟排序过程

 

源码

类声明

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");

 

运行截图：

clipboard[4]

------------------------------分割线------------------------------

C++ Primer Plus 第6版 中文版 清晰有书签PDF+源代码

读C++ Primer 之构造函数陷阱

读C++ Primer 之智能指针

读C++ Primer 之句柄类

将C语言梳理一下，分布在以下10个章节中：

  1. Linux-C成长之路（一）：Linux下C编程概要
  2. Linux-C成长之路（二）：基本数据类型
  3. Linux-C成长之路（三）：基本IO函数操作
  4. Linux-C成长之路（四）：运算符
  5. Linux-C成长之路（五）：控制流
  6. Linux-C成长之路（六）：函数要义
  7. Linux-C成长之路（七）：数组与指针
  8. Linux-C成长之路（八）：存储类，动态内存
  9. Linux-C成长之路（九）：复合数据类型
  10. Linux-C成长之路（十）：其他高级议题

本文永久更新链接地址：

相关内容