//只是这个时从子道父节点这样的判断而已。 int IncreaseKey(MyHeap* pHeap, int nPos) {
//循环和他父节点判断，只要 nPos > 1他就有父节点 while(nPos > 1) {
int nMax = pHeap->pnData[nPos]; int nParent = nPos / 2;
//如果他比父节点大，交换数据，并使判断进入父节点
//（因为只有父节点可能会影响堆得性质。他的数据改变了。） if (nMax > pHeap->pnData[nParent]) {
pHeap->pnData[nPos] = pHeap->pnData[nParent]; pHeap->pnData[nParent] = nMax; nPos = nParent; }
else //否则堆没有被破坏，退出循环 {
break; } }
return 1; }
//插入数据，这里pnHeap为要插入的队，nLen为当前堆得大小。 //nData为要插入的数据，这里注意报保证堆得空间足够。 int Insert(MyHeap* pHeap, int nData) {
++pHeap->nSize; //添加数据到末尾 pHeap->pnData[pHeap->nSize] = nData; IncreaseKey(pHeap, pHeap->nSize); return 1; }
//弹出堆中对大元素，并使堆得个数减一 int PopMaxHeap(MyHeap* pHeap) {
int nMax = pHeap->pnData[1]; //得到最大元素
//不要忘记维持堆得性质，因为最大元素已经弹出了，主要思路就是 //同他最大孩子填充这里。
int nPos = 1; //起始位1，因为他弹出，所以是这里开始破坏堆得性质的 int nChild = nPos * 2; //他的左孩子的位置， //循环填充，用最大孩子填充父节点 while(nChild <= pHeap->nSize) {
int nTemp = pHeap->pnData[nChild];
if (nChild + 1 <= pHeap->nSize && nTemp < pHeap->pnData[nChild + 1]) {
++nChild;
nTemp = pHeap->pnData[nChild]; }
pHeap->pnData[nPos] = nTemp; nPos = nChild; nChild *= 2; }
//最好一个用最末尾的填充。
pHeap->pnData[nPos] = pHeap->pnData[pHeap->nSize]; --pHeap->nSize; //堆个数量减一 return nMax; //返回最大值。 }
//程序入口main int main() {
MyHeap myHeap; //定义一个堆
myHeap.pnData = (int*)::malloc(sizeof(int) *11); //申请数据空间 myHeap.nSize = 0; //初始大小为0
for (int i = 1; i <= 10; ++i) //给优先队列堆里添加数据 {
Insert(&myHeap, i); }
for (int i = 1; i <= 10; ++i) //测试优先队列是否建立成功 {
printf(\ }
printf(\
while(myHeap.nSize > 0) //逐一弹出队列的最大值。并验证 {
printf(\ }
printf(\
::free(myHeap.pnData); //最后不要忘记释放申请的空间 system(\ return 0; }
基数排序
据说他的时间复杂度也是O(n)，他的思路就是：
没有计数排序那么理想，我们的数据都比较集中，都比较大，一般是4，5位。基本没有小的数据。
那我们的处理很简单，你不是没有小的数据嘛。我给一个基数，例如个位，个位都是[0-10)
范围内的。先对他进行归类，把小的放上面，大的放下面，然后个位排好了，在来看10位，我们也这样把小的放上面，大的放下面，依次内推，直到最高位排好。那么不就排好了吗？我们只需要做d(基数个数)的循环就可以了。时间复杂度相当于O(d * n) 因为d为常量，例如5位数，d就是5.所以近似为O(n)的时间复杂度。这次自己写个案例： 最初的数据 981 387 753 129 955 725 456 排好个位的数据 981 753 955 725 456 387 129 排好十位的数据 725 129 753 955 456 981 387 排好百位的数据 129 387 456 725 753 955 981 这里只需循环3次就出结果了。
3. 但是注意，我们必须要把个位排好。但是个位怎么排呢？这个是个问题。书上说的是一叠一叠的怎么合并，我是没有理解的。希望知道的有高手教我一下。
我是用的一个计数排序来排各位的，然后排十位。效率应该也低不到哪里去。 思路就这样咯。奉上源代码： #include
//计数排序，npRadix为对应的关键字序列，nMax是关键字的范围。npData是具体要 //排的数据，nLen是数据的范围，这里必须注意npIndex和npData对应的下标要一致 //也就是说npIndex[1] 所对应的值为npData[1]
int RadixCountSort(int* npIndex, int nMax, int* npData, int nLen) {
//这里就不用说了，计数的排序。不过这里为了是排序稳定 //在标准的方法上做了小修改。
int* pnCount = (int*)malloc(sizeof(int)* nMax); //保存计数的个数 for (int i = 0; i < nMax; ++i) {
pnCount[i] = 0; }
for (int i = 0; i < nLen; ++i) //初始化计数个数 {
++pnCount[npIndex[i]]; }
for (int i = 1; i < 10; ++i) //确定不大于该位置的个数。 {
pnCount[i] += pnCount[i - 1]; }
int * pnSort = (int*)malloc(sizeof(int) * nLen); //存放零时的排序结果。 //注意：这里i是从nLen-1到0的顺序排序的，是为了使排序稳定。 for (int i = nLen - 1; i >= 0; --i) {
--pnCount[npIndex[i]];
pnSort[pnCount[npIndex[i]]] = npData[i]; }
for (int i = 0; i < nLen; ++i) //把排序结构输入到返回的数据中。 {
npData[i] = pnSort[i]; }
free(pnSort); //记得释放资源。 free(pnCount); return 1; }
//基数排序
int RadixSort(int* nPData, int nLen) {
//申请存放基数的空间
int* nDataRadix = (int*)malloc(sizeof(int) * nLen); int nRadixBase = 1; //初始化倍数基数为1 bool nIsOk = false; //设置完成排序为false //循环，知道排序完成 while (!nIsOk) {
nIsOk = true;
nRadixBase *= 10;
for (int i = 0; i < nLen; ++i) {
nDataRadix[i] = nPData[i] % nRadixBase; nDataRadix[i] /= nRadixBase / 10; if (nDataRadix[i] > 0) {
nIsOk = false; } }
if (nIsOk) //如果所有的基数都为0，认为排序完成，就是已经判断到最高位了。 {
break; }
RadixCountSort(nDataRadix, 10, nPData, nLen); }
free(nDataRadix); return 1; }
int main() {
//测试基数排序。
int nData[10] = {123,5264,9513,854,9639,1985,159,3654,8521,8888}; RadixSort(nData, 10); for (int i = 0; i < 10; ++i) {
printf(\ }
printf(\
system(\ return 0; }
计数排序：
貌似计数排序的复杂度为o(n)。很强大。他的基本思路为：
1. 我们希望能线性的时间复杂度排序，如果一个一个比较，显然是不实际的，书上也在决策树模型中论证了，比较排序的情况为nlogn的复杂度。 2. 既然不能一个一个比较，我们想到一个办法，就是如果我在排序的时候就知道他的位置，那不就是扫描一遍，把他放入他应该的位置不就可以了嘛。
3. 要知道他的位置，我们只需要知道有多少不大于他不就可以了吗？
4. 以此为出发点，我们怎么确定不大于他的个数呢？我们先来个约定，如果数组中的元素都比较集中，都在[0, max]范围内。我们开一个max的空间b数组，把b数组下标对应的元素和要排序的A数组下标对应起来。这样不就可以知道不比他大的有多少个了吗？我们只要把比他小的位置元素个数求和，就是不比他大的。例如：A={3,5,7};我们开一个大小为8的数组b，把a[0] = 3 放入b[3]中，使b[3] = 0; 同理 b[5] = 1; b[7] = 2;其他我们都设置为-1，哈哈我们只需要遍历一下b数组，如果他有数据，就来出来，铁定是当前最小的。如果要知道比a[2]小的数字有多少个，值只需要求出b[0] – b[6]的有数据的和就可以了。这个0(n)的速度不是盖得。
5. 思路就是这样咯。但是要注意两个数相同的情况A = {1,2,3,3,4}，这种情况就不可以咯，所以还是有点小技巧的。
6. 处理小技巧：我们不把A的元素大小与B的下标一一对应，而是在B数组对应处记录该元素大小的个数。这不久解决了吗。哈哈。例如A = {1,2,3,3,4}我们开大小为5的数组b;记录数组A中元素值为0的个数为b[0] = 0, 记录数组A中元素个数为1的b[1] = 1,同理b[2] = 1, b[3] = 2, b[4] = 1;好了，这样我们就知道比A[4](4)小的元素个数是多少了：count = b[0] + b[1] + b[2] + b[3] = 4;他就把A[4]的元素放在第4个位置。
还是截张书上的图：