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

文章目录

  • 八、排序
    • 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; //查找左子表elselow=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; // 查找左子表elselow = 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中所有元素复制到BB[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;
}

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

基于遗传优化的Sugeno型模糊控制器设计matlab仿真

目录 1.课题概述 2.系统仿真结果 3.核心程序与模型 4.系统原理简介 5.完整工程文件 1.课题概述 基于遗传优化的Sugeno型模糊控制器设计matlab仿真,通过遗传优化算法优化模糊控制器的隶属函数参数&#xff0c;从而获得较优的控制效果。 2.系统仿真结果 3.核心程序与模型 …

如何将前端项目打包并部署到不同服务器环境

学习源码可以看我的个人前端学习笔记 (github.com):qdxzw/frontlearningNotes 觉得有帮助的同学&#xff0c;可以点心心支持一下哈&#xff08;笔记是根据b站尚硅谷的前端讲师【张天禹老师】整理的&#xff0c;用于自己复盘&#xff0c;有需要学习的可以去b站学习原版视频&…

新书推荐:7.3 for语句

本节必须掌握的知识点&#xff1a; 示例二十四 代码分析 汇编解析 7.3.1 示例二十四 ■for语句语法形式&#xff1a; for(表达式1;表达式2;表达式3) { 语句块; } ●语法解析&#xff1a; 第一步&#xff1a;执行表达式1&#xff0c;表达式1初始化循环变量&#xff1b; …

基于PHP的物业管理的设计与实现

第1章 绪论... 1 1.1 研究背景与意义... 1 1.2 国内外发展现状... 2 第2章 关键技术介绍... 3 2.1 PHP语言... 3 2.2 MySQL数据库... 3 2.3 Zend框架... 4 2.4 B/S架构... 4 第3章 系统需求分析... 5 3.1 可行性分析... 5 3.1.1 技术可行性分析... 5 3.1.2 经济可行…

IDEA 2024.1安装与破解

一、下载 官网地址&#xff1a;https://www.jetbrains.com/idea/download/other.html 二、安装 傻瓜式安装即可 三、破解 3.1 破解程序 网站&#xff1a;https://3.jetbra.in/ 3.2 获取激活码 点击*号部分即可复制成功

IOC控制反转

IOC IOC&#xff0c;全称为Inversion of Control(控制反转)&#xff0c;是一种设计原则&#xff0c;它反转了传统编程中的控制流程。在传统的编程模式中&#xff0c;组件之间的依赖关系是由组件自身在内部创建和维护的。而在控制反转模式中&#xff0c;这种依赖关系由外部容器(…

【Docker实战】进入四大数据库的命令行模式

上一篇我们讲了docker exec命令&#xff0c;这一次我们使用docker exec命令来进入四大数据库的命令行模式。 我们进行游戏开发或软件开发是离不开四大数据库的&#xff0c;这四大数据库分别是关系型数据库mysql、postgres&#xff0c;nosql数据库redis、mongodb。将它们容器化…

云上聚智——移动云云服务器进行后端的搭建及部署

什么是移动云 移动云是指将移动设备和云计算技术相结合&#xff0c;为移动应用提供强大的计算和存储能力的服务模式。传统的移动应用通常在本地设备上进行计算和存储&#xff0c;而移动云将这些任务转移到云端进行处理。通过移动云&#xff0c;移动设备可以利用云端的高性能计算…

【C++】——入门基础知识超详解

​​​​​​​ 目录 ​编辑 1.C关键字 2. 命名空间 2.1 命名空间定义 2.2 命名空间使用 命名空间的使用有三种方式&#xff1a; 注意事项 3. C输入&输出 示例 1&#xff1a;基本输入输出 示例 2&#xff1a;读取多个值 示例 3&#xff1a;处理字符串输入 示例…

神经网络不确定性综述(Part II)——Uncertainty estimation_Single deterministic methods

相关链接&#xff1a; 神经网络不确定性综述(Part I)——A survey of uncertainty in deep neural networks-CSDN博客 神经网络不确定性综述(Part II)——Uncertainty estimation_Single deterministic methods-CSDN博客 神经网络不确定性综述(Part III)——Uncertainty est…

