AI 助理
备案控制台
开发者社区 人工智能 文章 正文

【数据结构】排序-C语言版（一）

2023-02-07 94
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 【数据结构】排序-C语言版

各类排序算法基本思想是什么？如何实现？时间复杂度分别是多少？稳定吗？

常见的排序算法有如下7种：


一、插入排序


插入排序基本思想：把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列 。

1.直接插入排序

当插入第i(i>=1)个元素时，前面的array[0],array[1],…,array[i-1]已经排好序，此时用array[i]的排序码与 array[i-1],array[i-2],…的排序码顺序进行比较，找到插入位置即将array[i]插入，原来位置上的元素顺序后移

055-InsertSort.h 

1. #pragma once
2. #include<stdio.h>
3. #include <stdlib.h>
4. 
5. 
6. //打印
7. void Print(int* a, int n);
8. 
9. //直接插入排序
10. void InsertSort(int* a, int n);

055-InsertSort.c

1. #include "055-InsertSort.h"
2. 
3. //打印
4. void Print(int* a, int n)
5. {
6.  for (int i = 0; i < n; i++)
7.  {
8.    printf("%d ", a[i]);
9.  }
10. 
11.   printf("\n");
12. }
13. 
14. //直接插入排序
15. void InsertSort(int* a, int n)
16. {
17.   //多趟排序
18.   for (int i = 0; i < n - 1; i++)
19.   {
20.     //把temp插入到数组的[0,end]有序区间中
21.     int end = i;
22.     int temp = a[end + 1];
23.     while (end >= 0)
24.     {
25.       if (temp < a[end])
26.       {
27.         a[end + 1] = a[end];
28.         end--;
29.       }
30.       else
31.       {
32.         break;
33.       }
34.     }
35. 
36.     a[end + 1] = temp;
37. 
38.   }
39. 
40. }

055-TestInsertSort.c

1. #include "055-InsertSort.h"
2. 
3. void TestInsertSort()
4. {
5.  int arr[] = { 9,1,2,5,7,4,8,6,3,5 };
6.  InsertSort(arr, sizeof(arr) / sizeof(arr[0]));
7.  Print(arr, sizeof(arr)/sizeof(arr[0]));
8. }
9. 
10. int main()
11. {
12.   TestInsertSort();
13. 
14.   return 0;
15. }

直接插入排序的特性总结：

(1) 元素集合越接近有序，直接插入排序算法的时间效率越高

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

(3) 空间复杂度：O(1)，它是一种稳定的排序算法

(4) 稳定性：稳定

2、希尔排序

希尔排序法又称缩小增量法。基本思想：先选定一个整数，把待排序文件中所有记录分成个 组，所有距离为的记录分在同一组内，并对每一组内的记录进行排序。然后，取，重复上述分组和排序的工作。当到达=1时，所有记录在统一组内排好序。

055-ShellSort.h

1. #pragma once
2. #include<stdio.h>
3. #include <stdlib.h>
4. 
5. //打印
6. void Print(int* a, int n);
7. 
8. //希尔排序
9. void ShellSort(int* a, int n);

055-ShellSort.c

1. #include "055-ShellSort.h"
2. 
3. //打印
4. void Print(int* a, int n)
5. {
6.  for (int i = 0; i < n; i++)
7.  {
8.    printf("%d ", a[i]);
9.  }
10. 
11.   printf("\n");
12. }
13. 
14. //希尔排序 - 先分组，对分组的数据，插入排序
15. //1.预排序-接近有序
16. //2.直接插入
17. void ShellSort(int* a, int n)
18. {
19.   //gap>1的时候，预排序
20.   //gap==1的时候，直接插入排序
21.   int gap = n;
22.   while (gap > 1)
23.   {
24. 
25.     gap = gap / 3 + 1;
26.     for (int i = 0; i < n - gap; i++)
27.     {
28.       //把temp插入到数组的[0,end]有序区间中
29.       int end = i;
30.       int temp = a[end + gap];
31.       while (end >= 0)
32.       {
33.         if (temp < a[end])
34.         {
35.           a[end + gap] = a[end];
36.           end -= gap;
37.         }
38.         else
39.         {
40.           break;
41.         }
42. 
43.       }
44.       a[end + gap] = temp;
45. 
46.     }
47.     //printf("gap:%d-> ", gap);
48.     //Print(a, n);
49.   }
50. }

055-TestShellSort.c

1. #include " 055-ShellSort.h"
2. 
3. void TestShellSort()
4. {
5.  int arr[] = { 10,7,8,9,6,5,4,3,2,1,0,-1,-2,-3,-4,-5,-6,-7,-8,-9 };
6.  ShellSort(arr, sizeof(arr) / sizeof(arr[0]));
7.  Print(arr, sizeof(arr) / sizeof(arr[0]));
8. }
9. 
10. int main()
11. {
12.   TestShellSort();
13. 
14.   return 0;
15. }

