十大经典排序算法及其C语言实现--带动图展示

2024-04-11 14:36
文章标签 算法 语言 实现 展示 排序 经典 十大 带动

本文主要是介绍十大经典排序算法及其C语言实现--带动图展示，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

排序算法大概算起来有以下十种

640

一、冒泡排序（Bubble Sort）

冒泡排序（Bubble Sort）也是一种简单直观的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

1.1、动画演示

请添加图片描述

1.2、代码

void swap(int* a, int* b) {int temp = *a;*a = *b;*b = temp;
}void Bubble_sort(int *nums, int length) {for (int i=1; i<length; i++) {for (int j=0; j<length-i; j++) {if (nums[j] > nums[j+1]) {swap(&nums[j],&nums[j+1]);}}}
}

1.3、评价

最快就是当输入的数据是正序时。

最慢就是当输入的数据是反序时。

由于复杂度很高，所以数据量大时几乎不可以使用，但是算法简单，且为原地排序算法。

二、选择排序（Selection Sort）

选择排序是一种简单直观的排序算法，无论什么数据进去都是 O(n²) 的时间复杂度。所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。

2.1、动画演示

请添加图片描述

2.2、代码

void Selection_sort(int *nums, int length) {for (int i=0; i<length-1; i++) {int flag = i;for (int j=i+1; j<length; j++) {if (nums[j] < nums[flag]) flag = j;}swap(&nums[i],&nums[flag]);}
}

2.3、评价

优势是简单直观，选一个最小的放在前面

劣势是时间复杂度高，不适合大规模数据，不适合部分排序

三、插入排序（Insertion sort）

通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

3.1、动画演示

图片

3.2、代码

/* 写法1 */
void Insert_sort(int *nums, int length) {for (int i=1; i<length; i++) {for (int j=i; j>=1; j--) {if (nums[j] < nums[j-1]) {swap(&nums[j],&nums[j-1]);} else {break;}}}
}/* 写法2 */
void Insert_sort2(int *nums, int length) {for (int i=1; i<length; i++) {int temp = nums[i];int j;for (j=i; j>=1 && nums[j-1] > temp; j--) {nums[j] = nums[j-1];}nums[j] = temp;}
}

3.3、评价

插入排序是稳定的排序算法，即相同元素的相对位置在排序后不会改变。

时间复杂度高，不适合大规模数据，且每次插入都需要大量移动数据。

四、希尔排序（Shell sort）

希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。

希尔排序是基于插入排序的以下两点性质而提出改进方法的：

  • 插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率；
  • 但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位；

希尔排序的基本思想是：先选定一个整数gap，把待排序文件中所有元素分成gap组，即所有距离为gap的分在同一组内，并对每一组内的元素进行直接插入排序（本质是进行预排序，使数组更接近有序，目的是使最后一次直接插入排序提高效率）。然后取gap=gap/2或者gap=gap/3+1重复上述分组和排序的工作。当gap到达1时，数组是已经接近有序的，而对于直接插入排序在顺序有序或者接近顺序有序的数组内的时间复杂度为O(N)，效率很高，当gap=1，即以一个元素为一组，就相当于对整个数组进行直接插入排序了。得到的就是有序数组了。也就排好序了。

4.1、动画演示

在这里插入图片描述

  1. 选择增量序列： 首先确定一个增量序列，这个序列决定了每次分割的步长。常见的增量序列有 Hibbard 增量序列、Sedgewick 增量序列等。增量序列的选择对算法的效率有很大影响。
  2. 分割成子序列： 将原始序列分割成若干个子序列，每个子序列包含距离为增量序列中某个值的元素。通常是从第一个元素开始，每隔增量序列中的一个值取一个元素，这样依次形成子序列。
  3. 对各个子序列进行插入排序： 对每个子序列分别进行插入排序。即对每个子序列内部的元素进行排序，使得子序列内部基本有序。这一步通常采用的是简单插入排序。
  4. 逐步缩小增量： 重复上述步骤，但是每次使用的增量都会逐步缩小，直到增量为 1。
  5. 最后一次插入排序： 当增量为 1 时，整个序列会被分割成一个个相邻的子序列，此时进行最后一次插入排序。这时候，相邻元素之间的距离变为 1，即实现了对整个序列的最终排序。

4.2、代码

void Shell_sort(int *nums, int length) {for (int gap = length / 2; gap > 0; gap /= 2) {for (int i = gap; i < length; i++) {int temp = nums[i];int j;for (j = i; j >= gap && nums[j - gap] > temp; j -= gap) {nums[j] = nums[j - gap];}nums[j] = temp;}}
}

4.3、评价

