2025年Sorting 排序详解(c语言实现)

Sorting 排序详解(c语言实现)Sorting 排序详解 c 语言实现 今日突然有任务 明天补充完整 邮箱 期待交流 Hello 各位小伙伴 我是你们的课代表橙橙 今天呢我要给大家分享的是关于内排序的四种算法 插入排序 交换排序 选择排序 归并排序

大家好,我是讯享网,很高兴认识大家。

Sorting 排序详解(c语言实现)#

今日突然有任务,明天补充完整。
邮箱:期待交流。

Hello,各位小伙伴~我是你们的课代表橙橙,今天呢我要给大家分享的是关于内排序的四种算法:插入排序、交换排序、选择排序、归并排序。

我会先向大家详细的叙述这四种排序算法的内容(推荐书籍
《大话数据结构》入门),然后再和大家一起细致的去分析这几种算法(推荐书籍 《算法4》深入了解 )。(备注:说到推荐算法类书籍,《算法导论》怎么能少呢!但是奈何橙橙几次下定决心去啃都啃失败后,还是建议各位少侠先挑软骨头啃啦~)

在开始介绍算法前,我们先梳理几个关于排序的基本概念:

  1. 排序中的数据元素被称为记录;
  2. 排序的稳定性 : 是评判一个算法的重要指标
    如果一组记录排序前为(按照字母顺序排序):
    服装,安慕希,凳子,包子,灯笼,鳄鱼,菜包
    排序后为:
    安慕希,包子,菜包,凳子,灯笼,鳄鱼,服装

我们可以清晰地看到,排序前后“凳子”和“灯笼”的相对位置没有发生改变,则称我们本次的排序方法是稳定的;反之,为不稳定的。

  1. 内、外排序
    内排序: 排序的整个过程,待排序的记录全部被放在内存中;
    外排序:待排序的记录的个数太多,不能同时放置在内存中,整个排序过程需要在内外存之间多次交换数据才行。
    注:本篇博客只讲内排序。
  2. 算法的性能
  • 时间性能
  • 辅助空间
  • 算法的复杂性
    (对这部分有问题的可以去复习一下数据结构的课本)

接下来介绍的算法有:

  • 冒泡排序(简化版、正宗版)
  • 选择排序(简单选择排序、堆排序)
  • 插入排序(直接插入排序、希尔排序)
  • 分治思想法排序(归并排序、快速排序)

在算法详解前,先贴出完整的代码,大家可以根据代码来看算法,这样可能会更加容易理解。


讯享网

/*Author:Kim 

讯享网

邮箱:
Topic:Sorting
如果我的代码或者博客对你有一丝帮助的话,麻烦给我点个赞相互鼓励一下
*/