希尔排序特性总结：

（1）希尔排序是对直接插入排序的优化。

（2） 当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很快。整体而言，达到了优化的效果。

（3） 希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，因此在好些树中给出的希尔排序的时间复杂度都不固定，实验和基础上推断时间复杂度为O(N^1.3)。

       ① 最坏的情况是逆序时，gap很大时，while循环的时间复杂度为O(N)

       ② 当gap很小时，本来应该是O(N*N) ，但是经过预排序后，数组已经接近有序，所以这里还是O(N)

（4） 稳定性：不稳定


二、选择排序

选择排序基本思想：每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完 。

1.直接选择排序

基本思想：

（1）在元素集合array[i]—array[n-1]中选择关键码最大(小)的数据元素。

（2）若它不是这组元素中的最后一个(第一个)元素，则将它与这组元素中的最后一个(第一个)元素交换。

（3）在剩余的array[i]—array[n-2]（array[i+1]—array[n-1]）集合中，重复上述步骤，直到集合剩余1个元素。

055-SelectSort.h

1. #pragma once
2. #include<stdio.h>
3. #include <stdlib.h>
4. 
5. //打印
6. void Print(int* a, int n);
7. 
8. //直接选择排序
9. void SelectSort(int* arr, int n);

055-SelectSort.c

1. #include"055-SelectSort.h"
2. 
3. //打印
4. void Print(int* a, int n)
5. {
6.  for (int i = 0; i < n; i++)
7.  {
8.    printf("%d ", a[i]);
9.  }
10. 
11.   printf("\n");
12. }
13. 
14. void Swap(int* p1, int* p2)
15. {
16.   int temp = *p1;
17.   *p1 = *p2;
18.   *p2 = temp;
19. }
20. 
21. //直接选择排序
22. void SelectSort(int* a, int n)
23. {
24.   int left = 0, right = n - 1;
25.   while (left < right)
26.   {
27.     //选出最大的值和最小的值
28.     int maxIndex = left, minIndex = left;
29.     for (int i = left; i <= right; i++)
30.     {
31.       if (a[i] < a[minIndex])
32.       {
33.         minIndex = i;
34.       }
35.       if (a[i] > a[maxIndex])
36.       {
37.         maxIndex = i;
38.       }
39.     }
40.     Swap(&a[left], &a[minIndex]);
41. 
42.     //如果maxIndex和left位置重叠，那么maxIndex位置的书就被换走了，要修正一下max的位置
43.     if (maxIndex == left)
44.     {
45.       maxIndex = minIndex;
46.     }
47. 
48.     Swap(&a[right], &a[maxIndex]);
49.     ++left;
50.     --right;
51.   } 
52. }

055-TestSelectSort.c

1. #include "055-SelectSort.h"
2. 
3. void TestSelectSort()
4. {
5.  int arr[] = { 10,9,8,7 6,5,4,3,2,1};
6.  SelectSort(arr, sizeof(arr) / sizeof(arr[0]));
7. 
8.  Print(arr, sizeof(arr) / sizeof(arr[0]));
9. }
10. 
11. int main()
12. {
13.   TestSelectSort();
14. 
15.   return 0;
16. }

直接选择排序的特性总结：

（1）直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用

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

（3）空间复杂度：O(1)

（4）稳定性：不稳定

2.堆排序

堆排序(Heapsort)是利用堆这种数据结构所设计的一种排序算法，它是选择排序的一种。通过堆来进行选择数据。需要注意的是排升序要建大堆，排降序建小堆。堆的排序过程请查看文章【数据结构】堆-C语言版一文中堆的排序小节

055-HeapSort.h

1. #pragma once
2. #include<stdio.h>
3. #include<stdlib.h>
4. 
5. //打印
6. void Print(int* a, int n);
7. 
8. //堆排序
9. void HeapSort(int* arr, int n);

055-HeapSort.c

