排序算法

1.快速排序

快速排序通过一个切分元素将数组分为两个子数组，左子数组小于等于切分元素，右子数组大于等于切分元素，将这两个子数组排序也就将整个数组排序了。

重点：切分

取 a[l] 作为切分元素，然后从数组的左端向右扫描直到找到第一个大于等于它的元素，再从数组的右端向左扫描找到第一个小于它的元素，交换这两个元素。不断进行这个过程，就可以保证左指针 i 的左侧元素都不大于切分元素，右指针 j 的右侧元素都不小于切分元素。当两个指针相遇时，将切分元素 a[l] 和 a[j] 交换位置。
性能分析
- 快速排序是原地排序，不需要辅助数组，但是递归调用需要辅助栈。
- 快速排序最好的情况下是每次都正好将数组对半分，这样递归调用次数才是最少的。复杂度为O(NlogN)。
- 最坏的情况下，第一次从最小的元素切分，第二次从第二小的元素切分，如此这般。因此最坏的情况下需要比较 N2/2。为了防止数组最开始就是有序的，在进行快速排序时需要随机打乱数组。

    public static  void main(String[] args) {

        int[] nums = new int[]{3,5,2,4,1};
        sort(nums,0,nums.length-1);
        for (int num : nums) {
            System.out.print(num+" ");
        }

    }

    static void sort(int[] nums,int l,int h){
        if(h<=l)return;
        int j = partition(nums,l,h);
        sort(nums,l,j-1);
        sort(nums,j+1,h);
    }

    static int partition(int[] nums,int l,int h){
        int i = l, j = h+1;
        int v = nums[l];
        while(true){
            while(nums[++i]<v && i!=h);
            while(nums[--j]>=v && j!=l);
            if(j<=i){
                break;
            }
            swap(nums,i,j);
        }
        swap(nums,l,j);
        return j;
    }

    static void swap(int[] nums,int i,int j){
        int tmp = nums[i];
        nums[i]=nums[j];
        nums[j] = tmp;
    }

2.插入排序

每次都将当前元素插入到左侧已经排序的数组中，使得插入之后左侧数组依然有序。
对于数组 {3, 5, 2, 4, 1}，它具有以下逆序：(3, 2), (3, 1), (5, 2), (5, 4), (5, 1), (2, 1), (4, 1)，插入排序每次只能交换相邻元素，令逆序数量减少1，因此插入排序需要交换的次数为逆序数量。
插入排序的时间复杂度取决于数组的初始顺序，如果数组已经部分有序了，那么逆序较少，需要的交换次数也就较少，时间复杂度较低。
平均情况下插入排序需要 ~N2/4 比较以及 ~N2/4 次交换；
最坏的情况下需要 ~N2/2 比较以及 ~N2/2 次交换，最坏的情况是数组是倒序的；
最好的情况下需要 N-1 次比较和 0 次交换，最好的情况就是数组已经有序了。

    public static  void main(String[] args) {

        int[] nums = new int[]{3,5,2,4,1};
        insertionSort(nums);
        for (int num : nums) {
            System.out.print(num+" ");
        }

    }

    static void insertionSort(int[] nums){
        for(int i=1;i<nums.length;i++){
            for(int j=i;j>0 && nums[j]<nums[j-1];j--){  //注意：当且仅当 nums[j]<nums[j-1] 时，循环继续进行，否则在前面的外循环中已经排好序了
                swap(nums,j,j-1);
            }
        }
    }

3.选择排序

从数组中选择最小元素，将它与数组的第一个元素交换位置。再从数组剩下的元素中选择出最小的元素，将它与数组
的第二个元素交换位置。不断进行这样的操作，直到将整个数组排序。
选择排序需要 ~N2/2 次比较和 ~N次交换，它的运行时间与输入无关，这个特点使得它对一个已经排序的数组也需要
这么多的比较和交换操作。

    static void selectionSort(int[] nums){
        for(int i=0;i<nums.length-1;i++){
            int min = i;
            for(int j=i+1;j<nums.length;j++){
                if(nums[min]>nums[j]){
                    min = j;
                }
            }
            swap(nums,i,min);
        }
    }

4.归并排序

图解排序算法(四)之归并排序

归并排序（MERGE-SORT）是利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案”修补”在一起，即分而治之)。

可以看到这种结构很像一棵完全二叉树，本文的归并排序我们采用递归去实现（也可采用迭代的方式去实现）。分阶段可以理解为就是递归拆分子序列的过程，递归深度为log2n。

再来看看治阶段，我们需要将两个已经有序的子序列合并成一个有序序列，比如上图中的最后一次合并，要将[4,5,7,8]和[1,2,3,6]两个已经有序的子序列，合并为最终序列[1,2,3,4,5,6,7,8]，来看下实现步骤。

    static void sort(int[] nums){
        int[] temp = new int[nums.length];  //在排序前，先建好一个长度等于原数组长度的临时数组，避免递归中频繁开辟空间
        sort(nums,0,nums.length-1,temp);
    }

    static void sort(int[] nums,int l,int h,int[] temp){
        if(l<h){
            int mid = l + (h-l)/2;
            sort(nums,l,mid,temp);      //左边归并排序，使得左子序列有序
            sort(nums,mid+1,h,temp); //右边归并排序，使得右子序列有序
            merge(nums,l,mid,h,temp);   //将两个有序子数组合并操作
        }
    }

    static void merge(int[] nums,int l,int mid,int h,int[] temp){
        int i=l,j=mid+1,t=0;    //左序列指针,右序列指针，临时数组指针
        while(i<=mid&&j<=h){
            if(nums[i]>nums[j]){
                temp[t++] = nums[j++];
            }else{
                temp[t++] = nums[i++];
            }
        }

        while(i<=mid){  //将左边剩余元素填充进temp中
            temp[t++] = nums[i++];
        }

        while(j<=h){    //将右序列剩余元素填充进temp中
            temp[t++] = nums[j++];
        }

        t = 0;
        while(l<=h){     //将temp中的元素全部拷贝到原数组中
            nums[l++]=temp[t++];
        }
    }