希尔排序的时间复杂度取决于增量序列的选择，一般情况下为 O(n^2) 到 O(n^(3/2)) 之间，其中 n 是数组的长度。尽管希尔排序的时间复杂度不稳定，但在实际应用中，其性能通常比简单插入排序要好很多，特别是对于中等大小的数组。

五、归并排序（Merge sort）

归并排序（Merge sort）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。

作为一种典型的分而治之思想的算法应用，归并排序的实现由两种方法：

  • 自上而下的递归（所有递归的方法都可以用迭代重写，所以就有了第 2 种方法）
  • 自下而上的迭代

和选择排序一样，归并排序的性能不受输入数据的影响，但表现比选择排序好的多，因为始终都是 O(nlogn) 的时间复杂度。代价是需要额外的内存空间。

5.1、动画演示

请添加图片描述

5.2、代码

递归实现

void Merge(int *nums, int l, int r, int *tmp) {if (l >= r) return;int mid = (l + r) / 2;// 先分Merge(nums,l,mid,tmp);Merge(nums,mid+1,r,tmp);// 再合int l1 = l;int r1 = mid;int l2 = mid + 1;int r2 = r;int pos = 0;while (l1 <= r1 && l2 <= r2) {if (nums[l1] < nums[l2]) {tmp[pos++] = nums[l1++];} else {tmp[pos++] = nums[l2++];}}while (l1 <= r1) {tmp[pos++] = nums[l1++];}while (l2 <= r2) {tmp[pos++] = nums[l2++];}memcpy(nums+l,tmp,sizeof(int) * (pos));
}void Merge_sort(int *nums, int length) {int* tmp = (int*)malloc(sizeof(int) * length);Merge(nums,0,length-1, tmp);
}

非递归实现

void MergeSortNonR(int *nums, int length) {int* tmp = (int*)malloc(sizeof(int) * length);// gep为每次需要归并的元素个数for (int gap = 1; gap < length; gap *= 2) {for (int i=0; i<length; i += 2*gap) {int l1 = i;int r1 = i + gap - 1;int l2 = i + gap;int r2 = i + 2 * gap - 1;r2 = r2 < length-1 ? r2 : length - 1;int pos = 0;while (l1 <= r1 && l2 <= r2) {if (nums[l1] < nums[l2]) {tmp[pos++] = nums[l1++];} else {tmp[pos++] = nums[l2++];}}while (l1 <= r1) {tmp[pos++] = nums[l1++];}while (l2 <= r2) {tmp[pos++] = nums[l2++];}memcpy(nums + i, tmp, sizeof(int) * (pos));}}
}

5.3、评价

归并排序是一种非常有效的排序算法。稳定的时间复杂度：归并排序的时间复杂度为 O(n log n)，其中 n 是待排序序列的长度。这意味着在最坏、平均和最好情况下，归并排序的时间复杂度都保持在这个级别，这使得它在各种情况下都能表现出良好的性能。稳定性：归并排序是一种稳定的排序算法，即相同元素的相对位置不会改变。这意味着如果原始序列中存在相同的元素，经过归并排序后，它们的相对顺序将保持不变。适合大规模数据：归并排序对于大规模数据的排序效率较高，因为其时间复杂度相对较低且稳定，不会受到数据分布的影响。

六、快速排序

快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下，排序 n 个项目要 Ο(nlogn) 次比较。在最坏状况下则需要 Ο(n2) 次比较，但这种状况并不常见。事实上，快速排序通常明显比其他 Ο(nlogn) 算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实现出来。

6.1、动画演示

  1. 从数列中挑出一个元素，称为 “基准”（pivot）;
  2. 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
  3. 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序；

图片

6.2、代码

6.2.1、hoare法

123123

void Quick(int *nums, int l, int r) {if (l >= r) return;int begin = l;int end = r;while (l < r) {while (l < r && nums[r] >= nums[begin]) r--;while (l < r && nums[l] <= nums[begin]) l++;swap(&nums[l], &nums[r]);}swap(&nums[begin],&nums[l]);Quick(nums,begin,l-1);Quick(nums,l+1,end);
}void Quick_sort(int *nums, int length) {Quick(nums,0,length-1);
}

这种方法容易出bug

  1. right找小和left找大的过程中，要保证left < right，否则可能出现数组越界，比如1,9,6,4,2,7,8,2 ；右边的值都比key大，会导致越界。
  2. a[right] >= a[keyI]或者a[left] <= a[keyI]时，才能–right或者++left；如果是a[right] > a[keyI]或者a[left] < a[keyI]可能出现死循环，比如a[left] == a[right] == key时，交换完后不进入内部while，外部while陷入死循环。
6.2.2、挖坑法

img

