学步园

1.冒泡排序
2.选择排序
3.插入排序
4.交换排序
5.归并排序
6.快速排序
7.堆排序

8.希尔排序
9.双向冒泡排序
10.计数排序

11.基数排序

一、简单排序算法 

1.冒泡法： 
这是最原始，也是众所周知的最慢的算法了。他的名字的由来因为它的工作看来象是冒泡： 
// 冒泡法排序（升序）：O(n^2)<br /> // 思想：倒序，把比前一个元素小的与前一个交换，就相当于气泡上升。<br /> void BubbleSort(int* pData,int Count)<br /> {<br /> int iTemp;<br /> for(int i=1; i < Count; i++) // i，气泡上升顶点，<br /> {<br /> for(int j = Count-1; j >= i; j--) // 气泡上升过程<br /> {<br /> if(pData[j]<pData[j-1])<br /> {<br /> iTemp = pData[j-1];<br /> pData[j-1] = pData[j];<br /> pData[j] = iTemp;<br /> }<br /> }<br /> }<br /> }

倒序(最糟情况) 
第一轮：10,9,8,7->10,9,7,8->10,7,9,8->7,10,9,8(交换3次) 
第二轮：7,10,9,8->7,10,8,9->7,8,10,9(交换2次) 
第一轮：7,8,10,9->7,8,9,10(交换1次) 
循环次数：6次 
交换次数：6次 

其他： 
第一轮：8,10,7,9->8,10,7,9->8,7,10,9->7,8,10,9(交换2次) 
第二轮：7,8,10,9->7,8,10,9->7,8,10,9(交换0次) 
第一轮：7,8,10,9->7,8,9,10(交换1次) 
循环次数：6次 
交换次数：3次 

上面我们给出了程序段，现在我们分析它：这里，影响我们算法性能的主要部分是循环和交换， 
显然，次数越多，性能就越差。从上面的程序我们可以看出循环的次数是固定的，为1+2+...+n-1。 
写成公式就是1/2*(n-1)*n。 

现在注意，我们给出O方法的定义： 
   若存在一常量K和起点n0，使当n>=n0时，有f(n)<=K*g(n),则f(n) = O(g(n))。

从程序后面所跟的表可以看到，两种情况的循环相同，交换不同。其实交换本身同数据源的 
有序程度有极大的关系，当数据处于倒序的情况时，交换次数同循环一样（每次循环判断都会交换）， 
复杂度为O(n*n)。当数据为正序，将不会有交换。复杂度为O(0)。乱序时处于中间状态。正是由于这样的 
原因，我们通常都是通过循环次数来对比算法。 

2.交换法： 
交换法的程序最清晰简单，每次用当前的元素一一的同其后的元素比较并交换。 

// 交换法排序（升序）：O(n^2)<br /> // 思想：对于每一个元素，如果其后面的元素比它小，立刻与之交换，继续与之后的元素比较，交换<br /> void ExchangeSort(int* pData,int Count)<br /> {<br /> int iTemp;<br /> for(int i=0;i<Count-1;i++)<br /> {<br /> for(int j=i+1;j<Count;j++)<br /> {<br /> if(pData[j]<pData[i])<br /> {<br /> iTemp = pData[i];<br /> pData[i] = pData[j];<br /> pData[j] = iTemp;<br /> }<br /> }<br /> }<br /> }

倒序(最糟情况) 
第一轮：10,9,8,7->9,10,8,7->8,10,9,7->7,10,9,8(交换3次) 
第二轮：7,10,9,8->7,9,10,8->7,8,10,9(交换2次) 
第一轮：7,8,10,9->7,8,9,10(交换1次) 
循环次数：6次 
交换次数：6次 

其他： 
第一轮：8,10,7,9->8,10,7,9->7,10,8,9->7,10,8,9(交换1次) 
第二轮：7,10,8,9->7,8,10,9->7,8,10,9(交换1次) 
第一轮：7,8,10,9->7,8,9,10(交换1次) 
循环次数：6次 
交换次数：3次 

