各类排序方法简析
排序一般可以包括以下几种：
◆插入排序(直接插入排序,希尔排序)
◆选择排序(简单交换排序,堆排序)
◆交换排序(冒泡排序,快速排序)
◆归并排序
◆基数排序
下面逐一介绍：
1、插入排序
57 68 59 52------首先57与68比较,68>57,这2个数不做处理
57 68 59 52------59跟前面的57,68进行比较,找到合适的位置插入(57,68之间)
57 59 68 52------52和57,59,68进行比较,找到合适的位置插入(57前面)
52 57 59 68------最终结果
2、希尔(Shell)排序
希尔排序是插入排序的改进算法，其基本思想每一套都按照确定的间隔，使小的元素可以跳跃前进，缩小跳进直至为1
57 68 59 52 73 28 96 33 24 19------间隔用d=n/2=5
28 68 33 24 19 57 96 59 52 73------57|28、68|96、59|33、52|24、73|19分组进行比较
28 68 33 24 19 57 96 59 52 73------接下来d=d/2(步长一定为整数,且取奇数,如遇偶数则加1)=5/2=3
24 19 33 28 59 52 73 68 57 96------28|24|96|73、68|19|59、33|57|52分组比较
24 19 33 28 59 52 73 68 57 96------最后:d=d/2=1
19 24 28 33 52 57 59 68 72 96------用插入排序得到最终结果
3、简单选择排序
57 68 59 52------最小值为52和第一个交换
52 68 59 57------最小的是57和第二个交换
52 57 59 68------最小的为59不需要交换
52 57 59 68------完成
4、堆排序
什么是堆：n个元素的序列,满足父节点比子节点都要小或比他们都大,就是堆了,下面就是一个最小堆
1
2 3
4 5 6 7
8 9
46 79 56 38 40 84------先只需把它们按照完全二叉树填入
46
79 56
38 40 84
从最底层开始调整,56和84交换,79和38|40不用换
再看第2层46和79|84比较,和84交换
再对底层调整,56和46交换，得到一个正确的最大堆
84 79 56 38 4046------把首尾互调,再对除最大数外所有构造堆
... ...
5、冒泡排序
57 68 59 52------(第1个元素)57和68进行比较,不交换
57 68 59 52------(第2个元素)68和59进行比较,交换
57 59 68 52------(第3个元素)68和52进行比较,交换
57 59 52 68------对剩下的3个元素进行冒泡
57 59 52 ------57和59,不交换
57 59 52 ------59和52,交换
57 52 59 ------对剩下的2个元素进行冒泡
57 52 ------
57和52
,交换
52 57 59 68------
完成
6、快速排序
采用分治法把大问题分解为同类型的小问题。拿出一个元素，把比它大的放一边，小的放另外一边；又用同样的方法，对抓出一个“元素”同样的处理，一步步的下去就把每一个小系列的都弄出来的，把结果拼合一下就成功了。
57 6859 52 72 28 96 33 24 19
------以57为关键字进行归类
52 28 33 24 19 57 58 59 72 96------左边28，右边72
24 19 28 52 33 57 58 59 72 96------每堆任选一个排序得到最终结果
19 24 28 33 52 57 58 59 82 96------完成
7、归并排序
57 68 59 52 72 28 96 33------以2路归并为例,每2个分组排序
57 68 52 59 28 72 33 96------以4个一组排序
52 57 59 68 28 33 72 96------以8个一组排序
28 33 52 57 59 68 72 96------完成
8、基数排序
73 22 93 43 55 14 28 65 39 81------首先对个位排序(0-1),若相同则按自然顺序
81 22 43 73 93 14 55 65 28 39------再以十位排序(0-1),若相同则按自然顺序
14 22 28 39 43 55 65 73 81 93------完成
如果有百位，则再排序一次，直到排完所有位数。
附：各种排序复杂度比较表
--------------------------------------------------
注：至于详细的编码，可以参见以下内容：
--------------------------------------------------
-The End-