最近对于排序感兴趣了，参考了很多关于排序的书籍，写一些总结

1. 直接插入排序 （相邻比较）

       算法思想：外循环对趟数重复，每趟内循环先找插入位置，然后插入。

2. 折半插入排序
    折半插入排序用折半查找法确定插入位置。

3.气泡排序（bubble sort）

每趟两两相邻比较，发现逆序交换，最终将最大者交换到后面， 经过n-1趟，排序结束。

4.简单选择排序

第i 趟，R1 , R2 , R i-1已排好序，从R i , R i+1 , … R n中选择关键字最小的记录R j 与R i 交换位置。 经过n-1趟，排序结束。

5.希尔排序（shell sort）

给定一个递减的正整数间隔序列dk[0..t-1]且dk[0]必须为1，按每个间隔值dk的大小间隔分组，每组分别进行插入排序，经过t趟，排序结束。

间隔序列dk[0..t-1]的选取很重要，影响算法的效率。

6 快速排序

每趟取一个参照记录，称为枢轴（或支点），先从右向左，逐个记录与枢轴比较，如果逆序则交换，再从左向右，逐个记录与枢轴比较，如果逆序则交换，反复进行，直到左右相遇，结束一趟排序，
    并将枢轴记录交换到最终所在的位置上。所有大于枢轴的记录记录在右边，小于的在左边，一趟快速排序过程称为一个划分。然后分别对左右两部分进行相同的划分（或分割），得到4部分，再对每
    部分做相同划分，依次继续下去，直到每个小部分只有一个记录，排序结束。显然，对部分的划分操作完全相同，只是范围需修改，因此可以用递归实现，且最多经过[log2(n+1)]趟划分，排序结束。
7. 二路归并排序（merge sort）

该类排序方法的基本思想是：将两个有序集合并成一个新的有序集。

初始状态将每个元素构成一个有序集，第一趟将相邻的两个归并成一个新

有序集，变成n/2个有序集，第二趟，又将相邻的两个归并成一个新有序集，变成n/4个，依次继续下去，最多经过[log 2 n]+1趟，排序结束。

8．基数排序

第一趟，将末位字符相同的关键字，分配到同一个单链表中，然后逐个将各单链表中元素顺序收集到原链表中。

第二趟，将右边第二位符相同的关键字，分配到同一个单链表中，在逐个将各单链表中元素顺序收集到原链表中。

重复以上过程，直到最左边一位，排序结束。

重复次数 = 关键字位数。

几种排序过程的特征：

插入排序、简单选择排序：每趟把一个数据排在最终位置上，前几趟排序结果是前几个数据已有序。

起跑排序、堆排序：每趟把一个数据排在最终位置上，前几趟结果是最后几个数据已有序。

快速排序：每趟把一个数据排在最终位置上，使之前的小，之后的大。

希尔排序、归并排序、基数排序每趟不一定将一个数据排到最终位置上，只是局部有序。

最近对于排序感兴趣了，参考了很多关于排序的书籍，写一些总结

1. 直接插入排序 （相邻比较）

       算法思想：外循环对趟数重复，每趟内循环先找插入位置，然后插入。

2. 折半插入排序
    折半插入排序用折半查找法确定插入位置。

3.气泡排序（bubble sort）

每趟两两相邻比较，发现逆序交换，最终将最大者交换到后面， 经过n-1趟，排序结束。

4.简单选择排序

第i 趟，R1 , R2 , R i-1已排好序，从R i , R i+1 , … R n中选择关键字最小的记录R j 与R i 交换位置。 经过n-1趟，排序结束。

5.希尔排序（shell sort）

给定一个递减的正整数间隔序列dk[0..t-1]且dk[0]必须为1，按每个间隔值dk的大小间隔分组，每组分别进行插入排序，经过t趟，排序结束。

间隔序列dk[0..t-1]的选取很重要，影响算法的效率。

6 快速排序

每趟取一个参照记录，称为枢轴（或支点），先从右向左，逐个记录与枢轴比较，如果逆序则交换，再从左向右，逐个记录与枢轴比较，如果逆序则交换，反复进行，直到左右相遇，结束一趟排序，
    并将枢轴记录交换到最终所在的位置上。所有大于枢轴的记录记录在右边，小于的在左边，一趟快速排序过程称为一个划分。然后分别对左右两部分进行相同的划分（或分割），得到4部分，再对每
    部分做相同划分，依次继续下去，直到每个小部分只有一个记录，排序结束。显然，对部分的划分操作完全相同，只是范围需修改，因此可以用递归实现，且最多经过[log2(n+1)]趟划分，排序结束。
7. 二路归并排序（merge sort）

该类排序方法的基本思想是：将两个有序集合并成一个新的有序集。

初始状态将每个元素构成一个有序集，第一趟将相邻的两个归并成一个新

有序集，变成n/2个有序集，第二趟，又将相邻的两个归并成一个新有序集，变成n/4个，依次继续下去，最多经过[log 2 n]+1趟，排序结束。

8．基数排序

第一趟，将末位字符相同的关键字，分配到同一个单链表中，然后逐个将各单链表中元素顺序收集到原链表中。

第二趟，将右边第二位符相同的关键字，分配到同一个单链表中，在逐个将各单链表中元素顺序收集到原链表中。

重复以上过程，直到最左边一位，排序结束。

重复次数 = 关键字位数。

几种排序过程的特征：

插入排序、简单选择排序：每趟把一个数据排在最终位置上，前几趟排序结果是前几个数据已有序。

起跑排序、堆排序：每趟把一个数据排在最终位置上，前几趟结果是最后几个数据已有序。

快速排序：每趟把一个数据排在最终位置上，使之前的小，之后的大。

希尔排序、归并排序、基数排序每趟不一定将一个数据排到最终位置上，只是局部有序。