Algorithm-Sort

引言：

八大排序算法

排序模板

模板一：

public class Example {
    // 八大排序算法
    // 这里暗喻数组a实现了接口Comparable
    public static void sort(Comparable[] a) { 
        /*...*/ 
    }
    private static boolean less(Comparable v, Comparable w) { 
        return v.compareTo(w) < 0; 
    }
    private static void swap(Comparable[] a, int i, int j) { 
        Comparable t = a[i]; 
        a[i] = a[j]; 
        a[j] = t; 
    }
    private static void show(Comparable[] a) { 
        // 在单行中打印数组
        for (int i = 0; i < a.length; i++) 
            StdOut.print(a[i] + " "); 
        StdOut.println();
    }
    public static boolean isSorted(Comparable[] a) { 
        // 测试数组元素是否有序
        for (int i = 1; i < a.length; i++) 
            if (less(a[i], a[i-1])) 
                return false; 
        return true;
    }
    public static void main(String[] args) { 
        // 从标准输入读取字符串，将它们排序并输出 
        String[] a = In.readStrings(); 
        sort(a);
        assert isSorted(a); 
        show(a);
    }
}

模板二

public abstract class Example<T extends Comparable<T>> {
    // 八大排序算法
    public abstract void sort(T[] nums);
    
    // 返回v是否小于w
    protected boolean less(T v, T w) {
        return v.compareTo(w) < 0;
    }
    
    protected void swap(T[] a, int i, int j) {
        T t = a[i];
        a[i] = a[j];
        a[j] = t;
    }
    protected void show(T[] a) { 
        // 在单行中打印数组
        for (int i = 0; i < a.length; i++) 
            StdOut.print(a[i] + " "); 
        StdOut.println();
    }
    protected boolean isSorted(T[] a) { 
        // 测试数组元素是否有序
        for (int i = 1; i < a.length; i++) 
            if (less(a[i], a[i-1])) 
                return false; 
        return true;
    }
}
// 例如选择排序在改模板下的用法
public class Sort<T extends Comparable<T>> extends Example<T> {
    @Override
    public void sort(T[] nums) {
        int N = nums.length;
        for (int i = 0; i < N - 1; i++) {
            int min = i;
            for (int j = i + 1; j < N; j++) {
                if (less(nums[j], nums[min])) {
                    min = j;
                }
            }
            swap(nums, i, min);
        }
    }
}

下文使用的均为模板一。

交换排序

冒泡排序

在序列完全有序时，该算法只需遍历一遍数组，不用执行任何交换操作，时间复杂度为O(N) 。在最坏情况下，冒泡排序要执行n(n-1)/2 次交换操作，时间复杂度为O(N2) 。在平均情况下，冒泡排序的时间复杂度也是O(N2)。

public class BubbleSort {
    // 冒泡排序
    public static void sort(Comparable[] a) { 
        int N = a.length;
        boolean isSort = false;
        for(int i = 0; i < N -1 && !isSort; i ++){
            isSort = true;
            for(int j = 0; j < N - 1 - i; j ++){
                if(less(a[j + 1], a[j])){
                    isSort = false;
                    swap(a, j, j + 1);
                }
            }
        }
    }
    public static void main(String[] args) { 
        // 从标准输入读取字符串，将它们排序并输出 
        String[] a = In.readStrings(); 
        sort(a);
        assert isSorted(a); 
        show(a);
    }
}

