数据结构基础-排序算法整理

welcome to my blog

0. 笔记

不具备稳定性的排序： 选择排序、快速排序、堆排序. 例子{2,2,1}经选择排序后变成{1,2,2}
具备稳定性的排序： 冒泡排序、插入排序、归并排序、一切桶排序思想下的排序
目前没有找到时间复杂度O(NlogN)，额外空间复杂度O(1)，又稳定的排序

常见的坑
1，归并排序的额外空间复杂度可以变成O(1)，但是非常难，不需要掌握，有兴 趣可以搜“归并排序 内部缓存法”
2，“原地归并排序”的帖子都是垃圾，会让归并排序的时间复杂度变成O(N^2)
3，快速排序可以做到稳定性问题，但是非常难，不需要掌握， 可以搜“01 stable sort”
4，所有的改进都不重要，因为目前没有找到时间复杂度O(N*logN)，额外空间复 杂度O(1)，又稳定的排序。
5，有一道题目，是奇数放在数组左边，偶数放在数组右边，还要求原始的相对 次序不变，碰到这个问题，可以怼面试官。

1. 排序分类

根据能否将待排序的全部数据放入内存, 将排序分成内部排序和外部排序, 常见的排序指的是内部排序

根据排序过程中依据的原则, 可将内部排序分成:
|-- 插入排序: 直接插入排序; 希尔排序
|-- 交换排序: 冒泡排序; 快速排序
|-- 选择排序: 简单选择排序; 堆排序
|-- 归并排序: 二路归并排序

《算法》讲排序的顺序
|-- 初级排序: 选择排序; 插入排序; 希尔排序
|-- 归并排序
|-- 快速排序
|-- 堆排序

2. 选择排序

选择排序
外循环: 安排第0个位置, 安排第1个位置,安排第2个位置,…,安排第N-2个位置
外循环: [0,0]有序 [0,1]有序 [0,2]有序,…, [0,N-2]有序
外循环表示从什么范围上选出最小值: [0,N-1], [1,N-1], [2,N-1],…, [N-2, N-1]
对于每个范围, 拿出第一个元素作为临时最小值, 对于剩下的元素
通过内循环分别与最小值作比较, 该更新最小值的时候就进行更新

内循环结束后交换元素: 最小值和当前外循环范围的第一个元素交换

public static void selectionSort(int[] arr) {
    if (arr == null || arr.length < 2)
        return;
    int N = arr.length;
    for (int i = 0; i < N-1; i++) {
        int minIndex = i;
        for (int j = i + 1; j < N; j++) {
            if (arr[j] < arr[minIndex])
                minIndex = j;
        }
        swap(arr, i, minIndex); //注意和i交换
    }
}

(这已经简单到了极点):
1)选择最小的元素; 2)交换
两个特点:
1)运行时间和输入无关: 一个有序的数组和乱序的数组的排序时间是一样的! 因为不管有序无序,每次都得扫描待排序的所有元素, 也就是当前扫描一遍数组并不能为下一遍扫描提供什么信息, 这是个缺点, 其他排序算法会更善于利用输入的初始状态
2)数据移动是最少的: 每次扫描完一遍数组交换一次, N个元素一共交换N-1次. 交换次数和数组的大小是线性关系, 下面提到的所有排序算法都不具备这个特点(大部分的增长数量级都是线性对数或是平方级别)

3. 插入排序

插入排序
(就是抓扑克牌的样子; 当数组中逆序对较少时, 插入排序很可能比其他算法都快)
* 外循环: 安排索引为i的元素, 将arr[i]放到合适的位置(不一定是最终的位置), 使得arr[i] >= arr[i-1]
* 外循环: [0,1]有序 [0,2]有序 [0,3]有序,…, [0,N-1]有序
* 当N-1个元素都放在合适的位置之后, 整个数组也就有序了
* 内循环: 将arr[i]放到合适的位置

public static void insertionSort(int[] arr){
    if(arr==null || arr.length<2)
        return;//不对数组做操作
    int N = arr.length;
    for(int i=1; i<N; i++){
        for(int j=i; j>0 && arr[j] < arr[j-1]; j--){
            swap(arr, j, j-1);
        }
    }
}

为了给要插入的元素腾出空间, 我们需要将其余的所有元素在插入之前都向右移动一位
和选择排序相同的地方: 当前索引左边的所有元素都是有序的,但它们的最终位置还不确定, 为了给更小的元素腾出空间, 它们可能还会被移动. 当索引达到数组的右端时,数组排序就完成了
和选择排序不同的地方: 插入排序所需的时间取决于输入中元素的初始顺序. 例如,对于一个很大的且其中的元素已经有序(或接近有序)的数组进行排序将会比对随机顺序的数组或是逆序数组进行排序快得多

