数据结构与算法（二十）快速排序、堆排序(四)

数据结构与算法（三）软件设计(十九)https://blog.csdn.net/ke1ying/article/details/129252205

• 排序

分为 稳定排序 和 不稳定排序

内排序 和 外排序

内排序指在内存里，外排序指在外部存储空间排序

1、排序的方法分类。

插入排序：直接插入排序  和 希尔排序

交换类排序：冒泡排序  和   快速排序

选择类排序： 简单选择类排序 和 堆排序（效率非常高，处理过程复杂）

归并排序

基数排序

直接插入排序

23 30 29  17

第一步：23和30比较，位置不变。

第二步：29和30比较，29和23比较，发现29大于23小于30，所以插入中间

23 29 30 17

第三步：17和30比较，17和29比较，17和23比较，发现17小于23

17 23 29 30

希尔排序（shell排序）

给一组10位数

第一步：d1 = n/2 = 5 ，每5个一组，从第一个数和第六个数比较，第二个数和第七个数比较...依次类推，小的排到前面。

第二步：d2 = d1/2 = 3（取奇数），每3个一组，从第一个数和第六个数比较，第二个数和第七个数比较...依次类推，小的排到前面。

第三步；d3 = d2/2 = 1(取奇数)，直接插入排序最后得到结果。

这样效率会高很多。

直接选择排序

23 30 29 17

第一步：选择最小的17 放在最前面 ，所以 是17 23 30 29

第二步：在剩下里在选择最小的23，不动

第三步：在剩下里再选择最小的29，所以17 23 29 30

堆排序（排序算法最复杂的算法之一）

由图k1 = 10，k2=20，k3=13，k4=40，k5=50，k6=15，k7=16，k8=50，k9=45，k10=80

满足k1 <=k2 (10<20) 且 k1<k3 (10<13)

所以这时候就是小顶堆， 根永远比左孩子节点和右孩子节点小。

大顶堆则就是根永远比左孩子节点和右孩子节点大。

堆要先构建：

第一步：用给的数构建一个完全二叉树。

第二步：每次用最下面的非叶子节点与叶子结点比较，交换，依次往上比较。

堆排序使用非常广泛，效率高，特别是数值非常多的时候，而要求求前几名（前10名或者20名）的时候，这种场景非常好。

冒泡排序

通过相邻的元素之间比较和交换，将较小或者较大的元素逐渐从底部移动到顶部。

快速排序

采用的是分治法，基本思想把一个问题分成若干规模更小的相似子问题。

选择一个基准，每次与这个数比较，小于这个基准的在左边，大于的在右边，全部比对完后，再对两边的数做排序。

归并排序

将两个或两个以上的有序子表合并成一个新的有序表。当两个有序表继续合并，这时候叫做二路合并。

32 13 98 12 22 29 30 28

第一步：[13 23][12 98][22 29][28 30]

第二步：[12 13 23 98][22 28 29 30]

第三步：[12 13 22 23 28 29 30 98 ]

基数排序

第一步；按个位排序。

第二步：按十位排序。

第三步：按百位排序。

稳定的排序包含：直接插入、冒泡排序、归并排序、基数排序。

归并排序空间复杂度是O（n），其他基本都是O（1）。

堆排序效果比较好，因为涉及到树，往往就是O（nlog2n），归并和快速排序也类似与二分，所以效率也不低。