《内部排序算法学习总结》由会员分享,可在线阅读,更多相关《内部排序算法学习总结(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 我们可以认为它有三个关键字,分别是百位数,十位数和个位数,其中个位数优先级最低,百位数