江苏龙网

  1. 主页 > 生活百科 > >

常见的内排序和外排序算法( 二 )

排序算法


3．堆排序堆排序（Heap Sort）利用了我们在第5章中提到的堆作为逻辑存储结构，将输入array变成一个最大值堆 。然后，我们反复进行堆的弹出操作 。回顾之前所述的弹出过程：将堆顶元素与堆末元素交换，堆的大小减一，向下移动新的堆顶以维护堆的性质 。事实上，该操作等价于每次将剩余的最大元素移动到数组的最右边，重复这样的操作最终就能获得由小到大排序的数组 。初次建堆的时间复杂度为O(n)，删除堆顶元素并维护堆的性质需要O(logn)，这样的操作一共进行n次，故最终时间复杂度为O(nlogn) 。我们不需要利用额外空间，故空间复杂度O(1) 。具体实现如下：
void heapSort(int array[], int size)　{Heapify(array, size);for (int i = 0; i < size - 1; i++)popHeap(array);}Heapify和popHeap的实现参考本书第5章 。
4．桶排序和基数排序桶排序（Bucket Sort）和基数排序（Radix Sort）不需要进行数据之间的两两比较，但是需要事先知道数组的一些具体情况 。特别地，桶排序适用于知道待排序数组大小范围的情况 。其特性在于将数据根据其大小，放入合适的“桶（容器）”中，再依次从桶中取出，形成有序序列 。具体实现如下：
void BucketSort(int array[], int n, int max){// array of length n，all records in the range of [0,max)int tempArray[n];int i;for (i = 0; i < n; i++)tempArray[i] = array[i];int count[max];// bucketsmemset(count, 0, max * sizeof(int));for (i = 0; i < n; i++)// put elements into the bucketscount[array[i]]++;for (i = 1; i < max; i++)count[i] = count[i-1] + count [i];　// count[i] saves the starting index (in array) of value i+1// for value tempArray[i], the last index should be count[tempArray[i]]-1for (i = n-1; i >= 0; i--)array[--count[tempArray[i]]] = tempArray[i];}该实现总的时间代价为O(max+n)，适用于max相对n较小的情况 。空间复杂度也为O(max+n)，用以记录原始数组和桶计数 。
桶排序只适合max很小的情况，如果数据范围很大，可以将一个记录的值即排序码拆分为多个部分来进行比较，即使用基数排序 。基数排序相当于将数据看作一个个有限进制数，按照由高位到低位（适用于字典序），或者由低位到高位（适用于数值序）进行排序 。排序具体过程如下：对于每一位，利用桶排序进行分类，在维持相对顺序的前提下进行下一步排序，直到遍历所有位 。该算法复杂度为O(k*n)，k为位数（或者字符串长度） 。直观上，基数排序进行了k次桶排序 。具体实现如下：
void RadixSort(int Array[], int n, int digits, int radix){// n is the length of the array// digits is the number of digitsint　*TempArray = new int[n];int *count = new int[radix]; // radix bucketsint i, j, k;int Radix = 1; // radix modulo, used to get the ith digit of Array[j]// for ith digitfor (i = 1; i <= digits; i++)　{for (j = 0; j < radix; j++)count[j] = 0;// initialize counterfor (j = 0; j < n; j++){// put elements into bucketsk = (Array[j] / Radix) % radix;　// get a digitcount[k]++;}for (j = 1; j < radix; j++) {// count elements in the bucketscount[j] = count[j-1] + count[j];}// bucket sortfor (j = n-1; j >= 0; j--)　{k = (Array[j] / Radix ) % radix;count[k]--;TempArray[count[k]] = Array[j];}for (j = 0; j < n; j++) {// copy data back to arrayArray[j] = TempArray[j];}Radix *= radix;// get the next digit}}与其他排序方式相比，桶排序和基数排序不需要交换或比较，它更像是通过逐级的分类来把元素排序好 。
常见的外排序算法外排序算法的核心思路在于把文件分块读到内存，在内存中对每块文件依次进行排序，最后合并排序后的各块数据，依次按顺序写回文件 。外排序需要进行多次磁盘读写，因此执行效率往往低于内排序，时间主要花费于磁盘读写上 。我们给出外排序的算法步骤如下：
假设文件需要分成k块读入，需要从小到大进行排序 。
（1）依次读入每个文件块，在内存中对当前文件块进行排序（应用恰当的内排序算法） 。此时，每块文件相当于一个由小到大排列的有序队列 。
（2）在内存中建立一个最小值堆，读入每块文件的队列头 。
（3）弹出堆顶元素，如果元素来自第i块，则从第i块文件中补充一个元素到最小值堆 。弹出的元素暂存至临时数组 。
（4）当临时数组存满时，将数组写至磁盘，并清空数组内容 。
（5）重复过程（3）、（4），直至所有文件块读取完毕 。
本文节选自《程序员面试白皮书》

【常见的内排序和外排序算法】


推荐阅读


上一篇：社保和医保是一回事吗？

下一篇：一款强大的本地文件内容搜索软件，可搜索文件中的文字