摘要：将大的先放在后面，再下一次可以把相同大的放在上一次的之前，顺序改变。
之前介绍的排序算法：
计数排序是一个非基于比较的排序算法，该算法于1954年由
Harold H. Seward提出它的优势在于在对一定范围内的整数排序时，它的复杂度为Ο(n+k)（其中k是整数的范围），快于任何比较排序算法
当然这是一种牺牲空间换取时间的做法，而且当
O(k)>O(n*log(n))的时候其效率反而不如基于比较的排序（基于比较的排序的时间复杂度在理论上的下限是O(n*log(n)), 如归并排序，堆排序）
O(Max(N, Range))O(range)不适合排序了基本思路：遍历数组a，a[i]下标对应的count[a[i]]++
count数组大小
看样子范围应该是0到a数组中最大的数？
实则不是，如果数字是
1000， 1001， 1100
则从0到1100 ，浪费了很多空间
所以我们定义一个映射数组，所有的数字都是相对最小的数字的大小
1000， 1001， 1100
映射数组数字大小：a[i] - min
0， 1， 100
将它设置为count数组对应下标
这里主要是寻找数组下标与数组值之间的对应关系
count[i]，拷贝的数字是i + min进入原数组（返回映射）
count[i] 的数值表示，数字i需要拷贝到原数组的次数
所以count数组初始值都为0
拷贝一次count[i]–
//计数排序void CountSort(int* a, int n){ int max = a[0]; int min = a[0]; int i = 0; //取出最大和最小值找范围 for (i = 0; i < n; i++) { if (a[i] > max) { max = a[i]; } if (a[i] < min) { min = a[i]; } } //数组数字所在范围 int range = max - min + 1; //开辟内存空间，并且初始化为0 int* tmp = (int*)calloc(range, sizeof(int)); //malloc操作 //int* tmp = (int*)mallco(sizeof(int) * range); //memset(tmp, 0, sizeof(int) * range); if (!tmp) { printf("calloc fail/n"); exit(-1); } int* count = tmp; //计数 for (i = 0; i < n; i++) { count[a[i] - min]++; } int j = 0; //计数放回 for (i = 0; j < range; j++) { while (count[j]--) { a[i++] = j + min; } } free(tmp); tmp = NULL;}相同数值，在排序过后相对位置不发生改变
直接插入排序 稳定
因为是按顺序，从前往后，前1、2、3……个数依次插入排成有序
希尔排序 不稳定
因为是以x为长度，跨位置选数字组成一组开始插入排序
选择排序 不稳定
选择排序是按顺序比较前后，挑出最大和最小。将大的先放在后面，再下一次可以把相同大的放在上一次的之前，顺序改变。
但会有人说我可以通过控制代码，来选择第一次选到最大的那个是后面的那个数
还有一种情况
选择排序算法中还有一段是这样的，如果找到最大最小的两个数，最大的数在最小数需要放的位置，先交换最大和最小，改变序号
堆排序 不稳定
看图，向下调整之后位置改变
冒泡排序 稳定
前后两个数交换，可以控制代码使之相对位置不改变
快速排序 不稳定
假设最左为key，左边找大，右边找小
相对位置发生改变
归并排序 稳定
实质上细分来看是每个循环都是两个数组，相对顺序不变
按照从小到大的顺序归并到一个数组，所以稳定
计数排序 稳定
统计相同数值的个数，按顺序映射到原数组
文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/125655.html
摘要：之所以把计数排序桶排序基数排序放在一起比较，是因为它们的平均时间复杂度都为。动画计数排序思想找出待排序的数组中最大和最小的元素。桶排序计数排序能派上用场吗手机号码有位，范围太大，显然不适合用这两种排序算法。 showImg(https://segmentfault.com/img/bVbuF9e?w=900&h=500); 1. 前言 算法为王。 想学好前端，先练好内功，只有内功深厚者...
摘要：笔者写的数据结构与算法之美系列用的语言是，旨在入门数据结构与算法和方便以后复习。这应该是目前较为简单的十大经典排序算法的文章讲解了吧。比如原本在的前面，而，排序之后，在的后面十大经典排序算法冒泡排序思想冒泡排序只会操作相邻的两个数据。 showImg(https://segmentfault.com/img/bVbvHet); 1. 前言 算法为王。想学好前端，先练好内功，内功不行，就...
本篇有7k+字, 系统梳理了js中常见的12种排序算法。除了基本排序算法，文章还包含了希尔排序、堆排序、桶排序等较为复杂的排序实现，如果喜欢请点赞支持~谢谢. 原文: http://louiszhai.github.io/20... 导读 排序算法可以称得上是我的盲点, 曾几何时当我知道Chrome的Array.prototype.sort使用了快速排序时, 我的内心是奔溃的(啥是快排, 我只知道...
摘要：实际上，桶排序的应用场景十分的有限，对数据的要求比较苛刻。极端情况下，如果数据全部划分到一个桶内，就变成了非线性排序了。 1. 回顾 前面已经说完了几种非线性排序，它们分别是时间复杂度为 O(n2) 、适合小规模数据的冒泡排序、选择排序、插入排序，和应用较广泛的时间复杂度为 O(nlogn) 的希尔排序、归并排序、快速排序。其实这几种排序都有一个特性，那就是它们都是基于数据的比较和移动...
摘要：本文将介绍快速排序计数排序梳排序堆排序归并排序希尔排序选择排序插入排序地精排序联合冒泡排序鸡尾酒排序冒泡排序奇偶排序使用标志的冒泡排序种排序算法的实现。是一种不稳定的排序算法。 本文将介绍快速排序、计数排序、梳排序、堆排序、归并排序、希尔排序、选择排序、插入排序、地精排序、联合冒泡排序、鸡尾酒排序、冒泡排序、奇偶排序、使用标志的冒泡排序14种排序算法的实现。本文是由于阅读了文章《测试评...
阅读 3311·2023-01-11 11:02
阅读 3886·2023-01-11 11:02
阅读 2718·2023-01-11 11:02
阅读 4896·2023-01-11 11:02
阅读 4402·2023-01-11 11:02
阅读 5111·2023-01-11 11:02
阅读 4892·2023-01-11 11:02
阅读 3370·2023-01-11 11:02