从运行的表格来看，交换几乎和冒泡一样糟。事实确实如此。循环次数和冒泡一样 
也是1/2*(n-1)*n，所以算法的复杂度仍然是O(n*n)。由于我们无法给出所有的情况，所以 
只能直接告诉大家他们在交换上面也是一样的糟糕（在某些情况下稍好，在某些情况下稍差）。 

3.选择法： 
现在我们终于可以看到一点希望：选择法，这种方法提高了一点性能（某些情况下） 
这种方法类似我们人为的排序习惯：从数据中选择最小的同第一个值交换，在从剩下的部分中 
选择最小的与第二个交换，这样往复下去。 

// 选择法排序（升序）：O(n^2)<br /> // 思想：从前往后，对于每一个元素，均从其与之后所有元素中选择最小的一个交换这个元素<br /> void SelectSort(int* pData,int Count)<br /> {<br /> int iTemp;<br /> int iPos;<br /> for(int i=0;i<Count-1;i++)<br /> {<br /> iTemp = pData[i];<br /> iPos = i;<br /> for(int j=i+1;j<Count;j++) // 从其后找最小的一个<br /> {<br /> if(pData[j]<iTemp)<br /> {<br /> iTemp = pData[j];<br /> iPos = j;<br /> }<br /> }<br /> pData[iPos] = pData[i]; // 交换最小的元素<br /> pData[i] = iTemp;<br /> }<br /> }

倒序(最糟情况) 
第一轮：10,9,8,7->(iTemp=9)10,9,8,7->(iTemp=8)10,9,8,7->(iTemp=7)7,9,8,10(交换1次) 
第二轮：7,9,8,10->7,9,8,10(iTemp=8)->(iTemp=8)7,8,9,10(交换1次) 
第一轮：7,8,9,10->(iTemp=9)7,8,9,10(交换0次) 
循环次数：6次 
交换次数：2次 

其他： 
第一轮：8,10,7,9->(iTemp=8)8,10,7,9->(iTemp=7)8,10,7,9->(iTemp=7)7,10,8,9(交换1次) 
第二轮：7,10,8,9->(iTemp=8)7,10,8,9->(iTemp=8)7,8,10,9(交换1次) 
第一轮：7,8,10,9->(iTemp=9)7,8,9,10(交换1次) 
循环次数：6次 
交换次数：3次 
遗憾的是算法需要的循环次数依然是1/2*(n-1)*n。

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

4.插入法： 
插入法较为复杂，它的基本工作原理是抽出牌，在前面的牌中寻找相应的位置插入，然后继续下一张 
// 插入法排序：O(n^2)<br /> // 思想：把数组分为有序区和无序区两个部分，初始以起始第一个元素为有序区<br /> // 每次取出无序区的第一个元素，相当于把有序区容量加1，把取出的元素与有序区元素倒序比较<br /> // 如果取出的元素较小，则把该有序区元素后移，同时继续比较，直到其不小于有序区该位置元素<br /> // 把取出的元素，写入到该位置的下一位。<br /> // 由于空位一直随着比较迁移，不要再做其他移动工作。<br /> // 就相当于码扑克牌，从排队里抓起一张，然后插入到合适的位置，同时也把比它大的牌后移。<br /> void InsertSort(int* pData,int Count)<br /> {<br /> int iTemp;<br /> int iPos;<br /> for(int i=1;i<Count;i++)<br /> {<br /> iTemp = pData[i];<br /> iPos = i-1;<br /> while((iPos>=0) && (iTemp<pData[iPos])) // 找寻要插入的位置<br /> {<br /> pData[iPos+1] = pData[iPos]; // 要插入的位置还在前面，要把当前元素后移，留出空位<br /> iPos--;<br /> }<br /> pData[iPos+1] = iTemp; // 插入<br /> }<br /> }

倒序(最糟情况) 
第一轮：10,9,8,7->9,10,8,7(交换1次)(循环1次) 
第二轮：9,10,8,7->8,9,10,7(交换1次)(循环2次) 
第一轮：8,9,10,7->7,8,9,10(交换1次)(循环3次) 
循环次数：6次 
交换次数：3次 

