Java排序之快速排序

前言

快速排序作为排序算法的王者,我们没有理由不掌握它

引用自大话数据结构.png

• 快速排序的基本思想:
  通过一趟排序将待排序记录分割成独立的两部,其中一部分记录的关键字均比另一部分记录的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序的目的.

• 快速排序的快速理解:
  把数据分成左右两部分,左边的所有数据都比右边数据小, 再把左右两部分的数据按同样的方法排序. 很明显快速排序是不稳定的,排序的结果次序可能不一致.

举例分析

int s[] = {52,78,12,99,5,18,80,32,66};

快速排序示意图.png

画了一张很简单的图, 力求简单.每个格子想象成一个待挖的坑.

第一步: 我们先随便从数组中拿一个数据作为基准数p.便于演示,就用s[0] 吧,即p=s[0] . 注意,我们在s[0]处拿了一个数据,我们就想象从数组s中挖了一个坑,而且这个坑的位置就是s[0],下面我们来看看如何填坑

第二步:找 s[k] < p :从索引K的结尾处开始向前找. 找比s[0] (即p)小的数.如图中的绿色箭头方向,标号①表示绿色查找优先红色查找,很明显s[7]=32 < s[0]=52 , 此时我们把32挖出来去填s[0]的坑, 让s[0]=s[7] , 所以此时s[0]为32,就是说我们把第一个坑填了. 但是有一个新坑k[7],此时的数据顺序:
32,78,12,99,5,18,80,32,66

第三步:找 s[i] > p :从索引 i 的开始处从前向后找.找比s[0] (即p)大的数.如图中的红色箭头方向.我们看到 s[1] = 78 > p=52 .所以我们挖出s[1]的数据放到上一步的坑中,就是k[7]了.此时我们的新坑i[1] , 让 s[7]=s[1],此时的数据顺序:
32,78,12,99,5,18,80,78,66

我们在第二步中得到了K=7,在第三步中得到了i=1.那么在下一轮的查找中k从6开始,然后i从2开始.这样重复执行第二步然后第三步,直到 i = k . 这样就完成了左边的数据都是小于右边的数.之后用同样的方法从第一步开始分别对左右部分的数据进行排序,得到的就是最终的结果

Java代码示例

原理讲完了,我们来撸一下java的实现.

public void quickSort(int arr[],int sIndex,int eIndex){
        if (sIndex < eIndex) {
            int p = arr[sIndex] , i = sIndex , k = eIndex;
            while (i < k) {
                while(i < k && arr[k] >= p) // 从右向左找
                    k--;

                if (i < k ) arr[i++] = arr[k];

                while(i < k && arr[i] < p) // 从左向右找
                    i++;

                if (i < k ) arr[k--] = arr[i];
            }
            arr[i] = p;
            quickSort(arr, sIndex, i - 1); // 递归
            quickSort(arr, i + 1, eIndex);
        }
}

结束

快速排序还有很多优化版本,但是基本思想都是类似的,很大程度上取决P的选择,比如如果P处于数列的中间,那么就趋于平衡树,效率会提高.总的来说,快速排序名副其实,我们应该好好学习它.谢谢大家!

参考文章
白话经典算法系列之六 快速排序 快速搞定