- 这是别人自学的，很厉害的，图还画的很好，注释写的也很详细，太赞了！
- 补充一点方便以后学习巩固：
- 快速排序是另一个分而治之排序算法。归并排序的重点在于合并，快速排序的重点在于分
- 对于一个数组，起始为lo，结束为hi，轴点为pivot。通过每次选取不同的轴点，将轴点移动至某一位置，使得满足下述条件。
- 那么如何分呢？重点在于寻找轴点轴点需要满足的条件：其左侧元素都比其小，右侧元素都要比其大
- 转自：https://yq.aliyun.com/articles/680896?spm=a2c4e.11163080.searchblog.145.531c2ec1tDGVbS&do=login&accounttraceid=d9bd2178-2d75-4147-bc5f-a2075143e318
- 这是一篇自学文章,如果有错误地方请及时指出
- 基本思想就是,确定一个在数组中的值,这个值可以将数组分裂为两部分,然后这两部分再分别找到那个中间值,然后再分别按照中间值在切分数组,直到最后不可切分了,也就排序完成了,如下图
好了下面将是一次排序的大概流程图
JAVA代码实现：
public static void main(String[] args) {
int[] arrs = {7,12,3,5,8,15,9,6,6,6,6,19,-2};
quickSort(arrs,0,arrs.length - 1);
System.out.println(Arrays.toString(arrs));
}
private static void quickSort(int[] arrs, int l, int r) {
if (l < r){
//index就算返回回来的分割点
int index = getindex(arrs,l,r);
//有了分割点就知道怎么分割两段数据序列了
quickSort(arrs,l,index-1);
quickSort(arrs,index+1,r);
}
}
private static int getindex(int[] arrs, int l, int r) {
int base = arrs[l]; //取第一个值做base值
//保证不判断过头
while (l < r){
//arrs[r] > base 只要比base大的值就继续找,找到比base小的或者相等的
//就不满足条件就可以确定值的下标了
while (l < r && arrs[r] >= base){
//进来就代表比base大
r --;
}
//到这就算找到<=base的值了,然后赋值给left
arrs[l] = arrs[r];
//开始寻找比base大的值,流程跟上一个while一样
while (l < r && arrs[l] <= base){
l ++;
}
//到这就算找到>=base的值了,然后赋值个right
arrs[r] = arrs[l];
}
//然后将base值赋值给right
arrs[r] = base;
//返回这个分割点,即right
return r;
}
这里是快速排序的改进版，参考邓俊辉老师讲授：
做出下列改进，根据L、G、U三者大小关系的不变性，将数组分为四个部分：
轴点最初还是选取a[0]，L左界是lo，L右界是mi，G左界是mi+1，G右界是k，U左界是k，U右界是hi。
对于元素x逐个与轴点比较，若小于归为L，若大于归为G。当G区间足够大时，平滑式移动会比较复杂，在此采用滚动式移动比较简便，只要将x与G[mi+1]进行交换。为何能交换呢？因为G中元素均比x大，L中元素均比x小，这一条件始终满足。
遍历完成时，区间U会根据与轴点的大小，分别归入L、G，U会被完全分解，最终消失。最后一步，候选轴点与L右界进行交换，候选轴点归位，名副其实。
如上所示可以归纳为：
另一种改进版的快速排序方法实现：
int partition(int a[], int lo, int hi)
{
swap(a[lo],a[lo+rand()%(hi-lo+1)]);//随机交换，避免最坏情况的发生
int pivot = a[lo];
int mi=lo;
for(int i=lo+1;i<=hi;i++)//自左向右考察每个a[i]
if(a[i]<pivot)//若[k]小于轴点，则将其
swap(a[++mi],a[i]);//与[mi]交换，L向右扩展
swap(a[lo],a[mi]);//候选节点归位（名副其实）
return mi;//返回轴点的秩
}
void quickSort(int a[], int low, int high)
{
if (low < high)
{
int m = partition(a, low, high); // O(N)
// a[low..high] ~> a[low..m–1], pivot, a[m+1..high]
quickSort(a, low, m-1); // 递归地将左子阵列排序
// a[m] = pivot 在分区后就被排序好了
quickSort(a, m+1, high); // 然后将右子阵列排序
}
}