1. #include "055-HeapSort.h"
2. 
3. //打印
4. void Print(int* a, int n)
5. {
6.  for (int i = 0; i < n; i++)
7.  {
8.    printf("%d ", a[i]);
9.  }
10. 
11.   printf("\n");
12. }
13. 
14. void Swap(int* p1, int* p2)
15. {
16.   int temp = *p1;
17.   *p1 = *p2;
18.   *p2 = temp;
19. }
20. 
21. //向下调整
22. void AdjustDown(int* a, int n, int parent)
23. {
24.   int child = parent * 2 + 1;
25.   while (child < n)
26.   {
27.     //选出左右孩子中的小孩子，建大堆就把第二个<改成>
28.     if (child + 1 < n && a[child + 1] > a[child])
29.     {
30.       child++;
31.     }
32.     //小孩子比父亲小，交换小孩子和父亲，建大堆就把<改成>
33.     if (a[child] > a[parent])
34.     {
35.       Swap(&a[child], &a[parent]);
36.       //交换父亲和孩子后，可能导致不满足堆的定义，需要继续调整
37.       parent = child;
38.       child = parent * 2 + 1;
39.     }
40.     //小孩子比父亲大，跳出while循环，结束这一次的向下调整，否则一直死循环并且什么都不做
41.     else
42.     {
43.       break;
44.     }
45.   }
46. }
47. 
48. //堆排序
49. void HeapSort(int* a, int n)
50. {
51.   //升序，建大堆
52.   for (int i = (n - 1 - 1) / 2; i >= 0; i--)
53.   {
54.     AdjustDown(a, n, i);
55.   }
56.   int end = n - 1;
57.   while (end > 0)
58.   {
59.     Swap(&a[0], &a[end]);
60.     AdjustDown(a, end, 0);
61.     end--;
62.   }
63. }

055-TestHeapSort.c

1. #include "055-HeapSort.h"
2. 
3. void TestHeapSort()
4. {
5.  int arr[] = { 10,9,8,7 };
6.  HeapSort(arr, sizeof(arr) / sizeof(arr[0]));
7.  Print(arr, sizeof(arr) / sizeof(arr[0]));
8. }
9. 
10. int main()
11. {
12.   TestHeapSort();
13. 
14.   return 0;
15. }

堆排序的特性总结：

（1）堆排序使用堆来选数，效率就高了很多。

（2）时间复杂度：O(N*logN)

（3）空间复杂度：O(1)

（4）稳定性：不稳定


文章标签：
机器学习/深度学习
搜索推荐
关键词：
排序C语言
数据结构c语言
C语言数据结构
C语言排序
数据结构排序
玲娜贝儿～
目录
相关文章
ephemerals__
|
14天前
|
C语言
【数据结构】栈和队列（c语言实现）（附源码）
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表，遵循“先进后出”原则；队列则在一端插入、另一端删除，遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现，并提供了完整的代码示例。栈和队列在实际应用中非常广泛，如二叉树的层序遍历和快速排序的非递归实现等。
ephemerals__
90 9
ephemerals__
|
13天前
|
存储 搜索推荐 算法
【数据结构】树型结构详解 + 堆的实现（c语言）（附源码）
本文介绍了树和二叉树的基本概念及结构，重点讲解了堆这一重要的数据结构。堆是一种特殊的完全二叉树，常用于实现优先队列和高效的排序算法（如堆排序）。文章详细描述了堆的性质、存储方式及其实现方法，包括插入、删除和取堆顶数据等操作的具体实现。通过这些内容，读者可以全面了解堆的原理和应用。
ephemerals__
56 16
ephemerals__
|
9天前
|
搜索推荐 算法 C语言
【排序算法】八大排序（上）（c语言实现）（附源码）
本文介绍了四种常见的排序算法：冒泡排序、选择排序、插入排序和希尔排序。通过具体的代码实现和测试数据，详细解释了每种算法的工作原理和性能特点。冒泡排序通过不断交换相邻元素来排序，选择排序通过选择最小元素进行交换，插入排序通过逐步插入元素到已排序部分，而希尔排序则是插入排序的改进版，通过预排序使数据更接近有序，从而提高效率。文章最后总结了这四种算法的空间和时间复杂度，以及它们的稳定性。
ephemerals__
50 8
ephemerals__
|
9天前
|
搜索推荐 算法 C语言
【排序算法】八大排序（下）（c语言实现）（附源码）
本文继续学习并实现了八大排序算法中的后四种：堆排序、快速排序、归并排序和计数排序。详细介绍了每种排序算法的原理、步骤和代码实现，并通过测试数据展示了它们的性能表现。堆排序利用堆的特性进行排序，快速排序通过递归和多种划分方法实现高效排序，归并排序通过分治法将问题分解后再合并，计数排序则通过统计每个元素的出现次数实现非比较排序。最后，文章还对比了这些排序算法在处理一百万个整形数据时的运行时间，帮助读者了解不同算法的优劣。
ephemerals__
36 7
ephemerals__
|
13天前
|
C语言
【数据结构】二叉树（c语言）（附源码）
本文介绍了如何使用链式结构实现二叉树的基本功能，包括前序、中序、后序和层序遍历，统计节点个数和树的高度，查找节点，判断是否为完全二叉树，以及销毁二叉树。通过手动创建一棵二叉树，详细讲解了每个功能的实现方法和代码示例，帮助读者深入理解递归和数据结构的应用。
ephemerals__
62 8
ephemerals__
|
16天前
|
存储 C语言
【数据结构】手把手教你单链表（c语言）（附源码）
本文介绍了单链表的基本概念、结构定义及其实现方法。单链表是一种内存地址不连续但逻辑顺序连续的数据结构，每个节点包含数据域和指针域。文章详细讲解了单链表的常见操作，如头插、尾插、头删、尾删、查找、指定位置插入和删除等，并提供了完整的C语言代码示例。通过学习单链表，可以更好地理解数据结构的底层逻辑，提高编程能力。
ephemerals__
44 4
ephemerals__
|
17天前
|
存储 C语言
【数据结构】顺序表（c语言实现）（附源码）
本文介绍了线性表和顺序表的基本概念及其实现。线性表是一种有限序列，常见的线性表有顺序表、链表、栈、队列等。顺序表是一种基于连续内存地址存储数据的数据结构，其底层逻辑是数组。文章详细讲解了静态顺序表和动态顺序表的区别，并重点介绍了动态顺序表的实现，包括初始化、销毁、打印、增删查改等操作。最后，文章总结了顺序表的时间复杂度和局限性，并预告了后续关于链表的内容。
ephemerals__
49 3
ephemerals__
|
16天前
|
C语言
【数据结构】双向带头循环链表（c语言）（附源码）
本文介绍了双向带头循环链表的概念和实现。双向带头循环链表具有三个关键点：双向、带头和循环。与单链表相比，它的头插、尾插、头删、尾删等操作的时间复杂度均为O(1)，提高了运行效率。文章详细讲解了链表的结构定义、方法声明和实现，包括创建新节点、初始化、打印、判断是否为空、插入和删除节点等操作。最后提供了完整的代码示例。
ephemerals__
37 0
白子寰
|
1月前
|
C语言 C++
C语言 之 内存函数
C语言 之 内存函数
白子寰
33 3
文艺小青年
|
人工智能 C语言 机器学习/深度学习
C语言：实现N个整数排序，并插入一个整数！
文艺小青年
1219 0