其他： 
第一轮：8,10,7,9->8,10,7,9(交换0次)(循环1次) 
第二轮：8,10,7,9->7,8,10,9(交换1次)(循环2次) 
第一轮：7,8,10,9->7,8,9,10(交换1次)(循环1次) 
循环次数：4次 
交换次数：2次 

上面结尾的行为分析事实上造成了一种假象，让我们认为这种算法是简单算法中最好的，其实不是， 
因为其循环次数虽然并不固定，我们仍可以使用O方法。从上面的结果可以看出，循环的次数f(n)<= 
1/2*n*(n-1)<=1/2*n*n。所以其复杂度仍为O(n*n)（这里说明一下，其实如果不是为了展示这些简单 
排序的不同，交换次数仍然可以这样推导）。现在看交换，从外观上看，交换次数是O(n)（推导类似 
选择法），但我们每次要进行与内层循环相同次数的‘=’操作。正常的一次交换我们需要三次‘=’ 
而这里显然多了一些，所以我们浪费了时间。 

二、高级排序算法：

5、归并排序：

归并（Merge）排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。

归并排序具体工作原理如下（假设序列共有n个元素）：

1. 将序列每相邻两个数字进行归并操作，形成floor(n / 2)个序列，排序后每个序列包含两个元素
2. 将上述序列再次归并，形成floor(n / 4)个序列，每个序列包含四个元素
3. 重复步骤2，直到所有元素排序完毕

 // 归并排序--归并函数<br /> void Merge(int* pData, int first, int mid, int last)<br /> {<br /> //申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列<br /> int *pTemp = new int[last-first+1];<br /> int begin1 = first, begin2 = mid + 1;<br /> int i;<br /> for(i = 0; begin1 <= mid && begin2 <= last; ++i)<br /> {<br /> //比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置<br /> if(pData[begin1] <= pData[begin2])<br /> pTemp[i] = pData[begin1++];<br /> else<br /> pTemp[i] = pData[begin2++];<br /> }<br /> //若有剩余，直接拷贝出来粘到合并序列尾<br /> if(begin1 <= mid)<br /> memcpy_s(pTemp + i, (last-first+1)*sizeof(int), pData + begin1, (mid-begin1+1)*sizeof(int));<br /> else if(begin2 <= last)<br /> memcpy_s(pTemp + i, (last-first+1)*sizeof(int), pData + begin2, (last-begin2+1)*sizeof(int));<br /> //将排序好的序列拷贝回数组中<br /> memcpy_s(pData + first, (last-first+1)*sizeof(int), pTemp, (last-first+1)*sizeof(int));<br /> delete pTemp;<br /> }<br /> // 归并排序<br /> // 思路：分组排序，把排序后的数组归并<br /> void MergeSort(int* pData, int first, int last)<br /> {<br /> int mid = 0;<br /> if(first < last)<br /> {<br /> mid = (first+last)/2;<br /> MergeSort(pData, first, mid);<br /> MergeSort(pData, mid+1, last);<br /> Merge(pData, first, mid, last);<br /> }<br /> } 

比较操作的次数介于(nlogn) / 2和nlogn − n + 1。 赋值操作的次数是(2nlogn)。 归并算法的空间复杂度为：Θ (n)

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

