被问了好多次的基本排序算法，好多次都支支吾吾的说不出个所以然。这次下定决心好好总结下，并记录在此以免忘记
一:快速排序
定义以及算法方法参加百科http://baike.baidu.com/view/19016.htm
快排就是把要进行排序的序列(数组)分为两部分，用枢纽元隔开(就是分隔的用的元素)。前面的一部分都比枢纽元小(或者大),后面一部分都比枢纽元大(或者小)
逐级递归划分直到排序完成。
假设一个数组a[0]..........a[n].从中随机取一个元素作为枢纽元 a[i] (i = rand() % n).再对数组进行划分，划分为为a[i]小和a[i]大的两部分，再对此两部分分别
进行划分，以此类推直到划分完毕为止.
直接上代码:
int partition(int nAry[],int nBegin, int nEnd){ srand(int(time(0)));//随机种子 int nPivod = nBegin + rand() % (nEnd - nBegin);//把枢纽元放到首元素位置 swap(nAry,nBegin, nPivod);//两个标记，nFrontFlag标记比nAry[nPivoid]大的元素位置//nBlackFlag往后寻找,直到找到比nAry[nPivoid]小的元素就和nFrontFlag位置的元素交换//nFrontFlag再往后移动一个位置，此位置它所在的元素就大于nAry[nPivoid]//因为nBlackFlag之前的位置都是比nAry[nPivoid]要大的元素 int nFrontFlag = nBegin + 1;int nBlackFlag = nBegin + 1;for(nBlackFlag; nBlackFlag <= nEnd; nBlackFlag++) { if(nAry[nBlackFlag] < nAry[nBegin]) { if(nBlackFlag != nFrontFlag) swap(nAry, nBlackFlag, nFrontFlag); nFrontFlag++; } }//把枢纽元素放到枢纽位置。nFrontFlag位置就是枢纽位置 swap(nAry, nBegin, nFrontFlag - 1);return nFrontFlag - 1;}void quicksort(int nAry[], int nBegin, int nEnd){if(nBegin >= nEnd)return;int nPartion = partition(nAry, nBegin, nEnd); quicksort(nAry, nBegin, nPartion); quicksort(nAry, nPartion + 1, nEnd);}当然最好的枢纽元素还是取中值，就是首元素、尾元素、中间元素取中值。
二:堆排序
选择法排序就是从数组中选择最大、第二大、第三大。。这样的数一次和数组的前面元素进行交换。在选择最大、次大的元素过程中经历了很多重复的比较，这样效率就有所降低
堆排序就是构造一个堆结构，这个结构的首元素最大(或者最小)。在堆结构中进行比较的次数就会大幅减少
堆结构就是一个序列a[0]....a[n].序列中a[2 * i + 1]、a[2 * i + 2]必须>=a[i](或者<=).放到树结构中就是叶子节点必须大于等于其孩子节点
代码:
//从nBegin节点开始更新其孩子节点，让其符号堆结构void UpdateMinHeap(int nAry[], int nBegin, int nLen) { while((2 * nBegin + 1) <= (nLen - 1)) { int nLeft = 2 * nBegin + 1; int nRight = 2 * nBegin + 2; if(nRight <= (nLen - 1)) { if(nAry[nRight] < nAry[nLeft]) nLeft = nRight; } if(nAry[nBegin] > nAry[nLeft]) { swap(nAry, nBegin, nLeft); nBegin = nLeft; } //后面的已经处理过了 else break; } }//建立堆结构,从中间元素开始。叶子节点是堆结构，其孩子节点也是堆结构void BulidHeap(int nAry[], int nLen){for(int i = (nLen / 2); i >= 0; i--) { UpdateMinHeap(nAry, i, nLen); }}void heapsort(int nAry[], int nLenAry){ BulidHeap(nAry, nLenAry);//首元素为堆顶元素。后面元素为已经排好序的 for(int nLen = nLenAry; nLen > 0; nLen--) {if(nAry[0] > nAry[nLen - 1]) { swap(nAry, 0, nLen - 1); UpdateHeap(nAry, 0, nLen); } }}应用:Top K问题
题目描述：查找最大的k个元素题目：输入n个整数，输出其中最小的k个。例如输入1，2，3，4，5，6，7和8这8个数字，则最大的4个数字为5，6，7，8
如果是直接进行排序，再取前K个元素，那效率就很低了
一:划分:把要查找的元素放入到一个数组，对这一数组进行划分成两部分Smax,Smin，第一部分(Smax)中的元素都比第二部分(Smin)中的元素要大
1、如果|Smax|(Smax的数目)等于K的话，那么Smax中的元素就是题目要求，|Smax| >K的话，就在Smax中继续寻找K个元素
2、如果|Smax|<K,那么就在Smin中寻找k - |Smax|个元素
代码如下:
#include "stdafx.h"#include <stdio.h>#include <time.h>#include <stdlib.h>#include <memory.h>void swap(int nAry[], int nSrc, int nDes){int nTemp = nAry[nSrc]; nAry[nSrc] = nAry[nDes]; nAry[nDes] = nTemp;}int partition(int nAry[],int nBegin, int nEnd){ srand(int(time(0)));//随机种子 int nPivod = nBegin + rand() % (nEnd - nBegin);//把枢纽元放到首元素位置 swap(nAry,nBegin, nPivod);//两个标记，nFrontFlag标记比nAry[nPivoid]大的元素位置//nBlackFlag往后寻找,直到找到比nAry[nPivoid]小的元素就和nFrontFlag位置的元素交换//nFrontFlag再往后移动一个位置，此位置它所在的元素就大于nAry[nPivoid]//因为nBlackFlag之前的位置都是比nAry[nPivoid]要大的元素 int nFrontFlag = nBegin + 1;int nBlackFlag = nBegin + 1;for(nBlackFlag; nBlackFlag <= nEnd; nBlackFlag++) { if(nAry[nBlackFlag] > nAry[nBegin]) { if(nBlackFlag != nFrontFlag) swap(nAry, nBlackFlag, nFrontFlag); nFrontFlag++; } }//把枢纽元素放到枢纽位置。nFrontFlag位置就是枢纽位置 swap(nAry, nBegin, nFrontFlag - 1);return nFrontFlag - 1;}int *AddToPk(int *pK, int nAry[], int nLAryLen){for(int i = 0; i < nLAryLen; i++) { pK[i] = nAry[i]; }return pK + i;}void TopK(int pAry[], int nAryLen, int nK, int *pK){ if(nK <= 0)return;int nPar = partition(pAry,0, nAryLen - 1);//Smax == nAry[0] - nAry[nPar]//Smin == nAry[nPar + 1] --- nAry[nAryLen - 1]; int *pMax = pAry;int nSmaxLen = nPar + 1;int *pMin = pAry + nSmaxLen;int nSminLen = nAryLen - nSmaxLen;//|Smax| > nK if(nSmaxLen > nK) { //到Smax中去寻找 TopK(pMax, nSmaxLen, nK, pK); }//|Smax| < nK else { //Smax中的元素拷贝到数组中，再到Smin中去找剩下的 nK - |Smax| pK = AddToPk(pK, pMax, nSmaxLen); TopK(pMin,nSminLen, nK - nSmaxLen, pK); }}int main(int argc, char* argv[]){int nAry[] = {42,13,91,23,24,16,5,88,100,105,7,6,35,94,67,85,93,67};int nLenAry = (sizeof(nAry) / sizeof(int));for(int i = 0; i < nLenAry; i++) { printf("M", nAry[i]); } printf("\r\n");//quicksort(nAry, 0, nLenAry - 1); /*heapsort(nAry, nLenAry); for(int j = 0; j < nLenAry; j++) { printf("M", nAry[j]); } printf("\r\n");*/ printf("寻找最大的K个数,请输入K:");int nK = 0; scanf("%d", &nK);int * pK = new int[nK]; memset(pK,0, sizeof(int) * nK); TopK(nAry, nLenAry,nK,pK); printf("最大的%d数为:\r\n",nK);for(int j = 0; j < nK; j++) { printf("M", pK[j]); } printf("\r\n");return 0;}二:假设这一序列的前K个元素就是最大的K个元素 T[K]，再遍历剩下的N-K个元素。如果元素X <T[K]min (T[K]中的最小元素)，那就不管它，继续往下遍历，
如果X>T[K]min,那么就用X替换T[K]min.
可以采用推结构构造T[0]最小，每次替换以后再次更新堆，让T[0]最小。
这种方法可以处理大数据，并不需要把所有数据一次性读入到内存，只需要在内存中读入K个元素的数组
代码如下:
int main(int argc, char* argv[]){//生成一个10W整数的文件 srand(int(time(0)));//随机种子 FILE *fp = fopen("1.txt","w+");if(NULL == fp)return -1;for(int i = 0; i < 100000; i++) { int nNum = rand() % 10000 + (2 * i / 10);if(0 == fprintf(fp,"