dashan/learning_record_doc

Fork 0

dashan 3a91dd5fd9 doc 新增数据结构分析课常考知识点文档

2023-10-09 23:12:04 +08:00

24 KiB

Raw Permalink Blame History

本文由简悦 SimpRead 转码，原文地址 zhuanlan.zhihu.com

概念：

所谓排序，就是把一堆杂乱的数据，排成升序或降序 (递增 / 增减)。
排序稳定性： 假设一组数据 [1,2,9,5,5,6,8]，进行升序排序后，两个 5 的相应位置不发生改变，即称为稳定的排序，否则就是不稳定排序。

内部排序： 数据元素全部放在内存中进行排序。
外部排序： 即将待排序的记录存储在外存中，排序时再把数据一部分一部分地调入内存进行排序，在排序过程中需要多次进行内存和外存之间地交换。

插入排序

思路：

默认为第一个元素自己是有序的，从第二个元素开始。
取出第二个元素 tmp，往前进行比较。
若该元素比 tmp 大，则将该元素往后移一位，直到找到比 tmp 小的。
找到比 tmp 小于等于的元素后，tmp 插入到该元素的下一位。
循环 2~4 步骤。

步骤具体实现：

定义下标 i ，遍历数组。默认 i 下标已经是有序的，把 i 下标元素存入 tmp。
定义 j，j 从 i-1 的位置，开始向前遍历，遇到比 tmp 大的元素，就把此时 j 下标的元素往后移一位，直到下标等于或小于 0 停止。
j 下标元素小于 tmp，则把 tmp 元素插入该 j 下标的下一个位置。

时间复杂度： O(N^2);

空间复杂度： O(1);

稳定性： 稳定；

具体代码实现：

public static void insertSort(int[] array){
    //1.遍历数组
    for (int i = 0; i < array.length; i++) {
        int tmp = array[i];
        //2.往前遍历，进行插入
        int j = i-1;
        for ( ;j >=0 ; j--) {
            if(array[j] > tmp){
                int exchange  = array[j];
                array[j+1] = array[j];
                array[j] = exchange;
            }else{
                //没有比tmp小的，退出循环
                break;
            }
        }
        //3.此时j下标元素比tmp小，tmp插入j下标的下一个位置
        array[j+1] = tmp;
    }
}

结论：

当数据趋于有序时，排序时间越快，最好的情况下时间复杂度为 O(N);
当把循环中 array[j] > tmp的大于号改为大于等于，此时就不是稳定的排序了。

希尔排序

思路：

先将待排序列进行预排序，使得待排序列接近有序，此时进行插入排序。
把待排序的数据分为多个组，每组间隔为 5 或 3…。
若此组的第一个元素大于最后一个元素，将此组第一个元素和最后一个元素交换。
重复上述操作，直到每组间隔只有 1 时，所有数据都在统一组内进行排好序。

步骤具体实现：

定义 gap = 数组长度 \ 2。
把待排序列分为 gap 个组，每个组的第一个元素和最后一个元素进行比较交换。
重复上述操作
当 gap 为 1 时，进行插入排序。

时间复杂度： O(N^1.3);

空间复杂度： O(1);

稳定性： 不稳定。

具体代码实现：

public static void shell(int[] array){
    int gap = array.length;
    while(gap > 1){
        gap /= 2;//分组
        //1.每组头和尾进行比较交换
        for (int i = 0; i < array.length; i++) {
            int tmp = array[i];
            //2.往前遍历，一次步长为gap
            int j = i-gap;
            for ( ;j >=0 ; j-=gap) {
                if(array[j] > tmp){
                    int exchange  = array[j];
                    array[j+gap] = array[j];
                    array[j] = exchange;
                }else{
                    break;
                }
            }
            array[j+gap] = tmp;
        }

    }
}

结论：

希尔排序是对插入排序的优化。
当 gap>1 时，都是预排序，目的是为了让数组更趋于有序，当 gap==1 时，数组已经接近有序，这样进行插入排序就会很快。
希尔排序的时间复杂度不容易计算，因为 gap 的取值方法很多，导致很难计算，因此我们按照 Knuth 提出的时间复杂度 O(N^1.3) 来算。

选择排序

思路：

每次从待排序列中选择一个最小值 (最大), 存放在序列的起始位置，直到全部待排序的数据排完。

步骤具体实现：