　根据上面这种冒泡实现，若原数组本身就是有序的（这是最好情况），仅需n-1次比较就可完成；若是倒序，比较次数为 n-1+n-2+…+1=n(n-1)/2，交换次数和比较次数等值。所以，其时间复杂度依然为O(n2）。综合来看，冒泡排序性能还还是稍差于上面那种选择排序的。

快速排序

1565514415843

简介：在数组中找一个支点(任意),经过一趟排序后，支点左边的数都要比支点小，支点右边的数都要比支点大！

public class QuickSort {
    // 快速排序
    public static void sort(Comparable[] a, int start, int end) { 
        if(start < end){	// 递归出口
            swap(a, start, (int) (Math.random() * (end - start + 1) + start));
            // 基准值
            int base = arr[start];
            // 排序下标
            int low = start; 
            int high = end;
            while(low < high){	// while直到一个数
                while(low < high && base <= a[high])	// 只移动下标
                    high --;
                a[low] = a[high];
                while(low < high && a[low] <= base)		// 只移动下标
                    low ++;
                a[high] = a[low];
            }
            // while结束（下标相同），把基数赋给低位置的元素（这里low=high）
            a[low] = base;
            // 开始递归
            // 处理所有的小的数字
            quickSort(a, start, low);
            // 处理所有的大的数字
            quickSort(a, low+1, end);
        }
    }
    public static void main(String[] args) { 
        // 从标准输入读取字符串，将它们排序并输出 
        String[] a = In.readStrings(); 
        sort(a);
        assert isSorted(a); 
        show(a);
    }
}

总的来说，可以肯定的是对于大小为 N 的数组，的运行时间在 NlogN 的范围之内。归并排序也能做到这一点，但是快速排序一般会更快（尽管它的比较次数多 39%），因为它移动数据的次数更少。

扩展：参考，优化

插入排序

简介：每次都将当前元素插入到左侧已经排序的数组中，使得插入之后左侧数组依然有序。

public class InsertSort {
    // 插入排序
    public static void sort(Comparable[] a) { 
        int N = a.length;
        for(int i = 1; i < N; i ++){
            // 挨个来
            for(int j = i; j > 0 && less(a[j], a[j - 1]); j --){
                swap(a, j, j - 1);
            }
        }
    }
    public static void main(String[] args) { 
        // 从标准输入读取字符串，将它们排序并输出 
        String[] a = In.readStrings(); 
        sort(a);
        assert isSorted(a); 
        show(a);
    }
}

简单插入排序在最好情况下，需要比较n-1次，无需交换元素，时间复杂度为O(n);在最坏情况下，时间复杂度依然为O(n2)。但是在数组元素随机排列的情况下，插入排序还是要优于上面两种排序的。

优化：在插入时使用二分法查找插入的位置。

希尔排序

public class ShellSort {
    // 插入排序
    public static void sort(Comparable[] a) { 
        // 设置步长
        int N = a.length;
        int h = 1;
        
        // 小于 N 的最长步长
        while(h < N / 3)
            h = 3 * h + 1;	// 1, 4, 13, 40
        
        // 排序、本质为插入排序
        while(h >= 1){
            // 从步长 h 开始
            for(int i = h; i < N; i ++){
                // 区间[0,h)内为有序
                for(int j = i; j >= h && less(a[j], a[j - h]); j -= h){
                    swap(a, j, j - h);
                }
            }
            h = h / 3;
        }
    }
    
    public static void main(String[] args) { 
        // 从标准输入读取字符串，将它们排序并输出 
        String[] a = In.readStrings(); 
        sort(a);
        assert isSorted(a); 
        show(a);
    }
}

对于大规模的数组，插入排序很慢，因为它只能交换相邻的元素，每次只能将逆序数量减少 1。希尔排序的出现就是为了解决插入排序的这种局限性，它通过交换不相邻的元素，每次可以将逆序数量减少大于 1。

希尔排序使用插入排序对间隔 h 的序列进行排序。通过不断减小 h，最后令 h=1，就可以使得整个数组是有序的。

选择排序

public class SeletSort {
    // 选择排序
    public static void sort(Comparable[] a) { 
        int N = a.length;
        for(int i = 0; i < N - 1; i ++){
            for(int j = i + 1; j < N - 1; j ++){
                int min = i;
                if(less(a[j], a[min])){
                    min = j;
                }
            }
            swap(a, i, min);
        }
    }
    
    public static void main(String[] args) { 
        // 从标准输入读取字符串，将它们排序并输出 
        String[] a = In.readStrings(); 
        sort(a);
        assert isSorted(a); 
        show(a);
    }
}

运行时间和输入无关。为了找出最小的元素而扫描一遍数组并不能为下一遍扫描提供什么信息。其他算法会更善于利用输入的初始状态。
数据移动是最少的。每次交换都会改变两个数组元素的值，因此选择排序用了N次交换 ——交换次数和数组的大小是线性关系。其他任何算法都不具备这个特征（大部分的增长数量级都是线性对数或是平方级别）。
简单选择排序通过上面优化之后，无论数组原始排列如何，比较次数是不变的；对于交换操作，在最好情况下也就是数组完全有序的时候，无需任何交换移动，在最差情况下，也就是数组倒序的时候，交换次数为n-1次。综合下来，时间复杂度为O(n2)

堆排序

堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。如下图：

同时，我们对堆中的结点按层进行编号，将这种逻辑结构映射到数组中就是下面这个样子

该数组从逻辑上讲就是一个堆结构，公式描述为：

大顶堆：arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]
小顶堆：arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2]