热门文章

最新文章

  • 1
    C语言中的逗号操作符
  • 2
    《C语言及程序设计》实践参考——改造链表
  • 3
    C语言连接MySQL数据库
  • 4
    C语言中用于计算数组长度的函数 “strlen（） ”。
  • 5
    C语言预处理之二-----宏定义那点事儿
  • 6
    《C语言程序设计进阶教程》一第3章 预防、检测及消除bug
  • 7
    《C语言及程序设计》实践项目——数据的输入
  • 8
    C语言库函数大全及应用实例十
  • 9
    C语言中大小写字母的转化
  • 10
    【C语言进阶】字符串函数与内存函数的学习与模拟实现（上）
  • 1
    `geopandas`是一个开源项目，它为Python提供了地理空间数据处理的能力。它基于`pandas`库，并扩展了其对地理空间数据（如点、线、多边形等）的支持。`GeoDataFrame`是`geopandas`中的核心数据结构，它类似于`pandas`的`DataFrame`，但包含了一个额外的地理列（通常是`geometry`列），用于存储地理空间数据。
    69
  • 2
    “解锁Python高级数据结构新姿势：图的表示与遍历，让你的算法思维跃升新高度
    40
  • 3
    Redis数据结构—跳跃表 skiplist 实现源码分析
    62
  • 4
    逆袭之路！用 Python 玩转图的 DFS 与 BFS，让数据结构难题无处遁形
    65
  • 5
    Python中的列表（List）和元组（Tuple）是两种重要的数据结构
    53
  • 6
    【数据结构OJ题】链表分割
    32
  • 7
    【数据结构常见七大排序（三）上】—交换排序篇【冒泡排序】And【快速排序】
    45
  • 8
    【数据结构常见七大排序（二）】—选择排序篇【直接选择排序】And【堆排序】
    33
  • 9
    【数据结构常见七大排序（一）】—插入排序篇【直接插入排序】And【希尔排序】
    45
  • 10
    【数据结构OJ题】链表的回文结构
    39

    • 相关课程

    更多
  • Go语言核心编程 - 数据结构和算法
  • 你的第一门C语言课
  • C语言学习教程
  • Go语言核心编程 - 基础语法、数组、切片、Map

    • 相关电子书

    更多
  • 如何使用Tair增强数据结构构建丰富在线实时场景
  • Apache Flink 流式应用中状态的数据结构定义升级
  • 低代码开发师（初级）实战教程
    • 下一篇
    阿里云OSS设置跨域访问