数组元素排序（二）

快速排序（Quick Sort）由图灵奖获得者Tony Hoare发明，被列为20世纪十大算法之一，是迄今为止所有内排序算法中速度最快的一种，快速排序的时间复杂度为O(nlog(n))。

快速排序通常明显比同为O(nlogn)的其他算法更快，因此常被采用，而且快排采用了分治法的思想，所以在很多笔试面试中能经常看到快排的影子。

排序思想：

1. 从数列中挑出一个元素，称为"基准"（pivot），
2. 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
3. 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
4. 递归的最底部情形，是数列的大小是零或一，也就是永远都已经被排序好了。虽然一直递归下去，但是这个算法总会结束，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。

第一轮操作：

 第二轮操作

内部排序性能比较与选择

性能比较：

           从平均时间而言：快速排序最佳。但在最坏情况下时间性能不如堆排序和归并排序。

           从算法简单性看：由于直接选择排序、直接插入排序和冒泡排序的算法比较简单，将其认为是简单算法。对于Shell排序、堆排序、快速排序和归并排序算法，其算法比较复杂，认为是复杂排序。

           从稳定性看：直接插入排序、冒泡排序和归并排序时稳定的；而直接选择排序、快速排序、 Shell排序和堆排序是不稳定排序

           从待排序的记录数n的大小看，n较小时，宜采用简单排序；而n较大时宜采用改进排序。

选择：

           若n较小(如n≤50)，可采用直接插入或直接选择排序。 当记录规模较小时，直接插入排序较好；否则因为直接选择移动的记录数少于直接插入，应选直接选择排序为宜。

           若文件初始状态基本有序(指正序)，则应选用直接插入、冒泡或随机的快速排序为宜；

           若n较大，则应采用时间复杂度为O(nlgn)的排序方法：快速排序、堆排序或归并排序。

快排示例

   public static void main(String[] args) {
        int[] data = {9, -16, 30, 23, -30, -49, 25, 21, 30};
        System.out.println("排序之前：\n" + Arrays.toString(data));
        quickSort(data, 0, data.length - 1);
        System.out.println("排序之后：\n" + Arrays.toString(data));
    }

    public static void quickSort(int[] arr, int left, int right) {
        if (right >= left) {
            //基数
            int basic = arr[left];
            //定义指针
            int i = left;
            int j = right;

            while (i < j) {//左大
                while (i < j && arr[j] > basic) {
                    j--;
                }
                if (i < j) {
                    arr[i] = arr[j];
                    i++;
                }
                while (i < j && arr[i] < basic) {
                    arr[j] = arr[i];
                    i++;
                }
                if (i < j) {
                    arr[j] = arr[i];
                    j--;
                }
            }
            arr[i] = basic;
            quickSort(arr, left, i - 1);
            quickSort(arr, i + 1, right);
        }
    }