堆排序的基本思想是：将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了

步骤一构造初始堆。将给定无序序列构造成一个大顶堆（一般升序采用大顶堆，降序采用小顶堆)。

假设给定无序序列结构如下

此时我们从最后一个非叶子结点开始（叶结点自然不用调整，第一个非叶子结点 arr.length/2-1=5/2-1=1，也就是下面的6结点），从左至右，从下至上进行调整。

找到第二个非叶节点4，由于[4,9,8]中9元素最大，4和9交换。

这时，交换导致了子根[4,5,6]结构混乱，继续调整，[4,5,6]中6最大，交换4和6。

此时，我们就将一个无需序列构造成了一个大顶堆。

步骤二将堆顶元素与末尾元素进行交换，使末尾元素最大。然后继续调整堆，再将堆顶元素与末尾元素交换，得到第二大元素。如此反复进行交换、重建、交换。

将堆顶元素9和末尾元素4进行交换

重新调整结构，使其继续满足堆定义

再将堆顶元素8与末尾元素5进行交换，得到第二大元素8.

后续过程，继续进行调整，交换，如此反复进行，最终使得整个序列有序

再简单总结下堆排序的基本思路：

将无需序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆;
将堆顶元素与末尾元素交换，将最大元素”沉”到数组末端;
重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序。

public class HeapSort {
    public static void sort(int []arr){
        //1.构建大顶堆
        for(int i=arr.length/2-1;i>=0;i--){
            //从第一个非叶子结点从下至上，从右至左调整结构
            adjustHeap(arr,i,arr.length);
        }
        //2.调整堆结构+交换堆顶元素与末尾元素
        for(int j=arr.length-1;j>0;j--){
            swap(arr,0,j);//将堆顶元素与末尾元素进行交换
            adjustHeap(arr,0,j);//重新对堆进行调整
        }

    }

    /**
     * 调整大顶堆（仅是调整过程，建立在大顶堆已构建的基础上）
     * @param arr
     * @param i
     * @param length
     */
    public static void adjustHeap(int []arr,int i,int length){
        int temp = arr[i];//先取出当前元素i
        for(int k=i*2+1;k<length;k=k*2+1){//从i结点的左子结点开始，也就是2i+1处开始
            if(k+1<length && arr[k]<arr[k+1]){//如果左子结点小于右子结点，k指向右子结点
                k++;
            }
            if(arr[k] >temp){//如果子节点大于父节点，将子节点值赋给父节点（不用进行交换）
                arr[i] = arr[k];
                i = k;
            }else{
                break;
            }
        }
        arr[i] = temp;//将temp值放到最终的位置
    }
    public static void main(String []args){
        int []arr = {9,8,7,6,5,4,3,2,1};
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }
}

堆排序是一种选择排序，整体主要由构建初始堆+交换堆顶元素和末尾元素并重建堆两部分组成。其中构建初始堆经推导复杂度为O(n)，在交换并重建堆的过程中，需交换n-1次，而重建堆的过程中，根据完全二叉树的性质，[log2(n-1),log2(n-2)…1]逐步递减，近似为nlogn。所以堆排序时间复杂度一般认为就是O(nlogn)级。

