【数据结构】排序算法大全(快速、堆、归并、插入、折半、希尔、冒泡、计数、基数)各算法比较、解析+完整代码

文章目录

  • 八、排序
    • 1.插入排序
      • 1.1 直接插入排序
      • 1.2 折半插入排序
      • 1.3 希尔排序
    • 2.交换排序
      • 2.1 冒泡排序
      • 2.2 快速排序
    • 3.选择排序
      • 3.1 简单选择排序
      • 3.2 堆
        • 3.2.1 堆排序
        • 3.2.2 堆插入删除
        • *完善代码 堆
    • 4.归并、基数、计数排序
      • 4.1 归并排序
      • 4.2 基数排序
      • 4.3 计数排序
    • 5.内部排序算法的比较
    • *完整代码 排序

八、排序

1.插入排序

1.1 直接插入排序

  • 算法思想

    每次将一个待排序的记录按其关键字大小插入到前面已排序好的子序列中,直到全部记录插入完成。

    在这里插入图片描述

  • 代码

    不带哨兵:

    void InsertSort(int A[],int n){
        int i,j,temp;
        for(i=0;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];
                }
                A[j+1]=temp;//插入
            }
        }
    }
    

    带哨兵(第一个元素存待插入的元素):

    优点:不用每轮循环都判断j>=0

    void InsertSort(int A[],int n){
        int i,j;
        for(i=2;i<=n;i++){
            if(A[i]<A[i-1]){
                A[0]=A[i]; //哨兵
                for(j=i-1;A[0]<A[j];j--) //从后往前查找待插入位置
                    A[j+1]=A[j];
                A[j+1]=A[0];
            }
        }
    }
    
  • 算法效率

    • 空间复杂度: O ( 1 ) O(1) O(1)

    • 时间复杂度:主要来自对比关键字、移动元素。

      最好情况:共n-1趟处理,每一趟只需要对比一次,则 O ( n ) O(n) O(n)

      最坏情况:原本为逆序,则 O ( n 2 ) O(n^2) O(n2)

      平均时间复杂度: O ( n 2 ) O(n^2) O(n2)

      算法稳定性:稳定

1.2 折半插入排序

  • 算法思想

    在已排好的部分设置low和high指针,取中间点mid和待排序数据比较。

    当low>high时折半查找停止,应将[low,i-1]内的元素全部右移,并将A[0]复制到low所指位置;

    当A[mid]==A[0]时,为了保证算法的稳定性,应继续在mid所指位置右边寻找插入位置。

  • 代码

    void InsertSort(int A[],int n){
        int i,j,low,high,mid;
        for(i=2;i<=n;i++){
            A[0]=A[i];
            low=1;high=i-1; //折半查找范围
            while(low<=high){
                mid=(low+high)/2;
                if(A[mid]>A[0])
                    high=mid-1; //查找左子表
                else
                    low=mid+1; //查找右子表
            for(j=i-1;j>=high+1;i--)
                A[j+1]=A[j]; //后移元素,空出插入位置
            A[high+1]=A[0]; //插入
            }
        }
    }
    
  • 算法效率

    时间复杂度: O ( n 2 ) O(n^2) O(n2)

  • 对链表进行插入排序

    • 折半插入排序无法实现
    • 直接插入排序移动元素次数变少了,但关键字比较次数依然 O ( n 2 ) O(n^2) O(n2),所以时间复杂度也是 O ( n 2 ) O(n^2) O(n2)

1.3 希尔排序

  • 思想

    先部分有序,再全局有序。

    先将待排序表分割成若干形如 L [ i , i + d , i + 2 d , . . . , i + k d ] L[i,i+d,i+2d,...,i+kd] L[i,i+d,i+2d,...,i+kd]特殊子表,对各个子表分别进行直接插入排序。缩小增量d,重复上述过程,直到d=1为止。

  • 过程

在这里插入图片描述
在这里插入图片描述

  • 代码

    void ShellSort(int A[],int n){
        int d,i,j;
        //A[0]只是暂存单元,不是哨兵,当j<=0时,插入位置已到
        for(d=n/2;d>=1;d=d/2){ //步长变化
            for(i=d+1;i<=n;i++){
                if(A[i]<A[i-d]){ //需将A[i]插入有序增量子表
                    A[0]=A[i];
                    for(j=i-d;j>0&&A[0]<A[j];j-=d){
                        A[j+d]=A[j]; //记录后移
                    }
                    A[j+d]=A[0]; //插入
                }
            }
        }
    }
    
  • 性能分析

    • 空间复杂度: O ( 1 ) O(1) O(1)

    • 时间复杂度:和增量序列d的选择有关。

      目前无法用数学手段确切证明时间复杂度,最坏时间复杂度 O ( n 2 ) O(n^2) O(n2),n在某个范围内,可达 O ( n 1.3 ) O(n^{1.3}) O(n1.3)

    • 不稳定

    • 不能基于链表实现。

2.交换排序

  • 基于交换的排序:根据序列中两个元素关键字的比较结果来对这两个记录在序列中的位置。

