基本排序算法复习
基本排序算法回顾
以前学的几个基本排序算法大概简略回顾一下，以免忘记。。。。。。(冒泡就算了)
首先还是要回顾一下分治法，也就是把一个大的问题分成多个细节来处理，其实无论是在排序中的快排还是归并等等的许多算法都蕴含了这种思想。所谓分是分解，治是把小问题逐个击破，合就是把已解决的小问题合并。
归并排序
一串要排序的数字，把它一直细分下去，最后两两一对比较，然后再回退着比较。
1
2
3
4
5
6
7
8
9
10
11
12
1384571362
__________|__________
| |
8457 1362 分
______|______ ______|______
| | | |
84 57 13 62 ----------------------------------------------------
|______ ______| |______ ______|
| |
4578 1236 治
|___________ __________|
|
12345678快速排序
一串未排序的数字，假设两边各有一个动点(i,j)，数字串尾部动点先走，头部动点后走，每走一次两动点数字对比并排序，走到最后中间，与首数字对比并排序。然后就轮到两边了，先说左边，以头元素为标准，把左边的数以此与首数字对比，使大于它的在右边，小于它的在左边，这样一直重复到数字排列正确(排列次数看能进行多少次，就是平分多少次)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17· ·
6 1 2 7 9 3 4 5 10 8
|
· | ·
6 1 2 7 9 3 4 5 10 8
|
· | ·
6 1 2 5 9 3 4 7 10 8
|
·
6 1 2 5 4 3 9 7 10 8
|
3 1 2 5 4 6 9 7 10 8
| |
2 1 3 5 4 6 7 8 9 10
| |
1 2 3 4 5 6 7 8 9 10希尔排序(插入排序)
希尔排序是把乱序数字串长度除以2，n=length/2，则前n个数与自己加n的数为一组，比较并排序，然后刚才没有在一起的几个数比较并排序，至此数组的有序化大致完成，剩下的就是微调了。
1
2
3
4
5
6
7
8
9
10
11
12______________
__|___________ | _______________________
__|__|________ | | ==> __|_____|_____|_____|_____|
__|__|__|_____ | | | ==> | | | | | | | | | |
__|__|__|__|__ | | | | ==> 3 5 1 6 0 8 9 4 7 2
| | | | | | | | | |
8 9 1 7 2 3 5 4 6 0
n = 10/2 = 5
==>
==> 0 2 1 4 3 5 7 6 9 8
==>