三数中值法快速排序的Java实现

排序算法也是算法的一个重头戏，里面涉及的算法按时间复杂度可以分为两大类：

时间复杂度为O(n^2): 冒泡排序、选择排序、插入排序

时间复杂度为O(nlogn): 快速排序、归并排序

本文将重点介绍快速排序及其实现。

时间复杂度：

快速排序是目前已有的排序算法中最快的算法，它的平均时间复杂度为O(nlogn)，最坏时间复杂度为O(n^2)。

核心思路：分治思想

将原问题划分成若干子问题解决：数组A中选一个基准点pivot，数组中其他的元素与pivot逐个比较，每遇到一个大于pivot的元素和一个小于pivot的元素，两者交换位置，大的右移，小的左移，直至所有元素不再进行上述步骤。

pivot的选择：

常见的有以下三种方案：
首/尾法：如果数组是排好序的，那么选首/尾元素为pivot，可能会把所有元素移到另外一边，带来最坏时间复杂度为O(n^2)。
随机选择法：最坏时间复杂度为O(n^2)产生的概率小于头/尾法。
三数中值法：求数组的第一个元素、中间位置元素、最后一个元素的中值，将中值与最后一个元素交换即可，这样做的好处是降低了最坏时间复杂度产生的概率。
下面我们一起来看一下具体的实现：
part 1

思路分析：

pivot.png

代码：

//   三数中值法是为了防止最坏情况的出现，找到三数中值，并与right-1 交换，能减少一次交换次数，因为right 确定＞ 中值；
    public int midValue(int a[], int left, int right){
//        先确定数组里的数>=3个,这样才能选三个数里的中值：
        if(right-left+1>=3){
            int center =(left+right)/2;
            if(a[left]> a[center]){
                swap(a,left,center);
            }
            if(a[center]> a[right]){
                swap(a,center,right);
        }
//            这一步是防止原先的顺序为：321，相当于比较了原来的left、right；
            if(a[left]>a[center]){
                swap(a,left,center);
            }
            swap(a,center,right-1);
            return a[right-1];
        }else{
            if(a[left]>a[right]){
                swap(a,left,right);
            }
            return 0;
        }
    }

part 2

思路分析：

QuickSort.png

代码：

public int[] quickSortNew(int[] a, int left ,int right){

        int pivot = midValue(a,left,right);
//        首先分析数组的数目大于3时
        if(right-left+1>3){
            int i= left;
            int j= right -1;
            while (i<j){
//                如果满足括号里的条件，会一直继续下去 ，目的：a[i]>pivot 时才停下，所以条件取反时一直往右移：
                while (i<j && a[i]<= pivot){i+=1;}
//                同上，找到a[j]<pivot
                while (i<j && a[j]>= pivot){j-=1;}
//                以上循环停下的时候 ，如果正好i<j,交换a[i] a[j]的位置
                if(i<j){
                    swap(a, i, j);
                }else {
                    break;
                }
            }
            swap(a,i,right-1);
            quickSortNew(a,left,i-1);
            quickSortNew(a, i+1, right);
        }
        return a;
}

小结：
排序算法的很多都用了分治思想，把一个大问题划分成若干子问题来解决，在我们自己学习的时候，也可以把思考的过程划分成若干子过程来仔细研究，就像我刚刚只是思路分析了例子中排序的第一步，如果你感兴趣，且想把快速排序这个问题啃下，建议小伙伴们可以自己分析演练出后序过程，这样可以更好地帮助你理解这个问题。