常用排序算法

排序有内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。这里介绍的几种排序算法都是内部排序。

---

冒泡排序法

在要排序的一组数中，对当前还未排好序的范围内的全部数，自上而下对相邻的两个数依次进行比较和调整，让较大的数往下沉，较小的往上冒。即：每当两相邻的数比较后发现它们的排序与排序要求相反时，就将它们互换。

void BubbleSort(int* pData,int Count) { int iTmp; for(int i=1;i<Count;i++) { for(int j=Count-1;j>=i;j--) //从下向上冒泡 { if(pData[j]<pData[j-1]) { iTmp=pData[j]; pData[j]=pData[j-1]; pData[j-1]=iTmp; } } } }

双向冒泡法

通常的冒泡都是单向的，而这里是双向的，也就是说，还要进行反向冒泡。

void Bubble2Sort(int* pData,int count) { int itmp; int left=1; int right=count-1; int t; do { //正向的部分 for(int i=right;i>=left;i--) { if(pData[i]<pData[i-1]) { itmp=pData[i]; pData[i]=pData[i-1]; pData[i-1]=itmp; t=i; } } left=t+1; //反向的部分 for(int i=left;i<right+1;i++) { if(pData[i]<pData[i-1]) { itmp=pData[i]; pData[i]=pData[i-1]; pData[i-1]=itmp; t=i; } } right=t-1; }while(left<=right); }

交换排序法

每次用当前的元素一一的同其后的元素比较并交换。

void ExchangeSort(int* pData,int Count) { int iTmp; //从第一个元素开始，到倒数第二个结束，最后一个不用比较，肯定是最大的数 for(int i=0;i<Count-1;i++) { for(int j=i+1;j<Count;j++) { if(pData[i]>pData[j]) { iTmp=pData[i]; pData[i]=pData[j]; pData[j]=iTmp; } } } }

选择排序法

要点：从数据中选择最小的同第一个值交换，再从剩下的部分中选择最小的与第二个交换，反复下去。由于每次外层循环只产生一次交换，所以在数据较乱的时候，可以减少一定的交换次数（与冒泡法和交换法相比较）。

void SelectSort(int* pData,int Count) { int iTmp,iPos; for(int i=0;i<Count-1;i++) { iTmp=pData[i]; iPos=i; for(int j=i+1;j<Count;j++) { if(pData[j<iTmp) { iTmp=pData[j]; iPos=j; } } pData[iPos]=pData[i]; pData[i]=iTmp; } }

插入排序法

插入法较为复杂，它的基本工作原理是抽出牌，在前面的牌中找到相应的位置插入，然后继续下一张。中间有个过程挺像冒泡的，注意下面代码的while终止条件。

//插入法较为复杂，它的基本工作原理是抽出牌，在前面的牌中找到相应的位置插入，然后继续下一张。 template<class T> void InsertSort(T* a, const int len) { int itmp; int ipos; for (int i = 1; i < len; i++) //从第二张牌开始，与前面的比对 { itmp = a[i]; ipos = i - 1; while (ipos >= 0&&itmp<a[ipos]) { a[ipos + 1] = a[ipos]; --ipos; } a[ipos + 1] = itmp; } }

快速排序法

思路： 1.首先我们选择一个中间middle，程序中我们使用数组中间值。 2.然后比对比它小的放在左边，比它大的放在右边（具体实现是从两边找，找到后交换）。 3.然后对两边分别使用这个过程（最容易的方法，递归）。

递归实现：

void run(int* pData,int left,int right) { int i=left; int j=right; int middle=pData[(left+right)/2]; //中间值 int itmp; do { while(pData[i]<middle&&i<right) //左侧扫描找到左侧大于等于middle的值 ++i; while(pData[j]>middle&&j>left) //右侧扫描找到右侧小于等于middle的值 --j; if(i<=j) //找到一对后交换 { itmp=pData[i]; pData[i]=pData[j]; pData[j]=itmp; ++i; --j; } }while(i<=j); //如果两边扫描的下标交错，就停止（完成一次） //以上部分代码实现了middle值左侧的都比middle小，右侧的都比millde大，然后下面用递归 //当左边部分有值（left<j）,递归左半边 if(left<j) { run(pData,left,j); } //当右边部分有值(right>i),递归右半边 if(i<right) { run(pData,i,right); } } void QuickSort(int* pData,int count) { run(pData,0,count-1); }

归并排序法

思路和快速排序法思路近似，先将序列分割，分割后排序，排序后归并。

//将2个有序序列合并为一个有序序列 void Merge(int a[],int start,int mid,int end) { int i,j,k,n1,n2; n1=mid-start+1; //左边序列长度 n2=end-mid; //右边序列长度 int* L=new int[n1]; int* R=new int[n2]; memcpy(L,&a[start],n1*sizeof(int)); memcpy(R,&a[mid+1],n2*sizeof(int)); for(k=start,i=0,j=0;i<n1&&j<n2;k++) { if(L[i]<R[j]) { a[k]=L[i]; i++; } else { a[k]=R[j]; ++j; } } if(i<n1){ for(j=i;j<n1;j++,k++) { a[k]=L[j]; } } if(j<n2){ for(i=j;i<n2;i++,k++) { a[k]=R[i]; } } } void MergeSort(int a[],int start,int end) { if(start<end) { int mid=(start+end)/2; MergeSort(a,start,mid); MergeSort(a,mid+1,end); Merge(a,start,mid,end); } }

---

参考资料 http://blog.jobbole.com/11745/ http://www.cnblogs.com/eniac12/p/5329396.html