《C++ 八种排序算法总结及实现》由会员分享，可在线阅读，更多相关《C++ 八种排序算法总结及实现（10页珍藏版）》请在金锄头文库上搜索。
1、八种排序算法总结之C+版本五种简单排序算法一、冒泡排序 【稳定的】void BubbleSort( int* a,int Count ) /实现从小到大的最终结果 int temp;for(int i=1; i=i; j-) if( aj =n0时，有f(n)v=K*g(n),则f(n) = O(g(n)。(呵呵，不要 说没学好数学呀，对于编程数学是非常重要的 ！)现在我们来看 l/2*(n-l)*n,当 K=l/2, nO=l, g(n)=n*n 时，l/2*(n-l)*nv=l/2*n*n=K*g(n)。 所以f(n) =O(g(n)=O(n*n)。所以我们程序循环的复杂度为O(n*n)。
2、二、交换排序 【稳定的】 void ExchangeSort( int *a,int Count) int temp;for(int i=0; iCount-1; i+) for(int j=i+1; jCount; j+) if( aj ai ) temp = aj;aj = ai;ai = temp;时间复杂度为 O(n*n)。三、选择法 【不稳定的】 void SelectSort( int *a,int Count)int temp; /一个存储值int pos; /一个存储下标 for(int i=0; iCount; i+)temp = ai;pos = i;for(int j=i
3、+1; jCount; j+)if( aj temp ) /选择排序法就是用第一个元素与最小的元素交换 temp = aj;pos = j; /下标的交换赋值，记录当前最小元素的下标位置 apos = ai; ai = temp;遗憾的是算法需要的循环次数依然是l/2*(n-l)*n。所以算法复杂度为O(n*n)。我们来看他的交换。由于每次外层循环只产生一次交换(只有一个最小值)。所以 f(n)=0 & tempapos )apos+1 = apos; /将前一个元素后移一位 pos-;apos+1 = temp;其复杂度仍为 O(n*n)。 最终，我个人认为，在简单排序算法中，直接插入排序是
4、最好的。五、希尔排序法 【不稳定的】/* 希尔排序，n为数组的个数*/void ShellSort( int arr, int n ) int temp,pos;int d = n;/增量初值dod = d/3 + 1 ;for(int i= d; i=0 & temp 1 );三种高级排序算法一、快速排序辅助空间复杂度为 O(1)【不稳定的】void QuickSort( int *a,int left, int right)int i,j,middle,temp;i = left;j = right;middle = a (left+right)/2 ;dowhile( aimiddle
5、& imiddle & jleft ) / /从右扫描小于中值的数 j-;if( i=j ) /找到了一对值temp = ai;ai = aj;aj = temp;i+;j-; while ( ij ); /如果两边的下标交错，就停止(完成一次 )/当左半边有值(leftj)，递归左半边if( left j )QuickSort( a， left， j);/当右半边有值(righti)，递归右半边if( i right )QuickSort( a， i， right);它的工作看起来象一个二叉树。首先我们选择一个中间值middle,程序中我们使用数组 中间值，然后把比它小的放在左边，大的放在右
6、边(具体的实现是从两边找，找到一对后交 换)。然后对两边分别使用这个过程(最容易的方法递归)。注意，由于数据的随机性， 对 middle 的选择并不会影响该算法的效率。注意，在扫描过程中，对于给定参考值，对于向右(左)扫描，如果扫描值大(小)于或等于参考值，就需要进行交换。最终得到的结果是，j左边的值都小于参考值，而i右边的值都大于参考值，j和i之间的值都等于参考值。对j左边和i右边的分别使用递归，就可以完成最终的排序。这里我没有给出行为的分析，因为这个很简单，我们直接来分析算法：首先我们考虑最理想 的情况1. 数组的大小是2的幕，这样分下去始终可以被2整除。假设为2的k次方，即k=log2(
7、n)。2. 每次我们选择的值刚好是中间值，这样，数组才可以被等分。第一层递归，循环n次，第二层循环2*(n/2)所以共有 n+2(n/2)+4(n/4)+.+n*(n/n) = n+n+n+.+n=k*n=log2(n)*n 所以算法复杂度为 O(log2(n)*n) 其他的情况只会比这种情况差，最差的情况是每次选择到的 middle 都是最小值或最大值， 那么他将变成交换法(由于使用了递归，情况更糟)，但是糟糕的情况只会持续一个流程，到下一个流 程的时候就很可能已经避开了该中间的最大和最小值，因为数组下标变化了，于是中间值不 在是那个最大或者最小值。但是你认为这种情况发生的几率有多大？呵呵，
8、你完全不必担 心这个问题。实践证明，大多数的情况，快速排序总是最好的。如果你担心这个问题，你可以使用堆排序，这是一种稳定的O(log2(n)*n)算法，但是通常情 况下速度要慢于快速排序(因为要重组堆)。二、归并排序（两种实现方法均要掌握） 【稳定的】归并排序是一种极好的外部排序方法，即针对数据保存在磁盘上而不是高速内存中的 问题。以下程序参考数据结构课本P286页的模板，为使用指针链表实现的#include using namespace std;struct node/链表的节点数据int value;node *next;node * divide_from( node * head )
9、node * position, * midpoint, * second_half;if( (midpoint=head) = NULL ) /List is emptyreturn NULL;position = midpoint-next;while( position != NULL ) /Move position twice for midpoints one move position = position-next;if( position != NULL )midpoint = midpoint-next;position = position-next;second_hal
10、f = midpoint-next; midpoint-next = NULL; /在这里将原链拆断，分为两段 return second_half;node * merge( node * first, node * second)node * last_sorted; /当前已经链接好的有序链中的最后一个节点 node combined;/哑节点last_sorted = &combined;while( first!=NULL & second!=NULL )if( first-value value ) last_sorted-next = first; last_sorted = f
11、irst;first = first-next;else last_sorted-next = second;last_sorted = second; second = second-next;if( first=NULL ) last_sorted-next = second;elselast_sorted-next = first;return combined.next; /返回哑节点的后继指针，即为合并后的链表的头指针 /这里的参数必须是引用调用，需要这个指引去允许函数修改调用自变量void MergeSort( node * &head)if( head != NULL & hea
12、d-next != NULL ) /如果只有一个元素，则不需排序 node * second_half = divide_from( head );MergeSort( head );MergeSort( second_half );head = merge( head, second_half );int main()node a,b,c,d;node *p1, *p2, *p3, *p4,*head;p1 = &a;p2 = &b;p3 = &c;p4 = &d;a. value = 2;b. value = 4;c. value = 3;d. value = 1;a. next = p2;b. next = p3;c. next = p4;d. next = NULL;/调用归并排序前的结果head = p1;while( head != NULL )coutvaluenext;coutendl; MergeSort( p1 );/调用归并排序后的结果head = p1;while( head != NULL )coutvaluenext; couten