2.1 冒泡排序

  • 算法思想

    从后往前(或从前往后)两两比较相邻元素的值,若为逆序,则交换,直到序列比较完。

  • 代码

    //交换
    void swap(int &a,int &b){
        int temp=a;
        a=b;
        b=temp;
    }
    
    //冒泡排序
    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 ) O(1) O(1)

    • 时间复杂度:

      最好情况——有序 O ( n ) O(n) O(n)

      最坏情况——逆序 O ( n 2 ) O(n^2) O(n2)

    • 可以用于链表的排序。

2.2 快速排序

  • 算法思想

    基于分治法。

    1.在序列中任取一个元素作为基准(通常取首元素);

    2.遍历序列,将比基准元素小的放在基准元素的左边,比基准元素大的放在右边;

    3.遍历完成后,基准元素位置确定,对该基准元素的左右子表再次排序。

    在这里插入图片描述

  • 代码

    思路

    1.以序列第一个元素作为基准元素pivot;

    2.令low和high分别指向序列首尾;

    3.high不断左移直到找到比pivot小的元素,找到后交换low和high所指元素的位置;

    4.low不断右移直到找到比pivot大的元素,找到后交换low和high所指元素位置;

    5.当low==high时完成遍历,将基准元素放入low指针所指的地方,此时基准元素已经排序完成;

    6.递归排序基准元素的左右子序列。

    //用第一个元素将待排序序列划分为左右两个部分
    int Partition(int A[],int low,int high){
        int pivot=A[low]; //第一个元素作为基准
        while(low<high){
            while(low<high&&A[high]>=pivot) //high指针不断左移,直到找到比基准元素小的
                high--;
            A[low]=A[high]; //比基准小的元素左移
            while(low<high&&A[low]<=pivot) //low指针不断右移,直到找到比基准元素大的
                low++;
            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 ( l o g 2 n ) O(log_2n) O(log2n),最坏空间复杂度 O ( n ) O(n) O(n)

    • 时间复杂度=n*递归层数

      最好时间复杂度 O ( n l o g 2 n ) O(nlog_2n) O(nlog2n),最坏时间复杂度 O ( n 2 ) O(n^2) O(n2)

      平均时间复杂度 O ( n l o g 2 n ) O(nlog_2n) O(nlog2n)

    • 稳定性:不稳定

  • 优化

    • 若每次选中的基准元素将待排序序列划分成均匀两个部分,则递归深度最小,算法效率最高。

    • 优化思路:

      尽量选择可以把数据中分的数轴元素。

      如:1.选头中尾三个位置的元素,取中间值作为基准元素;2.随机选取一个元素。

3.选择排序

3.1 简单选择排序

  • 定义

    每一趟在待排序元素中选取关键字最小的元素加入有序子序列。

  • 代码

    //交换函数
    void swap(int &a,int &b){
        int temp=a;
        a=b;
        b=temp;
    }
    
    void SelectSort(int A[],int n){
        for(int i=0;i<n-1;i++){
            int min=i;
            for(int j=1+1;j<n;j++) //选择最小的
                if(A[j]<A[min])min=j;
            if(min!=i)swap(A[i],A[min]);
        }
    }
    
  • 性能分析

    • 空间复杂度: O ( 1 ) O(1) O(1)

    • 时间复杂度: O ( n 2 ) O(n^2) O(n2)

      无论有序、逆序、乱序,一定需要n-1趟处理

      总共需要对比关键字 ( n − 1 ) + ( n − 2 ) + . . . + 1 = n ( n − 1 ) / 2 (n-1)+(n-2)+...+1=n(n-1)/2 (n1)+(n2)+...+1=n(n1)/2

      交换元素次数<n-1

    • 稳定性:不稳定。

    • 实用性:既可以顺序表,也可以链表。

3.2 堆

3.2.1 堆排序
  • 什么是堆?

    若n个关键字序列 L [ 1... n ] L[1...n] L[1...n]满足以下某条性质,则称为堆(Heap):

    1.若满足 L ( i ) > = L ( 2 i ) L(i)>=L(2i) L(i)>=L(2i) L ( i ) > = L ( 2 i + 1 ) L(i)>=L(2i+1) L(i)>=L(2i+1) ( 1 < = i < = n / 2 ) (1<=i<=n/2) (1<=i<=n/2) —— 大根堆(大顶堆)

    2.若满足 L ( i ) < = L ( 2 i ) L(i)<=L(2i) L(i)<=L(2i) L ( i ) < = L ( 2 i + 1 ) L(i)<=L(2i+1) L(i)<=L(2i+1) ( 1 < = i < = n / 2 ) (1<=i<=n/2) (1<=i<=n/2) —— 小根堆(小顶堆)

  • 如何建立大根堆

    • 思路:把所有非终端结点( l e n / 2 到 1 len/2到1 len/21的结点)都检查一遍,是否满足大根堆要求,如果不满足,则调整。
    • 检查方式:检查当前结点是否满足 根>=左右,若不满足,将当前结点与更大的一个孩子互换
  • 代码

    思路:

    1.从len/2开始遍历;

    2.检查是否满足大/小根堆的要求;

    3.若不满足,将当前结点与更加大/小的孩子换。

    //建立大根堆
    void BuildMaxHeap(int A[],int len){
        for(int i=len/2;i>0;i--) //从后往前调整所有非终端结点
            HeadAdjust(A,i,len);
    }
    
    //将以k为根的子树调整为大根堆
    void HeadAdjust(int A[],int k,int len){
        A[0]=A[k]; //A[0]暂存子树根结点
        for(int i=2*k;i<=len;i*=2){ //沿key较大的子结点向下筛选
            if(i<len&&A[i]<A[i+1])//取key较大的子结点的下标  
                i++; 
            if(A[0]>=A[i])
                break; //筛选结束
            else{
                A[k]=A[i]; //将A[i]调整到双亲结点上
                k=i; //修改k值,以便继续向下筛选
            }
        }
        A[k]=A[0]; //被筛选结点的值放入最终位置
    }
    
  • 基于大根堆进行排序

    1.每一趟将堆顶元素加入有序子序列;

    2.与待排序序列中的最后一个元素交换;

    3.并将待排序元素序列再次调整为大根堆(小元素不断下坠)。

    代码:

    //建立大根堆
    void BuildMaxHeap(int A[],int len)
        
    //将以k为根的子树调整为大根堆
    void HeadAdjust(int A[],int k,int len)
        
    //堆排序完整逻辑
    void HeapSort(int A[],int len){
        BuidMaxHeap(A,len); //初始建堆
        for(int i=len;i>1;i--){
            swap(A[i],A[1]); //堆顶和堆底元素交换
            HeadAdjust(A,1,i-1); //把剩余的待排序元素整理成堆
        }
    }
    
  • 时间复杂度分析

    • 一个结点,每下坠一层,最多只需对比关键字2次

      若树高为h,某结点在第i层,则将这个结点向下调整最多只需要下坠h-i层,关键字对比次数不超过2(h-i)

    • 建堆过程,关键字对比次数不超过4n,建堆时间复杂度 O ( n ) O(n) O(n)

    • 每下坠一层,最多只需要对比关键字两次,因此每一趟排序复杂度不超过 O ( h ) = O ( l o g 2 n ) O(h)=O(log_2n) O(h)=O(log2n)

    • 总共有n-1趟,总时间复杂度为 O ( n l o g 2 n ) O(nlog_2n) O(nlog2n)

  • 稳定性

    若左右孩子一样大,优先和左孩子换,建堆时是稳定的,但是在排序时,堆顶和堆底互换,不稳定。

    ∴不稳定

  • 空间复杂度: O ( 1 ) O(1) O(1)

3.2.2 堆插入删除
  • 在堆中插入新元素

    • 对于小根堆,新元素放到表尾(堆底),与父节点对比,若新元素比父节点更加小,则互换。

      新元素一路上升,直到无法继续上升。

    • 对于大根堆,新元素放到表尾,与父节点对比,若新元素比父节点更加大,则互换。

      新元素一路上升,直到无法继续上升。

  • 在堆中删除

    • 被删除元素用堆底(表尾)元素代替,

      根据大/小根堆要求,让该元素不断下坠,直到无法下坠为止。

  • 关键字对比次数

    每次上升只需对比1次;

    每次下降可能2次(有两小孩),可能1次(只有一小孩)。

*完善代码 堆
#include <stdio.h>
#include <math.h>

// 辅助函数,用于交换两个整数的值
void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// 将以k为根的子树调整为大根堆
void HeadAdjust(int A[], int k, int len) {
    A[0] = A[k]; // A[0]暂存子树根结点
    for (int i = 2 * k; i <= len; i *= 2) { // 沿key较大的子结点向下筛选
        if (i < len && A[i] < A[i + 1]) // 取key较大的子结点的下标
            i++;
        if (A[0] >= A[i])
            break; // 筛选结束
        else {
            A[k] = A[i]; // 将A[i]调整到双亲结点上
            k = i; // 修改k值,以便继续向下筛选
        }
    }
    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--) {
        swap(&A[i], &A[1]); // 堆顶和堆底元素交换
        HeadAdjust(A, 1, i - 1); // 把剩余的待排序元素整理成堆
    }
}

// 插入新元素到大根堆
void Insert(int A[], int *len, int value) {
    A[++(*len)] = value; // 在数组末尾插入新元素
    int i = *len;
    while (i > 1 && A[i / 2] < A[i]) { // 向上调整
        swap(&A[i / 2], &A[i]);
        i /= 2;
    }
}

// 删除大根堆的根节点
void DeleteMax(int A[], int *len) {
    A[1] = A[(*len)--]; // 用最后一个元素替换根节点,并减少堆的大小
    HeadAdjust(A, 1, *len); // 调整堆
}

// 打印堆的结构
void PrintHeap(int A[], int len) {
    for (int i = 1; i <= len; i++) {
        printf("%d ", A[i]);
    }
    printf("\n");
}


// 打印堆的结构(水平树格式)
void PrintHeapStructure(int A[], int len) {
    int levels = (int)log2(len) + 1; // 计算堆的层数
    int maxWidth = (1 << (levels - 1)) * 3; // 每层最大宽度

    for (int level = 0; level < levels; level++) {
        int numElements = 1 << level; // 当前层的元素数量
        int spaceBetween = maxWidth / numElements; // 当前层元素之间的间隔

        for (int i = 0; i < numElements && (numElements + i - 1) < len; i++) {
            int index = numElements + i; // 元素的实际索引
            printf("%*s%d", spaceBetween / 2, "", A[index]); // 打印元素
        }
        printf("\n");
    }
}

int main() {
    int A[100] = {0, 6, 2, 10, 8, 7, 9, 3, 5, 4, 1}; // 注意索引0不使用
    int len = 10;

    printf("Original array:\n");
    PrintHeap(A, len);

    printf("Heap structure:\n");
    PrintHeapStructure(A, len);

    // 堆排序
    HeapSort(A, len);
    printf("Sorted array:\n");
    PrintHeap(A, len);
    printf("Heap structure:\n");
    PrintHeapStructure(A, len);

    // 插入新元素
    Insert(A, &len, 15);
    printf("After insert 15:\n");
    PrintHeap(A, len);
    printf("Heap structure:\n");
    PrintHeapStructure(A, len);

    // 删除堆顶元素
    DeleteMax(A, &len);
    printf("After deleting root:\n");
    PrintHeap(A, len);

    printf("Heap structure:\n");
    PrintHeapStructure(A, len);

    return 0;
}

4.归并、基数、计数排序

4.1 归并排序

  • 定义

    • 归并:把两个或多个已经有序的序列合并成一个。

    • 归并的方法:

      1.创建一个长序列,能放下已有的两个序列;

      2.i,j分别指向两个有序序列,k指向长序列;

      3.对比i,j所指元素,更小的先加入长序列,并且更小的元素所在指针加一;

      4.如果i或j已经遍历玩,往长序列中直接添加剩余元素。

      • 注:多路归并也一样,m路归并,每选出一个元素要对比m-1次。

  • 归并排序

    • 手算模拟:

    • 核心操作:把两个有序的队列合并成一个
  • 代码

    int *B=(int*)malloc(n*sizeof(int)); //辅助数组
    
    //mid左右两边各自有序,将两部分归并
    void Merge(int A[],int low,int mid,int high){
        int i,j,k;
        for(k=low;k<=high;k++){//将A中所有元素复制到B(使最后正确排序还是在A中)
            B[k]=A[k]; 
        }
        for(i=low,j=mid+1,k=i;i<=mid&&j<=high;k++){
            if(B[i]<=B[j]){ //较小值复制到A中
                A[k]=B[i++];
            }
            else{
                A[k]=B[j++];
            }
            while(i<=mid)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,high); //对右半部分递归排序
            Merge(A,low,high); //归并
        }
    }
    
  • 算法效率分析

    • 可把归并过程看成2路归并的归并树——形态上是一棵倒立的二叉树。

    • n个元素进行2路归并排序,归并趟数 = ⌈ l o g 2 n ⌉ =\lceil log_2n \rceil =log2n

      每趟归并时间复杂度为 O ( n ) O(n) O(n),则算法时间复杂度为 O ( n l o g 2 n ) O(nlog_2n) O(nlog2n)

    • 空间复杂度= O ( n ) O(n) O(n)

    • 稳定性:稳定。