#include <utility><br /> // 快速排序，递归算法<br /> // 思路：取数组中间值作为划分元素，使该值左端元素均不大于它，右端元素均不小于它。该值在排序后的位置就定了。<br /> void QuickSort1(int* pData, int left, int right) // left和right表示要排序的范围<br /> {<br /> int i,j;<br /> int middle,iTemp;<br /> i = left;<br /> j = right;<br /> middle = pData[(left+right)/2]; //求中间值 ，作为划分元素<br /> do<br /> {<br /> while((pData[i]<middle) && (i<right)) //从左扫描大于中值的数<br /> i++;<br /> while((pData[j]>middle) && (j>left)) //从右扫描大于中值的数<br /> j--;<br /> if(i<=j) //找到了一对值<br /> {<br /> //交换，使左端元素均不大于划分元素，右端元素均不小于划分元素<br /> std::swap(pData[i], pData[j]);<br /> i++;<br /> j--;<br /> }<br /> }while(i<=j);//如果两边扫描的下标交错，就停止（完成一次）<br /> //当左边部分有值(left<j)，递归左半边<br /> if(left<j)<br /> QuickSort1(pData,left,j);<br /> //当右边部分有值(right>i)，递归右半边<br /> if(right>i)<br /> QuickSort1(pData,i,right);<br /> }<br /> // 快速排序，非递归算法<br /> // 思路：同上<br /> // 优化：1、当划分组元素个数较少时，直接使用插入法排序，提高效率。<br /> // 2、选择左、中、右三个元素中处于中间的那个元素为划分元素，防止仅选择中间元素作为换分元素时，中间元素恰好为最小或最大值的情况。<br /> void QSort(int* pData, int nCount, int m = -1)<br /> {<br /> static const int M=7, NSTACK=64; // M是使用直接插入法排序的子数组大小，NSTACK是所需的辅助存储器<br /> int i,ir,j,jstack=-1,l=0; // i，j为循环算子，ir为当前分组右端，l当前为分组左端，jstack为当前栈数组滑标<br /> int a;<br /> int istack[NSTACK]; // 堆栈，存放分组范围，i存放分组范围左端，i+1存放分组范围右端<br /> if (m > 0) nCount = min(m,nCount); // m是可选参数，如果m>0,标识只对前m个元素排序<br /> ir=nCount-1; // 初始分组，ir为最右端位置，l为起始点位置<br /> for (;;)<br /> {<br /> if (ir-l < M) // 当子数组足够小时，插入法排序<br /> {<br /> for (j=l+1;j<=ir;j++) // 插入法排序算法<br /> {<br /> a=pData[j];<br /> for (i=j-1;i>=l;i--)<br /> {<br /> if (pData[i] <= a) break;<br /> pData[i+1]=pData[i];<br /> }<br /> pData[i+1]=a;<br /> }<br /> if (jstack < 0) break; // 堆栈为NULL，数组已经排序完成<br /> // 弹出堆栈，并开始新一轮划分<br /> ir=istack[jstack--]; // 右端<br /> l=istack[jstack--]; // 左端<br /> }<br /> else // 快速排序核心算法<br /> {<br /> int k=(l+ir) >> 1; // k为当前分组范围的中点<br /> std::swap(pData[k],pData[l+1]); // 先把中间元素存放在第二位置<br /> // 挑选左、中、右三元素的中值作为划分元素a<br /> // 同时重新排列以使a[l]<=a[l+1]<=a[ir]<br /> if (pData[l] > pData[ir])<br /> {<br /> std::swap(pData[l],pData[ir]);<br /> }<br /> if (pData[l+1] > pData[ir])<br /> {<br /> std::swap(pData[l+1],pData[ir]);<br /> }<br /> if (pData[l] > pData[l+1])<br /> {<br /> std::swap(pData[l],pData[l+1]);<br /> }<br /> i=l+1; // 为划分初始化指针，左指针<br /> j=ir; // 右指针<br /> a=pData[l+1]; // 取划分元素<br /> for (;;) // 开始内循环<br /> {<br /> do i++; while (pData[i] < a); // 从数组首部向后寻找大于a的元素<br /> do j--; while (pData[j] > a); // 从数组尾部向前寻找小于a的元素<br /> if (j < i) break; // 指针交汇，划分结束<br /> std::swap(pData[i],pData[j]); // 各自找到元素，交换元素<br /> } // 结束内循环，此时j左端的均元素均小于j右端的元素，且j位置的元素小于当前划分元素a.<br /> pData[l+1]=pData[j]; // 插入划分元素，此时该元素位置已定<br /> pData[j]=a;<br /> // 准备入栈，此时各指针顺序：[l...ji...ir],j处元素就是以排好序的划分元素a<br /> jstack += 2;<br /> // 将指针压入堆栈中更大的数组，立刻处理较小的数组<br /> if (jstack >= NSTACK) throw("NSTACK too small in sort.");<br /> if (ir-i+1 >= j-l) // 右端较长，压入右端部分<br /> {<br /> istack[jstack]=ir;<br /> istack[jstack-1]=i;<br /> ir=j-1; // 修改右端指针<br /> }<br /> else // 压入左端部分入栈<br /> {<br /> istack[jstack]=j-1;<br /> istack[jstack-1]=l;<br /> l=i; // 修改左端指针<br /> }<br /> }<br /> }<br /> }<br />

