十大经典排序算法及其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。

相关文章

不懂推荐算法也能设计推荐系统

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例，告诉我们不懂推荐算法的产品，也能从产品侧出发， 设计出一款不错的推荐系统。 相信很多新手产品，看到算法二字，多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法（注：传统是指科班出身的产品都会接触过）。但对于推荐算法，多数产品对着网上搜到的资源，都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后，更是加大了理解的难度。 但，不了解推荐算法，就无法做推荐系
阅读更多...
hdu1043（八数码问题，广搜 + hash（实现状态压缩） ）

hdu1043（八数码问题，广搜 + hash（实现状态压缩） ）

利用康拓展开将一个排列映射成一个自然数，然后就变成了普通的广搜题。 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#inclu
阅读更多...
康拓展开（hash算法中会用到）

康拓展开（hash算法中会用到）

康拓展开是一个全排列到一个自然数的双射（也就是某个全排列与某个自然数一一对应） 公式： X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。（a[i]在不同应用中的含义不同）； 典型应用： 计算当前排列在所有由小到大全排列中的顺序，也就是说求当前排列是第
阅读更多...
csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

这是一道扩展欧几里得算法的简单应用题，这题是在湖南多校训练赛中队友ac的一道题，在比赛之后请教了队友，然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意：把题意转变下就变成了：求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点：求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个
阅读更多...
综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动，这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升：减少抖动，提高图像的清晰度和细节表现力，使得监控画面更加真实可信。 - 细节增强：在低光条件下，抖
阅读更多...
【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...
【C++】_list常用方法解析及模拟实现

【C++】_list常用方法解析及模拟实现

相信自己的力量，只要对自己始终保持信心，尽自己最大努力去完成任何事，就算事情最终结果是失败了，努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一：什么是list？ •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二：list常用接口 •🌰1.默认成员函数 🔥构造函数（⭐） 🔥析构函数 •🌰2.list对象
阅读更多...
【Prometheus】PromQL向量匹配实现不同标签的向量数据进行运算

【Prometheus】PromQL向量匹配实现不同标签的向量数据进行运算

✨✨ 欢迎大家来到景天科技苑✨✨ 🎈🎈 养成好习惯，先赞后看哦~🎈🎈 🏆 作者简介：景天科技苑 🏆《头衔》：大厂架构师，华为云开发者社区专家博主，阿里云开发者社区专家博主，CSDN全栈领域优质创作者，掘金优秀博主，51CTO博客专家等。 🏆《博客》：Python全栈，前后端开发，小程序开发，人工智能，js逆向，App逆向，网络系统安全，数据分析，Django，fastapi
阅读更多...
让树莓派智能语音助手实现定时提醒功能

让树莓派智能语音助手实现定时提醒功能

最初的时候是想直接在rasa 的chatbot上实现，因为rasa本身是带有remindschedule模块的。不过经过一番折腾后，忽然发现，chatbot上实现的定时，语音助手不一定会有响应。因为，我目前语音助手的代码设置了长时间无应答会结束对话，这样一来，chatbot定时提醒的触发就不会被语音助手获悉。那怎么让语音助手也具有定时提醒功能呢？ 我最后选择的方法是用threading.Time
阅读更多...
Android实现任意版本设置默认的锁屏壁纸和桌面壁纸（两张壁纸可不一致）

Android实现任意版本设置默认的锁屏壁纸和桌面壁纸（两张壁纸可不一致）

客户有些需求需要设置默认壁纸和锁屏壁纸  在默认情况下 这两个壁纸是相同的  如果需要默认的锁屏壁纸和桌面壁纸不一样 需要额外修改 Android13实现 替换默认桌面壁纸： 将图片文件替换frameworks/base/core/res/res/drawable-nodpi/default_wallpaper.*  （注意不能是bmp格式） 替换默认锁屏壁纸： 将图片资源放入vendo
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2