软件设计师：排序算法总结

一、直接插入

排序方式：从第一个数开始，拿两个数比较，把后面一位跟前面的数比较，把较小的数放在前面一位

二、希尔

排序方式：按“增量序列（步长）”分组比较，组内元素比较交换

 假设初始关键字：48    37    64    96    75    12    26    58    54    3，有当增量序列为“5，3，1”时，希尔插入排序过程如下

第一组:48和12比较，48比12大则此时交换位置后最新排序为：12，37，64，96，75，48，26，58，54，3
                                    
第二组:在上一组排序结果的基础上，37和26比较，37比26大则此时交换位置后最新排序为：12，26，64，96，75，48，37，58，54，3
                                    
第三组:在上一组排序结果的基础上，64和58比较，64比58大则此时交换位置后最新排序为：12，26，58，96，75，48，37，64，54，3
                                
第四组:在上一组排序结果的基础上，96和54比较，96比54大则此时交换位置后最新排序为：12，26，58，54，75，48，37，64，96，3    
                                
第五组:在上一组排序结果的基础上，75和3比较，75比3大则此时交换位置后最新排序为：12，26，58，54，3，48，37，64，96，75

第一组:12，54，37，75按从小到大顺序排列交换位置后最新排序为：12，26，58，37，3，48，54，64，96，75    
                                                                                
第二组:在上一组排序结果的基础上，26，3，64按从小到大顺序排列交换位置后最新排序为：12，3，58，37，26，48，54，64，96，75
                                                                                
第三组:在上一组排序结果的基础上，58，48，96按从小到大顺序排列交换位置后最新排序为：12，3，48，37，26，58，54，64，96，75

三、简单选择

排序方式：每一次排序都把当前最小的元素拿出来
初始关键词：1，5，2，7，4

四、堆排序

排序方式：
1.先把元素按照完全二叉树的形式建成一个堆
2.再按大根堆（左<根>右）排序
3.从下往上调整，直至全部满足左<根>右
4.把堆顶元素跟堆底最后一个元素交换，继续调整，直至全部满足左<根>右

五、冒泡排序

排序方式：从第一个元素开始，前面一个元素跟后面一个元素两两比较，前面大于后面则交换

六、快速排序

排序方式：
1.从后往前找第一个小于关键字p（初始序列中第一个元素，且不会变更）
2.这里用i代表最前，j代表最后
3.当j>p时则j往前移一位(j--),当j<p时，把j的值赋值给i，这时候再从最前面开始找
4.当i<p时，i往后挪一位（i++）
5.当i>p时，把i的值赋值给j
6.循环以上步骤直到i=j,则把p的值赋值给i=j这个位置

七、归并排序

排序方式：假设有n个元素（ 2，1，4，7，3，5，6，2）；则n=8,每次按n/2分组排序