改进的插入排序
//改进版的插入排序,数组访问次数减半
//不再交换元素,因为交换一次需要访问两次数组(三次?)
//将交换替换为移动: 把大的元素向右移动

public static void insertionSortWithoutxchanges(int[] arr){
    Stopwatch timer = new Stopwatch();
    if(arr==null || arr.length<2)
        return;
    int N = arr.length;
    for(int i=1; i<N; i++){
        int temp = arr[i];
        int j;
        for(j = i; j>0 && arr[j-1] > temp; j--){
            arr[j] = arr[j-1];//大的元素右移
        }
        arr[j] = temp;
    }
}

4. 希尔排序

希尔排序
改进的插入排序, 将数组分成h组, 目的是增大每个元素的移动距离, 从而减少移动元素的次数

public static void shellSort(int[] arr){
    if(arr==null || arr.length <2)
        return;
    int N = arr.length;
    int h = 1;
    while(h < N/3)
        h = 3*h + 1;
    while(h>=1){
        //将数组变成h有序
        for(int i=h; i<N; i++){//因为要和当前元素"之前h距离"的元素相比, 所以第一个元素从h开始, 其之前的元素是0
            for(int j=i; j>=h && arr[j] < arr[j-h]; j -= h){ //子数组进行排序,h个子数组依次实现:前2两个元素有序, 前3个元素有序,..., 前h个元素有序
                swap(arr, j, j-h);
            }
        }
        h = h/3; //减小增量
    }
}

5. 冒泡排序

冒泡排序
*外循环:[N-1,N-1]有序, [N-2,N-1]有序, [N-3,N-1]有序,…,[2,N-1]有序, [1,N-1]有序
*外循环:将arr[i]放到正确的位置上
*内循环:将内循环范围中的最大值放到待排序元素的最后

public static void bubbleSort(int[] arr){
    if(arr==null || arr.length<2)
        return;
    int N = arr.length;
    //外循环:安排i
    for(int i=N-1; i>0; i--){
        for(int j=0; j<i; j++){
            if(arr[j] > arr[j+1])
                swap(arr, j, j+1);
        }
    }
}

6. 归并排序

归并排序
细节
|-- 如果不判断数组arr.length==0的情况,会导致栈溢出
|-- 注意辅助数组的长度
|-- 注意while的循环条件
|-- 归并过程可以浓缩成一句话 aux[i++] = arr[p1]<arr[p2] ? arr[p1++]:arr[p2++];
|-- 注意aux==>arr过程中,arr的起始索引

public static void mergeSort(int[] arr){
    if(arr==null || arr.length < 2) return; //细节:arr.length==0时如果不加判断, 会导致栈溢出! 一直递归调用left=0, right=-1, mid=-1的情况
    mergeSort(arr, 0, arr.length-1);
}
public static void mergeSort(int[] arr, int left, int right){
    //base case
    if(left == right) return;
    //
    int mid = left + ((right-left)>>1);
    mergeSort(arr, left, mid);
    mergeSort(arr, mid+1, right);
    merge(arr,left,mid, right);
}
public static void merge(int[] arr, int left, int mid, int right){
    int[] aux = new int[right-left+1]; //细节: 辅助数组的长度, 别错用成原始数组的长度
    int i=0, p1=left, p2=mid+1;
    while(p1!=mid+1 && p2!=right+1){  //也可以用while(p1<=mid && p2<=right)
        //细节:下面这四行可以浓缩成一行; aux[i++] = arr[p1]<arr[p2]? arr[p1++]:arr[p2++];
        if(arr[p1] < arr[p2])
            aux[i++] = arr[p1++];
        else
            aux[i++] = arr[p2++];
    }
    while(p1!=mid+1)//也可以写成while(p1<=mid)
        aux[i++] = arr[p1++];
    while(p2!=right+1)//也可以写成while(p2<=right)
        aux[i++] = arr[p2++];
    for(int k=0; k<aux.length; k++) //细节: 辅助数组的长度, 别错用成原始数组的长度
        arr[left++] = aux[k]; //细节: 原始数组索引从什么地方开始;  也可以写成arr[left+k] = aux[k];
}

7. 使用了归并排序思想的题:小和问题

小和问题
在一个数组中，每一个数左边比当前数小的数累加起来，叫做这个数组的小和。求一个数组 的小和。
例子:[1,3,4,2,5] 1左边比1小的数，没有; 3左边比3小的数，1; 4左边比4小的数，1、3; 2左边比2小的数，1; 5左边比5小的数，1、3、4、2; 所以小和为1+1+3+1+1+3+4+2=16