4.2 基数排序

  • 例子

    原始序列

    image-20240525152335161

    1.按各位元素排列

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

  • 定义

  • 基数排序得到递减序列过程如下:

    1.初始化:设置r个空队列

    2.按各个关键字位权重递增的次序(个、十、百),对d个关键字位分别做分配和收集。

    ​ 1)分配:顺序扫描各个元素,若当前处理的关键字位等于x,则将元素插入队尾。

    ​ 2)收集:把各队列中的结点依次出队并连接。

  • 算法效率分析

    基数排序通常基于链式存储实现。

    • 需要r个辅助队列,空间复杂度 O ( r ) O(r) O(r)
    • 一趟分配 O ( n ) O(n) O(n),一趟收集 O ( r ) O(r) O(r),总共d趟分配、收集,总时间复杂度 O ( d ( n + r ) ) O(d(n+r)) O(d(n+r))
  • 基数排序完整代码

    #include <stdio.h>
    #include <stdlib.h>
    
    // 定义元素类型
    typedef int ElemType;
    
    // 定义链表节点结构
    typedef struct LinkNode {
        ElemType data;
        struct LinkNode *next;
    } LinkNode, *LinkList;
    
    // 定义队列结构
    typedef struct {
        LinkNode *front, *rear;
    } LinkQueue;
    
    // 初始化队列
    void InitQueue(LinkQueue *q) {
        q->front = q->rear = (LinkNode *)malloc(sizeof(LinkNode));
        if (!q->front) {
            printf("Memory allocation failed\n");
            exit(1);
        }
        q->front->next = NULL;
    }
    
    // 判断队列是否为空
    int IsEmpty(LinkQueue q) {
        return q.front == q.rear;
    }
    
    // 入队
    void EnQueue(LinkQueue *q, ElemType e) {
        LinkNode *p = (LinkNode *)malloc(sizeof(LinkNode));
        if (!p) {
            printf("Memory allocation failed\n");
            exit(1);
        }
        p->data = e;
        p->next = NULL;
        q->rear->next = p;
        q->rear = p;
    }
    
    // 出队
    int DeQueue(LinkQueue *q, ElemType *e) {
        if (IsEmpty(*q)) return 0;
        LinkNode *p = q->front->next;
        *e = p->data;
        q->front->next = p->next;
        if (q->rear == p) q->rear = q->front;
        free(p);
        return 1;
    }
    
    // 获取数组中最大元素的位数
    int GetMaxDigits(ElemType arr[], int n) {
        int max = arr[0];
        for (int i = 1; i < n; i++) {
            if (arr[i] > max) {
                max = arr[i];
            }
        }
    
        int digits = 0;
        while (max > 0) {
            digits++;
            max /= 10;
        }
        return digits;
    }
    
    // 获取指定位置的数字
    int GetDigit(ElemType num, int pos) {
        for (int i = 0; i < pos; i++) {
            num /= 10;
        }
        return num % 10;
    }
    
    // 基数排序函数
    void RadixSort(ElemType arr[], int n) {
        int maxDigits = GetMaxDigits(arr, n);
    
        // 初始化10个队列用于每个基数位的分配
        LinkQueue queues[10];
        for (int i = 0; i < 10; i++) {
            InitQueue(&queues[i]);
        }
    
        // 对每个位数进行分配和收集
        for (int d = 0; d < maxDigits; d++) {
            // 分配阶段:将元素按当前位的值分配到对应的队列
            for (int i = 0; i < n; i++) {
                int digit = GetDigit(arr[i], d);
                EnQueue(&queues[digit], arr[i]);
            }
    
            // 收集阶段:将各个队列的元素依次出队放回数组
            int index = 0;
            for (int i = 0; i < 10; i++) {
                ElemType e;
                while (DeQueue(&queues[i], &e)) {
                    arr[index++] = e;
                }
            }
    
            // 打印当前步骤的排序结果
            printf("After sorting by digit %d: ", d + 1);
            for (int i = 0; i < n; i++) {
                printf("%d ", arr[i]);
            }
            printf("\n");
        }
    }
    
    int main() {
        ElemType arr[] = {520, 211, 438, 888, 007, 111, 985, 666, 996, 233,168};
        int n = sizeof(arr) / sizeof(arr[0]);
    
        printf("Original array: ");
        for (int i = 0; i < n; i++) {
            printf("%d ", arr[i]);
        }
        printf("\n");
    
        RadixSort(arr, n);
    
        printf("Sorted array: ");
        for (int i = 0; i < n; i++) {
            printf("%d ", arr[i]);
        }
        printf("\n");
    
        return 0;
    }
    