定义i，假设待排序列i下标元素是最小值，用 min 记录当前i下标。
定义 j，从i下一个位置开始往后遍历，遇到小于array[min]时更新 min，min 指向每次遍历的最小值下标，直到遍历完一次数组。
一次遍历完后array[i]和 min 下标进行交换。
重复上述操作，直到待排序数据剩余 1 个元素。

时间复杂度： O(N^2);

空间复杂度: O(1);

稳定性： 不稳定；

具体代码实现：

public static void selectSort(int[] array){
    for (int i = 0; i < array.length; i++) {
        int min = i;
        for (int j = i+1; j < array.length; j++) {
            if(array[j] < array[min]){
                //更新min的值
                min = j;
            }
        }
        if(min != i){
            int tmp = array[i];
            array[i] = array[min];
            array[min] = tmp;
        }

    }
}

结论： 效率不是很好，实际中很少使用。

堆排序

注意：排升序需要建大根堆，排降序建小根堆。 此文章默认举例排升序。

思路 & 具体步骤实现：

首先得建立一个大根堆。
把根节点与最后一个节点交换，每一次交换，最后一个节点向前走一步。
进行堆向下调整。

时间复杂度： O(N*logN)；

空间复杂度： O(1);

稳定性： 不稳定；

具体代码实现：

public static void heapSort(int[] array){
    //0.创建大根堆
    createHeap(array);// 时间 O(N)
    int end = array.length-1;
    while (end > 0){
        //1.每次根和最后一个节点交换
        int tmp = array[0];
        array[0] = array[end];
        array[end] = tmp;
        //2.向下调整 
        shiftDown(array,0,end);
        //3.最后一个节点已经是有升序的了
        end--;
    }
}
private static void createHeap(int[] array){
    //(array.length-1-1)->减一个1是数组下标是从0开始的，
    //减两个1是二叉树的概念：已知孩子节点求父亲节点 ->(i-1)/2
    for (int parent = (array.length-1-1)/2; parent >=0 ; parent--) {
        //向下调整
        shiftDown(array,parent,array.length);
    }
}
private static void shiftDown(int[] array,int parent,int len){
    int child = (parent*2)+1;
    while(child < len){
        if(child+1 < len && array[child+1] > array[child]){
            child++;
        }
        if(array[child] > array[parent]){
            int tmp = array[child];
            array[child] = array[parent];
            array[parent] = tmp;
            //继续向下调整
            parent = child;
            child = (parent*2)+1;
        }else {
            break;
        }
    }
}

冒泡排序

思路： 根据序列中的两个记录键值比较结果来交换这两个记录在序列中的位置，交换排序的特点是：将键值较大的记录向序列的尾部移动，键值较小的向前部移动。

具体步骤实现：

定义i遍历数组，控制趟数，总体趟数比数组长度少 1；
每趟让一个较大值移动到尾部。
定义j每次从 0 下标进行两两比较交换。

时间复杂度： O(N^2)；

空间复杂度： O(1)；

稳定性： 稳定；

具体代码实现：此处冒泡排序代码作了优化。

public static void bubbleSort(int[] array){
    for (int i = 0; i < array.length-1; i++) {
        boolean  flag = false;//判断此趟排序有没有交换
        for (int j = 0; j < array.length-1-i; j++) {
            if (array[j] > array[j + 1]) {
                int tmp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = tmp;
                flag = true;
            }
        }
        //若flag一趟下来为false 说明数组已经有序
        if(flag == false){
            break;
        }
    }
}

快速排序

基本思想：任取待排序元素中的某元素作为基准值，将待排序集合分割为两子序，左子序中所有元素均小于 基准值，右子序均大于 基准值，然后左右子序重复该过程，直到所有元素都排列在相应位置上。

6.1 Hoare 版

思路：

取数组最左边或最右边为 key。
先从右边开始找到小于 key 值。
再从左边走找到大于 key 值，左右进行交换。
左右相遇后，相遇点为此次遍历的基准值
最后与 key 位置交换。

具体实现步骤：

定义 key，指向数组最左边的元素。
定义 left 从数组左边开始遍历；定义 right 从右边开始遍历。
一定要 right 先走，再走 left。
当 right 和 left 相遇后，与 key 交换，相遇点为基准值。
遍历以该基准值分割的两子序。
递归重复上述操作。

具体代码实现：

public static void quickSort(int[] array){
    quickHelp(array,0,array.length-1);
}