这里我没有给出行为的分析，因为这个很简单，我们直接来分析算法：首先我们考虑最理想的情况 
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都是最小值或最大值，那么他将变 
成交换法（由于使用了递归，情况更糟）。

第二种方法采用了一些优化方法，效率要更高，避免了出现最坏的情况 。
如果你担心这个问题，你可以使用堆排序，这是一种稳定的O(log2(n)*n)算法，但是通常情况下速度要慢 
于快速排序（因为要重组堆）。

7、堆排序

堆排序的完整实现。代表了一个大公司的整个生存循环：雇佣N/2个工人，雇佣N/2个潜在的管理者，有一个值为升迁的过程，它是一种超级Peter原理的排序；最后按注定的过程：每个原来的雇员被一次提升为总裁。

堆排序的过程是：

1. 创建一个堆H[0..n-1]
2. 把堆首（最大值）和堆尾互换
3. 把堆的尺寸缩小1，并调用shift_down,目的是把新的数组顶端数据调整到相应位置，即重建堆
4. 重复步骤2，直到堆的尺寸为1

// 元素提升（上移），从[l,r]的元素中提出最大值作为堆[l,r]的堆顶。<br /> // 创建堆时：假设堆的形式是公司组织的二叉树结构，首先有N/2个元素作为员工，然后每进入一个元素作为潜在管理者，<br /> // 选择两个员工作为其直属下级，并从下级中选择较大值作为这两个员工的上级<br /> // 并把新来的员工插入到被升级的员工的位置上去，直至进入N/4个员工，选出N/4个上层节点；<br /> // 然后再进入节点时，就作为更高层次的潜在管理者，需要从下一级中找寻较大的作为此位置的真正管理者，如果下级的要升级，要带动更下级的升级<br /> // 重建堆时：每次从堆顶的直接下一级中选择最大元素晋升为老板，同时带动更下级的升迁。<br /> // 堆的特点：二叉树的形式，根为最大值（大根堆），节点向上的通路是相对排序的，但横向相邻的元素却没有必然的大小。<br /> //<br /> // 把一个线性数组理解为一个二叉树，那么索引i处元素的直接下级的第一个元素为2i+1。同层元素顺序存储<br /> // 证明：设i所在树的层为a，其在改层第b个节点，则 i = 2^a-1+b， 其直接下级的第一个元素索引 j = 2^(a+1)-1+2b = 2i+1<br /> void shift_down(int* pData, int l, int r)<br /> {<br /> int j, jold;<br /> int a = pData[l];<br /> jold = l; // jold用于存储a归位时的位置<br /> j = 2 * l + 1; // j为l的直接下属的第一个元素<br /> while (j <= r)<br /> {<br /> // 与下属中较大的比较，找到比后面相邻的元素较大的元素<br /> if(j < r && pData[j] < pData[j+1]) j++;<br /> // 找到a所在的层，停止筛选。否则更新a，继续<br /> if (a >= pData[j]) break;<br /> // 把较大的元素提前<br /> pData[jold] = pData[j];<br /> jold = j; // 更新a将要归位的位置<br /> j = 2 * j + 1;<br /> }<br /> pData[jold] = a; // 将a归位<br /> }<br /> // 堆排序<br /> void HeapSort(int* pData, int nCount)<br /> {<br /> // 创建堆<br /> for(int i = nCount/2-1; i >= 0; i--)<br /> // 堆创建时，i作为shift_down的左范围从n/2-1 to 0<br /> shift_down(pData, i, nCount-1);<br /> // 堆排序<br /> for(int i = nCount-1; i > 0; i--)<br /> {<br /> // 堆选择时，shift_down的右范围从n-2 to 0<br /> std::swap(pData[0], pData[i]); // 在数组尾部清出一个空间，使堆顶弹出并存入其中<br /> shift_down(pData, 0, i-1); // 重建堆<br /> }<br /> }