归并排序

简介：即将两个有序的数组归并成一个更大的有序数组。先（递归地）将它分成两半分别排序，然后将结果归并起来。归并排序最吸引人的性质是它能够保证将任意长度为 N 的数组排序所需时间和 NlogN 成正比；它的主要缺点则是它所需的额外空间和 N 成正比。

归并排序分为三个过程：

将数列随意划分为两部分（在均匀划分时时间复杂度为O(NlogN) ）
递归地分别对两个子序列进行归并排序
合并两个子序列

public class MergeSort {
    // 归并排序
    public static void sort(int[] arr) {
        sort(arr, 0, arr.length - 1);
    }

    public static void sort(int[] arr, int L, int R) {
        if(L == R) {
            return;
        }
        int mid = L + ((R - L) >> 1);
        sort(arr, L, mid);
        sort(arr, mid + 1, R);
        merge(arr, L, mid, R);
    }

    public static void merge(int[] arr, int L, int mid, int R) {
        int[] temp = new int[R - L + 1];
        int i = 0;
        int p1 = L;
        int p2 = mid + 1;
        // 比较左右两部分的元素，哪个小，把那个元素填入temp中
        while(p1 <= mid && p2 <= R) {
            temp[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
        }
        // 上面的循环退出后，把剩余的元素依次填入到temp中
        // 以下两个while只有一个会执行
        while(p1 <= mid) {
            temp[i++] = arr[p1++];
        }
        while(p2 <= R) {
            temp[i++] = arr[p2++];
        }
        // 把最终的排序的结果复制给原数组
        for(i = 0; i < temp.length; i++) {
            arr[L + i] = temp[i];
        }
    }
}

public class MergeSort {
    public static void sort(int []arr){
        //在排序前，先建好一个长度等于原数组长度的临时数组，避免递归中频繁开辟空间
        int []temp = new int[arr.length];
        sort(arr,0,arr.length-1,temp);
    }
    private static void sort(int[] arr,int left,int right,int []temp){
        if(left<right){
            int mid = (left+right)/2;
            sort(arr,left,mid,temp);//左边归并排序，使得左子序列有序
            sort(arr,mid+1,right,temp);//右边归并排序，使得右子序列有序
            merge(arr,left,mid,right,temp);//将两个有序子数组合并操作
        }
    }
    private static void merge(int[] arr,int left,int mid,int right,int[] temp){
        int i = left;//左序列指针
        int j = mid+1;//右序列指针
        int t = 0;//临时数组指针
        while (i<=mid && j<=right){
            if(arr[i]<=arr[j]){
                temp[t++] = arr[i++];
            }else {
                temp[t++] = arr[j++];
            }
        }
        while(i<=mid){//将左边剩余元素填充进temp中
            temp[t++] = arr[i++];
        }
        while(j<=right){//将右序列剩余元素填充进temp中
            temp[t++] = arr[j++];
        }
        t = 0;
        //将temp中的元素全部拷贝到原数组中
        while(left <= right){
            arr[left++] = temp[t++];
        }
    }
    public static void main(String []args){
        int []arr = {9,8,7,6,5,4,3,2,1};
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }
}

归并排序是稳定排序，它也是一种十分高效的排序，能利用完全二叉树特性的排序一般性能都不会太差。java中Arrays.sort()采用了一种名为TimSort的排序算法，就是归并排序的优化版本。从上文的图中可看出，每次合并操作的平均时间复杂度为O(n)，而完全二叉树的深度为|log2n|。总的平均时间复杂度为O(nlogn)。而且，归并排序的最好，最坏，平均时间复杂度均为O(nlogn)。

排序模板

交换排序

冒泡排序

快速排序

插入排序

插入排序

希尔排序

选择排序

选择排序

堆排序

归并排序

计数排序