交换排序-快速排序

• 时间复杂度：高效的排序算法，比较次数和移动次数都应该尽可能的少。
• 空间复杂度：算法执行期所需要辅助空间和待排序的数据量无关。理想空间复杂度为O(1)

简述

快速排序可以说算是针对冒泡排序的一种优化，冒泡排序是顺序交换，这样交换次数顺序增长。如果我们做跳跃的交换，那么可以使得交换次数也是跳跃性，会有所降低

算法思想

1. 找出一个枢轴，用于做比较交换，并记下后用。一般用第一个(用第一、中间、最后三个取中后来效果会更好)，定一个高位:high和底位:low
2. 从表的高位开始，往左进行比较，找到一个关键字小于枢轴，则将high和枢轴交换。否则high--
3. 从表的低位开始，往右进行比较，找到一个关键字大于等于枢轴，则将low和枢轴交换。否则low++
4. 重复2和3步，直到low==high位置，此时low和high的位置则是枢轴在本趟排序在表的最终位置，成功将表分成比枢轴小和比枢轴大两个字表在枢轴左右两侧。

以上2和3步骤，每次交换，要做三次记录：

一次移动low到high，一次移动high到low，加中间借助了temp这一类的。

我们可以减少移动记录：

比如一开始记录下枢轴值，在每次移动的时候，只移动要与枢轴交换的记录，移动完成后，最后将开始记录下的枢轴关键字放入最终的枢轴位置。

算法实现

private static class QuickSortClass {

        /**
         * 进行快速排序
         */
        public void quickSort() {
            List<Integer> integers = new ArrayList<>();
            int[] intArray = new int[]{1, 44, 3, 33, 77, 25, 98, 221, 33, 16};

            for (int value : intArray) {
                integers.add(value);
            }
            eSort(integers, 0, intArray.length - 1);
            System.out.print(integers);
        }

        /**
         * 计算枢轴位置，通过进行一轮交换得到新的枢轴位置
         *
         * @param ints
         * @return 返回交换后的枢轴的位置
         */
        private int evaluatePrivotPartition(List<Integer> ints, int l, int h) {

            /*第一步：先选取枢轴记录，使用三者取中原则，我们用第一个、中间一个、最后一个来比较大小，
             取中间大小中间一个为枢轴记录并与第一个交换*/

            int low = l;
            int high = h;

            int oneValue = ints.get(low);
            System.out.println("oneValue=" + oneValue);
            int centerPart = (high + low) / 2;
            int centerValue = ints.get(centerPart);
            System.out.println("centerValue=" + centerValue);
            int lastValue = ints.get(high);
            System.out.println("lastValue=" + lastValue);
            
            int privotDef = oneValue;
            
             //取出中间一个，做中枢记录,如果不用此步骤，那么默认选第一个
            if (oneValue > Math.min(centerValue, lastValue) && oneValue < Math.max(centerValue, lastValue)) {
                privotDef = oneValue;
            } else if (centerValue > Math.min(oneValue, lastValue) && oneValue < Math.max(oneValue, lastValue)) {
                privotDef = centerValue;
                //交换中枢位置
                ints.set(low, centerValue);
                ints.set(centerPart, oneValue);
            } else {
                privotDef = lastValue;
                ints.set(low, lastValue);
                ints.set(high, oneValue);
            }
            System.out.println("枢轴记录:privotDef=" + privotDef);

            /*重复第二三步，直到low==high为止*/
            while (low < high) {
            /*每一轮的交换执行*/
                //第二步：从high往左,如果high位置的值大于等于枢轴记录，那么high--
                while (low < high
                        && ints.get(high) >= privotDef) {
                    high--;
                }
                //小于枢轴值时候，需要和做交换，将high移到low
                if (low < high) {
                    ints.set(low, ints.get(high));
                }

                //第三步：从low往右,如果low位置的值小于等于枢轴记录，那么low++
                while (low < high
                        && ints.get(low) <= privotDef) {
                    low++;
                }
                //找到比枢轴记录大的值，那么low换到high
                if (low < high) {
                    ints.set(high, ints.get(low));
                }
            }

            //将记录下来的枢轴放入low位置，枢轴记录到位
            ints.set(low, privotDef);

            for (Integer value : ints) {
                System.out.print(value + " ");
            }
            System.out.print("\n");
            return low;
        }

        /**
         * 执行快速排序入口
         *
         * @param ints
         * @param low
         * @param high
         */
        private void eSort(List<Integer> ints, int low, int high) {
            //只要low和high不相等,就代表交换后子表长度依旧大于1
            if (low < high) {
                int privotP = evaluatePrivotPartition(ints, low, high);
                eSort(ints, low, privotP - 1);//对左字表进行递归排序
                eSort(ints, privotP + 1, high);//对右字表进行递归排序
            }
        }
    }

• 客户端调用

public static void main(String[] args) {
        System.out.println("Hello World!");
        new QuickSortClass().quickSort();
    }

可以看到，在evaluatePrivotPartition中有一个,取中间值的步骤，不加那一步也是可以，跑一下你就会发现，本次排序用了6趟。如果不加那一步，则默认使用第一个为枢轴记录，最后排序下来的趟数会是7趟。

不要小看只多了一趟，如果数更大，优势会更明显。

算法分析

• 时间复杂度

可以看下排序的递归树：

image

大致也能看出，排序的躺数取决于递归树的深度.

1. 最好的情况：每一趟都能将记录均匀分割成两个长度大致相等的子表，类似折半查找。n个序列，枢轴定位时间O(n)，若T(n)是对n个元素进行排序所需对时间，且每次定位，正好把序列划分为长度相等的两个子表，设Cn是一个常数，表示n个元素进行一趟快速排序的时间，则总时间：

T(n)=Cn+2T(n/2)

T(n) <=n+2T(n/2)

继续往下得到T(n)约等于O(nlog₂n)

2. 最坏的情况：带排序序列已经排好的情况下，其递归数为单只树，每次划分得到一个比上一个少的序列，这样必须经过n-1趟才能将所有记录定位，而且第i趟需要经过n-i次比较，比较次数就为n²/2

为了避免最坏情况，所以我们可以使用三者取中原则进行选取枢轴记录，就是前面代码用到的方式

• 空间复杂度

排序是递归的，所以需要有一个栈来存放相应的数据。最大递归调用次数与递归树的深度一致。为O(log₂n)，最坏情况下为O(n)

算法特点

1. 不稳定：记录非顺序次地移动导致
2. 难用于链式结构：需要定位表的下界和上界，适合顺序结构
3. 平均来说，快排可以说是内部排序中最快的一种了，在初始无序，n比较大的情况，使用快排是比较合适的。