[数据结构与算法]【浅学Java数据结构】排序大全

1. 排序的概念

1. 排序：所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。
2. 稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。
3. 内部排序：数据元素全部放在内存中的排序。
4. 外部排序：数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序。

2. 总览常见的排序算法

3. 直接插入排序

当插入第i(i>=1)个元素时，前面的array[0],array[1],…,array[i-1]已经排好序，此时用array[i]的排序码与array[i-1],array[i-2],…的排序码顺序进行比较，找到插入位置即将array[i]插入，原来位置上的元素顺序后移

public static void insertSort(int []arr){
        for(int i=1;i<arr.length;i++){
            for(int j=i;j>0;j--){
                if(arr[j]<arr[j-1]){
                    int tmp = arr[j];
                    arr[j] = arr[j-1];
                    arr[j-1]=tmp;
                }else{
                    break;
                }
            }
        }
    }

4. 希尔排序

希尔排序法又称缩小增量法。希尔排序法的基本思想是：先选定一个整数，把待排序文件中所有记录分成个组，所有距离为的记录分在同一组内，并对每一组内的记录进行排序。然后，取，重复上述分组和排序的工作。当到达=1时，所有记录在统一组内排好序。

public  static void shellSort(int []arr){
        int gap = arr.length/2;//设置增量初始值
        while(gap>0){
            for(int i=gap;i<arr.length;i++){
                for(int j=i;j>gap-1;j-=gap){
                    if(arr[j]<arr[j-gap]){
                        int tmp =arr[j];
                        arr[j]=arr[j-gap];
                        arr[j-gap]=tmp;
                    }else {
                        break;
                    }
                }
            }
            gap=gap/2;
        }
    }

希尔排序的特性总结：

1. 希尔排序是对直接插入排序的优化。
2. 当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的对比。
3. 希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，因此在好些树中给出的希尔排序的时间复杂度都不固定。

5. 直接选择排序

public static void selectSort(int []arr){
        for(int i=0;i<arr.length;i++){
            int maxi=0;
            int j=0;
            for(j=1;j<arr.length-i;j++){
                if(arr[j]>arr[maxi]){
                    maxi=j;
                }
            }
            int tmp = arr[maxi];
            arr[maxi]=arr[j-1];
            arr[j-1]=tmp;
        }
    }

6. 堆排序

思路：

1. 升序：建大堆，然后将堆顶元素与堆尾元素交换，然后向下调整。
2. 降序：建小堆，然后将堆顶元素与堆尾元素交换，然后向下调整。
3. 注意：堆顶元素与堆尾元素交换完后，堆尾的下标 -1 ,因为此时堆尾即是最值，已经到了排序的目标位置，不需要再动。

public static void shiftDown(int []arr,int root,int len){
        int parent = root;
        int child = parent*2+1;//左孩子
        while(child<len){
            if(child+1<len&&arr[child]<arr[child+1]){
                child=child+1;
            }
            if(arr[child]>arr[parent]){
                int tmp=arr[child];
                arr[child]=arr[parent];
                arr[parent]=tmp;
            }else{
                break;
            }
            parent = child;
            child = parent*2+1;
        }
    }
    public static void heapSort(int []arr){
        int len=arr.length;
        for(int i=(len-1)/2;i>=0;i--){
            shiftDown(arr,i,len);
        }
        int end = len-1;
        while(end>=0){
            int top=arr[0];
            arr[0]=arr[end];
            arr[end]=top;
            end--;//堆尾的下标 -1
            shiftDown(arr,0,end);
        }
    }

7. 冒泡排序

public static void bubbleSort(int []arr){
        for(int i=0;i<arr.length-1;i++){
            boolean flag = false;//设置标志，如果某趟没有进行元素的交换，就说明数组已经有序
            for(int j=1;j<arr.length-i;j++){
                if(arr[j]<arr[j-1]){
                    int tmp=arr[j];
                    arr[j]=arr[j-1];
                    arr[j-1]=tmp;
                    flag = true;
                }
            }
            if(flag==false){
                break;
            }
        }
    }

8. 快速排序(递归)

public class Test {
    // Hoare版————以左边为key，一定要从右边开始找，不然循环结束后的那一步交换就会出问题
    public static int partion1(int []arr,int left,int right){
        int key=arr[left];
        int start = left;
        int end = right;
        while(start<end){
            while(start<end&&arr[end]>=key){
                end--;
            }
            while(start<end&&arr[start]<=key){
                start++;
            }
            int tmp = arr[end];
            arr[end]=arr[start];
            arr[start]=tmp;
        }
        arr[left]=arr[end];
        arr[end]=key;
        return end;
    }

