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

《C++ 八种排序算法总结及实现》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、八种排序算法总结之C++版本五种简单排序算法一、冒泡排序【稳定的】voidBubbleSort(int*a,intCount)//实现从小到大的最终结果{inttemp;for(inti=1;i=i;j--)if(a[j]=n0时，有f(n)<=K*g(n

2、),则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)。二、交换排序【稳定的】voidExchangeSort(int*a,intCount){inttemp;for(inti=0;i

3、if(a[j]

4、，记录当前最小元素的下标位置}a[pos]=a[i];a[i]=temp;}}遗憾的是算法需要的循环次数依然是1/2*(n-1)*n。所以算法复杂度为O(n*n)。我们来看他的交换。由于每次外层循环只产生一次交换（只有一个最小值）。所以f(n)<=n所以我们有f(n)=O(n)。所以，在数据较乱的时候，可以减少一定的交换次数。一、插入法【稳定的】voidInsertSort(int*a,intCount){inttemp;//一个存储值intpos;//一个存储下标for(inti=1;i

5、//最多做n-1趟插入{temp=a[i];//当前要插入的元素pos=i-1;while(pos>=0&&temp

6、(inti=d;i=0&&temp1);}三种高级排序算法一、快速排序辅助空间复杂度为O（1）【不稳定的】voidQuickSort(int*a,intleft,intright){inti,j,middle,temp;i=left;j=right;middle=a[(left+ri

7、ght)/2];do{while(a[i]middle&&j>left)//从右扫描小于中值的数j--;if(i<=j)//找到了一对值{temp=a[i];a[i]=a[j];a[j]=temp;i++;j--;}}while(ii）,递归右

8、半边if(i