算法 排序

星期二, 8月 6, 2019 | 4分钟阅读 | 更新于 星期二, 3月 14, 2023

@

将杂乱无章的数据元素,通过一定的方法按关键字顺序排列的过程叫做排序

一、冒泡排序

两个数比较大小,较大的数下沉,较小的数冒起来

  1. 比较相邻的元素,如果第一个比第二个大,就交换它们两个
  2. 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对,这样在最后的元素应该会是最大的数
  3. 继续重复上述过程,依次将第n-1、n-2...1个最大数排好位置 冒泡排序.gif 设置标志位flag,如果发生了交换flag设置为true;如果没有交换就设置为false。当一轮比较结束后如果flag仍为false,即:这一轮没有发生交换,说明数据的顺序已经排好,没有必要继续进行下去。

二、选择排序

每一趟从待排序的数据元素中选出最小(或最大)的一个元素,顺序放在已排好序的数列的最后,直到全部待排序的数据元素排完

  1. 第一次遍历n-1个数,找到最小的数值与第一个元素交换
  2. 第二次遍历n-2个数,找到最小的数值与第二个元素交换
  3. 一直重复到第n-1次 选择排序.gif

三、插入排序

在要排序的一组数中,假定前n-1个数已经排好序,现在将第n个数插到前面的有序数列中,使得这n个数也是排好顺序的。如此反复循环,直到全部排好顺序。

  1. 从第一个元素开始,该元素可以认为已经被排序;
  2. 取出下一个元素,在已经排序的元素序列中从后向前扫描;
  3. 如果该元素(已排序)大于新元素,将该元素移到下一位置;
  4. 重复步骤3,直到找到已排序的元素小于或者等于新元素的位置;
  5. 将新元素插入到该位置后;回到步骤2直到最后一个元素 插入排序.gif

四、希尔排序

也称为缩小增量排序,希尔排序是把记录按一定增量分组,对每组使用直接插入排序算法排序,直到增量减至1

  1. 在要排序的一组数中,根据某一增量分为若干子序列,并对子序列分别进行插入排序。
  2. 然后逐渐将增量减小,并重复上述过程。直至增量为1,此时数据序列基本有序,最后进行插入排序。

五、归并排序

将已有序的子序列合并,得到完全有序的序列,重复直到只有一个序列;即先使每个子序列有序,再使子序列段间有序

  1. 把长度为n的输入序列分成两个长度为n/2的子序列;
  2. 对这两个子序列分别采用归并排序;
  3. 将两个排序好的子序列合并成一个最终的排序序列。

六、快速排序

通过一趟排序将待排记录分隔成独立的两部分,其中一部分记录的关键字均比另一部分的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序

  1. 先从数列中取出一个数作为key值;
  2. 将比这个数小的数全部放在它的左边,大于或等于它的数全部放在它的右边;
  3. 对左右两个小数列重复第二步,直至各区间只有1个数。 快速排序.gif

七、堆排序

利用堆这种数据结构所设计的一种排序算法。堆积是一个完全二叉树的结构,并同时满足堆积的性质:即子结点的键值总是不大于(大顶堆)或者不小于(小顶堆)其父结点。

  1. 将数据构造成大顶堆(或小顶堆) 2、按大顶堆规则重复取出堆顶元素,即为有序序列

八、计数排序

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

  1. 找出待排序的数组中最大和最小的元素;
  2. 统计数组中每个值为i的元素出现的次数,存入数组C的第i项;
  3. 对所有的计数累加(从C中的第一个元素开始,每一项和前一项相加);
  4. 反向填充目标数组:将每个元素i放在新数组的第C(i)项,每放一个元素就将C(i)减去1 计数排序.gif

九、桶排序

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

  1. 将待排序元素划分到不同的桶。先扫描一遍序列求出最大值 maxV 和最小值 minV ,设桶的个数为 k ,则把区间 [minV, maxV] 均匀划分成 k 个区间,每个区间就是一个桶。将序列中的元素分配到各自的桶
  2. 对每个桶内的元素进行排序。可以选择任意一种排序算法
  3. 将各个桶中的元素合并成一个大的有序序列

十、基数排序

基数排序按关键字的各个位逐轮排序。以从低位到高位的 LSD 方法为例,每轮使用稳定排序;它不是直接按数值作为数组下标存放元素。

  1. 取得数组中的最大数,并取得位数;

  2. arr为原始数组,从最低位开始取每个位组成radix数组;

  3. 按当前位对整个数组做稳定的计数排序,保留同位值元素的相对次序;再依次处理更高位,直到最高位 基数排序.gif

    计数排序和基数排序不一样

© 2026 我的博客

🌱 Powered by Hugo with theme Dream.

关于这个博客

关于博客

记录软件开发过程的一些知识和技巧,提升自我

关于博主

除了才华一无所有~~ 薪尽自然凉~~ 强迫症患者~~ 热爱古风~~