void Quick(int *nums, int l, int r) {if (l >= r) return;int hole = l;int key = nums[l];while (l < r) {while (l < r && nums[r] >= key) r--;nums[hole] = nums[r];hole = r;while (l < r && nums[l] <= key) l++;nums[hole] = nums[l];hole = l;}nums[hole] = key;Quick(nums,l,hole-1);Quick(nums,hole+1,r);
}void Quick_sort(int *nums, int length) {Quick(nums,0,length-1);
}
6.2.3、前后指针法

img

void Quick(int *nums, int l, int r) {if (l >= r) return;int prev = l;int cur = l+1;int key = l;while (cur <= r) {if (nums[cur] < nums[key] && ++prev != cur) {swap(&nums[prev],&nums[cur]);}++cur;}Quick(nums,l,prev-1);Quick(nums,prev+1,r);
}void Quick_sort(int *nums, int length) {Quick(nums,0,length-1);
}

6.3、评价

快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序。实际上确实非常快，使用场景也非常广泛

七、堆排序（Heap sort）

利用堆这种数据结构进行排序，堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。堆排序可以说是一种利用堆的概念来排序的选择排序。分为两种方法：

  • 大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列；

  • 小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列；

堆排序的平均时间复杂度为 Ο(nlogn)。

7.1、动画演示

图片

7.2、代码

// 调整堆，将以root为根的子树调整为最大堆
void heapify(int arr[], int n, int root) {int largest = root; // 初始化根节点为最大值int left = 2 * root + 1; // 左子节点int right = 2 * root + 2; // 右子节点// 如果左子节点比根节点大，则更新最大值if (left < n && arr[left] > arr[largest]) {largest = left;}// 如果右子节点比根节点大，则更新最大值if (right < n && arr[right] > arr[largest]) {largest = right;}// 如果最大值不是根节点，则交换根节点和最大值节点，并递归调整子树if (largest != root) {swap(&arr[root], &arr[largest]);heapify(arr, n, largest);}
}// 堆排序函数
void heapSort(int arr[], int n) {// 构建最大堆for (int i = n / 2 - 1; i >= 0; i--) {heapify(arr, n, i);}// 依次取出堆顶元素，调整堆for (int i = n - 1; i > 0; i--) {swap(&arr[0], &arr[i]); // 将当前堆顶元素（最大值）与数组末尾元素交换heapify(arr, i, 0); // 调整堆}
}

7.3、评价

堆排序不稳定，但是时间复杂度稳定，适用于大规模数据。

  • 堆排序通常需要随机访问数组元素，对于链式结构来说不太适用，因此在链表实现中可能效率较低。

  • 如果待排序的数据分布不均匀，堆排序的性能可能会下降，因为堆排序是一种基于比较的排序算法，而数据分布不均可能导致比较次数增多。

  • 相对于其他简单的排序算法（如插入排序、冒泡排序），堆排序的实现相对复杂，需要对堆的概念和操作有一定的了解。

八、计数排序

计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。

8.1、动画演示

图片

8.2、代码

void Counting_sort(int *nums, int length) {int *cache = (int *)malloc(sizeof(int) * 20);memset(cache,0,sizeof(int) * 20);for(int i=0;i<length;i++) {cache[nums[i]] ++;}int pos = 0;for(int i=0;i<20;i++) {while (cache[i]) {nums[pos++] = i;cache[i]--;}}
}

8.3、评价

计数排序具有线性复杂度，简单易实现，对于范围有限的数据非常友好。

九、桶排序

桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。

  • 在额外空间充足的情况下，尽量增大桶的数量
  • 使用的映射函数能够将输入的 N 个数据均匀的分配到 K 个桶中

其主要是先把序列中的数据划分为一个个的范围，每个范围相当一个桶，将数据放入桶中，每个桶分别进行排序，然后取出拼接即可。计数排序不适用于序列中max-min范围较广或者序列中的数据不是整数的情况，但是桶排序没有这些限制，其主要步骤是将数据放入桶中，桶中的数据自己排序。

桶排序是一种针对大数据的排序方式,数据量越大,桶排序的优势越大

十、基数排序

基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。

10.1、动画演示

图片

10.2、评价

基数排序适用于待排序元素为非负整数，并且数值范围不是很大的情况。它将整数按位数划分，并依次进行排序，适用于范围较小的整数排序。

基数排序可扩展到外部排序，即处理大规模数据的排序问题。例如，可以将数据分块读入内存，然后使用基数排序对每个数字位进行排序，再将结果写回磁盘。

基数排序的这些优势使得它在某些特定的排序需求中具有较好的性能和适用性。然而，基数排序的缺点是需要额外的存储空间来存储中间结果，且对待排序元素的数据类型有一定要求（通常是非负整数）。