4.3 计数排序

  • 定义

    对每个待排序元素x,统计小于x的元素个数,利用信息可以确定x的最终位置。

  • 代码

    //A[]是输入序列
    //B[]是输出序列
    //C[]存储计数值
    void CountSort(ElemType A[],ElemType B[],int n,int k){
        int i,C[k];
        for(i=0;i<k;i++){ //初始化计数数组
            C[i]=0;
        }
        for(i=0;i<n;i++){ //统计每个元素出现次数
            C[A[i]]++;
        }
        for(i=1;i<k;i++){
            C[i]=C[i]+C[i-1]; //C中存小于等于i的个数
        }
        for(i=n-1;i>=0;i--){
            B[C[A[i]-1]]=A[i]; //将元素A[i]放在输出数组B的正确位置上
            C[A[i]]=C[A[i]]-1;
        }
    }
    

5.内部排序算法的比较

  • 内部排序就是在内存中进行的,以上都是内部排序。

  • 比较

    算法种类最好时间复杂度最坏时间复杂度平均情况空间复杂度是否稳定
    直接插入排序 O ( n ) O(n) O(n) O ( n 2 ) O(n^2) O(n2) O ( n 2 ) O(n^2) O(n2) O ( 1 ) O(1) O(1)
    冒泡排序 O ( n ) O(n) O(n) O ( n 2 ) O(n^2) O(n2) O ( n 2 ) O(n^2) O(n2) O ( 1 ) O(1) O(1)
    简单选择排序 O ( n 2 ) O(n^2) O(n2) O ( n 2 ) O(n^2) O(n2) O ( n 2 ) O(n^2) O(n2) O ( 1 ) O(1) O(1)
    希尔排序 O ( 1 ) O(1) O(1)
    快速排序 O ( n l o g 2 n ) O(nlog_2n) O(nlog2n) O ( n l o g 2 n ) O(nlog_2n) O(nlog2n) O ( n 2 ) O(n^2) O(n2) O ( l o g 2 n ) O(log_2n) O(log2n)
    堆排序 O ( n l o g 2 n ) O(nlog_2n) O(nlog2n) O ( n l o g 2 n ) O(nlog_2n) O(nlog2n) O ( n l o g 2 n ) O(nlog_2n) O(nlog2n) O ( 1 ) O(1) O(1)
    二路归并排序 O ( n l o g 2 n ) O(nlog_2n) O(nlog2n) O ( n l o g 2 n ) O(nlog_2n) O(nlog2n) O ( n l o g 2 n ) O(nlog_2n) O(nlog2n) O ( n ) O(n) O(n)
    基数排序 O ( d ( n + r ) ) O(d(n + r)) O(d(n+r)) O ( d ( n + r ) ) O(d(n + r)) O(d(n+r)) O ( d ( n + r ) ) O(d(n + r)) O(d(n+r)) O ( r ) O(r) O(r)

