快速排序

快速排序（Quick Sorting）是迄今为止所有内排序算法中速度最快的一种。

它的基本思想是：任取待排序序列中的某个元素作为标准（也称为支点、界点，一般取第一个元素），通过一次划分，将待排元素分为左右两个子序列，左子序列元素的排序码均小于基准元素的排序码，右子序列的排序码则大于或等于基准元素的排序码，然后分别对两个子序列继续进行划分，直至每一个序列只有一个元素为止。最后得到的序列便是有序序列。

一次划分的具体过程:

1. low指向待划分区域首元素，high指向待划分区域尾元素
2. s[0]=s[low] (为了减少数据的移动,将作为标准的元素暂存到R[0]中，最后再放入最终位置)
3. high从后往前移动直到s[high]<s[0]
4. s[low]=s[high], low++
5. low从前往后移动直到s[low]>=s[0]
6. s[high]=s[low], high--
7. goto 3
8. 直到low==high时，s[low]=s[0] (即将作为标准的元素放到其最终位置) 。概括地说, 一次划分就是从表的两端交替地向中间进行扫描, 将小的放到左边, 大的放到右边, 作为标准的元素放到中间。

快速排序.gif

快速排序示例:

代码：

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int[] s = { 49, 38, 65, 97, 76, 13, 27, 49 };
        new QuickSort().quick_Sort(s, 0, s.length-1);

        for (int i = 0; i < s.length; i++) {
            System.out.printf("%d ", s[i]);
        }
    }

    void quick_Sort(int[] s, int low, int high) {

        if (low > high) {
            return;
        }
        int left = low;
        int right = high;

        int key = s[low];
        while (left < right) {

            while (s[right] >= key && right > left) {
                right--;
            }
            while (s[left] <= key && right > left) {
                left++;
            }

            if (left < right) {
                int temp = s[left];
                s[left] = s[right];
                s[right] = temp;
            }

        }
        s[low] = s[left];
        s[left] = key;
        
        
        quick_Sort(s, low, right-1);
        quick_Sort(s, right+1, high);

    }

输出：

13 27 38 49 49 65 76 97 

快速排序的性能分析

排序算法	平均时间性能	最好时间性能	最坏时间性能	辅助空间	稳定性
快速排序					不稳定

快速排序的时间复杂度

如果每次划分对一个对象定位后，该对象的左子序列与右子序列的长度相同, 则下一步将是对两个长度减半的子序列进行排序, 这是最理想的情况。

假设n是2的幂，n=2 ,(k=log n),假设支点位置位于序列中间k2，这样划分的子区间大小基本相等。 n+2(n/2)+4(n/4)+….+n(n/n)=n+n+……..+n=nk=nlog2n因此，快速排序的最好时间复杂度为O（nlog n）。而且2在理论上已经证明，快速排序的平均时间复杂度也为O（nlog n）。
实验结果表明:
就平均计算时间而言, 快速排序是所2有内排序方法中最好的一个。在最坏的情况, 即待排序对象序列已经按其排序码从小到大排好序的情况下, 其递归树成为单支树, 每次划分只得到一个比上一次少一个对象的子序列(蜕化为冒泡排序)。必须经过n-1趟才能把所有对象定位, 而且第 i趟需要经过 n-i次排序码比较才能找到第 i个对象的安放位置，总的排序码比较次数将达到
因此，快速排序的最坏时间复杂度为O(n2)。

快速排序的空间复杂度及稳定性

快速排序是递归的，需要有一个栈存放每层递归调用时的指针和参数。最大递归调用层次数与递归树的高度一致。理想情况为log2(n+1) ；最坏情况即待排序对象序列已经按其排序码从小到大排好序的情况下 , 其递归树成为单支树,深度为n。

• 快速排序最好的空间复杂度为O（log 2n）,最坏的空间复杂度为O(n)(即快速排序所需用的辅助空间)。
• 快速排序是一种不稳定的排序方法。可用{3,2,2'}序列来验证。