堆排序的平均时间复杂度为O(nlogn)，空间复杂度为Θ(1)。

8、SHELL排序

// 希尔排序，其中m数组中已有m个元素已排序<br /> // 思路：直接插入法的变形。选取一个逐渐递减的增量序列，按此增量对数组进行分组按直接插入法排序，然后减小增量再分组排序<br /> void ShellSort(int* pData, int nCount, int m)<br /> {<br /> int i, j, inc, n = nCount;<br /> int v;<br /> if (m > 0) n = min(m, n);<br /> inc = 1; // 确定初始增量<br /> do<br /> {<br /> inc *= 3;<br /> inc++;<br /> } while (inc <= n);<br /> do<br /> {<br /> // 部分排序的循环<br /> inc /= 3; // 减小增量<br /> for (i = inc; i < n; i++)<br /> { // 直接插入法的外循环<br /> v = pData[i];<br /> j = i;<br /> while (pData[j - inc] > v)<br /> { // 直接插入法的内循环<br /> pData[j] = pData[j - inc];<br /> j -= inc;<br /> if (j < inc) break;<br /> }<br /> pData[j] = v;<br /> }<br /> } while (inc > 1);<br /> } 

三、其他排序 

9、双向冒泡： 又叫鸡尾酒排序
通常的冒泡是单向的，而这里是双向的，也就是说还要进行反向的工作。 
代码看起来复杂，仔细理一下就明白了，是一个来回震荡的方式。 
// 双向冒泡排序<br /> void Bubble2Sort(int* pData, int nCount)<br /> {<br /> int i;<br /> int left = 1;<br /> int right =nCount -1;<br /> int t;<br /> do<br /> {<br /> //正向的部分<br /> for (i = right; i >= left; i--)<br /> {<br /> if(pData[i] < pData[i-1])<br /> {<br /> std::swap(pData[i], pData[i-1]);<br /> t = i;<br /> }<br /> }<br /> left = t+1;<br /> //反向的部分<br /> for(i = left; i < right + 1; i++)<br /> {<br /> if(pData[i] < pData[i-1])<br /> {<br /> std::swap(pData[i], pData[i-1]);<br /> t = i;<br /> }<br /> }<br /> right = t-1;<br /> }while(left <= right);<br /> }
双向冒泡排序最糟或是平均所花费的次数都是O(n²)，但如果序列在一开始已经大部分排序过的话，会接近O(n)。

10、计数排序

算法的步骤如下：

1. 找出待排序的数组中最大和最小的元素
2. 统计数组中每个值为i的元素出现的次数，存入数组C的第i项
3. 对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）
4. 反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1

// 计数排序<br /> void CountSort(int* pData, int nCount)<br /> {<br /> int i, j;<br /> // 计算排序数组的可取值范围<br /> int minNum = pData[0], maxNum = pData[0];<br /> for(i = 1; i < nCount; i++)<br /> {<br /> if(pData[i] < minNum)<br /> minNum = pData[i];<br /> else if(pData[i] > maxNum)<br /> maxNum = pData[i];<br /> }<br /> // 计数数组<br /> int range = maxNum - minNum + 1;<br /> int *pTemp = new int[range];<br /> memset(pTemp, 0, range * sizeof(int));<br /> // 如果元素存在，对应位置计数加1<br /> for(i = 0; i < nCount; ++i)<br /> {<br /> pTemp[pData[i]-minNum]++;<br /> }<br /> // 按顺序输出<br /> int k = 0;<br /> for(i = minNum; i <= maxNum; ++i)<br /> for(j = 0; j < pTemp[i - minNum]; ++j)<br /> pData[k++] = i;<br /> delete pTemp;<br /> } 

当输入的元素是 n 个 0 到 k 之间的整数时，它的运行时间是 Θ(n + k)。

11、基数排序