思路: 对数组进行归并排序, 归并过程涉及小和的产生, 所以修改merge函数即可
递归函数核心逻辑: 左半部分产生的小和 + 右半部分产生的小和 + 左右两部分合并产生的小和
注意:小和只会在左半部分某个元素小于右半部分某个元素时产生(题目要求就是左<右时产生小和). 某两部分归并后将小和返回给上一层函数, 合并的范围在上一层函数中作为左半部分或者右半部分. 所以小和的计算不会重复

public static int mergeSortForSmallSum(int[] arr){
    if(arr==null || arr.length < 2) return -1;
    int res = mergeSort(arr, 0, arr.length-1);
    return res;
}

public static int mergeSort(int[] arr, int left, int right){
    if(left == right ) return 0;
    int mid = left + ((right - left) >> 1);
    int res = 0;
    //核心逻辑:左子树产生的小和, 右子树产生的小和, 左右子树合并过程中产生的小和
    res = mergeSort(arr, left, mid) + mergeSort(arr, mid+1, right) + merge(arr,left,mid,right);
    return res;
}

public static int merge(int[] arr, int left, int mid, int right){
    int[] help = new int[right - left + 1];
    int res = 0;
    int i=0, p1=left, p2=mid+1;
    while(p1<=mid && p2<=right){
        res += arr[p1] < arr[p2] ? (right-p2+1)*arr[p1]:0; //arr[p1]<arr[p2]的话,arr[p1]比所有的arr[p2...]都小
        help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
    }
    while(p1<=mid)
        help[i++] = arr[p1++];
    while(p2<=right)
        help[i++] = arr[p2++];

    for(int k=0; k<help.length; k++)
        arr[left++] = help[k];
    return res;
}

8. 使用了归并排序思想的题:逆序对问题

逆序对问题
在一个数组中，左边的数如果比右边的数大，则这两个数构成一个逆序对，请打印所有逆序对

思路:将归并排序改成递减的形式, 这样左边就大于右边了. 用一个容器存储逆序对, 归并过程及左涉右两部分数比大小, 所以修改merge函数即可
逆序对的产生条件:左>右
递归函数核心逻辑: 左半部分产生的逆序对 + 右半部分产生的逆序对 + 左右两部分合并时产生的逆序对

public class MergeSort_ReversePair {
    public static void mergeSortForReversePair(int[] arr){
        if(arr==null || arr.length<2) return;
        String res = mergeSort(arr, 0, arr.length-1);
        System.out.println(res);
    }
    public static String mergeSort(int[]arr, int left, int right){
        //base case
        if(left == right ) return "";
        //
        int mid = left + ((right-left)>>1);
        String res = "";
        res += mergeSort(arr, left, mid); // left half
        res += mergeSort(arr, mid+1, right); // right half
        res += merge(arr, left, mid, right); // merge process
        return res;
    }
    public static String merge(int[] arr, int left, int mid, int right){
        // helpful arr: right - left + 1
        int[] help = new int[right - left + 1];
        // index for help arr;  double pointer
        int i=0, p1=left, p2=mid+1;
        // return value
        String res = "";
        // reverse order
        while(p1<=mid && p2<=right){
            if(arr[p1] > arr[p2]){
                int temp = p2;
                while(temp<=right)
                    res += "("+arr[p1]+" "+arr[temp++]+") ";
                help[i++] = arr[p1++];
            }
            else{
                help[i++] = arr[p2++];
            }
        }
        //left elements (开始漏写了下面这两个while)
        while(p1<=mid)
            help[i++] = arr[p1++];
        while(p2<=right)
            help[i++] = arr[p2++];
        // help ==> arr
        for(int k=0; k<help.length; k++)
            arr[left++] = help[k];
        return res;
    }

9. 堆排序

堆排序

• 堆排序: 务必牢牢掌握两个基本操作: 1)上浮的heapInsert操作 2)下沉的heapify操作
• 堆排序分为两个过程
• 建堆:
  从左到右使用heapInsert建堆,时间复杂度是O(NlogN);
  从右到左使用heapify建堆,时间复杂度是O(N);
  要保证遍历过的元素们都是大根堆: 所以从左到右建堆只能用上浮heapInsert; 从右到左建堆只能用下沉heapify
  建堆后只能保证父节点的值大于其子节点的值, 不能保证整个数组有序
