江苏龙网

  1. 主页 > 生活百科 > >

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

排序算法

常见的内排序算法所谓的内排序是指所有的数据已经读入内存，在内存中进行排序的算法 。排序过程中不需要对磁盘进行读写 。同时，内排序也一般假定所有用到的辅助空间也可以直接存在于内存中 。与之对应地，另一类排序称作外排序，即内存中无法保存全部数据，需要进行磁盘访问，每次读入部分数据到内存进行排序 。我们在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_sortint mid = right - (right - left) / 2;merge_sort( array, helper, left, mid );merge_sort( array, helper, mid + 1, right);// now we merge two parts into oneint 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++];elsearray[curr++] = helper[helperRight++];}// left part has some large elements remaining. Put them into the right sidewhile( 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 。


推荐阅读


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

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