数据结构与算法（三）软件设计(十九)
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），归并和快速排序也类似与二分，所以效率也不低。