//具体实现排序调用函数
private static void quickHelp(int[] array,int start,int end){
    if (start >= end){
        return;
    }
    //1.找基准值
    int pivot = hoare(array,start,end);
    //2.左右子序重复该操作
    quickHelp(array,start,pivot-1);
    quickHelp(array,pivot+1,end);
}
private static int hoare(int[] array,int left ,int right){

    int index = left;//记录key下标
    int key = array[left];
    while(left < right){
        //1.先从右 找到比key小的值
        while(left < right && array[right] >= key){
            right--;
        }
        //2.再从左找到比key大的值
        while(left < right && array[left] <= key){
            left++;
        }
        //3.交换左右值
        int tmp = array[left];
        array[left]  = array[right];
        array[right] = tmp;
    }
    //4.相遇点和key下标交换
    int tmp = array[left];
    array[left]  = array[index];
    array[index] = tmp;
    return left;
}

代码优化：

此排序，递归下去就好像一颗二叉树，当排序的是有序时，就只有左子树或者只有右子树，此时排序的时间复杂度最高，所有：在找基准值先，尽量让左右子树划分平衡。当递归到一定层数是进行插入排序，因为越往下层遍历，这一层的递归次数越多，比如第一层递归 2 次，第二次递归 4 次…。

步骤：

设定一个边界值，达到边界值时进行插入排序。
保证每次划分均匀：（3 个数找中数）
如待排序：1 2 3 4 5 把 1 和 3 和 5 进行比较，找出中间值，把最左边值和中间值交换。

具体代码实现：

public static void quickSort(int[] array){
    quickHelp(array,0,array.length-1);
}

//具体实现排序调用函数
private static void quickHelp(int[] array,int start,int end){
    if (start >= end){
        return;
    }
    //对start - end 区间进行插入排序
    if(start <= 15){
        insertSortHelp(array,start,end);
    }
    //在找基准前尽量保证左右划分均匀
    int index = findMin(array,start,end);
    swap(array,start,index);

    //1.找基准值
    int pivot = hoare(array,start,end);
    //2.左右子序重复该操作
    quickHelp(array,start,pivot-1);
    quickHelp(array,pivot+1,end);
}
public static void insertSortHelp(int[] array,int left,int right){
    for (int i = left; i <= right; i++) {
        int tmp = array[i];
        int j = i-1;
        for ( ;j >=0 ; j--) {
            if(array[j] > tmp){
                swap(array,j,j+1);
            }else{
                break;
            }
        }
        array[j+1] = tmp;
    }
}
private static int findMin(int[] array,int left,int right){
    int midIndex = (left+right)/2;

    if(array[left] < array[right]){
        if(array[left] > array[midIndex]){
            return left;
        }else if(array[right] < array[midIndex]){
            return right;
        }else {
            return midIndex;
        }
    }else{//array[left] > array[right]
        if(array[left] < array[midIndex]){
            return left;
        }else if(array[right] > array[midIndex]){
            return right;
        }else {
            return midIndex;
        }
    }
}
private static int hoare(int[] array,int left ,int right){

    int index = left;//记录key下标
    int key = array[left];
    while(left < right){
        //1.先从右 找到比key小的值
        while(left < right && array[right] >= key){
            right--;
        }
        //2.再从左找到比key大的值
        while(left < right && array[left] <= key){
            left++;
        }
        //3.交换左右值
        swap(array,left,right);
    }
    //4.相遇点和key下标交换
    swap(array,left,index);
    return left;
}
private static void swap(int[] array,int i,int j) {
    int tmp = array[i];
    array[i] = array[j];
    array[j] = tmp;
}

6.2 挖坑法

思路：

大致思路根 Hoare 版本类似；

选最左边的元素存入 key，在此位置形成一个坑位；
先从右开始遍历和 key 比较，再从左遍历，进行左右交换。
左右相交后，把 key 的放入相交点位置。

具体实现步骤：

先将第一个元素存入临时变量 key，形成一个坑位。
定义 left 从数组左边开始走、right 从右边开始走。
先从右开始遍历找到比 key 小的元素，放入 left 的位置；
然后 left 找到比 key 大的元素，放入 right 的位置。
待 left 和 right 下标相遇后，把 key 的元素放入相交点。
重复上述操作。

具体代码实现【递归】：

public static void digSort(int[] array,int start ,int end){
    if(start >= end){
        return;
    }
    int left = start;
    int right = end;
    int key = array[left];
    while(left < right){
        //1.先从右开始 找到比key小的
        while (left < right && array[right] >= key){
            right--;
        }
        //2.把小值填入左边的坑位
        array[left] = array[right];

        //3.再从左开始 找到比key大的
        while (left < right && array[left] <= key){
            left++;
        }
        //4.把大值填入右边的坑位
        array[right] = array[left];
    }
    array[left] = key;
    //递归
    digSort(array,start,left-1);//遍历key左边
    digSort(array,left+1,end);//遍历key右边
}

