除了基数排序（我···我看了一下，感觉好麻烦的，就没看了···不好意思啊···），以下包括了所有考研计算机要求的内排简介
1.直接插入：n-1趟（用for循环）；
其中一趟：待排文件中第一个元素插入到已排序文件中适当位置使仍然有序。最初，除了第一个元素（可看成已排序文件），整个文件为待排文件。
时间复杂度：O(n^2)。
2.折半插入：n-1趟（用for循环）；
其中一趟：将待排文件中第一个元素用折半插入法插入到已排文件中适当位置是仍然有序。最初，除了第一个元素（可看成已排序文件），整个文件为待排文件。
折半插入法：
int left=0,right=i-1; //目前已排文件有i个元素
Element temp = list.Vector[i]; //现在排第i+1个元素，即i号元素
while(left<=right){ //折半核心部分
int middle = (left+right)/2;
if(temp.getKey()
right = middle - 1;
else left = middle + 1;
}
时间复杂度：O(n^2)。
3.冒泡：n趟（用for循环）；
其中一趟：从底部（即待排文件尾）开始，两两比较得到水里泡泡（即待排文件里所有元素）中最轻的（即最小的）浮到水面（即排到待排文件头），最终可得到升序文件。最初，整个文件为待排文件。
时间复杂度： O(n^2)。
4.选择：n-1趟（用for循环）；
其中一趟：从待排文件中选一个最小的元素排到待排文件头。最初，除了第一个元素（可看成已排序文件），整个文件为待排文件。
时间复杂度 O(n^2)。
5.希尔：很多趟，很多次选择增量；
先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。所有距离为dl的倍数的记录放在同一个组中。先在各组内进行直接插人排序；然后，取第二个增量d21重复上述的分组和排序，直至所取的增量dt=1(dtt-l<…21)，即所有记录放在同一组中进行直接插入排序为止。
时间复杂度 O(nlog n)。
6.快速：分治（分而治之）的思想。
很多趟，但每一趟都不是即刻产生一个当下最小的元素而排好；
而是，每一趟都对整个待排文件“做手脚”，即：通过递归，每次使各个子待排文件的枢轴（枢轴指：向下取整地算出各个子待排文件的中间元素）左边的每个元素均小于右边的每个元素。
时间复杂度 最坏：O(n^2)；平均：O(nlog n)。
7.堆：堆分大根堆，小根堆；
通常：大根堆：用来堆排序；小根堆：用来构造优先级队列；
堆排序是个建堆重建堆过程（熊岳山大师上课时说过滴原话哟！崇拜~）：
建大根堆，拿走根，再建大根堆，再拿走根；
每次将新拿到的大根放到待排文件尾，最终形成升序的有序文件。
时间复杂度 O(nlog n)。
8.二路归并：
归并：将多个有序序列归并为一个有序序列；
二路归并：将两个有序序列归并为一个有序序列。
二路归并排序算法：将n个长度为1的子序列两两二路归并，最后变为一个有序序列。
具体地说：
第1趟归并排序时，将数列A[1..n]看作是n个长度为1的有序序列，将这些序列两两归并，若n为偶数，则得到[n/2]个长度为2的有序序列；若n为奇数，则最后一个子序列不参与归并。第2趟归并则是将第1趟归并所得到的有序序列两两归并。如此反复，直到最后得到一个长度为n的有序文件为止。
时间复杂度 O(nlog n)。
排序计算的复杂度评价：好O(nlog n)；坏O(n^2)；理想O(n)。
基于比较的任何内部排序法，最坏情况下所需比较次数不少于O(nlog n).
The End
阅读(1147) | 评论(0) | 转发(0) |
