被問了好多次的基本排序算法，好多次都支支吾吾的說不出個所以然。這次下定決心好好總結(jié)下，并記錄在此以免忘記

一:快速排序

定義以及算法方法參加百科http://baike.baidu.com/view/19016.htm

快排就是把要進行排序的序列(數(shù)組)分為兩部分，用樞紐元隔開(就是分隔的用的元素)。前面的一部分都比樞紐元小(或者大),后面一部分都比樞紐元大(或者小)

逐級遞歸劃分直到排序完成。

假設(shè)一個數(shù)組a[0]..........a[n].從中隨機取一個元素作為樞紐元 a[i] (i = rand() % n).再對數(shù)組進行劃分，劃分為為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);
//兩個標(biāo)記，nFrontFlag標(biāo)記比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);
}

　　當(dāng)然最好的樞紐元素還是取中值，就是首元素、尾元素、中間元素取中值。

二:堆排序

選擇法排序就是從數(shù)組中選擇最大、第二大、第三大。。這樣的數(shù)一次和數(shù)組的前面元素進行交換。在選擇最大、次大的元素過程中經(jīng)歷了很多重復(fù)的比較，這樣效率就有所降低

堆排序就是構(gòu)造一個堆結(jié)構(gòu)，這個結(jié)構(gòu)的首元素最大(或者最小)。在堆結(jié)構(gòu)中進行比較的次數(shù)就會大幅減少

堆結(jié)構(gòu)就是一個序列a[0]....a[n].序列中a[2 * i + 1]、a[2 * i + 2]必須>=a[i](或者<=).放到樹結(jié)構(gòu)中就是葉子節(jié)點必須大于等于其孩子節(jié)點

代碼:

//從nBegin節(jié)點開始更新其孩子節(jié)點，讓其符號堆結(jié)構(gòu)
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;}//后面的已經(jīng)處理過了elsebreak;} }
//建立堆結(jié)構(gòu),從中間元素開始。葉子節(jié)點是堆結(jié)構(gòu)，其孩子節(jié)點也是堆結(jié)構(gòu)
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);
//首元素為堆頂元素。后面元素為已經(jīng)排好序的
for(int nLen = nLenAry; nLen > 0; nLen--)
{
if(nAry[0] > nAry[nLen - 1])
{
swap(nAry, 0, nLen - 1);
UpdateHeap(nAry, 0, nLen);
}
}
}

應(yīng)用:Top K問題

題目描述：查找最大的k個元素
題目：輸入n個整數(shù)，輸出其中最小的k個。
例如輸入1，2，3，4，5，6，7和8這8個數(shù)字，則最大的4個數(shù)字為5，6，7，8

如果是直接進行排序，再取前K個元素，那效率就很低了

一:劃分:把要查找的元素放入到一個數(shù)組，對這一數(shù)組進行劃分成兩部分Smax,Smin，第一部分(Smax)中的元素都比第二部分(Smin)中的元素要大

1、如果|Smax|(Smax的數(shù)目)等于K的話，那么Smax中的元素就是題目要求，|Smax| >K的話，就在Smax中繼續(xù)尋找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);
//兩個標(biāo)記，nFrontFlag標(biāo)記比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中的元素拷貝到數(shù)組中，再到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("%4d", nAry[i]);
}
printf("\r\n");

//quicksort(nAry, 0, nLenAry - 1);
/*heapsort(nAry, nLenAry);
for(int j = 0; j < nLenAry; j++)
{
printf("%4d", nAry[j]);
}
printf("\r\n");*/
printf("尋找最大的K個數(shù),請輸入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數(shù)為:\r\n",nK);
for(int j = 0; j < nK; j++)
{
printf("%4d", pK[j]);
}
printf("\r\n");

return 0;
}

二:假設(shè)這一序列的前K個元素就是最大的K個元素 T[K]，再遍歷剩下的N-K個元素。如果元素X <T[K]min (T[K]中的最小元素)，那就不管它，繼續(xù)往下遍歷，

如果X>T[K]min,那么就用X替換T[K]min.

可以采用推結(jié)構(gòu)構(gòu)造T[0]最小，每次替換以后再次更新堆，讓T[0]最小。

這種方法可以處理大數(shù)據(jù)，并不需要把所有數(shù)據(jù)一次性讀入到內(nèi)存，只需要在內(nèi)存中讀入K個元素的數(shù)組

代碼如下:

int main(int argc, char* argv[])
{
//生成一個10W整數(shù)的文件
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,"%8d", nNum))
return -2;
}
if(fp)
{
fclose(fp);
fp = NULL;
}
printf("從100000個數(shù)據(jù)中取出最大的8個:\r\n");
int nAry[8] = {0};
fp = fopen("1.txt","r+");
for(int j = 0; j < 8; j++)
{
int nR = fscanf(fp, "%d",nAry + j);
}
printf("文件開頭8條數(shù)據(jù):\r\n");
for( j = 0; j < 8; j++)
{
printf("%8d\t", nAry[j]);
}
BulidHeap(nAry, sizeof(nAry) / sizeof(int)); //建堆
int nTemp = 0;
while(fscanf(fp, "%d", &nTemp) != EOF)
{
if(nTemp > nAry[0])
{
nAry[0] = nTemp;
UpdateMinHeap(nAry, 0, sizeof(nAry) / sizeof(int));
}
}
printf("\r\n");
printf("文件中最大的8條數(shù)據(jù)為:\r\n");
for( j = 0; j < 8; j++)
{
printf("%8d\t", nAry[j]);
}
if(fp)
{
fclose(fp);
fp = NULL;
}
return 0;
}

　　總結(jié):假設(shè)已經(jīng)成立，再做處理。分治，把整體問題，分成部分來考慮。

轉(zhuǎn)載于:https://www.cnblogs.com/AirSpuer/archive/2011/08/02/2125221.html

總結(jié)

以上是生活随笔為你收集整理的排序算法以及其应用的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。