Java实现快速排序

快速排序是经典排序算法之一，它的基本思想是：通过一趟排序使要排序的数据分为两部分，其中一部分的所有数据比另外一部分的所有数据都要小，然后再用此方法对这两部分继续排序。通过递归，最终使整个数据达到有序序列，其中也有二分的思想。

设要排序的数组是arr[0]……arr[N-1]，首先任意选取一个数据（通常选用数组的第一个数）作为关键数据，然后将所有比它小的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一趟快速排序。

一趟快速排序的算法是：

1）设置两个变量：i、j，初始值：i = 0；j = N - 1。

2）以第一个数组元素作为关键数据，赋值给key，即key=arr[0]；

3）从j开始向前搜索，即由后开始向前搜索(j--)，找到第一个小于key的值arr[j]；从i开始向后搜索，即由前开始向后搜索(i++)，找到第一个大于key的arr[i]，将arr[j]和arr[i]互换；

4）重复第3步，直到i=j； (第3步中，没找到符合条件的值，即arr[j]不小于key、arr[i]不大于key的时候改变j、i的值，使得j=j-1，i=i+1，直至找到为止。找到符合条件的值，进行交换的时候i， j指针位置不变。另外，i==j这一过程一定正好是i+或j-完成的时候，此时令循环结束）。

java实现：

public class QuickSort {

    private static int[] arr = {1,3,2,9,5,11,16,12,91,36,78,13,16,28,25,68,35,231,12,123,34,45,235,56,51,78,65};
    public static void main(String[] args) {
        System.out.println("排序前:");
        printArr();
        quickSort(0, arr.length - 1);
        System.out.println();
        System.out.println("排序后:");
        printArr();
    }

    public static void quickSort(int left, int right) {
        int i, j, key, temp;
        if (left > right) {
            return;
        }
        key = arr[left];
        i = left;
        j = right;
        while(i != j) {
            while (arr[j] >= key && i < j) {
                j--;
            }
            while (arr[i] <= key && i < j) {
                i++;
            }
            if (i < j) {
                temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
        arr[left] = arr[i];
        arr[i] = key;
        quickSort(left, i - 1);
        quickSort(i + 1, right);
    }

    //遍历输出数组
    public static void printArr() {
        for (int i : arr) {
            System.out.print(i + " ");
        }
    }
}

执行结果如下：

排序前:
1 3 2 9 5 11 16 12 91 36 78 13 16 28 25 68 35 231 12 123 34 45 235 56 51 78 65 
排序后:
1 2 3 5 9 11 12 12 13 16 16 25 28 34 35 36 45 51 56 65 68 78 78 91 123 231 235 
Process finished with exit code 0