• 排序:取出一个最大值并重新调整堆:exch(0,N-1),heapify, 时间复杂度是O(logN); 排序整体的时间复杂度是O(NlogN)
• 综合考虑建堆和排序两个过程, 总的时间复杂度是O(NlogN), 空间复杂度是O(1)

    public static void heapSort(int[] arr){
        if(arr==null||arr.length<2)return;
        //建堆
        int size = arr.length;
        
        //从左到右上浮建堆,O(NlogN)
//        for(int i=0; i<size; i++)
//            heapInsert(arr,i);

        //从右到左下沉建堆,O(N), 推荐使用这种方式
        for(int i=size-2; i>=0; i--)
            heapify(arr,i,size);
        //排序
        while(size>0){
            swap(arr,0,size-1);
            //下沉
            heapify(arr, 0, --size);
        }
    }
    //上浮
    public static void heapInsert(int[] arr, int index){
        // 跳出循环条件: 当前节点比父节点小; index==0
        while(arr[index] > arr[(index-1)/2]){
            swap(arr, index, (index-1)/2);
            index = (index-1)/2;
        }
    }
    //下沉
    //注意:堆的大小单独用一个变量size表示, 而不是用arr.length
    //注意:下沉过程中至少有两个越界判断
    public static void heapify(int[] arr, int index, int size){
        int left = 2*index+1; //左孩子索引
        // 循环时: 左孩子索引不越界
        while (left < size) {
            //找出两个孩子节点中值更大的孩子节点的索引
            //只要left或者left+1小于size,就能保证一定存在相应的左右孩子
            int largest = left + 1 < size && arr[left+1] > arr[left] ? left+1: left;
            //找出孩子节点和父节点中的最大值对应的索引
            largest = arr[index] > arr[largest] ? index : largest;
            //父节点最大的话就不用交换了, 跳出循环即可
            if(largest == index)
                break;
            //here,  更大的孩子节点比父节点更大
            swap(arr, index, largest);
            //下沉
            index = largest;
            left = 2*index+1;
        }
    }

10. 堆排序扩展题目

已知一个几乎有序的数组，几乎有序是指，如果把数组排好顺序的话，每个元素移动的距离可以不超过k，并且k相对于数组来说比较小。请选择一个合适的排序算法针对这个数据进行排序。

    public static void shellSort(int[] arr){
        if(arr==null || arr.length <2)
            return;
        int N = arr.length;
        int h = 1;
        while(h < N/3)
            h = 3*h + 1;
        while(h>=1){
            //将数组变成h有序
            for(int i=h; i<N; i++){//因为要和当前元素"之前h距离"的元素相比, 所以第一个元素从h开始, 其之前的元素是0
                for(int j=i; j>=h && arr[j] < arr[j-h]; j -= h){ //子数组进行排序,h个子数组依次实现:前2两个元素有序, 前3个元素有序,..., 前h个元素有序
                    swap(arr, j, j-h);
                }
            }
            h = h/3; //减小增量
        }
    }

11. 荷兰国旗问题(掌握partition)

当前值 < 划分值: 换,扩,跳
当前值 > 划分值: 换,扩
当前值==划分值: 跳

public static void partition(int[] arr, int left, int right, int v){
    int small = left - 1; //小于区域初始值; 往右扩
    int big = right + 1; //大于区域初始值; 往左扩
    //循环结束时: 小于区的边界和大于区的边界重合
    while(left < big){
        if(arr[left] == v)          //当前数等于划分值
            left++;                 //当前数跳下一个
        else if(arr[left] < v){            //当前数小于划分值
            swap(arr, left, small+1);    //当前数和小于区的下一个数交换
            small++;                       //小于区扩
            left++;                       //当前数跳下一个
        }
        else{                         //当前数大于划分值
            swap(arr, left, big-1);   //当前数与大于区的前一个数交换
            big--;                    //大于区扩
        }
    }
}
public static void partitionConsice(int[] arr, int left, int right, int v){
    int small = left - 1;
    int big = right + 1;
    while(left < big){
        if(arr[left] == v)
            left++;
        else if(arr[left] < v)
            swap(arr, left++, ++small);
        else
            swap(arr, left, --big);
    }
}

12. 快速排序

快速排序
1)将数组分成小于区,等于区,大于区
2)将数组分成小于等于区, 大于区
采用2)的划分方式, 一次partition只能安排好一个元素
采用1)的划分方式,可能安排好多个相同的元素, 比1)稍稍好一点
时间复杂度: 安排一个元素用O(logN), 所以总体的时间复杂度为O(NlogN)
空间复杂度: O(1)

public static void quickSort(int[] arr){
    if(arr==null || arr.length<2) return;
    quickSort(arr, 0, arr.length-1);
}