讯享网#include <stdio.h> #include <stdlib.h> #define MAXSIZE 10 #define true 1 #define false 0 // 数据结构准备 typedef struct { int r[MAXSIZE + 1];// r[0]用作哨兵或者临时变量 int length; }SqList; // 排序 = 比较 +移动 // 移动函数 void swap(SqList* L, int i, int j) { int k; k = L->r[i]; L->r[i] = L->r[j]; L->r[j] = k; } void show(SqList *L) { int i; for (i = 1; i < L->length; i++) printf(" %d", L->r[i]); } //------------------------------------------------- //冒泡排序 void BubbleSort0(SqList* L) { int i, j; for (i = 1; i <= L->length; i++){ for (j = i+1; j <= L->length; j++){ if (L->r[i] > L->r[j]) { swap(L,i, j); show(L); printf("\n"); } } } } void BubbleSort(SqList* L){ int i,j; // 用来检测,当记录已经有序时则结束循环 int flag = true; for(i=1;i<=L->length&&flag;i++){ flag = false; for(j=L->length;j>i;j--){ if(L->r[j]<L->r[j-1]){ swap(L,j,j-1); flag = true; } } show(L); printf("\n"); } } void SelectSort(SqList* L){ int i,j,min; for(i=1;i<=L->length;i++){ min = i; for(j=i+1;j<=L->length;j++){ if(L->r[min]>L->r[j]) min = j; } if(min!=i) swap(L,min,i); show(L); printf("\n"); } } void InsertSort(SqList* L){ int i,j; for(i=2;i<L->length;i++){ if(L->r[i]<L->r[i-1]){ L->r[0] = L->r[i]; for(j=i-1;j>0&&L->r[0]<L->r[j];j--){ L->r[j+1] = L->r[j]; } L->r[j+1] = L->r[0]; } show(L); printf("\n"); } } void ShellSort(SqList* L){ int i,len=L->length; do{ len = len/2+1; for(i=1;(i+len)<=L->length;i++){ if(L->r[i]>L->r[i+len]) swap(L,i,i+len); } }while(len!=1); printf("已排成一个大致有序的序列\n"); show(L); printf("进行简单插入排序:\n"); InsertSort(L); } void HeapSort(SqList* L){ int i; for(i=L->length/2;i>0;i--){ HeapAdjust(L,i,L->length); } for(i=L->length;i>=1;i--){ swap(L,1,i); HeapAdjust(L,1,i-1); show(L); printf("\n"); } } void HeapAdjust(SqList* L,int s,int m){ int temp,j; temp=L->r[s]; for(j=2*s;j<=m;j++){ if(j<m&&L->r[j]<L->r[j+1]) ++j; if(temp>=L->r[j]) break; L->r[s] = L->r[j]; s=j; } L->r[s] = temp; } int main(void) { int i; //数据准备 SqList* L = (SqList*)malloc(sizeof(SqList)); L->length = 9;// 0号房间用来做哨兵或者临时变量 int arr[10] = { 114,135,156,181,119,156,172,146,183,177 }; for (i = 0; i < 10; i++) L->r[i + 1] = arr[i]; printf("排序前:\n"); show(L); printf("\n"); //------------------简化版冒泡排序--------------------- printf("冒泡排序:\n"); BubbleSort0(L); //------------------正宗冒泡排序--------------------- for (i = 0; i < 10; i++) L->r[i + 1] = arr[i]; printf("正宗冒泡排序:\n"); BubbleSort(L); //------------------选择排序--------------------- for (i = 0; i < 10; i++) L->r[i + 1] = arr[i]; printf("简单选择排序:\n"); SelectSort(L); //------------------直接插入排序--------------------- for (i = 0; i < 10; i++) L->r[i + 1] = arr[i]; printf("直接插入排序:\n"); InsertSort(L); //------------------希尔排序--------------------- for (i = 0; i < 10; i++) L->r[i + 1] = arr[i]; printf("希尔排序:\n"); ShellSort(L); //------------------希尔排序--------------------- for (i = 0; i < 10; i++) L->r[i + 1] = arr[i]; printf("堆排序:\n"); HeapSort(L); return 0; } 

1 . 冒泡排序
冒泡排序一种交换排序,它的基本思想是:两两比较相邻记录的关键字,如果反序则交换,知道没有反序为止。可以简单记忆为,大泡下降,小泡上升。

2. 选择排序
简单选择排序法是通过n-i次关键字间的比较,从n-i+1个记录中选出关键字最小的记录,并和第i(1<=i<=n)个记录交换。

3. 直接插入排序

3.1 直接插入排序
直接插入排序的基本操作是将一个记录插入到已经排好序的有序表中,从而得到一个新的、记录数加1的有序表。(如果觉得理解起来有困难的话建立,摸一手牌,跟着代码走一遍你就再也不会忘记了(๑╹◡╹)ノ""")

3.2 希尔排序
我们在前一节将的直接插入排序,应该说它的效率在某些时候是很高的,比如,我们的记录本身就是基本有序的;还有就是记录数比较少时,直接插入的优势也是很明显的。可问题就在于这两个条件本身就过于苛刻,现实中记录少或者基本有序都属于特殊的情况。
不过别急,有条件当然是好,条件不存在嘛,我们创造条件也是可以去做的。于是就有了希尔排序。
希尔排序 = 跳跃分割 + 直接插入排序

4. 堆排序
首先介绍一下堆:
堆是具有下列性质的完全二叉树:每个节点的值都大于或者等于其左右孩子结点的值,成为大顶堆;或者每个结点的值都小于或者等于其左右孩子结点的值,称为小顶堆。
堆排序算法:将待排序的序列构造成一个大顶堆。此时,整个序列的最大值就是堆顶的根节点。将它移走(其实就是将其与堆数组的末尾元素交换,此时末尾元素就是最大值),然后将剩余的n-1个序列重新构造成一个堆,这样就会得到n个元素的次大值。如此反复执行,便能够得到一个有序序列了。

小讯
上一篇 2025-03-15 17:02
下一篇 2025-04-09 15:51

相关推荐

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容,请联系我们,一经查实,本站将立刻删除。
如需转载请保留出处:https://51itzy.com/kjqy/131754.html