内部排序算法学习总结

《内部排序算法学习总结》由会员分享，可在线阅读，更多相关《内部排序算法学习总结（9页珍藏版）》请在金锄头文库上搜索。

1、Sorting algorithm Sorting by Counting 通过计数的方式来排序 Comparison Counting 假设对 A1.N数组进行排序，用一个数组 count1.N来统计每个数应该出现的位置， 1 Set count1.N = 0; 2 for i = N; i 1; i- 2 for j = i-1; j =1; j-; if Aj Ai countj+; else counti+; 例如对于数组 2 3 4 1 5 第一次统计后 count 为：0 0 0 0 4 第二次统计后 count 为：1 1 1 0 4 第三次统计后 count 为：1 1 3 0

2、 4 第四次统计后 count 为：1 2 3 0 4 最后的 count 则对应了其出现的下标值 显然该算法时间复杂度为 O(n2）空间复杂度为 O(n)，很烂的算法，没啥用处，不过不需要移动记录 Distribution Counting 该方法是对上面方法的改进，假设数组 A 的最大值和最小值分别为 min max，设置一个 countmin.max数组来统计每个数应该出现的位置 1 Set countmin.max = 0; 2 for( i = 1; i = 1; j-) if (Aj Ai) Aj+1 = Aj; else break; Aj + 1 = pivote; 该算法最坏

3、情况就是输入数组为逆序的情况， 则比较和移动的次数为 1+2+.+N-1= N*(N-1)/2 O(n2) 平均下来，对于 i，每次比较和移动次数为 i/2，则总的次数为 N*(N-1)/4 约为(N2)/4 该算法在 N 不是很大，且数组基本有序的情况下，可以获得最好的效率，因此很多排序算法在对数据进行部分排序时，通常使用该算法。 Binary Insertion and two-way Insertion 对于第 i 个数，因为前 i-1 个数都是有序的了，我们需要找到合适的位置来将 i 插入进去，因此我们可以使用二分查找的方式在 i-1 中寻找合适的位置，例如对于 i=64，则比较 A3

4、2，如果大于 A64则比较 A16否则比较 A48，这样查找相应的插入位置只需要 log2N 次比较。但是即使我们找到了合适的插入位置，我们仍然需要将后面的记录往后挪一个位置，来腾出空间给要插入的数 Ai，因此总的时间复杂度并没有降低。 Shell Sorting 希尔排序希尔排序 如果某个排序算法，一次只移动一个位置的话，那么其时间复杂度是 O(n)，因此如果我们要提高效率的话，那么每次比较不能只是移动一个位置，而应该移动尽可能多的位置。希尔排序就是这样的算法，也称为 Diminishing increment sortion 例如对于 16 条记录，我们将其分为 8 组(A1,A9) (A

5、2, A10).(A8, A16)分别对每一组进行排序 之后分为 4 组（A1, A5, A9, A 13).(A4, A8, A12, A16)分别对每一组进行排序 然后分为 2 组，分别对每一组排序 最后对整个数组排序 对于每一个小组的排序可以使用直接插入排序。 对于组的选取可以根据数据的不同来选取， 但是最后一定是 1，例如此处是 8 4 2 1 当然也可以划分为 7 5 3 1 等等。 /h is the group number ShellSort(array A, int N, int h) for(i = 1; i 0; k-=h) if (Ak Aj) Ak+h = Ak; e

6、lse break; Ak+h = pivote; /assume array h stores the group number Shell(array A, int N, array h, int g_num) for(i = 1; i Aj+1) exchange(Aj, Aj+1); 此处给出的是最简单的实现方法， 显然这个方法还有很多改进的地方， 比如说不一定非要循环 N-1 次，如果某次循环的时候发现没有进行交换了，则表明序列已经是顺序的了，可以跳出，比如每次也不一定非要循环到 N-i 的地方，而是循环到上次最后一次做 exchange 操作的下标处就可以了，因为后面没有再进行 e

