几种常见排序算法的基本介绍,性能分析,和c语言实现 |
您所在的位置：网站首页 › 排序算法全解析c语言 › 几种常见排序算法的基本介绍,性能分析,和c语言实现 |
几种常见排序算法的基本介绍,性能分析,和c语言实现
|
本文介绍6种常见的排序算法,以及他们的原理,性能分析和c语言实现: 为了能够条理清楚,本文所有的算法和解释全部按照升序排序进行
首先准备一个元素无序的数组arr[],数组的长度为length,一个交换函数swap, 在main函数中实现排序函数的调用,并输出排序结果: void swap(int*x , int*y) { int temp = *x; *x = *y; *y = temp; } int main() { int arr[] = { 1,8,5,7,4,6,2,3}; int length = sizeof(arr) / sizeof(int); sort(arr, length); for (int i = 0;i < length;i++) { printf("%d\n", arr[i]); } return 0; }
插入排序 第一次循环:
第二次循环:
第三次循环:
外层循环每执行一次就从无序区向有序区中插入一个数据arr[i] 里层循环控制插入的数据arr[i]与其前一个数据比较,如果比前一个数据小,就让前一个数据后移1位 ...不断重复上述步骤,直到找到不比arr[i]小的数据arr[j],因为arr[j]后面的数据都后移了1位,所以直接将arr[i]放在空闲的arr[j+1]位置
c程序实现: void CRsort(int arr[], int length) { int temp; for (int i = 0;i < length;i++) { temp = arr[i]; for (int j = i - 1;j >= 0;j--) { if (arr[j] > temp) { arr[j + 1] = arr[j]; } else { arr[j + 1] = temp; break; } } } }
性能分析 稳定性 : 稳定 -->内层循环执行时,只有遇到大于arr[i]的才会后移,等于arr[i]的不会后移 时间复杂度 : (最坏n²,最好n,平均n²) -->数据量为n的情况下,外层循环执行n次,内层循环最多执行n次,如果是数据是有序的内层循环只会执行1次 数据越有序,插入排序的执行效率就越高 空间复杂度: 1 -->程序没有用到递归,临时变量不占用存储资源,因此空间复杂度为1
希尔排序 希尔排序又叫"缩小增量排序",是插入排序的一种改进排本: 插入排序优点是适合处理接近有序的元素,缺点是每次只能比较一个元素,希尔排序利用了这两个特点: 区别于普通的插入排序,希尔排序有一个增量序列r,r的初始值一般取 int(length/2),也就是元素数量除以2向下取整 将所有相隔r个单位的元素组成一组,在组内完成排序 增量每次折半,直到最后一次排序时,增量为1,这时元素一定是有序的
最外层循环控制增量组,即每次循环的增量 里面的两层循环就是一个最基本的插入排序,只不过每次加入有序组的不是arr[i+1],而是arr[i+增量] c程序实现: void ShellSort(int arr[], int length) { int r, temp, j; for (r = length / 2;r >= 1;r = r / 2) { for (int i = r;i < length;i++) { temp = arr[i]; j = i - r; while (j >= 0 && temp 每个元素都是在自己的排序组中排序,两个值相同的元素出于不同的排序组中他们总体的相对位置可能会发生变化时间复杂度 : (最坏n²,最好n,平均n^1.3) -->希尔排序的分析是一个复杂的问题，以为它的时间是所取“增量”序列的函数，这涉及到一些数学上尚未解决的难题,摘自网上. 最好和普通插入排序相同,如果是数据是有序的内层循环只会执行1次 同样拥有插入排序的特点:数据越有序,它的执行效率就越高 空间复杂度: 1 -->程序没有用到递归,临时变量不占用存储资源,因此空间复杂度为1
冒泡排序 冒泡排序
外层循环每次都将一个元素置入有序区 内层循环控制置入的元素:设置一个指针j,拿arr[j]的值与arr[j+1]进行比较: 如果arr[j] arr[j + 1]) { swap(&arr[j],&arr[j+1]); change = 1; } } if (change == 0) { return 0; } } } 性能分析 稳定性 : 稳定 -->数据只有在大于或小于时才会交换,相等时不会交换,因此相同数据的相对位置不会发生改变 时间复杂度 : (最坏n²,最好n,平均n²) -->在数据完全有序时,不会有数据交换,根据上面的优化处理,状态码change不会改变,外层循环执行一次就结束,时间复杂度为n+1,也就是n. 而如果是非常无序的数据,外层循环执行满n次,时间复杂度就是n² 空间复杂度: log(2)(N) -->程序没有用到递归,临时变量不占用存储资源,因此空间复杂度为1
快速排序 快速排序是一种效率比较高的排序方法,这张图片我认为介绍的很清楚,搬运来用一下,出处在文章下面:
c程序实现: void KSSort(int arr[], int left, int right) { if (left 程序没有用到递归,临时变量不占用存储资源,因此空间复杂度为1
堆排序 堆排序是选择排序的改进版本,它比堆排序的性能要高很多. 要实现堆排序,首先要了解这几个知识点: 大根堆:每个节点的值都大于他的左右子树(小根堆反之) 完全二叉树:除了最后一层之外的其他每一层都被完全填充，并且所有结点都保持向左对齐。 在n个节点的完全二叉树中,叶子节点有(n+1)/2个,非叶子节点有(n-1)/2个 在堆中,下标为n的数的左子树为2n+1,右子树为2n+2
首先要能够将一组无序的数排列成大根堆,大根堆的构造方法如下:
... 外层循环从最后一个非叶子节点( length/2-1 )向根节点遍历,每遍历到一个数据,就执行下面操作: 设置一个根指针i,指向当前要操作树的根节点 比较该树的左右子树的值,将biger指针指向较大的子树 如果该子树的值比根节点还大(arr[biger]>arr[i]),将该子树的值与根节点交换,并将i指针指向该子树,使之成为新的根节点 ......递归执行上一步操作,直到有根节点不小于左右子树为止
构造出大根堆之后,每次取整个堆的根节点(也就是第一个元素)存入有序区,将堆的最后一个元素作为根节点 剩下的元素继续构造大根堆,直到数据完全存入有序区 c程序实现: void MkHeap(int arr[], int i, int length) { int bigger = 2 * i + 1; int temp; if (bigger 0;j--) { swap(&arr[j],&arr[0]); MkHeap(arr, 0, j-1); } }性能分析 稳定性 : 不稳定 -->先假设稳定,然后举个反例: {6,7,7}这棵树左右子树的值都是7,本来左子树是应该是在前面的,但是6加入有序区之后右子树的7会被提到最上面,这样他们的顺序就被调换了 时间复杂度 : (最坏nlogn,最好nlogn,平均nlogn ) -->根据性质,外层循环会执行n次(n代表排序的元素个数),将所有数据全部加入有序区. 而内层递归函数指针从0到n,每次增长前一个的2n+1,忽略掉常数1,也就是执行log(2)(N)次 因此为Nlog(2)(N)次,忽略掉底数2,时间复杂度为nlogn 插入/希尔排序适合接近有序的数据,而堆排序适合非常无序的数据,因为无论数据多么杂乱,希尔排序的时间复杂度都是nlogn (不放心再说一下 : log(2)(N)是log以2为底n的对数 , 不是log2乘n , 因为底数打不出来只能这样写) 空间复杂度: log(2)(N) -->这里程序递归了log(2)(N)次,每次递归都占用内存,因此空间复杂度为log(2)(N) 当然也可以使用循环的方式实现,但是那样写出来结构略显混乱,不如递归方式清晰
不稳定算法口诀:快些选队
参考资料(文中的部分图片和思想来自以上材料): 1. 《新编数据结构习题与解析》 2. 文章 https://www.cnblogs.com/skywang12345/p/3603935.html https://www.cnblogs.com/jingmoxukong/p/4302891.html http://www.sohu.com/a/341037266_115128 https://www.toutiao.com/a6593273307280179715/?iid=6593273307280179715 3. 关于快速排序算法的稳定性？ - 知遥其实是德鲁伊的回答:https://www.zhihu.com/question/45929062/answer/262452296 |
【本文地址】
今日新闻 |
推荐新闻 |