6.3 前后指针法

了解即可，见得比较少，整体思路大体一样。

定义 key 存储数组起始元素，prev 指向数组开始位置；cur 指 prev 后一个位置。
当 cur 下标元素小于 key，prev 向后走，并且此时 prev 下标的元素不等于 cur 下标元素，则进行交换
否则 cur 一直往后走，当 cur 走完时，prev 下标和数组最左边左边下标交换。
递归重复上述操作。

public static void quick(int[] array,int start,int end){
    if(start >= end){
        return;
    }
    int pivot = partition(array,start,end);
    quick(array,start,pivot-1);
    quick(array,pivot+1,end);
}
private static int partition(int[] array, int left, int right) {
    int prev = left ;
    int cur = left+1;
    while (cur <= right) {
        if(array[cur] < array[left] && array[++prev] != array[left]) {
            swap(array,cur,prev);
        }
        cur++;
    }
    swap(array,prev,left);
    return prev;
}

6.4 快速排序非递归

思路：使用栈，模拟递归

先找到基准
判断基准左右是否存在两个元素及以上。
把以基准为界左边的数组最左边下标和最右边下标入栈
再基准右边的数组最左边下标和最右边下标入栈
弹出栈顶两个下标，对此下标区间再进行找基准【弹出顺序：先右后左】
重复上述操作。
快速排序非递归最重要的就是找基准。

具体代码实现：

public static void quickSort2(int[] array){
    Stack<Integer> stack = new Stack<>();
    int left = 0;
    int right = array.length-1;
    //找基准
    int pivot = finMid(array,left,right);//排序核心代码
    //1.判断基准左边有没有2个元素    1   2    3    4    5    9
    if(pivot > left+1){       //若基准：3    left:1    pivot < left+1
        //把最左边和最右边的下标入栈
        stack.push(left);
        stack.push(pivot-1);
    }
    //2.判断基准右边有没有2个元素
    if(pivot < right-1){
        //把最左边和最右边的下标入栈
        stack.push(pivot+1);
        stack.push(right);
    }
    //3.弹出2个元素，重复上述操作
    while(!stack.isEmpty()){
        //注意弹出顺序：先右和左
        right = stack.pop();
        left = stack.pop();
        pivot = partition(array,left,right);

        if(pivot > left+1){
            stack.push(left);
            stack.push(pivot-1);
        }
        if(pivot < right-1){
            stack.push(pivot+1);
            stack.push(right);
        }
    }
}
private static int finMid(int[] array,int left ,int right){

    int index = left;//记录key下标
    int key = array[left];
    while(left < right){
        //1.先从右 找到比key小的值
        while(left < right && array[right] >= key){
            right--;
        }
        //2.再从左找到比key大的值
        while(left < right && array[left] <= key){
            left++;
        }
        //3.交换左右值
        swap(array,left,right);
    }
    //4.相遇点和key下标交换
    swap(array,left,index);
    return left;
}

快速排序总结：

综合性能和使用场景比较好。
一般快速排序三种方法使用顺序：挖坑法 ->Hoare 法 -> 前后指针法

归并排序

核心思想：分而治之

即：将待排序列拆分，再合并成为有序序列。

先把序列逐层进行拆分：

当拆分到只有一个元素时，再从下往上逐层合并，首先对第一层序列号 1(元素 4)，和序列号 2(元素 5) 进行合并

创建一个大数组，长度为序列号 1 和序列号 2 长度之和，s1、s2 指针分别指向两个小序列号 (数组) 的第一个元素，ret 指向大数组的第一个元素。

比较 [s1]、[s2] 指向的元素，4<5，将 4 放入 ret 指向的空间，ret 往右走一步，s1 往右走一步。

此时序列号 1(数组) 已经没有元素，直接将序列号 2 的元素放入大数组中。

4.[8]和 [1]、[7] 和[2]、[6]和[3]，用同样方式进行合并。

以 [4,5] 为序列 1，[1,8]为序列 2，继续进行合并。

6.[4]和 [1] 比较，4>1，把 [1] 放入 ret 指向的空间，[s2]往右走一步。

重复上述操作，直到把 [4,5] 和[1,8]合并成【1,4,5,8】。

以 [2,7] 为序列 3，[3,6]为序列 4，用同样的方式合并成为新的序列【2,3,6,7】；

