C语言超详细梳理排序算法的使用
排序的概念及其运用
排序的概念
排序:所谓排序,就是使一串记录,按照其中的某个或某些关键字的大小,递增或递减的排列起来的操作。
稳定性:假定在待排序的记录序列中,存在多个具有相同的关键字的记录,若经过排序,这些记录的相对次
序保持不变,即在原序列中,r[i]=r[j],且r[i]在r[j]之前,而在排序后的序列中,r[i]仍在r[j]之前,则称这种排
序算法是稳定的;否则称为不稳定的。 内部排序:数据元素全部放在内存中的排序。
外部排序:数据元素太多不能同时放在内存中,根据排序过程的要求不能在内外存之间移动数据的排序。
排序运用
高校排名:
接下来,我会一一介绍几种常见的排序算法
插入排序
直接插入排序
直接插入排序是一种简单的插入排序法
基本思想: 把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中,直到所有的记录插入完为止,得到一个新的有序序列
代码的实现
//直接插入排序 void InsertSort(int* a, int n) { assert(a);//传入数组不为空指针 int i; for (i = 0; i < n - 1; i++) { int end = i; int x = a[end + 1]; while (end >= 0) { //升序 if (a[end] >x) { a[end + 1] = a[end]; end--; } else { break; } } a[end + 1] = x; } }
希尔排序
解析
- 希尔排序在直接排序之前,进行预排列,将某些极端数据更快的排列到数列前面,构成一个接近排列好的序列,最后再进行一次直接插入排序
- 预排列的原理也是插入排列,只不过这里的将数组分成了gap组,分别对每一个小组进行插入排序
// 希尔排序 void ShellSort(int* a, int n) { int gap = n; while (gap > 1) { gap /= 2; for (int i = 0; i < n - gap; i++) { int end = i; int x = a[end + gap]; while (end >= 0) { if (a[end] > x) { a[end + gap] = a[end]; end-=gap; } else break; } a[end + gap] = x; } } }
当gap > 1时都是预排序,目的是让数组更接近于有序。当gap == 1时,数组已经接近有序的了,这样就会很快。这样整体而言,可以达到优化的效果。我们实现后可以进行性能测试的对比
选择排序
直接选择排序
解析
每一次遍历待排序的数据元素从中选出最小(或最大)的一个元素,存放在序列的起始(或者末尾)位置,直到全部待排序的数据元素排完
代码的实现
// 选择排序 void SelectSort(int* a, int n) { int begin = 0, end = n - 1;//记录下标 while (begin < end) { int mini = begin; for (int i = begin; i <= end; i++) { //遍历找到最小数据并记录下标 if (a[i] < a[mini]) mini = i; } Swap(&a[begin], &a[mini]);//交换 begin++;//缩小范围 } }
总结
时间复杂度:O(N^2)
空间复杂度:O(1)
稳定性:不稳定
不推荐使用
堆排序
堆排序是指利用堆(数据结构)进行选择数据的一种排序算法
基础思想:
- 原则:
先将原数组建成堆,需要注意的是排升序要建大堆,排降序建小堆
注:以大堆为例
- 建堆:
一个根节点与子节点数据如果不符合大堆结构,那么则对根节点数据进行向下调整,而向下调整的前提是左右子树也符合大堆结构,所以从堆尾数据的根节点位置开始向下调整建大堆
- 排序:
大堆堆顶数据一定是待排数据中最大的,将堆顶数据与堆尾数据交换,交换后将除堆尾数据看成新堆,对现堆顶数据进行向下调整成大堆,以此循环直至排列完毕
- 向下调整:
找到子节点中的较大数据节点比较,如果父节点数据比大子节点小则交换,直到不符合则停止向下交换,此时再次构成了一个大堆结构.
代码的实现
void Adjustdown(int* a, int n,int parent) { int child = parent * 2 + 1; while (child < n) { //找到数据大的子结点 if (child + 1 < n && a[child + 1] > a[child]) { child++; } //父节点数据小于子节点就交换 if (a[parent] < a[child]) { Swap(&a[parent], &a[child]); //更新下标 parent = child; child = parent * 2 + 1; } else//否则向下调整完毕 break; } } // 堆排序(升序)建大堆 void HeapSort(int* a, int n) { int i; //建大堆 for (i = (n - 1 - 1) / 2; i >= 0; i--) { Adjustdown(a, n, i); } //交换调整 for (i = n - 1; i >= 0; i--) { Swap(&a[0], &a[i]);//与当前堆尾数据交换 Adjustdown(a, i, 0);//对交换后堆顶数据进行向下调整 } }
总结:
堆排序使用堆来选数,效率就高了很多。
时间复杂度:O(N*logN)
空间复杂度:O(1)
稳定性:不稳定
交换排序之冒泡排序
冒泡排序
每次遍历数组,对相邻数据进行比较,不符合排序要求则交换
代码的实现
// 冒泡排序 void BubbleSort(int* a, int n) { int i, j; for (i = 0; i < n - 1; i++)//趟数 { for (j = 0; j < n - 1 - i; j++)//比较次数 { if (a[j] > a[j + 1])//满足条件 Swap(&a[j], &a[j + 1]);//交换 } } }
总结
排序的第一篇就讲到这里了,下一篇还会讲快速排序和归并排序,希望大家多多支持!!
到此这篇关于C语言超详细梳理排序算法的使用的文章就介绍到这了,更多相关C语言 排序算法内容请搜索猪先飞以前的文章或继续浏览下面的相关文章希望大家以后多多支持猪先飞!
原文出处:https://blog.csdn.net/yin_ming_hui/article/details/123744576
相关文章
- 这篇文章主要为大家详细介绍了C语言实现放烟花的程序,有音乐播放,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2021-02-23
- 本篇文章主要介绍C语言中char的知识,并附有代码实例,以便大家在学习的时候更好的理解,有需要的可以看一下...2020-04-25
- 作者:Sabine 【导读】本文介绍了C#的四种排序算法:冒泡排序、选择排序、插入排序和希尔排序 冒泡排序 using System; namespace BubbleSorter { public class Bubb...2020-06-25
- 这篇文章主要用实例讲解C#递归算法的概念以及用法,文中代码非常详细,帮助大家更好的参考和学习,感兴趣的朋友可以了解下...2020-06-25
- 这篇文章主要介绍了详解如何将c语言文件打包成exe可执行程序,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-02-25
antdesign-vue结合sortablejs实现两个table相互拖拽排序功能
这篇文章主要介绍了antdesign-vue结合sortablejs实现两个table相互拖拽排序功能,本文通过实例图文相结合给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友可以参考下...2021-01-09- 这篇文章主要介绍了C# 参数按照ASCII码从小到大排序(字典序)的方法,非常不错,具有参考借鉴价值,需要的朋友可以参考下...2020-06-25
- free函数是释放之前某一次malloc函数申请的空间,而且只是释放空间,并不改变指针的值。下面我们就来详细探讨下...2020-04-25
- 这篇文章主要介绍了C语言中计算正弦的相关函数总结,包括正弦和双曲线正弦以及反正弦的函数,需要的朋友可以参考下...2020-04-25
详解C语言中的rename()函数和remove()函数的使用方法
这篇文章主要介绍了详解C语言中的rename()函数和remove()函数的使用方法,是C语言入门学习中的基础知识,需要的朋友可以参考下...2020-04-25- 这篇文章主要为大家详细介绍了js实现列表按字母排序,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2020-08-11
- 这篇文章主要介绍了C语言中求和、计算平均值、方差和标准差的实例,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-12-10
- 本篇文章主要讲解C语言 基本语法,这里提供简单的示例和代码来详细讲解C语言的基本语法,开始学习C语言的朋友可以看一下,希望能够给你带来帮助...2021-09-18
- 在本篇文章里小编给大家整理的是关于C#实现排序的代码以及相关知识点,需要的朋友们参考下。...2020-06-25
- 这篇文章主要是介绍了.net C# 实现任意List的全组合算法实现代码,需要的朋友可以参考下...2020-06-25
同时兼容JS和C#的RSA加密解密算法详解(对web提交的数据加密传输)
这篇文章主要给大家介绍了关于同时兼容JS和C#的RSA加密解密算法,通过该算法可以对web提交的数据进行加密传输,文中通过图文及示例代码介绍的非常详细,需要的朋友们可以参考借鉴,下面来一起看看吧。...2020-06-25图文详解Heap Sort堆排序算法及JavaScript的代码实现
这篇文章以图文详解Heap Sort堆排序算法及JavaScript的代码实现,堆排序算法基于类二叉树的堆数据结构,需要的朋友可以参考下...2016-05-05- 这篇文章主要介绍了C语言中send()函数和sendto()函数的使用方法,是C语言入门学习中的基础知识,需要的朋友可以参考下...2020-04-25
- 这篇文章主要为大家详细介绍了js实现数组冒泡排序、快速排序的原理,感兴趣的小伙伴们可以参考一下...2016-03-10
- 今天小编就为大家分享一篇C语言实现从文件读入一个3*3数组,并计算每行的平均值,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-04-25