java快速排序法

快速排序由C. A. R. Hoare在1960年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

1、快速排序思想及原理

事实上，快速排序是堆冒泡排序的一种改进。

它的基本思想是：通过一趟排序将要排序的数据分割为两部分，第一部分所有数据比第二部分的所有数据小，按照这种思路将两部分数据再次分别进行快速排序，可以使用递归完成，最终使得整个数据序列有序。

具体来讲，在待排数据中找一个基准数据（通常取第一个数），接下来将待排数据中比基准数据小的放在待排数据的左侧，将比待排数据中比基准数据大的放在待排数据右侧。此时，左右两个分区的元素相对有序，接着采用上述思路继续对左右两个分区继续排序，直到各分区只有一个元素位置。这里用到了一个典型的分治思想。

下面我们用图解的方式来演示这个排序过程：

假设下面这个数组是待排序数组：

（6, 1, 2, 7, 9, 3, 4, 5, 10, 8）

按照快速排序的思想，首先得把这组数分成相互独立的两部分，其中一部分比中的数比另一部分的数都小。如何实现这一步呢？

[mark_a]方法其实很简单：首先选取待排序数组的第一个数为基准数，也就是6，然后分别从初始序列“（6,1,2,7,9,3,4,5,10,8）”两端开始“探测”。先从右往左找一个小于6的数，再从左往右找一个大于6的数，然后交换他们。这里可以用两个变量i和j，分别指向序列最左边和最右边。我们为这两个变量起个好听的名字“哨兵i”和“哨兵j”。刚开始的时候让哨兵i指向序列的最左边（即i=1），指向数字6。让哨兵j指向序列的最右边（即j=10），指向数字8。[/mark_a]

首先哨兵j开始出动。因为此处设置的基准数是最左边的数，所以需要让哨兵j先出动，这一点非常重要（请自己想一想为什么）。哨兵j一步一步地向左挪动（即j–），直到找到一个小于6的数停下来。接下来哨兵i再一步一步向右挪动（即i++），直到找到一个数大于6的数停下来。最后哨兵j停在了数字5面前，哨兵i停在了数字7面前。

现在交换哨兵i和哨兵j所指向的元素的值。交换之后的序列为（6, 1, 2, 5, 9, 3, 4, 7, 10, 8）。

接下来开始哨兵j继续向左挪动（再友情提醒，每次必须是哨兵j先出发）。他发现了4（比基准数6要小，满足要求）之后停了下来。哨兵i也继续向右挪动的，他发现了9（比基准数6要大，满足要求）之后停了下来。此时再次进行交换，交换之后的序列为（6, 1, 2, 5, 4, 3, 9, 7, 10, 8）。

哨兵j继续向左挪动，他发现了3（比基准数6要小，满足要求）之后又停了下来。哨兵i继续向右移动，糟啦！此时哨兵i和哨兵j相遇了，哨兵i和哨兵j都走到3面前。说明此时“探测”结束。3比6小所以我们将基准数6和3进行交换。交换之后的序列为（3, 1, 2, 5, 4, 6, 9, 7, 10, 8）。

此时第一趟排序结束，我们已经把待排序数组分成了以6为基准，左边一列序列，右边一序列，左边序列的数比右边序列的数都小。不过此时左右两部分中的数各自的排序仍然是混乱的，还要继续排序。

快速排序的排序过程已经通过上面的图解讲解清楚了，接下来左右两部分的数据继续按照快速排序的方式来排序。

下面举例说明：

待排序列依次为3、5、7、2、11、6、1、3、8、4、10、12。

步骤：
1、选取一个基准数，一般选第0个元素3。
2、将比基准数小的移动到左侧，比基准数大的移动到右侧，相等的不移动，此时基准数位置为K。
3、对左右两侧重复步骤1和步骤2，直到左右侧细分到只有一个元素。
快排的难点也就是在第2步，怎么移动各个数据？
  a、首先从数列的右边开始往左找，设下标为i，也就是i--操作，找到第一个比基准数小的值，让他与基准数交换；
  b、接着开始从左往右找，设下标为j，也就是j++，找到第一个比基准数大的值，让他与基准数交换位置；
  c、重复1和2，直到i和j相遇时结束，最后基准值所在位置为k。

2、java快排代码

public class FastSort {
    public static void main(String[] args) {
        int[] array = new int[] { 3, 5, 7, 2, 11, 6, 1, 3, 8, 4, 10, 12 };

        fastSort(array, 0, array.length - 1);
        print(array);
    }

    private static void fastSort(int[] array, int l, int r) {
        if (l > r) {
            return;
        }

        int low = l;
        int high = r;
        int key = array[l];
        while (low < high) {
            for (;; high--) {
                if (high <= low) {
                    break;
                }
                if (array[high] < key) {
                    array[low] = array[high];
                    break;
                }
            }

            for (;; low++) {
                if (high <= low) {
                    break;
                }
                if (array[low] > key) {
                    array[high] = array[low];
                    break;
                }
            }
        }
        if (low == high) {
            array[low] = key;
        }

        // print(array);

        fastSort(array, 0, low - 1);
        fastSort(array, low + 1, r);

    }

    private static void print(int[] array) {
        for (int i : array) {
            System.out.print(i + " ");
        }

    }

}

3、快排的特点及性能

快排是在冒泡排序之上改进而来的，冒泡排序每次只能交换相邻的两个元素，而快排则是跳跃式的交换，交换距离很大，总的比较次数和交换次数少了很多，速度也快了很多。
快排的平均时间复杂度为O(nlogn)，事实上，大多数情况下，排序速度要快于这个时间复杂度。快排实际上是采用的一种分而治之的思想，把问题分解为一个个的小问题去逐一解决，最终在把结果组合起来。
快排因为递归调用，所以空间复杂度为O(logn)。
快排是一种不稳定的排序算法，在经过排序后，等值的元素的相对位置可能发生改变。
快排基本上被认为是相同数量级中所有排序算法中平均性能最好的。