最后将 [1,4,5,8] 和[2,3,6,7]用同样的方式合并成新的序列

时间复杂度：O(N*logN) ： 归并排序算法每次将序列折半分组，共需要 logN 轮。

空间复杂度：O(N)： 归并排序算法排序过程中需要额外的一个序列去存储排序后的结果，所占空间是 N。

稳定性：稳定

具体代码实现：

public static void merge(int[] array,int start,int end){
    if(start >= end){
        return;
    }
    //1.分解
    int mid = (start+end)/2;//折半递归
    merge(array,start,mid);
    merge(array,mid+1,end);
    //2.合并 合并两个小数组为一个大数组
    mergeHelp(array,start,mid,end);
}
private static void mergeHelp(int[] array,int left,int mid,int right){
    //这里直接合并[4,5]和[1,8],因为[4]和[5]两个数组太小了，不好理解
    //第一个小数组下标范围
    int s1 = left;
    int e1 = mid;
    //第二个小数组下标范围
    int s2 = mid+1;
    int e2 = right;
    //合并的大数组
    int[] ret = new int[right-left+1];
    int k = 0;//ret下标
    while(s1 <= e1 && s2 <= e2){
        //进行比较
        if( array[s1] <= array[s2]){
            ret[k++] = array[s1++];
        } else{
            ret[k++] = array[s2++];
        }
    }
    //存放剩余的有序元素
    while(s1 <= e1){
        ret[k++] = array[s1++];
    }
    while(s2 <= e2){
        ret[k++] = array[s2++];
    }
    //把合并完的有序元素，放入原来的数组里->所有归并排序空间复杂度高
    for (int i = 0; i < k; i++) {
        //+left 因为每次合并ret存的元素对应的array下标在发生变化
        //若存入给ret的 5 6 7 8 对应原数组下标为 4 5 6 7
        //那+left(4)，刚好存入原数组正确的位置
        array[i+left] = ret[i];
    }
}

非递归版本：【模拟递归】

public static void mergerSort(int[] array){
    int gap = 1;//模拟递归到每组序列只有一个元素
    while(gap < array.length){
        //合并
        for (int i = 0; i < array.length; i+= 2*gap) {
            int left = i;
            int mid = left+gap-1;
            //判断越界
            if(mid >= array.length){
                mid = array.length-1;
            }
            int right = mid+gap;
            //判断越界
            if(right >= array.length){
                right = array.length-1;
            }
            mergeHelp(array,left,mid,right);
        }
        gap *= 2;
    }
}
private static void mergeHelp(int[] array,int left,int mid,int right){
    //第一个小数组下标范围
    int s1 = left;
    int e1 = mid;
    //第二个小数组下标范围
    int s2 = mid+1;
    int e2 = right;
    //合并的大数组
    int[] ret = new int[right-left+1];
    int k = 0;//ret下标
    while(s1 <= e1 && s2 <= e2){
        //进行比较
        if( array[s1] <= array[s2]){
            ret[k++] = array[s1++];
        } else{
            ret[k++] = array[s2++];
        }
    }
    //存放剩余的有序元素
    while(s1 <= e1){
        ret[k++] = array[s1++];
    }
    while(s2 <= e2){
        ret[k++] = array[s2++];
    }
    for (int i = 0; i < k; i++) {
        array[i+left] = ret[i];
    }
}

总结：

归并的缺点是需要 O(N) 的空间复杂度。
归并排序的思想更多是在解决磁盘中的外排序问题。
排序算法复杂度及稳定性分析

排序方法	最好	平均	最坏	空间复杂度	稳定性
冒泡排序	O(n)	O(n^2)	O(n^2)	O(1)	稳定
插入排序	O(n)	O(n^2)	O(n^2)	O(1)	稳定
选择排序	O(n^2)	O(n^2)	O(n^2)	O(1)	不稳定
希尔排序	O(n)	O(N^1.3)	O(n^2)	O(1)	不稳定
堆排序	O(n * log(n))	O(n * log(n))	O(n * log(n))	O(1)	不稳定
快速排序	O(n * log(n))	O(n * log(n))	O(n^2)	O(logn)~O(n)	不稳定
归并排序	O(n * log(n))	O(n * log(n))	O(n * log(n))	O(1)	稳定

24 KiB Raw Permalink Blame History Unescape Escape

插入排序

希尔排序

选择排序

堆排序

冒泡排序

快速排序

6.1 Hoare 版

6.2 挖坑法

6.3 前后指针法

6.4 快速排序非递归

归并排序

24 KiB

Raw Permalink Blame History