*完整代码 排序

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>

// 交换
void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

//--------------------插入排序--------------------
void InsertSort(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];
            }
            A[j + 1] = temp; // 插入
        }
    }
}

//--------------------折半插入排序--------------------
void InsertHaftSort(int A[], int n) {
    int i, j, low, high, mid;
    for (i = 1; i < n; i++) {
        int temp = A[i];
        low = 0; high = i - 1; // 折半查找范围
        while (low <= high) {
            mid = (low + high) / 2;
            if (A[mid] > temp)
                high = mid - 1; // 查找左子表
            else
                low = mid + 1; // 查找右子表
        }
        for (j = i - 1; j >= low; j--)
            A[j + 1] = A[j]; // 后移元素,空出插入位置
        A[low] = temp; // 插入
    }
}

//--------------------希尔排序--------------------
void ShellSort(int A[], int n) {
    int d, i, j;
    // A[0]只是暂存单元,不是哨兵,当j<=0时,插入位置已到
    for (d = n / 2; d >= 1; d /= 2) { // 步长变化
        for (i = d; i < n; i++) {
            if (A[i] < A[i - d]) { // 需将A[i]插入有序增量子表
                int temp = A[i];
                for (j = i - d; j >= 0 && temp < A[j]; j -= d) {
                    A[j + d] = A[j]; // 记录后移
                }
                A[j + d] = temp; // 插入
            }
        }
    }
}

