C++ 八种排序算法总结及实现

八种排序算法总结之C++版本

五种简单排序算法

一、 冒泡排序 【稳定的】

void BubbleSort( int* a,int Count ) //实现从小到大的最终结果

{

int temp;

for(int i=1; i<Count; i++) //外层每循环一次，将最小的一个移动到最前面 for(int j=Count-1; j>=i; j--)

if( a[j] < a[j-1] )

{

temp = a[j];

a[j] = a[j-1];

a[j-1] = temp;

}

}

现在注意，我们给出O方法的定义：

若存在一常量K和起点n0，使当n>=n0时，有f(n)<=K*g(n),则f(n) = O(g(n))。（呵呵，不要说没学好数学呀，对于编程数学是非常重要的！！！）

现在我们来看1/2*(n-1)*n，当K=1/2，n0=1，g(n)=n*n时，1/2*(n-1)*n<=1/2*n*n=K*g(n)。所以f(n) =O(g(n))=O(n*n)。所以我们程序循环的复杂度为O(n*n)。

二、 交换排序 【稳定的】

void ExchangeSort( int *a,int Count)

{

int temp;

for(int i=0; i<Count-1; i++)

for(int j=i+1; j<Count; j++)

if( a[j] < a[i] )

{

temp = a[j];

a[j] = a[i];

a[i] = temp;

}

}

时间复杂度为O(n*n)。

三、 选择法 【不稳定的】

void SelectSort( int *a,int Count)

{

int temp; //一个存储值

int pos; //一个存储下标

for(int i=0; i<Count; i++)

{

temp = a[i];

pos = i;

for(int j=i+1; j<Count; j++)

if( a[j] < temp ) //选择排序法就是用第一个元素与最小的元素交换 {

temp = a[j];

pos = j; //下标的交换赋值，记录当前最小元素的下标位置 }

a[pos] = a[i];

a[i] = temp;

}

}

遗憾的是算法需要的循环次数依然是1/2*(n-1)*n。所以算法复杂度为O(n*n)。

我们来看他的交换。由于每次外层循环只产生一次交换（只有一个最小值）。所以f(n)<=n 所以我们有f(n)=O(n)。所以，在数据较乱的时候，可以减少一定的交换次数。

四、 插入法 【稳定的】

void InsertSort( int *a,int Count)

{

int temp; //一个存储值

int pos; //一个存储下标

for(int i=1; i<Count; i++) //最多做n-1趟插入

{

temp = a[i]; //当前要插入的元素

pos = i-1;

while( pos>=0 && temp<a[pos] )

{

a[pos+1] = a[pos]; //将前一个元素后移一位

pos--;

}

a[pos+1] = temp;

}

}

其复杂度仍为O(n*n)。

最终，我个人认为，在简单排序算法中，直接插入排序是最好的。

五、 希尔排序法 【不稳定的】

/*

* 希尔排序，n为数组的个数

*/

void ShellSort( int arr[], int n )

{

int temp,pos;

int d = n; //增量初值

do{

d = d/3 + 1 ;

for(int i= d; i<n; i++ )

{

temp = arr[i];

pos = i-d;

while( pos>=0 && temp < arr[pos] ) {

arr[ pos + d ] = arr[pos];

pos -= d;

}

arr[ pos + d ] = temp;

}

} while( d > 1 );

}

//实现增量为d的插入排序

三种高级排序算法

一、 快速排序 辅助空间复杂度为O（1） 【不稳定的】

void QuickSort( int *a,int left, int right)

{

int i,j,middle,temp;

i = left;

j = right;

middle = a[ (left+right)/2 ];

do

{

while( a[i]<middle && i<right ) //从左扫描大于中值的数

i++;

while( a[j]>middle && j>left ) //从右扫描小于中值的数

j--;

if( i<=j ) //找到了一对值

{

temp = a[i];

a[i] = a[j];

}

a[j] = temp; i++; j--; } } while ( i<j ); //如果两边的下标交错，就停止(完成一次) //当左半边有值（left<j）,递归左半边 if( left < j ) QuickSort( a, left, j); //当右半边有值（right>i）,递归右半边 if( i < right ) QuickSort( a, i, right);

它的工作看起来象一个二叉树。首先我们选择一个中间值middle，程序中我们使用数组中间值，然后把比它小的放在左边，大的放在右边（具体的实现是从两边找，找到一对后交换）。然后对两边分别使用这个过程（最容易的方法——递归）。注意，由于数据的随机性，对middle的选择并不会影响该算法的效率。

注意，在扫描过程中，对于给定参考值，对于向右(左)扫描，如果扫描值大(小)于或等于参考值，就需要进行交换。最终得到的结果是，j左边的值都小于参考值，而i右边的值都大于参考值，j和i之间的值都等于参考值。对j左边和i右边的分别使用递归，就可以完成最终的排序。

这里我没有给出行为的分析，因为这个很简单，我们直接来分析算法：首先我们考虑最理想的情况

1.数组的大小是2的幂，这样分下去始终可以被2整除。假设为2的k次方，即k=log2(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都是最小值或最大值，那么他将变

成交换法（由于使用了递归，情况更糟），但是糟糕的情况只会持续一个流程，到下一个流程的时候就很可能已经避开了该中间的最大和最小值，因为数组下标变化了，于是中间值不在是那个最大或者最小值。但是你认为这种情况发生的几率有多大？？呵呵，你完全不必 …… 此处隐藏：5059字，全部文档内容请下载后查看。喜欢就下载吧 ……