11 int *pnD2 = new int[n2 + 1]; //申请二个保存第一个数据的空间 13 for (int i = 0; i < n1; ++i) //复制第一个数据到临时空间里面 14 {
15 pnD1[i] = nData[nP + i]; 16 }
17 pnD1[n1] = INT_MAX; //将最后一个数据设置为最大值(哨兵) 19 for (int i = 0; i < n2; ++i) //复制第二个数据到临时空间里面 20 {
21 pnD2[i] = nData[nM + i]; 22 }
23 pnD2[n2] = INT_MAX; //将最后一个数据设置为最大值(哨兵) 25 n1 = n2 = 0; 27 while(nP < nR) 28 {
29 nData[nP++] = pnD1[n1] < pnD2[n2] ? pnD1[n1++] : pnD2[n2++]; //取出当前最小值到指定位置 30 }
32 delete pnD1; 33 delete pnD2; 34 return true; 35 }
37 //合并排序的合并程序他合并数组nData中位置为[nP,nM) 和[nM,nR). 38 bool Merge(int nData[], int nP, int nM, int nR) 39 {
40 //这里面有几个注释语句是因为当时想少写几行而至。看似短了，其实运行时间是一样的，而且不易阅读。
42 int nLen1 = nM - nP; //第一个合并数据的长度 43 int nLen2 = nR - nM; //第二个合并数据的长度
44 int* pnD1 = new int[nLen1]; //申请一个保存第一个数据的空间 45 int* pnD2 = new int[nLen2]; //申请一个保存第一个数据的空间 46
47 int i = 0;
48 for ( i = 0; i < nLen1; ++i) //复制第一个数据到临时空间里面 49 {
50 pnD1[i] = nData[nP + i]; 51 }
53 int j = 0;
54 for (j = 0; j < nLen2; ++j) //复制第二个数据到临时空间里面 55 {
56 pnD2[j] = nData[nM + j]; 57 }
59 i = j = 0;
60 while (i < nLen1 && j < nLen2) 61 {
62 //nData[nP++] = pnD1[i] < pnD2[j] ? pnD1[i++] : pnD2[j++]; //取出当前最小值添加到数据中
64 if (pnD1[i] < pnD2[j]) //取出最小值，并添加到指定位置中，如果pnD1[i] < pnD2[j] 65 {
66 nData[nP] = pnD1[i]; //取出pnD1的值，然后i++，定位到下一个个最小值。 67 ++i; 68 }
69 else //这里同上 70 {
71 nData[nP] = pnD2[j]; 72 ++j; 73 }
74 ++nP; //最后np++，到确定下一个数据 75 }
77 if (i < nLen1) //如果第一个数据没有结束（第二个数据已经结束了） 78 {
79 while (nP < nR) //直接把第一个剩余的数据加到nData的后面即可。 80 {
81 //nData[nP++] = pnD1[i++]; 82 nData[nP] = pnD1[i]; 83 ++nP; 84 ++i; 85 } 86 }
87 else //否则（第一个结束，第二个没有结束） 88 {
89 while (nP < nR) //直接把第一个剩余的数据加到nData的后面即可。 90 {
91 //nData[nP++] = pnD2[j++]; 92 nData[nP] = pnD2[j]; 93 ++nP; 94 ++j; 95 } 96 }
98 delete pnD1; //释放申请的内存空间 99 delete pnD2; 100
101 return true; 102 }
104 //合并的递归调用,排序[nBegin, nEnd)区间的内容 105 bool MergeRecursion(int nData[], int nBegin, int nEnd) 106 {
107 if (nBegin >= nEnd - 1) //已经到最小颗粒了,直接返回 108 {
109 return false; 110 }
112 int nMid = (nBegin + nEnd) / 2; //计算出他们的中间位置，便于分治 113 MergeRecursion(nData, nBegin, nMid); //递归调用，合并排序好左边一半 114 MergeRecursion(nData, nMid, nEnd); //递归调用，合并排序好右边一半
115 //Merge(nData, nBegin, nMid, nEnd); //将已经合并排序好的左右数据合并，时整个数据排序完成
116 MergeStandard(nData, nBegin, nMid, nEnd);//(用更接近标准的方法合并) 118 return true; 119 }
121 //合并排序
122 bool MergeSort(int nData[], int nNum) 123 {
124 return MergeRecursion(nData, 0, nNum); //调用递归，完成合并排序 125 }
127 int main() 128 {
129 int nData[10] = {4,10,3,8,5,6,7,4,9,2}; //创建10个数据，测试 131 MergeSort(nData, 10);
132 for (int i = 0; i < 10; ++i) 133 {
134 printf(\135 }
137 printf(\
138 system(\139 return 0; 140 } 堆排序
#include
//交换两个整数。注意一定要if判断是否两个相等，如果 //不相等才交换，如果相等也交换会出错的。a^a = 0 inline void Swap(int& a, int& b) {
if (a != b) {
a^= b; b^= a; a^= b; } }
//维持一个最大堆
int Heapify(int* npData, int nPos, int nLen) {
int nMax = -1; //暂存最大值
int nChild = nPos * 2; //他的左孩子位置 while(nChild <= nLen) //判断他是否有孩子 {
nMax = npData[nPos]; //是当前最大值为他 if (nMax < npData[nChild]) //与左孩子比较 {
nMax = npData[nChild]; //如果比左孩子小，就时最大值为左孩子 }
//同理与右孩子比较，这里要注意，必须要保证有右孩子。 if (nChild + 1 <= nLen && nMax < npData[nChild + 1]) {
++nChild; //赋值最大值的时候把孩子变为右孩子，方便最后的数据交换 nMax = npData[nChild]; }
if (nMax != npData[nPos]) //判断是否该节点比孩子都打，如果不大 {
Swap(npData[nPos], npData[nChild]); //与最大孩子交换数据 nPos = nChild; //该节点位置变为交换孩子的位置
nChild *= 2; //因为只有交换后才使不满足堆得性质。 }
else //都最大了，满足堆得性质了。退出循环 {
break; } }
return 1; //维持结束。 }
//建立一个堆
int BuildHeap(int* npData, int nLen) {
//从nLen / 2最后一个有叶子的数据开始，逐一的插入堆，并维持堆得平衡。 //因为堆是一个完全二叉树，所以nlen/2+1- nLen之间肯定都是叶子。 //叶子还判断什么呢。只有一个数据，肯定满足堆得性质咯。 for (int i = nLen / 2; i >= 1; --i) {
Heapify(npData, i, nLen); }
return 1; }
//堆排序
int HeapSort(int* npData, int nLen) {
BuildHeap(npData, nLen); //建立一个堆。
while(nLen >= 1) //逐一交和第一个元素交换数据到最后 { //完成排序 Swap(npData[nLen], npData[1]); --nLen;
Heapify(npData, 1, nLen);//交换之后一定要维持一下堆得性质。 } //不然小的成第一个元素,就不是堆了。 return 1; }
//main函数， int main() {
int nData[11] = {0,9,8,7,6,5,4,3,2,1,0}; //测试数据，下标从1开始哦。 HeapSort(nData, 10); //堆排序
for (int i = 1; i <= 10; ++i) //输出排序结果。 {
printf(\ }
printf(\
system(\ return 0; }
用堆排序实现优先队列
1.一个是他是一个数组（当然你也可以真的用链表来做。）。
2.他可以看做一个完全二叉树。注意是完全二叉树。所以他的叶子个数刚好是nSize / 2个。 3.我使用的下标从1开始，这样好算，如果节点的位置为i,他的父节点就是i/2,他的左孩子结点就是i*2,右孩子结点就是i*2+1，如果下标从0开始，要复杂一点。 4.他的父节点一定不比子节点小（我所指的是最大堆）。 由这些性质就可以看出堆得一些优点：
1.可以一下找到最大值，就在第一个位置heap[1].
2.维持堆只需要log(2,n)(n是数据个数)的复杂度，速度比较快。他只需要比较父与子之间的大小关系，所以比较次数就是树的高度，而他是一个完全二叉树，所以比较次数就是log(2,n)。 具体实现：
具体实现就看看源代码吧！ #include
//定义一个堆得结构体， struct MyHeap {
int* pnData; //指向数据的指针 int nSize; //当前堆中的元素个数 };
//调整数据，维持堆得性质，这个和上次heapify的作用一样