//--------------------冒泡排序--------------------
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; // 本趟遍历没有发生交换,说明已经有序
    }
}

//--------------------快速排序--------------------
int Partition(int A[], int low, int high) {
    int pivot = A[low]; // 第一个元素作为基准
    while (low < high) {
        while (low < high && A[high] >= pivot) // high指针不断左移,直到找到比基准元素小的
            high--;
        A[low] = A[high]; // 比基准小的元素左移
        while (low < high && A[low] <= pivot) // low指针不断右移,直到找到比基准元素大的
            low++;
        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); // 划分右子表
    }
}

//--------------------选择排序--------------------
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]);
    }
}

//---------------------堆排序--------------------
void HeapAdjust(int A[], int k, int len) {
    int temp = A[k]; // A[0]暂存子树根结点
    for (int i = 2 * k + 1; i < len; i = 2 * i + 1) { // 沿key较大的子结点向下筛选
        if (i + 1 < len && A[i] < A[i + 1]) // 取key较大的子结点的下标
            i++;
        if (temp >= A[i])
            break; // 筛选结束
        else {
            A[k] = A[i]; // 将A[i]调整到双亲结点上
            k = i; // 修改k值,以便继续向下筛选
        }
    }
    A[k] = temp; // 被筛选结点的值放入最终位置
}

// 建立大根堆
void BuildMaxHeap(int A[], int len) {
    for (int i = len / 2 - 1; i >= 0; i--) // 从后往前调整所有非终端结点
        HeapAdjust(A, i, len);
}

// 堆排序完整逻辑
void HeapSort(int A[], int len) {
    BuildMaxHeap(A, len); // 初始建堆
    for (int i = len - 1; i > 0; i--) {
        swap(&A[i], &A[0]); // 堆顶和堆底元素交换
        HeapAdjust(A, 0, i); // 把剩余的待排序元素整理成堆
    }
}

//---------------------归并排序--------------------
void Merge(int A[], int B[], int low, int mid, int high) {
    int i, j, k;
    for (k = low; k <= high; k++) { // 将A中所有元素复制到B
        B[k] = A[k];
    }
    for (i = low, j = mid + 1, k = low; i <= mid && j <= high; k++) {
        if (B[i] <= B[j]) { // 较小值复制到A中
            A[k] = B[i++];
        } else {
            A[k] = B[j++];
        }
    }
    while (i <= mid) A[k++] = B[i++];
    while (j <= high) A[k++] = B[j++];
}

void MergeSort(int A[], int B[], int low, int high) {
    if (low < high) {
        int mid = (low + high) / 2; // 从中间划分
        MergeSort(A, B, low, mid); // 对左半部分归并排序
        MergeSort(A, B, mid + 1, high); // 对右半部分归并排序
        Merge(A, B, low, mid, high); // 归并
    }
}