7、xchange，则表明后面已经是有序的了。 exchange_bound = N-1; is_exchange = 0; for(i = 1; i Aj+1) exchange(Aj, Aj+1); is_exchage+; exchange_bound = j; if (is_exchange = 0) break; QuickSort 快速排序快速排序 快速排序的基本思想是通过 partition， partition 是从待排序列中选取某个值， 然后按照这个值来进行划分， 左边的数都小于这个值， 右边的数都大于这个值， 然后对左边和右边的数继续划分。 partition(array, l

8、ow, high) if (array = NULL) return -1; if (low = high) return low; pivote = arraylow; i = low; j = high; while( true) while(arrayj = pivote i = low - 1; j = low; while(j = high) return; mid = partition(array, low, high); quicksort(array, low, mid -1); quicksort(array, mid+1, high); 快速排序最坏情况下的时间复杂度需要

9、 O(n2)， 但是一般情况下， 快速排序的时间复杂度为 O(n*log2n)，在比较排序中，快速排序是性能最好的一种排序方式，另外也可以对其进行改进，当划分后的子数组个数小于 8 个的时候，可以使用直接排序，而不必再进行划分了。 Radix Exchanging sorting 基数交换排序基数交换排序 基数交换排序是利用每个数的二进制表示来进行排序的， 同一般的比较不同， 它是通过二进制相应的位为 0 或 1 来比较。它有点类似与快速排序，其过程是： 1、将序列按照最高位来划分，左边的数该位都为 0，右边的数该位都为 1. 2、继续对最高位为 0 的新序列按照下一位为 0 还是 1 继续划

10、分，右边序列也一样，直到最后一位 这样最终就得到了有序的序列了。 radixPartition(array, low, high, bit) if (array = NULL) return -1; if (low = high) return low; i = low; j = high; while(true) while(arrayj mid = radixPartition(array, low, high, bit); bit = bit 1; radixSort(array, low, mid, bit); radixSort(array, mid+1, high, bit); 基

11、数排序的时间复杂度和快速排序一样，但是据说比快速排序要快一点。 Sorting By Selection 选择排序选择排序 排序算法中另外一个比较重要的方式就是选择， 通过不断的选择来求得最终有序的序列， 最简单的方法一般是： 1、从序列中找到最小的数，输出，将这个为止置为无穷大； 2、继续步骤 1 3、直到 N 个记录都已经选取出来了 选择排序要求所有待排列的数据都是已知的， 其最终结果是一次一次累计产生出来的， 而上面提到的其它排序方式， 在排序中间我们始终是没有办法得到一个有序的序列， 直到排序完成之后才最终得到有序的序列，而选择排序则排序过程中生成的结果都已经是有序的了。 上面的方法每

12、找到一个最小记录需要 N-1 次比较，并且需要一个 N 个大小的空间来存储最终的结果， 显然我们可以对其进行改进， 不需要使用无穷大值， 而只需要在每次找到一个最小值之后，将该值放置到原数组中合适的位置上就可以了。 Straight Selection Sort 直接选择排序直接选择排序 StrainghtSort(array, low, high) iMin = low; for (i = low; i arrayi) largest = l_child; if (r_child arraylargest) largest = r_child; if (largest != i) excha

13、nge(arraylargest, arrayi); HeapAdjust(array, largest, N); HeapSort(array, N) for(i = N/2; i =0; i-) HeapAdjust(array, i, N); for(i = N; i 1; i-) exchange(array1, arrayi); HeapAdjust(array, 1, i-1); 其时间复杂度为 O(N*log2N)， 对于 N 很大的情况， 该算法效率还不错， 但是当 N 很小的时候，该算法性能并不好， 因为第一次构建堆的时候是比较耗时的， 后面查找元素调整堆都最多只需要进行 h

14、（树的高度）次比较就够了 。 相比较快速排序，在最坏情况下，快速排序不如堆排序，堆排序的最坏情况和平均情况下性能差别不大，但是在平均情况下，快速排序则明显优于堆排序。 但是堆排序有个比较有意思的现象就是 Largest in, first out。因此堆排序可以用来实现优先级队列（Priority Queue)，例如操作系统按照进程的优先级调度，进程的优先级也许会不断的发生变化，但是每次出队的进程总会是优先级最高的。如果要实现优先级队列，则除了上述操作之外，还需要加入修改，插入操作。 Sorting By Merging 归并排序归并排序 归并的意思就是将两个或多个已经有序的数组合并为一个有序

15、的数组。 两路归并算法为： Merge(arraya, m, arrayb, n) while(i =m i+; else newArrayk+ = arraybj; j+; while(i = m) newArrayk+ = arrayai; while(j = n) newArrayk+ = arraybj; return newArray; 显然上述算法最多需要进行 m+n 次比较。 因此我们可以将一个数组不断的划分为多个小数组，对小数组进行排序后再归并为一个大的数组， 直到所有都归并完成。 另外我们也可以引入直接插入排序来对小数组先排序， 然后向上归并。 Sorting By Distribution 分布排序分布排序 Radix Sorting 基数排序基数排序 基数排序是对待排序列中存在多个关键字的情况下进行排序， 例如我们对扑克牌进行排序， 扑克牌有花色和面值两个关键字， 那么基数排序就是先按照优先级较小的关键字分成若干堆， 然后把这些堆垒成一个堆，接着按照更高优先级来将这个堆化为新的 N 个堆，把这些堆继续垒成一个堆，直到所有关键字都做完了，那么最后的结果就是有序的了。 例如对于数组：329 457 657 839 436 720 355 我们可以认为它有三个关键字，分别是百位数，十位数和个位数，其中个位数优先级最低，百位数