    //挖坑法
    public static int partion2(int []arr,int left,int right){
        int pivot=arr[left];
        int start=left;
        int end=right;
        while(start<end){
            while(start<end&&arr[end]>=pivot){
                end--;
            }
            arr[start]=arr[end];
            while(start<end&&arr[start]<=pivot){
                start++;
            }
            arr[end]=arr[start];
        }
        arr[end]=pivot;
        return end;
    }
    //前后指针法————画图理解下代码
    public static void swap(int []arr,int i,int j){
        int tmp=arr[i];
        arr[i]=arr[j];
        arr[j]=tmp;
    }
    public static int partion3(int []arr,int left,int right){
        int prev=left;
        int cur=left+1;
        while(cur<=right){
            if(arr[cur]<arr[left]){
                prev++;
                if(cur!=prev){
                    swap(arr,cur,prev);
                }
            }
            cur++;
        }
        swap(arr,prev,left);
        return prev;
    }
    public static void insertSortRange(int[] array,int low,int end) {
        for(int i = low+1;i <= end;i++) {
            int tmp = array[i];
            int j = i-1;
            for (; j >= low ; j--) {
                if(array[j] > tmp) {
                    array[j+1] = array[j];
                }else {
                    break;
                }
            }
            array[j+1] = tmp;
        }
    }
    private static int medileOfThreeIndex(int []arr,int left,int right){
        int mid=left+(right-left)>>>1;
        if(arr[left]<arr[right]){
            if(arr[mid]<arr[left]){
                return left;
            }else if(arr[mid]>arr[right]){
                return right;
            }else{
                return mid;
            }
        }else{
            if(arr[mid]<arr[right]){
                return right;
            }else if(arr[mid]>arr[left]){
                return left;
            }else{
                return mid;
            }
        }
    }
    public static void quickSort(int []arr,int left,int right){
        if(left>=right){
            return;
        }
        if(right-left+1<=450000){//可以优化区间内的比较速度
            //当在某个区间的时候，进行插入排序，这里就先不写了
            insertSortRange(arr,left,right);
            return;
        }
        //三数取中用来解决递归深度太深的问题
        int index=medileOfThreeIndex(arr,left,right);
        swap(arr,left,index);
        int div = partion2(arr,left,right);
        quickSort(arr,left,div-1);
        quickSort(arr,div+1,right);
    }

    public static void quickSortTest(int [] arr){
        arr = Arrays.copyOf(arr,arr.length);
        long startTime = System.currentTimeMillis();
        quickSort(arr,0,arr.length-1);
        long endTime = System.currentTimeMillis();
        System.out.println("快速排序："+(endTime-startTime));
        //System.out.println(Arrays.toString(arr));
    }
    public static void main(String[] args) {
        int[] arr = new int[50_0000];
        Random random = new Random();
        //本身 并没有根本上解决 有序情况下  递归深度太深的情况---》根本上解决问题-》尽量让每次划分更均匀
        for (int i = 0; i < arr.length; i++) {
            //arr[i] = i;
            //arr[i] = random.nextInt(50_0000);
        }
        //int []arr = {0,1,2,3,4,5,6,7,8,9};
        quickSortTest(arr);
    }
}

总结：

1. 在用 Hoare版找基准时，在以左边为key，一定要从右边开始找，不然循环结束后的那一步就会出问题
2. 运用三数取中可以减少递归的深度。
3. 设置区间运用插入排序，在一定程度上也能减少递归的深度，但是在设置区间的时候，一定要把握好区间的大小，过于大的区间使用插入排序就会使排序的时间复杂度升高。
4. 快排的时间复杂度虽然和堆排序、希尔排序一样，但快排的速度在大多数情况下时优于堆排序和希尔排序
5. 在Hoare、挖坑法、前后指针法这些当中，更推荐使用挖坑法，他是Hoare的升级，理解起来也没有前后指针法那么难。

9. 快速排序(非递归)

思路：非递归的实现一定是建立在一次划分的基础之上，第一次划分之后，将划分后的结果处理之后入栈，然后就根据具体的操作模拟进行入栈出栈就行。

注意：下面的代码中piovt>left+1就是用来判断 piovt 左边是否有超过一个元素，如果超过一个元素的话，就得再进行划分；如果没有超过一个元素，那么这个区间就是有序的，无需再进行划分，即这个区间无需再进行入栈操作。

public static void quickSortNor(int []arr){
        Stack<Integer> stack = new Stack<>();
        int left=0;
        int right =arr.length-1;
        int piovt = partion2(arr,left,right);
        if(piovt>left+1){
            stack.push(left);
            stack.push(piovt-1);
        }
        if(piovt<right-1){
            stack.push(piovt+1);
            stack.push(right);
        }
        while (!stack.empty()){
            right = stack.pop();
            left = stack.pop();
            piovt = partion2(arr,left,right);

            if(piovt>left+1){
                stack.push(left);
                stack.push(piovt-1);
            }
            if(piovt<right-1){
                stack.push(piovt+1);
                stack.push(right);
            }
        }
    }