int main() {
    int A[] = {34, 8, 64, 51, 32, 21};
    int n = sizeof(A) / sizeof(A[0]);

    printf("Insertion Sort:\n");
    InsertSort(A, n);
    for (int i = 0; i < n; i++) printf("%d ", A[i]);
    printf("\n");

    int B[] = {34, 8, 64, 51, 32, 21};
    printf("Binary Insertion Sort:\n");
    InsertHaftSort(B, n);
    for (int i = 0; i < n; i++) printf("%d ", B[i]);
    printf("\n");

    int C[] = {34, 8, 64, 51, 32, 21};
    printf("Shell Sort:\n");
    ShellSort(C, n);
    for (int i = 0; i < n; i++) printf("%d ", C[i]);
    printf("\n");

    int D[] = {34, 8, 64, 51, 32, 21};
    printf("Bubble Sort:\n");
    BubbleSort(D, n);
    for (int i = 0; i < n; i++) printf("%d ", D[i]);
    printf("\n");

    int E[] = {34, 8, 64, 51, 32, 21};
    printf("Quick Sort:\n");
    QuickSort(E, 0, n - 1);
    for (int i = 0; i < n; i++) printf("%d ", E[i]);
    printf("\n");

    int F[] = {34, 8, 64, 51, 32, 21};
    printf("Selection Sort:\n");
    SelectSort(F, n);
    for (int i = 0; i < n; i++) printf("%d ", F[i]);
    printf("\n");

    int G[] = {34, 8, 64, 51, 32, 21};
    printf("Heap Sort:\n");
    HeapSort(G, n);
    for (int i = 0; i < n; i++) printf("%d ", G[i]);
    printf("\n");

    int H[] = {34, 8, 64, 51, 32, 21};
    int *tempB = (int *)malloc(n * sizeof(int));
    printf("Merge Sort:\n");
    MergeSort(H, tempB, 0, n - 1);
    for (int i = 0; i < n; i++) printf("%d ", H[i]);
    printf("\n");

    free(tempB);

    return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/648290.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

PCL 二维凸包切片法计算树冠体积

目录 一、算法原理1、原理概述2、参考文献二、代码实现三、结果展示本文由CSDN点云侠原创,原文链接。如果你不是在点云侠的博客中看到该文章,那么此处便是不要脸的爬虫与GPT。 一、算法原理 1、原理概述 二维凸包法是先将树冠等间隔分层切片,如图(e)采用二维凸包算法对每层…

中国改革报是什么级别的报刊?在哪些领域具有较高的影响力?

中国改革报是什么级别的报刊&#xff1f;在哪些领域具有较高的影响力&#xff1f; 《中国改革报》是国家发展和改革委员会主管的全国性综合类报纸。它在经济领域和改革发展方面具有重要的影响力&#xff0c;是传递国家政策、反映改革动态的重要平台。该报对于推动中国的经济改…

实验室课程|基于SprinBoot+vue的实验室课程管理系统(源码+数据库+文档)

实验室课程管理系统 目录 基于SprinBootvue的实验室课程管理系统 一、前言 二、系统设计 三、系统功能设计 1管理员功能模块 2学生功能模块 3教师功能模块 四、数据库设计 五、核心代码 六、论文参考 七、最新计算机毕设选题推荐 八、源码获取&#xff1a; 博主介…

PyTorch深度学习实战(44)——基于 DETR 的目标检测模型

PyTorch深度学习实战&#xff08;44&#xff09;——基于 DETR 的目标检测模型 0. 前言1. Transformer1.1 Transformer 基础1.2 Transformer 架构 2. DETR2.1 DETR 架构2.2 实现 DETR 模型 3. 基于 DETR 实现目标检测3.1 数据加载与模型构建3.2 模型训练与测试 小结系列链接 0.…

WindowsCMD窗口配置OhMyPosh

WindowsCMD窗口配置OhMyPosh 文章目录 WindowsCMD窗口配置OhMyPosh1. 按装Clink1. 安装Oh-My-Posh2. 安装Clink2. 安装后的位置 2. 编写Lua脚本1. oh-my-posh Lua脚本2. 重启cmd窗口看效果 OhMyPosh对Windows CMD 没有现成的支持。 然而可以使用Clink来做到这一点&#xff0c;它…

深度学习——自己的训练集——训练模型(CNN)

训练模型 1.导入必要的库2.加载类别名称3.创建标签映射字典4.加载图像数据和对应的标签5.构建和编译CNN模型6.训练模型7.保存训练好的模型 1.导入必要的库 导入处理数据和训练模型时需要的库 os: 这个模块提供了与操作系统交互的功能&#xff0c;比如文件和目录操作。 cv2: 这…

2024-5-10-从0到1手写配置中心Config之Spring Value热更新

定义SpringValueProcessor处理类 实现BeanPostProcessor后置处理器接口&#xff0c;扫描所有的Spring value&#xff0c;保存起来。实现ApplicationListener接口&#xff0c;在配置变更时&#xff0c;更新所有的spring value 实现BeanPostProcessor后置处理器接口 实现postPr…

移动云:连接未来的智慧之旅

随着数字化转型的加速&#xff0c;云服务在各行各业中的应用越来越广泛。移动云不仅提供了灵活的计算和存储资源&#xff0c;还通过创新的技术手段&#xff0c;为企业和开发者解决了许多实际问题。在这个变革的大背景下&#xff0c;移动云服务作为中国移动倾力打造的云业务品牌…

155. 最小栈

题目&#xff1a; 设计一个支持 push &#xff0c;pop &#xff0c;top 操作&#xff0c;并能在常数时间内检索到最小元素的栈。 实现 MinStack 类: MinStack() 初始化堆栈对象。void push(int val) 将元素val推入堆栈。void pop() 删除堆栈顶部的元素。int top() 获取堆栈顶…

深入解析内置模块OS:让你的Python代码更懂操作系统

新书上架~&#x1f447;全国包邮奥~ python实用小工具开发教程http://pythontoolsteach.com/3 欢迎关注我&#x1f446;&#xff0c;收藏下次不迷路┗|&#xff40;O′|┛ 嗷~~ 目录 一、OS模块简介与基础应用 二、文件与目录操作详解 三、OS模块的高级应用&#xff1a;双色…

【算法】前缀和——除自身以外数组的乘积

本节博客是用前缀和算法求解“除自身以外数组的乘积”&#xff0c;有需要借鉴即可。 目录 1.题目2.前缀和算法3.变量求解4.总结 1.题目 题目链接&#xff1a;LINK 2.前缀和算法 1.创建两个数组 第一个数组第i位置表示原数组[0,i-1]之积第二个数组第i位置表示原数组[i1,n-1]…

How to limit request by IP on nginx?

/etc/nginx/conf.d/default.conf 1.Define a limit_req_zone # 定義限流區塊 limit_req_zone $binary_remote_addr zonelimit_zone:10m rate2r/s; limit_req_zone $binary_remote_addr zonelimit_zone:10m rate2r/s; 是一个 Nginx 配置指令&#xff0c;用于定义请求限制区域和…

【linux】多线程(2)

文章目录 线程的应用生产消费者模型自制锁生产消费队列成员参数生产函数消费函数 任务处理方式主函数 POSIX信号量sem_wait()sem_post() 线程池应用场景示例 单例模式饿汉实现单例 吃完饭, 立刻洗碗, 这种就是饿汉方式. 因为下一顿吃的时候可以立刻拿着碗就能吃饭.懒汉实现单例…

GMSL2硬件设计V1.1

一、说明 GMSL(Gigabit Multimedia Serial Links),中文名称为千兆多媒体串行链路,是Maxim公司(现属于ADI)推出的一种高速串行接口,通过同轴电缆或屏蔽双绞线(STP)传输高速串行数据,用于汽车摄像头和显示器应用。GMSL2就是指ADI专有的第二代千兆多媒体串行链路技术,传输…

重生之while在鸣潮学习HTML

个人主页&#xff1a;终端 今天是开荒的第五天&#xff0c;数据坞都刷了吗&#xff0c;没刷就过来学html&#xff01; 目录 JavaWeb学习路线 1.HTML入门 1.1什么是HTML 1.2HTML&CSS&JavaScript的作用 1.3什么是超文本 1.4什么是标记语言 1.5HTML基础结构 1.6HTML的…

通过acme.sh和cloudflare实现免费ssl证书自动签发

参考使用acme.sh通过cloudflare自动签发免费ssl证书 | LogDicthttps://www.logdict.com/archives/acme.shshi-yong-cloudflarezi-dong-qian-fa-mian-fei-sslzheng-shu

Jmeter-使用手册(_5.5版本)

JMeter是一个Java桌面应用程序&#xff0c;具有使用Swing图形API的图形界面。可以进行接口、性能等测试&#xff0c;也可以对任何数据库进行同样的测试&#xff0c;具有可移植性&#xff0c;可跨平台支持Windows&#xff0c;Linux&#xff0c;Mac上使用。 JMeter运行场景不仅可…

【openlayers系统学习】4.2Mapbox 样式渲染图层

二、Mapbox 样式渲染图层 显然我们目前的地图需要一些样式。 VectorTile​ 图层的样式与 Vector​ 图层的样式工作方式完全相同。那里描述的样式在这里也适用。 对于这样的地图&#xff0c;创建数据驱动的样式&#xff08;对矢量图层操作&#xff09;非常简单。但矢量切片也用…

AIGC 003-Controlnet升级你的SD让图像生成更加可控!

AIGC 003-Controlnet升级你的SD让图像生成更加可控&#xff01; 文章目录 0 论文工作1 论文方法2 效果 0 论文工作 ControlNet 论文 (Adding Conditional Control to Text-to-Image Diffusion Models) 提出了一种名为 ControlNet 的神经网络结构&#xff0c;旨在为大型文本到图…

趣店集团golang一面要个20K,Channel什么情况下会出现死锁,有遇到过吗?

结束后面试官加了VX&#xff0c;并询问方便二面的时间&#xff0c;一直还没回复&#xff0c;拖着拖着给忘啦... 面试题 1、自我介绍 2、你在团队里头负责哪一块&#xff0c;这个物流开放平台流量多大 3、为什么今年3月份被从物流开放团队转到了finance财务部门&#xff0c;感…