首页 > 代码库 > 三天一算法:快速排序
三天一算法:快速排序
i---> 6, 5, 7, 8, 3 , 2 , 9 , 10 <----j
首先以第一个为基准值 6
1： j从右边出发，在j移动到2的时候发现小于6，j停了下来，
然后i开始移动，当i移动到7的时候发现大于6，于是i也停了下来
然后i和j交换了他们所代表的值
6, 5, 7, 8, 3 , 2 , 9 , 10 --> 6, 5, 2, 8, 3 , 7 , 9 , 10
2： 然后j继续向左移动，在移动到3的时候发现小于6，j停了下来，
i也继续移动，当移动到8的时候发现大于6，于是i又停了下来
i和j交换了他们所代表的值
6, 5, 2, 8, 3 , 7 , 9 , 10 --> 6, 5, 2, 3, 8 , 7 , 9 , 10
3: 继续，j继续向左移动，当移动到3的时候i == j，循环结束
这个时候呢，我们要把i代表的值和基准值进行交换
6, 5, 2, 3, 8 , 7 , 9 , 10 --> 3, 5, 2, 6, 8 , 7 , 9 , 10
在这个的整个过程中呢，6我们已经找好了它的位置，我们就不在管它了，于是我们把6前后分成了2组，[3,5,2] 和[8, 7, 9, 10]
我们再继续对[3, 5, 3]和[8, 7, 9, 10]重新上面的过程，最后我们就能得到最终结果：2，3，5，6，7，8，9，10
#include<iostream>using namespace std;int a[] = {6, 5, 7, 8, 3, 2, 9, 10 };void QuickSort(int left, int right){ if (left >= right) //如果left >= right就没有必要交换了，因为本身已经排序了 return; int guard = a[left]; int i = left; int j = right; while (i != j) { while (a[j] >= guard && i < j) //保证每次要先从右边开始遍历 j--; while (a[i] <= guard && i < j) i++; if (i < j) { int t = a[i]; a[i] = a[j]; a[j] = t; } } a[left] = a[i]; //结束后要把基准值和当前的那个值进行交换 a[i] = guard; QuickSort(left, i - 1); QuickSort(i+1, right);}int main(){ QuickSort(0, sizeof(a)/sizeof(int) -1); for (int i = 0; i < sizeof(a)/sizeof(int) ;i++ ) cout << a[i] << " " ; cout << endl;}
三天一算法:快速排序