public static void quickSort(int[] arr, int left, int right){
    if(left < right){
        int[] equal = partition(arr, left, right);
        quickSort(arr,left, equal[0]-1);
        quickSort(arr,equal[1]+1, right);
    }
}
public static int[] partition(int[] arr, int left, int right){
    int small = left - 1; //小于区域
    int big = right; //大于区域
    int v = left + (int)((right - left + 1)*Math.random()); //开始的时候我又错用成arr.length了!!!  后来没有加left!! 蠢哭了
    swap(arr, v,  right);//随机选择一个数作为划分值
    while(left<big){
        if(arr[left]<arr[right])
            swap(arr, left++, ++small);
        else if(arr[left] > arr[right])
            swap(arr, left, --big);
        else
            left++;
    }
    //将划分值和大于区域的边界值交换
    swap(arr, right, big);
    return new int[]{small+1,big};
}

错误的递归终止条件案例, 看注释

public static void quickSort_bad_basecase(int[] arr, int left, int right){
    //base case
    if(left == right)
        return;
    //{21, 11, 23, 6, 21, 2} 2为划分值时, partition返回{0,0},  会出现quickSort(arr,left, -1)的情况,但是 base case:if(left == right) 没有针对这个情况处理
    // 23为划分值时, partition返回{5,5},会出现quickSort(arr,6, right)的情况, 但是 base case:if(left == right) 没有针对这个情况处理
    int[] equal = partition(arr,left, right);
    quickSort(arr, left, equal[0]-1);
    quickSort(arr, equal[1]+1, right);
}

13. 桶排序

桶排序思想下的排序
1）计数排序 2）基数排序
分析：
1)桶排序思想下的排序都是不基于比较的排序
2)时间复杂度为O(N)，额外空间负载度O(M)
3)应用范围有限，需要样本的数据状况满足桶的划分

14. 桶排序之–计数排序

桶排序–计数排序

public static void countSort(int[] arr){
    if(arr==null || arr.length<2)
        return;
    int max = Integer.MIN_VALUE;
    //找出数组中的最大值,用来确定桶的大小
    for(int i=0; i<arr.length; i++)
        max = Math.max(max, arr[i]);
    //建桶
    int[] bucket = new int[max+1];
    //记录每个数出现的次数
    for(int i=0; i<arr.length; i++)
        bucket[arr[i]]++;
    //排序阶段; 从桶中倒出来
    int i = 0;
    for(int j=0; j<bucket.length; j++)
        while(bucket[j]-- > 0)
            arr[i++] = j;
}

15. 桶排序之–基数排序

桶排序–基数排序

public static void radixSort(int[] arr){
    if(arr==null || arr.length < 2)
        return;
    radixSort(arr, 0, arr.length-1, maxbits(arr));
}

//不用left和right也行吧... 感觉没用上left和right
public static void radixSort(int[] arr, int left, int right, int digit){
    final int radix = 10; //默认是十进制数
    int i = 0, j = 0;

    //创建桶
    int[] bucket = new int[right - left + 1];
    // 有几位数就需要循环几次
    for(int d = 1; d <= digit; d++){
        //每一位都有0~9这十种可能
        int[] count = new int[radix];
        //统计第d位各个数字出现的次数
        for(i=left; i<=right; i++){
            j = getDigit(arr[i], d); //开始把i写错了
            count[j]++;
        }
        //更新count, 使count[x]表示0~x有几个数
        //一定是从i=1开始
        for(i=1; i<radix; i++)
            //更新后的count[i]表示[0,1]有几个数. 比如count[6] = 7,说明第d位中[0,6]一共有7个, 可以把当前这个6放到bucket中的第5位(索引从0开始)
            count[i] = count[i] + count[i-1];
        //入桶; 桶中装的是原数组中具体的数
        //由于count的更新方式, 所以入桶过程需要从后向前进行
        for(i = right; i>= left; i--){
            j = getDigit(arr[i], d);
            // 把当前这个j放到bucket中的第count[j] - 1位(索引从0开始)
            bucket[count[j] - 1] = arr[i];
            count[j]--;
        }
        //排序过程
        //出桶
        for(i=left,j=0; i<=right; i++, j++)
            arr[i] = bucket[j];
    }
}

//获取数组中最大的元素的位数
public static int maxbits(int[] arr){
    int max = Integer.MIN_VALUE;
    for(int i=0; i<arr.length; i++)
        max = Math.max(max, arr[i]);
    int res = 0;
    while(max != 0){
        res++;
        max /= 10;
    }
    return res;
}
//获取某个数的第d位
public static int getDigit(int x, int d){
    return (x/(int)(Math.pow(10,d-1)))%10;
}