将所有待比较数值(正整数)统一为同样的数位长度,数位较短的数前面补零. 然后, 从最低位开始, 依次进行一次排序.这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列.
基数排序的方式可以采用LSD（Least significant digital）或MSD（Most significant digital），LSD的排序方式由键值的最右边开始，而MSD则相反，由键值的最左边开始。

// 基数排序<br /> // 思路：对数组元素每一位进行排序<br /> void RadixSort(int* pData, int nCount, int maxDigits)<br /> {<br /> const int base = 10;<br /> int arCountSort[10];<br /> int* pTemp = new int[nCount];<br /> int i, j;<br /> int t = 1;<br /> // LSD<br /> for(i = 0; i < maxDigits; ++i)<br /> {<br /> // 计数排序算子<br /> memset(arCountSort, 0, sizeof(int) * 10);<br /> for(j = 0; j < nCount; ++j)<br /> {<br /> arCountSort[pData[j]/t%base]++;<br /> }<br /> // 为了定位原元素的位置<br /> for(j = 1; j < 10; ++j)<br /> {<br /> arCountSort[j] += arCountSort[j-1];<br /> }<br /> // 按位排序好的数组写入临时数组里<br /> // 此处要用倒序，因为低位已经排过序，同一组优先进低位排序中靠后的<br /> for(j = nCount-1; j >= 0; --j)<br /> {<br /> int splitDigit = pData[j]/t%base;<br /> pTemp[arCountSort[splitDigit] - 1] = pData[j];<br /> arCountSort[splitDigit]--;<br /> }<br /> memcpy_s(pData, sizeof(int) * nCount, pTemp, sizeof(int) * nCount);<br /> t *= base;<br /> }<br /> } 

MSD算法代码：

// MSD法，基数排序+计数排序<br /> void RadixSort(int* pData, int index, int nCount, int maxDigits)<br /> {<br /> if(nCount <= 1 || maxDigits <= 0)<br /> return;<br /> const int base = 10;<br /> int arCountSort[base]; // 各位元素计数数组<br /> int arCountSortTemp[base];<br /> int* pTemp = new int[nCount];<br /> int i;<br /> int t = (int)pow((float)base, maxDigits-1);</p> <p> // 计数排序算子<br /> memset(arCountSort, 0, sizeof(int) * base);<br /> for(i = index; i < index + nCount; ++i)<br /> {<br /> arCountSort[pData[i]/t%base]++;<br /> }<br /> memcpy_s(arCountSortTemp, sizeof(int)*base, arCountSort, sizeof(int)*base);<br /> // 为了定位原元素的位置,此处每个arCountSort数组存放的是当前位前所有值的个数<br /> for(i = 1; i < base; ++i)<br /> {<br /> arCountSort[i] += arCountSort[i-1];<br /> }<br /> for(i = 0; i < base; ++i)<br /> {<br /> arCountSort[i] -= arCountSortTemp[i];<br /> }<br /> // 正序输出<br /> for(i = index; i < index + nCount; ++i)<br /> {<br /> int splitDigit = pData[i]/t%base;<br /> // splitDigit也为当前值在arCountSort表示的桶内的索引<br /> pTemp[arCountSort[splitDigit]] = pData[i];<br /> arCountSort[splitDigit]++;<br /> }<br /> memcpy_s(pData + index, sizeof(int) * nCount, pTemp, sizeof(int) * nCount);<br /> // 递归<br /> RadixSort(pData, index, arCountSort[0], maxDigits-1);<br /> for(i = 1; i < base; ++i)<br /> {<br /> RadixSort(pData, index + arCountSort[i-1], arCountSort[i] - arCountSort[i-1], maxDigits-1);<br /> }<br /> delete pTemp;<br /> }<br /> void RadixSortMSD(int* pData, int nCount, int maxDigits)<br /> {<br /> RadixSort(pData, 0, nCount, maxDigits);<br /> printf_s("基数排序结果：");<br /> for(int i = 0; i < nCount; i++)<br /> {<br /> printf_s("%d ", pData[i]);<br /> }<br /> printf_s("/n");<br /> }