基数排序不需要比较

这篇关于十大经典排序算法及其C语言实现--带动图展示的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/894353。

相关文章

使用Sentinel自定义返回和实现区分来源方式

使用Sentinel自定义返回和实现区分来源方式

《使用Sentinel自定义返回和实现区分来源方式》：本文主要介绍使用Sentinel自定义返回和实现区分来源方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Sentinel自定义返回和实现区分来源1. 自定义错误返回2. 实现区分来源总结Sentinel自定
阅读更多...
Java实现时间与字符串互相转换详解

Java实现时间与字符串互相转换详解

《Java实现时间与字符串互相转换详解》这篇文章主要为大家详细介绍了Java中实现时间与字符串互相转换的相关方法,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录一、日期格式化为字符串（一）使用预定义格式（二）自定义格式二、字符串解析为日期（一）解析ISO格式字符串（二）解析自定义
阅读更多...
opencv图像处理之指纹验证的实现

opencv图像处理之指纹验证的实现

《opencv图像处理之指纹验证的实现》本文主要介绍了opencv图像处理之指纹验证的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学... 目录一、简介二、具体案例实现1. 图像显示函数2. 指纹验证函数3. 主函数4、运行结果三、总结一、
阅读更多...
Springboot处理跨域的实现方式(附Demo)

Springboot处理跨域的实现方式(附Demo)

《Springboot处理跨域的实现方式(附Demo)》：本文主要介绍Springboot处理跨域的实现方式(附Demo),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不... 目录Springboot处理跨域的方式1. 基本知识2. @CrossOrigin3. 全局跨域设置4.
阅读更多...
Spring Boot 3.4.3 基于 Spring WebFlux 实现 SSE 功能(代码示例)

Spring Boot 3.4.3 基于 Spring WebFlux 实现 SSE 功能(代码示例)

《SpringBoot3.4.3基于SpringWebFlux实现SSE功能(代码示例)》SpringBoot3.4.3结合SpringWebFlux实现SSE功能,为实时数据推送提供... 目录1. SSE 简介1.1 什么是 SSE？1.2 SSE 的优点1.3 适用场景2. Spring WebFlu
阅读更多...
基于SpringBoot实现文件秒传功能

基于SpringBoot实现文件秒传功能

《基于SpringBoot实现文件秒传功能》在开发Web应用时,文件上传是一个常见需求,然而,当用户需要上传大文件或相同文件多次时,会造成带宽浪费和服务器存储冗余,此时可以使用文件秒传技术通过识别重复... 目录前言文件秒传原理代码实现1. 创建项目基础结构2. 创建上传存储代码3. 创建Result类4.
阅读更多...
SpringBoot日志配置SLF4J和Logback的方法实现

SpringBoot日志配置SLF4J和Logback的方法实现

《SpringBoot日志配置SLF4J和Logback的方法实现》日志记录是不可或缺的一部分,本文主要介绍了SpringBoot日志配置SLF4J和Logback的方法实现,文中通过示例代码介绍的非... 目录一、前言二、案例一：初识日志三、案例二：使用Lombok输出日志四、案例三：配置Logback一
阅读更多...
Python如何使用__slots__实现节省内存和性能优化

Python如何使用__slots__实现节省内存和性能优化

《Python如何使用__slots__实现节省内存和性能优化》你有想过,一个小小的__slots__能让你的Python类内存消耗直接减半吗,没错,今天咱们要聊的就是这个让人眼前一亮的技巧,感兴趣的... 目录背景：内存吃得满满的类__slots__：你的内存管理小助手举个大概的例子：看看效果如何？1.
阅读更多...
Python+PyQt5实现多屏幕协同播放功能

Python+PyQt5实现多屏幕协同播放功能

《Python+PyQt5实现多屏幕协同播放功能》在现代会议展示、数字广告、展览展示等场景中,多屏幕协同播放已成为刚需,下面我们就来看看如何利用Python和PyQt5开发一套功能强大的跨屏播控系统吧... 目录一、项目概述：突破传统播放限制二、核心技术解析2.1 多屏管理机制2.2 播放引擎设计2.3 专
阅读更多...
Python实现无痛修改第三方库源码的方法详解

Python实现无痛修改第三方库源码的方法详解

《Python实现无痛修改第三方库源码的方法详解》很多时候,我们下载的第三方库是不会有需求不满足的情况,但也有极少的情况,第三方库没有兼顾到需求,本文将介绍几个修改源码的操作,大家可以根据需求进行选择... 目录需求不符合模拟示例 1. 修改源文件2. 继承修改3. 猴子补丁4. 追踪局部变量需求不符合很
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2