Docker-Android安卓模拟器本地部署并实现远程开发测试

文章目录 1. 虚拟化环境检查2. Android 模拟器部署3. Ubuntu安装Cpolar4. 配置公网地址5. 远程访问小结 6. 固定Cpolar公网地址7. 固定地址访问 本文主要介绍如何在Ubuntu系统使用Docker部署docker-android安卓模拟器&#xff0c;并结合cpolar内网穿透工具实现公网远程访问本地…

用常识滚雪球:拼多多的内生价值,九年的变与不变

2024年5月22日&#xff0c;拼多多公布了今年一季度财报&#xff0c;该季度拼多多集团营收868.1亿元&#xff0c;同比增长131%&#xff0c;利润306.0亿&#xff0c;同比增长了202%&#xff0c;数据亮眼。 市场对拼多多经历了“看不见”、“看不懂”、“跟不上”三个阶段。拼多多…

STM32无源蜂鸣器播放音乐

开发板&#xff1a;野火霸天虎V2 单片机&#xff1a;STM32F407ZGT6 开发软件&#xff1a;MDKSTM32CubeMX 文章目录 前言一、找一篇音乐的简谱二、确定音调三、确定节拍四、使用STM32CubeMX生成初始化代码五、代码分析 前言 本实验使用的是低电平触发的无源蜂鸣器 无源蜂鸣器是…

【数据库】通过一个实例来认识数据流图DFD

导读&#xff1a;通过一个实例&#xff08;数据中台&#xff09;说明数据流图DFD的作用、介绍了常见的数据流图元素及其标准符号以及如何画数据流图。数据流图主要被分析师、系统设计师、流程优化专家、系统管理员以及与系统开发和维护相关的人员查看和使用。对于刚考完2024年5…

设计模式 18 迭代器模式 Iterator Pattern

设计模式 18 迭代器模式 Iterator Pattern 1.定义 迭代器模式 (Iterator Pattern) 是一种行为型设计模式&#xff0c;它提供了一种访问集合元素的标准方法&#xff0c;而无需暴露集合的内部表示。 提供一种方法顺序访问一个聚合对象中的各个元素&#xff0c;而又不需要暴露该…

B树与B+树区别

B树和B树是常见的数据库索引结构&#xff0c;都具有相较于二叉树层级较少&#xff0c;查找效率高的特点&#xff0c;它们之间有以下几个主要区别&#xff1a; 1.节点存储数据的方式不同 B树的叶子结点和非叶子节点都会存储数据&#xff0c;指针和数据共同保存在同一节点中B树…

vue 引入 emoji 表情包

vue 引入 emoji 表情包 一、安装二、组件内使用 一、安装 npm install --save emoji-mart-vue二、组件内使用 import { Picker } from "emoji-mart-vue"; //引入组件<picker :include"[people,Smileys]" :showSearch"false" :showPreview&q…

YAML详情

一、kubernetes支持对象 Kubernetes支持YAML和JSON格式管理资源对象 JSON格式&#xff1a;主要用于api接口之间消息的传递YAML格式&#xff1a;用于配置和管理&#xff0c;YAML是一种简洁的非标记性语言&#xff0c;内容格式人性化&#xff0c;较易读 二、YAML语法格式注意点 …

微信小程序开发 tabbar组件常见问题

一、 tabbar不显示问题 问题 刚开始我在app.json中配置了下面的代码&#xff0c;但tabbar并没有显示。代码如下&#xff1a; "tabBar": {"custom": true,"color": "#7A7E83","selectedColor": "#3cc51f","…

C++ | Leetcode C++题解之第113题路径总和II

题目&#xff1a; 题解&#xff1a; class Solution { public:vector<vector<int>> ret;unordered_map<TreeNode*, TreeNode*> parent;void getPath(TreeNode* node) {vector<int> tmp;while (node ! nullptr) {tmp.emplace_back(node->val);node …