DS内排总结

mumumu

发布于 2023-04-23 17:15:24

3200

发布于 2023-04-23 17:15:24

文章被收录于专栏：blog1blog1

排序

前言

复习排序这一章时，感觉内容很多很杂乱，加上代码听得半懂不懂，于是就来总结一下。前几天状态不在线，回家休息了两天，空了三天节奏。4.14写完这篇继续赶进度了，争取今天写完内部排序的习题，学完外排，结束DS了。

插入排序

直接插入排序

基本思路（个人理解）：从第一个元素开始扫描，如果第i个元素比它前面的元素小，就把i前面所有比i大的元素依次向后移一位，将i插到前面留出的空位。
基本思路（略官方）：每次将⼀个待排序的记录按其关键字⼤⼩插⼊到前⾯已排好序的⼦序列中，直到全部记录插⼊完成。
代码：

void insert_directly(int A[],int n){
    int i,j,temp;
    for(i=1;i<n;i++){
        if(A[i]<A[i-1]){
            temp = A[i];
            for(j = i-1;j>=0 && A[j]>temp;--j){
                A[j+1] = A[j];//所有大于temp(第i个)的都向后移一位（给第i个留位置插入）
            }
            A[j+1] = temp;
        }
    }
}//(没有用哨兵)

空间效率：常数辅助单元，O(1)
时间效率
- 最好：表中元素为有序，则不用移动元素，n个元素比n-1次即可，时间复杂度为O(n)
- 最坏：表中元素逆序，总的比较次数和移动次数达到最大，总时间复杂度：O(n^2^)
- 平均：O(n^2^)
稳定性：稳定的

折半插入排序

基本思路：当前处理的元素之前的元素已经是有序的了，所以先⽤折半查找找到应该插⼊的位置，再移动元素
和直接插入的区别：改进了一点点比较元素的次数
时间复杂度：整体看依旧是O(n^2^)
代码（用哨兵）

void insert_inhalf(int A[],int n){
    int i,j,low,mid,high;
    for(i=2;i<n;i++){
        A[0] = A[i];//哨兵A[0]保存待插入元素A[i]
        low = 1;
        high = i-1;
        while(low<=high){
            mid = (low+high)/2;
            if(A[mid]>A[0]){//查左子表  注意这里，即使A[mid]和A[0]想相同，也要再查找一次，目的是保证算法的稳定性。直到low>high，才停止循环
                high = mid - 1;
            } else
                low = mid + 1;//查右子表
        }
        for(j=i-1;j>=high+1;--j){//将[low,i-1]内的元素全部右移
            A[j+1] = A[j];
        }
        A[high+1] = A[0];
    }
}

希尔排序

基本思想：先将待排序表分割成若⼲形如 L[i, i + d, i + 2d,…, i + kd] 的“特殊”⼦表，对各个⼦表分别进⾏直接插⼊排序。缩小增量d，重复上述过程，直到d=1为⽌。eg：A[1],A[5],A[9],A[13]
- 先追求表中元素部分有序，再逐渐逼近全局有序
代码

void shellsort(int A[],int n){
    int d;//增量
    int i,j;
    for(d = n/2; d>=1; d=d/2){//增量变化
        for(i=d+1; i<n; ++i){//轮流处理不同子表
            if(A[i]<A[i-d]){
                A[0] = A[i];//只是暂存在A[0]，不是哨兵
                for(j=i-d; j>0 && A[0]<A[j]; j-=d)//相当于在每个子表进行直接插入排序
                    A[j+d] = A[j];
                A[j+d] = A[0];
            }
        }
    }
}

空间复杂度：常数个辅助单元：O(1)
时间复杂度
- n在某个特定范围：不好推直接记住：O(n^1.3^)
- 最坏：d = 1时，相当于直接插入排序：O(n^2^)
稳定性：相同的关键字可能被划分到不同的子表，可能会改变相对次序，因此不稳定
适用性：要求顺序存储（随机访问）

交换排序

冒泡排序

