|
所谓的内排序是指所有的数据已经读入内存，在内存中进行排序的算法。排序过程中不需要对磁盘进行读写。同时，内排序也一般假定所有用到的辅助空间也可以直接存在于内存中。与之对应地，另一类排序称作外排序，即内存中无法保存全部数据，需要进行磁盘访问，每次读入部分数据到内存进行排序。我们在9.1.2“常见的外排序算法”中讨论该类问题。 1．合并排序 合并排序（Merge Sort）是一种典型的排序算法，应用“分而治之（divide and conquer）”的算法思路，将线性数据结构（如array、vector或list）分为两个部分，对两部分分别进行排序，排序完成后，再将各自排序好的两个部分合并还原成一个有序结构。由于合并排序不依赖于随机读写，因此具有很强的普适性，适用于链表等数据结构。算法的时间复杂度为O(nlogn)，如果是处理数组需要额外O（n）空间，处理链表只需要O（1）空间。算法实现如下： void merge_sort( int array[], int helper[], int left, int right){ if( left >=right ) return; // divide and conquer: array will be divided into left part and right part // both parts will be sorted by the calling merge_sort int mid=right - (right - left) / 2; merge_sort( array, helper, left, mid ); merge_sort( array, helper, mid + 1, right); // now we merge two parts into one int helperLeft=left; int helperRight=mid + 1; int curr=left; for(int i=left; i <=right; i++) helper[i]=array[i]; while( helperLeft <=mid && helperRight <=right ){ if( helper[helperLeft] <=helper[helperRight] ) array[curr++]=helper[helperLeft++]; else array[curr++]=helper[helperRight++]; } // left part has some large elements remaining. Put them into the right side while( helperLeft <=mid ) array[curr++]=helper[helperLeft++]; } 当递归调用merge_sort返回时，array的左右两部分已经分别由子函数排序完成，我们利用helper数组暂存array中的数值，再利用两个while循环完成合并。helper数组的左右半边就是两个排序完的队列，第一个while循环相当于比较队列头，将较小的元素取出放入array，最后使得array的左半边由小到大排序完成。第二个while循环负责扫尾，把helper左半边剩余元素复制入array中。注意，此时我们不需要对helper右半边做类似操作，因为即使右半边有剩余元素，它们也已经处于array中恰当的位置。 关于合并排序更多理论方面的讨论，请见9.3“工具箱”。 2．快速排序 快速排序（Quick Sort）是最为常用的排序算法，C++自带的排序算法的实现就是快速排序。该算法以其高效性，简洁性，被评为20世纪十大算法之一（虽然合并排序与堆排序的时间复杂度量级相同，但一般还是比快速排序慢常数倍）。快速排序的算法核心与合并排序类似，也采用“分而治之”的想法：随机选定一个元素作为轴值，利用该轴值将数组分为左右两部分，左边元素都比轴值小，右边元素都比轴值大，但它们不是完全排序的。在此基础上，分别对左右两部分递归调用快速排序，使得左右部分完全排序。算法的平均时间复杂度是O(nlogn)，在最坏情况下为O(n^2)，额外空间复杂度为O(logn)。算法实现如下： int partition( int array[], int left, int right ) { int pivot=array[right]; while( left !=right ){ while( array[left] < pivot && left < right) left++; if (left < right) { swap( array[left], array[right--]); } while( array[right] > pivot && left < right) right--; if( left < right ) swap( array[left++], array[right]); } //array[left]=pivot; return left; } void qSort( int array[], int left, int right ){ if( left >=right ) return; int index=partition( array, left, right); qSort(array, left, index - 1); qSort(array, index + 1, right); } partition函数先选定数组right下标所指的元素作为轴值，用pivot变量存储该元素值。然后，右移left，即从左向右扫描数组，直到发现某个元素大于轴值或者扫描完成。如果某个元素大于轴值，则将该元素与轴值交换。该操作特性在于：保证交换后轴值左侧的元素都比轴值小。再次，左移right，即从右向左扫描数组，直到发现某个元素小于轴值或者扫描完成。如果某个元素小于轴值，则将该元素与轴值交换。该操作特性在于：保证交换后轴值右侧的元素都比轴值大。重复上述过程直到left和right相遇，最终相遇的位置即为轴值所在位置。由于上述操作的特性，最终轴值左侧的元素都比轴值小，轴值右侧的元素都比轴值大。 关于快速排序的更多理论讨论请见9.3“工具箱”。C++标准模版库提供函数sort，实现快速排序的功能：sort( iterator first, iterator last, Compare comp ); // can also be pointers here。 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]; // buckets memset(count, 0, max * sizeof(int)); for (i=0; i < n; i++) // put elements into the buckets count[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]]-1 for (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 digits int *TempArray=new int[n]; int *count=new int[radix]; // radix buckets int i, j, k; int Radix=1; // radix modulo, used to get the ith digit of Array[j] // for ith digit for (i=1; i <=digits; i++) { for (j=0; j < radix; j++) count[j]=0; // initialize counter for (j=0; j < n; j++) { // put elements into buckets k=(Array[j] / Radix) % radix; // get a digit count[k]++; } for (j=1; j < radix; j++) { // count elements in the buckets count[j]=count[j-1] + count[j]; } // bucket sort for (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 array Array[j]=TempArray[j]; } Radix *=radix; // get the next digit } } 与其他排序方式相比，桶排序和基数排序不需要交换或比较，它更像是通过逐级的分类来把元素排序好。 外排序算法的核心思路在于把文件分块读到内存，在内存中对每块文件依次进行排序，最后合并排序后的各块数据，依次按顺序写回文件。外排序需要进行多次磁盘读写，因此执行效率往往低于内排序，时间主要花费于磁盘读写上。我们给出外排序的算法步骤如下： 假设文件需要分成k块读入，需要从小到大进行排序。 （1）依次读入每个文件块，在内存中对当前文件块进行排序（应用恰当的内排序算法）。此时，每块文件相当于一个由小到大排列的有序队列。 （2）在内存中建立一个最小值堆，读入每块文件的队列头。 （3）弹出堆顶元素，如果元素来自第i块，则从第i块文件中补充一个元素到最小值堆。弹出的元素暂存至临时数组。 （4）当临时数组存满时，将数组写至磁盘，并清空数组内容。 （5）重复过程（3）、（4），直至所有文件块读取完毕。 本文节选自《程序员面试白皮书》 本书是程序员和IT从业人员的面试求职指南。本书遵从大多数面试参考图书的组织方式，结合实例，按照常见的数据结构、算法以及计算机基础知识进行章节划分。每一章的“知识要点”部分介绍章节涉及的相关知识点，回顾重要的基础知识点；“模式识别”部分给出一些例题，帮助大家总结解决相关问题的常见方法，并且通过分析问题中的关键信息，教授读者如何从题目中分析题型和解题方法。程序员面试是对于面试者计算机知识的全面检测，因此，本书设有专门的章节覆盖了网络、操作系统、编译器、算法和数据结构等等各个领域的知识。 本书作者来自硅谷一线的IT公司，书中包含了作者亲身的经验和体验，书中收集的题目部分来自互联网上分享的面试经验、在线编程网站leetcode，以及一些著名的面试参考资料。本书适合想要从事正规的程序员、架构师以及相关IT公司的专业人士和学生参考，尤其适合那些以一线IT外企或互联网公司为求职目标的读者阅读。 |
|
|
来自： 新用户0175WbuX > 《待分类》
