1 快速排序
通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列
2 分析思路
很明显，先是用到了 partition算法思想（前面的博客提到了），然后再把原始数据分成几部分然后递归同样用partition算法处理
3 代码实现
1) 代码实现方式1
#include <iostream> #include <vector> using namespace std; /* *交换函数 */ void swap(int* a, int* b) { int temp = *a; *a = *b; *b = temp; } /* * 打印vector */ void printVector(vector<int> v) { for (int i = 0; i < v.size(); ++i) { std::cout << v[i] << "\t"; } std::cout << std::endl; } /* *partition算法 记得如果这里是C++我们传递的是vector类型，我们记得要加引用， *不然改变不了数据，这里和java传递ArrayList不一样，ArrayList作为参数可以改变集合里面的值， *所以C++如果函数传递非基本数据类型，一半都是带引用的 */ int partitionOne(vector<int>& vector, int start, int end) { if (start > end) { std::cout << "vector is empty or start > end" << std::endl; return -1; } int pivot = vector[start]; while (start < end) { //我们先从尾巴开始 while (start < end && pivot <= vector[end]) { --end; } //这里用的数组赋值，而不是直接用swap交换函数，那么下面的2步也是用数组赋值，而不是用swap交换函数 vector[start] = vector[end]; while (start < end && pivot >= vector[start]) { ++start; } vector[end] = vector[start]; } vector[start] = pivot; printVector(vector); return start; } /* *partition算法, 这里只不过增加了2个变量i和j *， */ int partitionTwo(vector<int>& vector, int start, int end) { if (start > end) { return -1; } int i = start; int j = end; int pivot = vector[start]; while (i < j) { //我们先从尾巴开始 while (i < j && pivot <= vector[j]) { --j; } //这里用的数组赋值，而不是直接用swap交换函数，那么下面的2步也是用数组赋值，而不是用swap交换函数 vector[i] = vector[j]; while (i < j && pivot >= vector[i]) { ++i; } vector[j] = vector[i]; } vector[i] = pivot; printVector(vector); // quickSort1(vector, start, i - 1);/*最后用同样的方式对分出来的左边的小组进行同上的做法*/ // quickSort1(vector, i + 1, end); return i; } /* *partition算法, 这里只不过增加了2个变量i和j,然后使用了交换函数swap *， */ int partitionThree(vector<int>& vector, int start, int end) { if (start > end) { return -1; } int i = start; int j = end; int pivot = vector[start]; while (i < j) { //我们先从尾巴开始 while (i < j && pivot <= vector[j]) { --j; } while (i < j && pivot >= vector[i]) { ++i; } //这里用的shiswap交换函数，那么下面的是是也是swap交换函数 swap(vector[i], vector[j]); } swap(vector[i], vector[start]); printVector(vector); return i; } /** *快速排序 调用第一个partitionOne */ void quickSortOne(vector<int>& vector, int start, int end) { if (vector.size() < 0 || start > end) return; int index = partitionOne(vector, start, end); quickSortOne(vector, start, index - 1); quickSortOne(vector, index + 1, end); } /** *快速排序 调用第二个partitionTwo */ void quickSortTwo(vector<int>& vector, int start, int end) { if (vector.size() < 0 || start > end) return; int index = partitionTwo(vector, start, end); quickSortTwo(vector, start, index - 1); quickSortTwo(vector, index + 1, end); } /** *快速排序 调用第三个partitionThree */ void quickSortThree(vector<int>& vector, int start, int end) { if (vector.size() < 0 || start > end) return; int index = partitionThree(vector, start, end); quickSortThree(vector, start, index - 1); quickSortThree(vector, index + 1, end); } int main() { vector<int> v1; //[5,9,2,1,4,7,5,8,3,6] v1.push_back(5); v1.push_back(9); v1.push_back(2); v1.push_back(1); v1.push_back(4); v1.push_back(7); v1.push_back(5); v1.push_back(8); v1.push_back(3); v1.push_back(6); std::cout << "old data print " << std::endl; printVector(v1); quickSortOne(v1, 0, v1.size() - 1); // quickSortTwo(v1, 0, v1.size() - 1); // quickSortThree(v1, 0, v1.size() - 1); std::cout << "after partitionOne" << std::endl; printVector(v1); return 0; }
运行结果如下
old data print 5 9 2 1 4 7 5 8 3 6 3 4 2 1 5 7 5 8 9 6 1 2 3 4 5 7 5 8 9 6 1 2 3 4 5 7 5 8 9 6 1 2 3 4 5 7 5 8 9 6 1 2 3 4 5 7 5 8 9 6 1 2 3 4 5 6 5 7 9 8 1 2 3 4 5 5 6 7 9 8 1 2 3 4 5 5 6 7 9 8 1 2 3 4 5 5 6 7 8 9 1 2 3 4 5 5 6 7 8 9 after partitionOne 1 2 3 4 5 5 6 7 8 9
上面我们写了3个parition函数，我们调用quickSortOne(v1, 0, v1.size() - 1)或者quickSortTwo(v1, 0, v1.size() - 1)或者quickSortThree(v1, 0, v1.size() - 1)其中的的一个，结果都是一样。