基本思想：从后往前两两比较相邻元素的值，若为逆序（前面的比后面的大），则交换他们，直到序列比较完，我们称为第一趟冒泡。每次冒泡的结果是把最小的一个放到第一位。最多n-1趟排好n个元素。
代码

void swap(int &a,int &b){
    int t;
    t = a;
    a = b;
    b = t;
}
void BubbleSort(int A[],int n){
    for(int i=0;i<n-1;i++){
        bool flag = false;//表示本趟冒泡是否发生交换
        for(int j=n-1;j>i;j--){
            if(A[j-1]>A[j])
                swap(A[j-1],A[j]);
            flag = true;
        }
        if(flag==false)//本趟没有发生交换，说明表已经有序
            return;
    }
}

空间复杂度：O(1)
时间复杂度
- 最好：初始有序：只需比较，不用移动，比较n-1次，O(n)
- 最差：初始逆序，移动n-1次，第i趟要比n-i次
  - 交换次数 = 比较次数 = 1+2+….+n O(n^2^)
  - 移动次数 = 3倍的交换次数，根据swap()函数，每次交换需要移动三次元素来交换位置
稳定性：稳定

快速排序

基本思想：在待排序表L[1…n]中任取⼀个元素pivot作为枢轴（或基准，通常取⾸元素），通过⼀趟排序将待排序表划分为独⽴的两部分L[1…k-1]和L[k+1…n]，使得L[1…k-1]中的所有元素⼩于pivot，L[k+1…n]中的所有元素⼤于等于 pivot，则pivot放在了其最终位置L(k)上，这个过程称为⼀次“划分”。然后分别递归地对两个⼦表重复上述过程，直⾄每部分内只有⼀个元素或空为⽌，即所有元素放在了其最终位置上。
代码

int Partition(int A[],int low,int high){//用第一个元素将待排序序列划分为两部分
    int pivot = A[low];//第一个元素作为枢轴
    while(low<high){
        while(low<high && A[high]>=pivot){
            high = high - 1;
        }
        A[low] = A[high];//比枢轴小的元素前移
        while(low<high && A[low]<=pivot){
            low = low + 1;
        }
        A[high] = A[low];//比枢轴大的元素后移
    }
    A[low] = pivot;
    return low;
}
void QuickSort(int A[],int low,int high){
    if(low<high){
        int pivotpos = Partition(A,low,high);
        QuickSort(A,low,pivotpos-1);//划分左子表
        QuickSort(A,pivotpos+1,high);//划分右子表
    }
}

特点：快排过程不产生有序子序列，但每趟排序会将枢轴元素放在最终的位置上
算法性能：取决于递归层数，若每次划分的越均匀，则递归深度越低，划分的越不均匀，则递归深度越深。
- 空间复杂度：O(递归层数)，可以将整个排序的过程看为n个结点的二叉树，则最小空间复杂度:O(log~2~n)，最大空间复杂度：O(n)
- 时间复杂度：最好时间复杂度：O(nlog~2~n)，最坏时间复杂度：O(n^2^)，平均时间复杂度：O(nlog~2~n)

稳定性：不稳定，因为high指针是从后往前扫描的，若两个元素值相同，则后一个元素会被优先拿到前面去，相对位置发生变化。

选择排序

简单选择排序

基本思想：设排序表L[1…n]，第i趟排序会从L[i…n]中选择关键字最小的元素和i交换，每趟排序可以确定一个元素的最终位置，经过n-1趟排序可以排好n个元素
代码

void SelectSort(int A[],int n){
    for(int i=0;i<n-1;i++){
        int min = i;//记录最小元素位置
        for(int j=i+1;j<n;j++){
            if(A[j]<A[min])
                min = j;
        }
        if(min != i)
            swap(A[i],A[min]);
    }
}

空间效率：常数个辅助单元：O(1)
时间效率：无非就是看比较次数和移动次数
- 移动次数：若原表有序，则最好情况下移动0次，最差情况下移动3(n-1)次（每交换一次需要移动三次）
- 比较次数：无论原表是否有序，都会比较1+2+3+….+n-1 = n(n-1)/2次，因此时间复杂度始终是O(n^2^)
稳定性：不稳定