10. 归并排序(递归)

思路：先使每个子序列有序，再使子序列段间有序

//合并函数
private static void merge(int []arr,int left,int right,int mid){
        int s1=left;
        int e1=mid;
        int s2=mid+1;
        int e2=right;
        int k=0;
        int []newArr=new int[right-left+1];
        while(s1<=e1&&s2<=e2){
            if(arr[s1]<=arr[s2]){
                newArr[k++]=arr[s1++];
            }else{
                newArr[k++]=arr[s2++];
            }
        }
        while(s1<=e1){
            newArr[k++]=arr[s1++];
        }
        while(s2<=e2){
            newArr[k++]=arr[s2++];
        }
        //将临时数组的值拷贝会原来的数组
        for(int i=0;i<newArr.length;i++){
            arr[left+i]=newArr[i];
        }
    }
    public static void mergeSort(int []arr,int left,int right){
        if(left>=right){//区间内少于两个元素
            return;
        }
        int mid = left+((right-left)>>>1);//找到区间的中点，然后将区间划分
        mergeSort(arr,left,mid);
        mergeSort(arr,mid+1,right);
        merge(arr,left,right,mid);将区间合并为一个有序的区间
    }

11. 归并排序(非递归)

思路：先2个一组进行合并，再4个一组进行合并…
注意：再划分区间的时候，mid和right的值可能超过数组长度，因此要进行修正

private static void merge(int []arr,int left,int right,int mid){
        int s1=left;
        int e1=mid;
        int s2=mid+1;
        int e2=right;
        int k=0;
        int []newArr=new int[right-left+1];
        while(s1<=e1&&s2<=e2){
            if(arr[s1]<=arr[s2]){
                newArr[k++]=arr[s1++];
            }else{
                newArr[k++]=arr[s2++];
            }
        }
        while(s1<=e1){
            newArr[k++]=arr[s1++];
        }
        while(s2<=e2){
            newArr[k++]=arr[s2++];
        }
        for(int i=0;i<newArr.length;i++){
            arr[left+i]=newArr[i];
        }
    }
public static void merageSortNor(int []arr){
        int gap=1;
        while(gap<arr.length){
            for(int i=0;i<arr.length;i+=2*gap){
                int left=i;
                int mid=left+gap-1;
                //修正mid
                if(mid>=arr.length){
                    mid=arr.length-1;
                }
                //修正right
                int right=mid+gap;
                if(right>=arr.length){
                    right=arr.length-1;
                }
                merge(arr,left,right,mid);
            }
            gap*=2;
        }

海量数据的排序问题

外部排序：排序过程需要在磁盘等外部存储进行的排序
前提：内存只有 1G，需要排序的数据有 100G
因为内存中因为无法把所有数据全部放下，所以需要外部排序，而归并排序是最常用的外部排序

1. 先把文件切分成 200 份，每个 512 M
2. 分别对 512 M 排序，因为内存已经可以放的下，所以任意排序方式都可以
3. 进行 2路归并，同时对 200 份有序文件做归并过程，最终结果就有序了

12. 排序算法复杂度及稳定性分析：

最好情况下的时间

平均时间

最坏情况下的时间

空间复杂度

稳定性

13. 其他非基于比较的算法（了解思想即可）

上面的这些排序算法都是基于比较的，下面介绍几种不基于比较的算法。

13.1 计数排序

思想：计数排序又称为鸽巢原理，是对哈希直接定址法的变形应用。 操作步骤：

1. 统计相同元素出现次数
2. 根据统计的结果将序列回收到原来的序列中

public static void countSort(int arr[]){
        //先找出数组中的最大值和最小值
        int max=arr[0];
        int min=arr[0];
        for(int i=1;i<arr.length;i++){
            if(arr[i]>max){
                max=arr[i];
            }
            if(arr[i]<min){
                min=arr[i];
            }
        }
        //根据最大值和最小值，创建一个临时数组
        int [] count = new int[max-min+1];
        //将arr中的数据统计入count中，值为 i 的数，就存在count数组中下标为 i 的位置
        for(int i=0;i<arr.length;i++){
            count[arr[i]-min]++;
        }
        //根据数组count，将数据有序的还原到arr数组当中
        int index=0;
        for(int i=0;i<count.length;i++){
            while(count[i]>0){
                arr[index]=i+min;
                count[i]--;
                index++;
            }
        }
    }

时间复杂度：O（MAX（N,范围）)
空间复杂度：O（范围）
稳定性：稳定（以下面这种方式）

13.2基数排序

链接: 基数排序

13.3 桶排序

链接: 桶排序