为什么需要复习排序算法，因为面对许多数据处理的时候，我们需要有限考虑时间复杂度，基本排序算法能够给我们很多灵感！
| 数据结构 | 不定 |
|---|---|
| 最差时间复杂度 | O(n^2) |
| 最优时间复杂度 | O (n*log n) |
| 平均时间复杂度 | O (n*log n) |
| 最差空间复杂度 | 根据实现的方式不同而不同 |
快速排序法：
1 #include<iostream> 2 #include<vector> 3 #include<ctime> 4 using namespace std; 5 6 #include<boost/timer.hpp> 7 8 9 void print(const vector<int>& vec) 10 { 11 for (auto ele : vec) 12 { 13 cout << ele << " "; 14 } 15 cout << endl; 16 } 17 //产生随机数组 18 void makeRandVec(vector<int>&vec, int num) 19 { 20 srand((unsigned int)time(nullptr)); 21 for (int i = 0; i < num; i++) 22 { 23 vec.push_back(rand() % 101);// 0~100 24 } 25 } 26 27 //<5>快速排序 左边挖坑 - 从右边找人填坑 - 右边挖坑 - 从左边找人填坑 28 void quickSort(vector<int>& vec, int start, int end) 29 { 30 // vec 原始： 4 2 8 0 5 7 1 3 9 31 int i = start; 32 int j = end; 33 //基准数 34 int temp = vec[start]; // temp = 4 // [] 2 8 0 5 7 1 3 9 35 if (i < j) 36 { 37 while (i < j)//循环退出的时候 i = j 38 { 39 //从右向左找到比i指向元素小的元素来填上面的[] 40 while (i < j && vec[j] >= temp) 41 { 42 j--; 43 }//这里找到了3，下面准备入坑（上面的[] ） 44 if (i < j) 45 { 46 vec[i] = vec[j];// 3 2 8 0 5 7 1 [] 9 47 i++;//准备从左向右找一个比基准数大的数 48 } 49 //从左向右找到比i指向元素大的元素来填上面的[] 50 while (i < j && vec[i] < temp) 51 { 52 i++; 53 }//这里找到了8，下面准备入坑 54 if (i < j) 55 { 56 vec[j] = vec[i];// 3 2 [] 0 5 7 1 8 9 57 j--; 58 } 59 } 60 //此时将基准数放到 i的 位置（此时 i = j； 且左边都比vec[i]小，右边都比vec[i]大） 61 vec[i] = temp; //3 2 1 0 4 5 8 9 62 quickSort(vec, start, i - 1); //递归，对左边 63 quickSort(vec, i + 1, end); //递归，对右边 64 } 65 } 66 #define MAX 20 67 68 int main() 69 { 70 //准备随机数组 71 vector<int> rvec; 72 makeRandVec(rvec, MAX); 73 //<5>快速排序 74 vector<int> vec5(rvec); 75 print(vec5); 76 int start = 0; int end = vec5.size() - 1; 77 boost::timer timer5; quickSort(vec5, start, end); 78 cout << "the cost time of quickSort = " << 1000 * timer5.elapsed() << "ms" << endl; 79 print(vec5); 80 81 82 return 1; 83 }
思考：例如对于 数组 A = 4 2 8 0 5 7 1 3 9 进行排序；
1、取temp = 4；此时 A = [] 2 8 0 5 7 1 3 9；
2、从右向左遍历，找一个比temp小的数，也即3，填坑得 A = 3 2 8 0 5 7 1 [] 9；
3、从左向右遍历，找一个比temp大的数，也即8，填坑得 A = 3 2 [] 0 5 7 1 8 9；