堆排序

堆
- 若满⾜：L(i)≥L(2i)且L(i)≥L(2i+1) （1 ≤ i ≤n/2 ）—— ⼤根堆（⼤顶堆）
- 若满⾜：L(i)≤L(2i)且L(i)≤L(2i+1) （1 ≤ i ≤n/2 ）—— ⼩根堆（⼩顶堆）
  - 结合完全二叉树理解，大根堆就是跟比左右孩子大的，小根堆就是跟比左右孩子小的
  - 与二叉排序数区分，二叉排序树是左<=跟<=右
基本思路：
每⼀趟将堆顶元素加⼊有序⼦序列（与待排序序列中的最后⼀个元素交换），
并将待排序元素序列再次调整为⼤根堆（小元素不断“下坠”）
代码

void HeadAdjust(int A[],int k,int len){//将k为跟的子树调整为大根堆
    A[0] = A[k];//A[0]暂存子树的根节点
    for(int i=2*k; i<=len; i*=i){//沿k较大的子节点向下筛选
        if(i<len && A[i]<A[i+1])
            i++;//取k较大的孩子结点的下标
        if(A[0]>A[i])
            break;//当前跟结点比孩子大，不用调整
        else{
            A[k] = A[i];//较大的孩子结点换到父节点
            k = i;
        }
    }
    A[k] = A[0];//被筛选结点的位置放在最终位置
}
void BuildMaxHeap(int A[],int len){//建立大根堆
    for(int i=len/2;i>0;i--)//从后往前每个分支结点，将其子树调整为大根堆
        HeadAdjust(A,i,len);
}
void HeapSort(int A[],int len){
    BuildMaxHeap(A,len);
    for(int i=len; i>1; i--){//n-1趟的交换和建堆过程
        swap(A[i],A[1]);//堆顶元素和堆底元素互换
        HeadAdjust(A,1,i-1);//剩余待排序元素整理成堆
    }
}

时间复杂度：建堆时间为O(n)，之后有n-1次向下调整操作，每次调整时间复杂度为O(h)，所以最好最差平均都为O(nlog~2~n)
空间复杂度：常数个辅助单元：O(1)
稳定性：不稳定，进行筛选时有可能把后面相同关键字的元素调整到前面

归并排序和基数排序

归并排序

基本思路：归并：把两个或多个已经有序的序列合并成⼀个
代码

int *B = (int *) malloc(7 * sizeof (int));
void Merge(int A[],int low,int mid,int high){
    int i,j,k;
    for(k=low; k<=high; k++){
        B[k] = A[k];//A中的所有元素赋值于B
    }
    for(i=low,j=mid+1,k=i; i<=mid&&j<=high; k++){//分成两组，i初值为第一组的第一个元素，j初值为第二组的第一个元素，第一组从[1,mid]，第二组[mid+1,high]
        if(B[i]<=B[j]){
            A[k] = B[i];//A[k]是排序后的数组
            i++;
        }
        else{
            A[k] = B[j];
            j++;
        }
    }
    while(i<=mid)//说明for循环是因为j>high而结束，第二个表检测完，则后续把第一个表的剩余元素全加进来即可
        A[k++] = B[i++];
    while(j<=high)
        A[k++] = B[j++];
}
void MergeSort(int A[],int low,int high){
    if(low<high){
        int mid = (low+high)/2;//从中间划分
        MergeSort(A,low,mid);//递归左半部分 归并排序
        MergeSort(A,mid+1,high);//递归右半部分，归并排序
        Merge(A,low,mid,high);//归并排好序的两部分
    }
}

基于分治的思想
空间效率：辅助数组B[n]，所以空间复杂度为O(n)
时间效率：每趟归并O(n)，共需要log~2~n(向上取整)趟（结合二叉树理解），所以总时间效率O(nlog~2~n)
- 时间效率和初始序列是否有序无关，最好最坏平均都是O(nlog~2~n)
稳定性：稳定（可以自己设置Merge()时，扫到两个相等元素，优先选先扫到的）