本文共 1797 字，大约阅读时间需要 5 分钟。

接触到快排是在对Arrays.sort的排序底层进行研究的情况下，发现不接触算法，不看懂排序的原理，根本就不可能更深的去理解底层写法。 

Arrays.sort对基本数据结构的排序算法是采用的快排，对对象的排序算法是采用的归并排序。  为什么要使用快排呢？  因为快排的排序速度是极快的。  为什么说快排不稳定呢？  因为值相同的元素排序可能不同，而归并排序却很稳定。

这也就是Arrays对基本数据类型采用快排，因为基本数据类型的排序快排已经足够了，对对象的排序就需要更稳定的归并排序了。

以下是快排的实现代码

public static void sort(int[] a, int low, int high) {        int start = low;        int end = high;        int key = a[start];        while (end > start) {            /* 从后往前.找到比key小的，就与key交换位置 */            while (end > start && a[end] >= key)  //end > start 必须要                end--;            if (a[end] <= key) {  //这里如果用异或来交换的话不能用<=                int temp = a[end];                a[end] = a[start];                a[start] = temp;            }            /* 从后往前.找到比key小的，就与key交换位置 */            /*从前往后，找到比key大的，就与key交换位置*/            while (end > start && a[start] <= key)// 如果没有比关键值大的，比较下一个，直到有比关键值大的交换位置                start++;            if (a[start] >= key) {   //这里如果用异或来交换的话不能用<=                int temp = a[start];                a[start] = a[end];                a[end] = temp;            }            /*从前往后，找到比key大的，就与key交换位置*/        }        /*一轮循环后，比key大的被key交换到key的左边，比key小的被key交换到key的右边，实现了左边都比key小，右边都比key大*/        for (int i = 0; i < a.length; i++) {            System.out.print(a[i] + " ");        }        System.out.println();        // 递归排序key的左右两边 直到最后start==low end==high 结束调用        if (start > low)            sort(a, low, start - 1);        if (end < high)            sort(a, end + 1, high);    }

 

 

同样，我将其分为了几个模块。 

快排的大致思想是，设立一个基准数key，一轮循环将比key大的放到key的右边，比key小的放到key的左边 

然后递归排序 key左边的数与key右边的数，即实现排序。  他的代码可能没有冒泡排序选择排序那么好理解，实现思想看明白了也不会很难。

快排的实现我将其分成下面的步骤 

1.一次循环中，包含一次由后向前的遍历，一次由前向后的遍历；  2.由后向前的遍历实现了将比基准数小的值放在基准数的前面，由前向后的值将比基准数大的值放在基准数的后面；  3.一次循环跑完end>start，即遍历完整个数据的数，此时将数组分成左右两边；  4.递归1-3排序基准值左右两边的数据，递归结束条件即完成排序。

转载地址：http://nriob.baihongyu.com/