C++排序算法总结及性能大致分析.docx
《C++排序算法总结及性能大致分析.docx》由会员分享，可在线阅读，更多相关《C++排序算法总结及性能大致分析.docx（27页珍藏版）》请在冰点文库上搜索。
C++排序算法总结及性能大致分析
这里讲的排序默认为内排序。
参考书籍：
数据结构（C语言版）
秦玉平马靖善主编
冯佳昕周连秋副主编
清华大学出版社
按照排序过程中依据的原则不同划分为：
（1）插入排序包括直接插入排序，折半插入排序，2_路插入排序，shell排序
（2）交换排序包括简单交换排序，冒泡排序，快速排序
（3）选择排序包括简单选择排序，*树形选择排序，*堆排序
（4）归并排序
（5）计数排序包括*计数排序，基数排序
*上面打星号的代码没有添加*
下面代码修改自
主要修改了快速排序的错误，添加了折半插入排序和2_路插入排序，而且按照以上
（1）~（5）重新改写了程序的结构。
代码如下：
排序头文件：
sort.h
#ifndef__SORT_H__
#define__SORT_H__
/************************************************************************/
/*排序头文件*/
/************************************************************************/
/************************************************************************/
/*头文件包含*/
#include"insertSort.h"
#include"exchangeSort.h"
#include"selectSort.h"
#include"mergeSort.h"
#include"countSort.h"
/************************************************************************/
#endif
（1）插入排序：
insertSort.h
#ifndef__INSERTSORT_H__
#define__INSERTSORT_H__
/************************************************************************/
/*常用头文件包含*/
#include
usingnamespacestd;
/************************************************************************/
/************************************************************************/
/*插入排序的思想
插入排序属于插入方法的排序算法，它的想法是从第一个元素开始，创建
有序序列，把未排序序列依次插入到有序序列中，以此类推
*/
/************************************************************************/
/*函数实现，按从小到大排序*/
template
voidinsertSort（vector&v）
{
/*直接插入排序*/
for（unsignedinti=1;i{
Ttmp=v[i];
intj=i-1;
while（j>=0&&v[j]>tmp）
{
v[j+1]=v[j];
j--;
}
v[j+1]=tmp;
}
}
template
voidbiInsertSort（vector&v）
{
/*折半插入排序*/
for（unsignedinti=1;i{
Ttmp=v[i];
intlow=0;
inthigh=i-1;
while（low<=high）
{
intmid=（low+high）/2;
if（tmp>v[mid]）
{
low=mid+1;
}
else
{
high=mid-1;
}
}
intj=i-1;
while（j>=0&&v[j]>tmp）
{
v[j+1]=v[j];
j--;
}
v[j+1]=tmp;
}
}
template
voidbinInsertSort（vector&v）
{
/*2_路查找排序*/
vectorvecTmp（v）;
intfirst,final,low,high,mid,k,j;
unsignedinti,siz;
siz=v.size（）;
first=final=0;
for（i=1;i{
Ttmp=v[i];
if（tmp>=vecTmp[0]）
{
low=0;
high=final;
while（low<=high）
{
mid=（low+high）/2;
if（v[i]>vecTmp[mid]）
{
low=mid+1;
}
else
{
high=mid-1;
}
}
for（j=final;j>=low;j--）
{
vecTmp[j+1]=vecTmp[j];
}
vecTmp[low]=tmp;
final++;
}
else
{
if（first==0）
{
first=siz-1;
vecTmp[siz-1]=tmp;
}
else
{
low=first;
high=siz-1;
while（low<=high）
{
mid=（low+high）/2;
if（tmp>vecTmp[mid]）
{
low=mid+1;
}
else
{
high=mid-1;
}
}
for（j=first;j<=high;j++）
{
vecTmp[j-1]=vecTmp[j];
}
vecTmp[high]=tmp;
first--;
}
}
}
for（i=0,j=first;j{
v[i]=vecTmp[j];
}
for（k=0;k<=final;k++）
{
v[i++]=vecTmp[k];
}
}
/************************************************************************/
/*希尔排序*/
/*希尔排序的思想
希尔排序属于插入方法的排序算法，可以说是插入排序算法的改进版本，
它的想法是把数据分组，在分组内进行插入排序，以此类推，分组的大小
跟数据量有关系，D.E.Knuth建议数据量很大时按3*n+1分组，例如100
的数据时，可以取1，4，13，40。
*/
template
voidshellSort（vector&v）
{
for（unsignedintcount=（unsignedint）v.size（）/2;count>0;count/=2）
{
for（unsignedintgroup=0;group {
for（unsignedinti=group;i {
Ttmp=v[i];
intj=i-count;
while（j>=0&&v[j]>tmp）
{
v[j+count]=v[j];
j-=count;
}
v[j+count]=tmp;
}
}
}
}
/************************************************************************/
/************************************************************************/
#endif
（2）交换排序：
exchangeSort.h
#ifndef__EXCHANGESORT_H__
#define__EXCHANGESORT_H__
/************************************************************************/
/*常用头文件包含*/
#include
/*要用templatevoidswap（Type&_Left,Type&_Right）;*/
#include
#include
usingnamespacestd;
/************************************************************************/
/************************************************************************/
/*交换排序的思想
交换排序属于比较法的排序算法，它的想法是扫描整个数据，从第0个元素
开始，跟以后的元素逐个比较，按照排序规则（从小到大或者从大到小）交换
顺序，比较完第a后再去比较第a+1个元素，以此类推
*/
/*函数实现，按从小到大排序*/
template
voidexchageSort（vector&v）
{
for（unsignedinti=0;i{
for（unsignedintj=i+1;j {
if（v[i]>v[j]）
{
swap（v[i],v[j]）;
}
}
}
}
/************************************************************************/
/*冒泡排序的思想
冒泡排序属于比较法的排序算法，它的想法是比较相邻的两个数据，按照排序
规则（从小到大或者从大到小）交换顺序，再去比较下一组相邻元素，以此类推
*/
/************************************************************************/
/*函数实现，按从小到大排序*/
template
voidbubbleSort（vector&v）
{
boolflag=true;
for（unsignedinti=0;（i{
flag=false;
for（unsignedintj=0;j {
if（v[j]>v[j+1]）
{
swap（v[j],v[j+1]）;
flag=true;
}
}
}
}
/************************************************************************/
/************************************************************************/
/*快速排序的思想
快速排序的想法是尽可能的减少每次排序的数据量以提高效率，那么对于
任意从数据中取出的数据，可以按照大小把比它小的放在它的左边，比它
大的放在它的右边，那么这个数的位置就确定了，再在它的左右两边分别
按此排序，这就是快速排序。
*/
/*函数实现，按从小到大排序*/
template
voidquickSort（vector&v,unsignedintleft,unsignedintright）
{
if（left{
unsignedintpivot=left;
unsignedintlow=left+1;
unsignedinthigh=right;
while（low {
while（low {
low++;
}
while（low=v[pivot]）
{
high--;
}
if（low {
swap（v[low],v[high]）;
}
}
if（v[pivot]>v[high]）
{
swap（v[pivot],v[high]）;
}
if（high>left）
{
quickSort（v,left,high-1）;
}
if（low {
quickSort（v,low,right）;
}
}
}
/************************************************************************/
#endif
（3）选择排序：
selectSort.h
#ifndef__SELECTSORT_H__
#define__SELECTSORT_H__
/************************************************************************/
/*常用头文件包含*/
#include
/*要用templatevoidswap（Type&_Left,Type&_Right）;*/
#include
usingnamespacestd;
/************************************************************************/
/************************************************************************/
/*选择排序的思想
选择排序属于选择法的排序算法，它的想法是按照排序规则（从小到大或者
从大到小）查找最小（大）的元素，并与第一个元素交换，再在剩下的元素中
重复此过程以此类推
*/
/************************************************************************/
/************************************************************************/
/*函数实现，按从小到大排序*/
template
voidselectSort（vector&v）
{
for（unsignedinti=0;i{
unsignedintmin=i;
for（unsignedintj=i+1;j {
if（v[min]>v[j]）
{
min=j;
}
}
swap（v[i],v[min]）;
}
}
//////////////////////////////////////////////////////////////////////////
#endif
（4）归并排序：
mergeSort.h
#ifndef__MERGESORT_H__
#define__MERGESORT_H__
/************************************************************************/
/*常用头文件包含*/
#include
/*要用templatevoidswap（Type&_Left,Type&_Right）;*/
#include
usingnamespacestd;
/************************************************************************/
/************************************************************************/
/*归并排序的思想
归并排序的思想跟快排序类似，即先不断地把数据分割至每组只有一个数据，
然后在按大小归并成一组有序数。
*/
/*函数实现，按从小到大排序*/
template
voidmergeSort（vector&v,unsignedintleft,unsignedintright）
{
unsignedinthalf;
if（left{
half=（left+right）/2;
mergeSort（v,left,half）;
mergeSort（v,half+1,right）;
merge（v,left,v,left,half,v,half+1,right）;
}
}
template
voidmerge（vector&v,unsignedintleft,
vectorA,unsignedintleftA,unsignedintrightA,
vectorB,unsignedintleftB,unsignedintrightB）
{
//归并，把向量A按始末位置leftA，rightA，
// 向量B按始末位置leftB，rightB,
// 排序归并到v中
unsignedintindexA=leftA;
unsignedintindexB=leftB;
while（indexA<=rightA&&indexB<=rightB）
{
if（A[indexA]>B[indexB]）
{
v[left++]=B[indexB++];
}
else
{
v[left++]=A[indexA++];
}
}
while（indexA<=rightA）
{
v[left++]=A[indexA++];
}
while（indexB<=rightB）
{
v[left++]=B[indexB++];
}
}
/************************************************************************/
#endif
（5）计数排序：
countSort.h
#ifndef__COUNTSORT_H__
#define__COUNTSORT_H__
/************************************************************************/
/*常用头文件包含*/
#include
#include
usingnamespacestd;
/************************************************************************/
/************************************************************************/
/*基数排序的思想
基数排序是根据数字的性质来进行的排序算法，它首先分离出个位数，并把
原数据按照个位数大小依次排序，得到一个排序结果，再将这个排序结果按
照十位数的大小在进行排序，以此类推，知道最高位排序即完成。
基数排序必须是正整数。
*/
/*函数实现，按从小到大排序*/
unsignedintfindMax（vectorv）;
unsignedintfindk（unsignedintnum,unsignedintkth）;
voidradixSort（vector&v）
{
unsignedintno;
unsignedintcount=findMax（v）
升级会员 