排序算法总结,常用计算机排序算法简单总结

on 2011-6-20 in 博文摘选 | 0 Comment
计算机排序算法主要分为内排序和外排序，内排序主要指数据存储在内存中的排序，外排序通常指待排序的数据量很大，而且大部分数据存储于文件中，排序时需要读写文件的排序。通常大家讨论的都是内排序，因为内排序是外排序的根基，通常外排序过程都程序要辅助内排序。
最常见的内排序是冒泡排序，其时间复杂度为O(n^2), 空间复杂度为O(1)，基本上属于就地排序，而且该算法具有稳定性，在数据量不大，而且顺序基本已经排列好的情况下，该算法应该被优先考虑，其实现代码如下：

冒泡排序（Bubble Sort）

//Data swop function void Swap(int &p,int &q) { p=p^q; q=p^q; p=p^q; } //Bubble sort void BuubleSort(int ArrayInput[],int nNum) { int i = 0, j=0; for( i=0; i ) { for(j=0; j) { if(ArrayInput[j] > ArrayInput[j+1]) { Swap( ArrayInput[j], ArrayInput[j+1] ); } } } } int _tmain(int argc, _TCHAR* argv[]) { int nNum = 10; int ArrayInput[] = {2,3,1,4,8,8,9,7,6,5}; BuubleSort(ArrayInput, nNum); for(int i=0; i) { cout << ArrayInput[i] << " "; } cout <<endl; return 0; }

另一个比较常用的内排序是快速排序，其平均时间复杂度为O(nlgn), 最坏时间复杂度为O(n^2), 该算法为不稳定排序算法，通常对大量数据进行排序时，时间优势还是比较明显的。


快速排序（Quick Sort）
N个元素被分成3组：left, right, pivot，其中Left<=pivot<=right，所以left和right可以分别排序，而且Quick Sort中可以省去对结果组合的步骤,代码如下:
//Data swop function void Swap(int &p,int &q) { p=p^q; q=p^q; p=p^q; } //Partition function int Partition(int ArrayInput[],int nLow,int nHigh) { int i = 0, j=0, nTemp=0; i=nLow; j=nHigh; nTemp=ArrayInput[i]; do { //From right to left while((ArrayInput[j]>nTemp) && (i
Tags:  排序算法 计算机常用算法 常用的排序算法 常用排序算法 排序算法总结

延伸阅读

最新评论

发表评论