個人介紹及問題解決

BubbleSort（冒泡排序）

定義：在同一個數(shù)組中高帖，從數(shù)組第一個數(shù)開始，相鄰兩個數(shù)進行比較元镀，按照小左大右或者大右小左的順序绍填，依次循環(huán)遍歷，進行排序栖疑！

void BubbleSort(int *arr,int Length)
{
    int i = 0;
    int j = 1;
    int sys = 0;
    for (i = 0; i < Length-1; i++)
    {
        for (j = 0; j < Length-i-1; j++)
        {
            if (arr[j]>arr[j+1])
            {
                arr[j] = arr[j]^arr[j+1];
                arr[j+1] = arr[j]^arr[j+1];
                arr[j] = arr[j]^arr[j+1];
            }

        }
        sys++;
    }

    return ;
}

改進版冒泡排序

在原有的基礎(chǔ)上讨永，我們添加了標(biāo)記！記錄了最后一次交換的位置遇革！
如5卿闹，1，4萝快，6锻霎，3，2揪漩，7旋恼，8，9氢拥。最后一次交換的位置在2處蚌铜，并且設(shè)定我們每次循環(huán)的到2，不對7嫩海，8，9
進行比較囚痴，節(jié)省我們運算的效率叁怪！

冒泡排序是對全部已經(jīng)排好序列排序最快的

void BetterBubbleSort(int *arr,int Length)
{
    int i = 0;
    int j = 1;
    int pmark;
    int sys = 0;
    for (; i < Length-1; i++)
    {
        pmark = 0;
        for (j = 0; j < Length-i-1; j++)
        {
            if (arr[j]>arr[j+1])
            {
                arr[j] = arr[j]^arr[j+1];
                arr[j+1] = arr[j]^arr[j+1];
                arr[j] = arr[j]^arr[j+1];
                pmark = j+1;
            }

        }

        i == Length - pmark - 1;
        sys++;
    }

    return ;
}

不帶中間變量實現(xiàn)兩個相同類型不同值變量間的互換

1. 加減法

int a = 5;
int b = 3;
a = a+b;
b = a-b;
a = a-b;

2. 異或^

int a = 5;
int b = 3;
a = a^b;
b = a^b;
a = a^b;

ps:若對于*a，*b值進行交換深滚，*a奕谭，*b不能指向同一塊地址空間！

SelectSort選擇排序

首先痴荐，用第一個數(shù)去和所有數(shù)進行比較血柳，選出其中最小的數(shù)，放在第一位生兆，在用第二個數(shù)去和全部數(shù)進行比較难捌，最小的放在第二位，依次循環(huán)遍歷鸦难！

void SelectSort(int *Arr,int nLength)
{
    int i = 0;
    int j = 1;
    int min = 0;
    for (i = 0; i < nLength; i++)
    {
        for (j = i; j < nLength-1; j++)
        {
            if (Arr[i] > Arr[j])
            {
                Arr[j] = Arr[j]^Arr[i];
                Arr[i] = Arr[j]^Arr[i];
                Arr[j] = Arr[j]^Arr[i];
            }
        }
    }
}

代碼優(yōu)化：把每次都交換的位置根吁，換成比較完之后，有一個int記下來合蔽，不用每次比較完進行交換击敌，而是最后直接用記錄的數(shù)組下標(biāo)進行交換！

InsertSort插入排序

把當(dāng)前數(shù)組分成兩部分拴事，第一部分有序沃斤，第二部分無序圣蝎，將無序數(shù)組依次插入有序數(shù)組里去！
例如數(shù)組：10衡瓶，20捅彻，3，8鞍陨，55.用一個temp保存無序數(shù)組第一個

適合場景：每個元素距離其最終位置不遠(yuǎn)時步淹，我們選擇插入排序。

1. 首先把10當(dāng)成有序數(shù)組的最后一位诚撵，20當(dāng)成無序數(shù)組的第一位缭裆，20和10比較，20比10大不移動寿烟。
2. 之后用無序數(shù)組向后移動一位澈驼，變成3，3和20比較筛武，比20小缝其，把3放10和20中間，在用3和10比徘六，比10小内边，放10前面。
3. 此時有序最后一位仍是20待锈，用8再去和前面幾位有序數(shù)組進行比較漠其，一次循環(huán)遍歷！

void InsertSort(int arr[],int nLength)
{
    int j;//有序數(shù)組的最后位置
    int i;//無序數(shù)組的第一個
    int temp;

    if(arr == NULL || nLength <=0)return;

    for(i = 1;i<nLength;i++)
    {
        j = i-1;
        temp = arr[i]; //保存無序數(shù)組的第一個

        //進行比較
        while(temp < arr[j] && j >=0)
        {
            //將前一個元素向后移動 
            arr[j+1] = arr[j];
            j--;
        }

        //將元素放入其對應(yīng)位置
        arr[j+1] = temp;
    }

}

快排

快排的優(yōu)點：是比較次數(shù)最少的排序竿音！

挖坑填補法

例如數(shù)組：7和屎，2，8春瞬，4柴信，3，5宽气。我們用temp標(biāo)記7

1. 我們將第一數(shù)7當(dāng)標(biāo)準(zhǔn)值随常，此時相當(dāng)于7是一個坑（用粗斜體標(biāo)記），然后我們從后面依次找比標(biāo)準(zhǔn)值7小的數(shù)抹竹，
   第一個5就比7小线罕，我們將5放到7的坑里。數(shù)組變成5窃判，2钞楼，8，4袄琳，3询件，7燃乍，這是坑變成最后位數(shù)！
2. 然后我們在前面找一個比標(biāo)準(zhǔn)值大的數(shù)宛琅，第3個數(shù)8比標(biāo)準(zhǔn)值大刻蟹，這是我們將8填到數(shù)7的坑里！這是數(shù)組變成了：
   5嘿辟，2舆瘪，7，4红伦，3英古，8，我們對已經(jīng)操作的數(shù)昙读，不再進行考慮比較召调！
3. 這時我們在從前面開始找一個數(shù)比標(biāo)準(zhǔn)值小的數(shù)3，填坑蛮浑。數(shù)組變成了：2唠叛，3，4沮稚，7艺沼，8，此時前面和后面的數(shù)壮虫，
   皆比標(biāo)準(zhǔn)值小和大澳厢！
4. 標(biāo)準(zhǔn)值前面的數(shù)我們看做一個區(qū)域，標(biāo)準(zhǔn)值后面的數(shù)我們看成一個區(qū)域囚似。依次遞歸循環(huán)此區(qū)域。

//挖坑填補法 
int Sort(int arr[],int nLow,int nHigh)
{
    int temp ;
    temp = arr[nLow]; //保存標(biāo)準(zhǔn)值

    while(nLow < nHigh)
    {
        //從后向前找比標(biāo)準(zhǔn)值小的
        while( nLow < nHigh)
        {
            if(arr[nHigh] > temp)
            {
                nHigh--;
            }

            //小的放前面
            else
            {
                arr[nLow] = arr[nHigh];
                nLow++;
                break;
            }
        }

        //從前往后找比標(biāo)準(zhǔn)值大的
        while(  nLow < nHigh)
        {
            if(arr[nLow] < temp)
            {
            nLow++;
            }
            //大的放后面
            else
            {
                arr[nHigh] = arr[nLow];
                nHigh--;
                break;
            }
        }
    }

    //填坑
    arr[nLow] = temp;
    return nLow;
}
void QuickSort(int arr[],int nLow,int nHigh)
{
    int nIndex;
    if(arr == NULL )return;
    if(nLow < nHigh)
    {
        //找到標(biāo)準(zhǔn)值位置
        nIndex = Sort(arr,nLow,nHigh);

        //根據(jù)標(biāo)準(zhǔn)值將當(dāng)前數(shù)組分割成兩部分
        Sort(arr,nLow,nIndex-1);
        Sort(arr,nIndex+1,nHigh);
    }
}

區(qū)間（域）分割法

快排的一種线得，比挖坑填補法快饶唤！類似與挖坑填補法，是其優(yōu)化升級版吧贯钩！
例如募狂，數(shù)組：7，5角雷，4祸穷，3，6

1. 我們選最后一個數(shù)6作為標(biāo)準(zhǔn)值勺三，有兩個標(biāo)記雷滚，一個是循環(huán)標(biāo)記I，一個是區(qū)域標(biāo)記s吗坚。s= i - 1
   s用黃體標(biāo)記祈远，i用粗斜體標(biāo)記呆万！s，7车份，5谋减，4，3扫沼，6
2. 用數(shù)6去和第一個數(shù)7比較出爹，比標(biāo)準(zhǔn)值大，7,5,4缎除，3严就，6，則將遍歷元素移動到下一處伴找，比標(biāo)準(zhǔn)值6小盈蛮，
   則將數(shù)5和7交換，5技矮，7抖誉，4，3衰倦，6袒炉。
3. 將遍歷指針指下一處，5樊零，7我磁，4，3驻襟，6夺艰，比標(biāo)準(zhǔn)值小，將4和第二個數(shù)交換沉衣。5郁副，4，7豌习，3存谎，6
   移動遍歷指針，5肥隆，4既荚，7，3栋艳，6
4. 比標(biāo)準(zhǔn)值小恰聘，將3和第三個數(shù)交換。5，4憨琳，3诫钓，7，6篙螟，移動遍歷指針菌湃。5，4遍略，3惧所，7，6
5. 這時遍歷結(jié)束绪杏，判斷++s與i是否相等下愈，若不等，5蕾久，4势似，3，7僧著，6履因，數(shù)組[s]與數(shù)組[i]交換。
6. 5盹愚，4栅迄，3，6皆怕，7毅舆，此時標(biāo)準(zhǔn)值6前小后大，遞歸遍歷愈腾！

//區(qū)間分割法
int Sort(int arr[],int nLow,int nHigh)
{
    int nSmall;//小區(qū)間的右邊界
    nSmall = nLow-1;
    for(nLow;nLow < nHigh;nLow++)
    {
        //和標(biāo)準(zhǔn)值進行比較
        if(arr[nLow] < arr[nHigh])
        {
            //擴張小區(qū)間
            if(++nSmall != nLow)
            {
                arr[nSmall] = arr[nSmall] ^ arr[nLow];
                arr[nLow] = arr[nSmall] ^ arr[nLow];
                arr[nSmall] = arr[nSmall] ^ arr[nLow];
            }
        }
    }

    //標(biāo)準(zhǔn)值放入對應(yīng)位置
    if(++nSmall != nHigh)
    {
        arr[nSmall] = arr[nHigh] ^ arr[nSmall];
        arr[nHigh] = arr[nHigh] ^ arr[nSmall];
        arr[nSmall] = arr[nHigh] ^ arr[nSmall];
    }

    return nSmall;
}

void QuickSort(int arr[],int nLow,int nHigh)
{
    int nIndex;
    if(arr == NULL )return;
    if(nLow < nHigh)
    {
        //找到標(biāo)準(zhǔn)值位置
        nIndex = Sort(arr,nLow,nHigh);

        //根據(jù)標(biāo)準(zhǔn)值將當(dāng)前數(shù)組分割成兩部分
        QuickSort(arr,nLow,nIndex-1);
        QuickSort(arr,nIndex+1,nHigh);
    }
}

快排區(qū)間分割優(yōu)化

若我們選擇的標(biāo)準(zhǔn)值恰好是最小值或者最大值憋活，這是快排發(fā)生交換的次數(shù)最多，如果我們在選擇下標(biāo)的時候進行優(yōu)化虱黄，
我們用隨機數(shù)選擇3個下標(biāo)余掖，之后選其中位數(shù)，會最大限度的減少極值下標(biāo)的可能礁鲁！

//找中間值下標(biāo)
int GetIndex(int arr[],int nLow,int nHigh)
{
    int a,b,c;
    srand(time(NULL));

    //隨機出三個在下標(biāo)范圍之內(nèi)的下標(biāo)
    a = rand()%(nHigh-nLow+1) + nLow;
    b = rand()%(nHigh-nLow+1) + nLow;
    c = rand()%(nHigh-nLow+1) + nLow;

    //找到三個的中間值
    if(arr[a] > arr[b])
    {
        if(arr[b] > arr[c])
            return b;
        else
        {
            if(arr[a] < arr[c])
                return a;
            else
                return c;
        }       
    }
    else
    {
        if(arr[a] > arr[c])
            return a;
        else
        {
            if(arr[b] < arr[c])
                return b;
            else
                return c;
        }
    }
}

//區(qū)間分割法
int Sort(int arr[],int nLow,int nHigh)
{
    int nSmall;//小區(qū)間的右邊界
    int nIndex;
    nSmall = nLow-1;

    //降低標(biāo)準(zhǔn)值是最大最小值得概率
    nIndex = GetIndex(arr,nLow,nHigh);
    if(nIndex != nHigh)
    {
        arr[nIndex] = arr[nIndex] ^ arr[nHigh];
        arr[nHigh] = arr[nIndex] ^ arr[nHigh];
        arr[nIndex] = arr[nIndex] ^ arr[nHigh];
    }

    for(nLow;nLow < nHigh;nLow++)
    {
        //和標(biāo)準(zhǔn)值進行比較
        if(arr[nLow] < arr[nHigh])
        {
            //擴張小區(qū)間
            if(++nSmall != nLow)
            {
                arr[nSmall] = arr[nSmall] ^ arr[nLow];
                arr[nLow] = arr[nSmall] ^ arr[nLow];
                arr[nSmall] = arr[nSmall] ^ arr[nLow];
            }
        }
    }

    //標(biāo)準(zhǔn)值放入對應(yīng)位置
    if(++nSmall != nHigh)
    {
        arr[nSmall] = arr[nHigh] ^ arr[nSmall];
        arr[nHigh] = arr[nHigh] ^ arr[nSmall];
        arr[nSmall] = arr[nHigh] ^ arr[nSmall];
    }

    return nSmall;
}

void QuickSort(int arr[],int nLow,int nHigh)
{
    int nIndex;
    if(arr == NULL )return;
    if(nLow < nHigh)
    {
        //找到標(biāo)準(zhǔn)值位置
        nIndex = Sort(arr,nLow,nHigh);

        //根據(jù)標(biāo)準(zhǔn)值將當(dāng)前數(shù)組分割成兩部分
        QuickSort(arr,nLow,nIndex-1);
        QuickSort(arr,nIndex+1,nHigh);
    }
}

快排終極優(yōu)化

如果數(shù)量過少時，直接采用插入排序赁豆！

CountSort計數(shù)排序

基于非比較排序
適用場景：數(shù)據(jù)分配非常密集的時候仅醇！
例如數(shù)組：2，1魔种，3析二，1，2，2叶摄，3属韧，4

1. 首先在數(shù)組中找到最大值和最小值。
2. 然后申請一個max-min+1的數(shù)組空間蛤吓。
3. 遍歷數(shù)組宵喂，如第一個數(shù)2，就在申請的數(shù)組空間下標(biāo)為2-最小值的位置+1会傲。
   相當(dāng)于在申請的數(shù)組第2個位置锅棕，計數(shù)加一，每次遇到相同的值都加一淌山。
4. 相當(dāng)于在申請的數(shù)組空間對應(yīng)下標(biāo)對應(yīng)著參數(shù)數(shù)組中的值裸燎，記錄其出現(xiàn)的次數(shù)。
5. 遍歷申請的數(shù)組空間泼疑，對應(yīng)著下標(biāo)將值依次存入?yún)?shù)數(shù)組德绿。

void CountSort(int arr[],int nLength)
{
    int *pCount = NULL;
    int i;
    int j;
    int nMin,nMax;

    if(arr == NULL || nLength <=0)return;

    //找最大值和最小值
    nMax = arr[0];
    nMin = arr[0];
    for(i = 1;i<nLength;i++)
    {
        if(arr[i] > nMax)
        {
            nMax = arr[i];
        }
        if(arr[i] < nMin)
        {
            nMin = arr[i];
        }
    }
    //開辟計數(shù)數(shù)組
    pCount = (int *)malloc(sizeof(int ) * (nMax-nMin+1));
    memset(pCount,0,sizeof(int ) * (nMax-nMin+1));
    //計數(shù)
    for(i = 0;i<nLength;i++)
    {
        pCount[arr[i]-nMin]++;
    }
    //放回原數(shù)組
    j = 0;
    for(i = 0;i< nMax-nMin+1;i++)
    {
        while(pCount[i] != 0)
        {
            arr[j] = i+nMin;
            j++;
            pCount[i]--;
        }
    }
}

ShellSort希爾排序

插入排序的優(yōu)化，按步長進行分組退渗，然后在組內(nèi)進行插入排序移稳，然后在二分法步長，重復(fù)此過程氓辣。（ps:不一定要二分步長）

使用場景：數(shù)據(jù)少的時候秒裕！

例如：35，5钞啸，9几蜻，12，21体斩，8梭稚，7，4絮吵，13弧烤，25，21蹬敲，14暇昂，長度，n

1. 第一次：$ gap=\displaystyle\frac{n}{2}=6 $伴嗡，也就是說差6為一組急波，35和7一組，5和4瘪校，9和13澄暮，12和25名段，21和21，8和14泣懊。
   每組內(nèi)進行插入排序伸辟，所以35和7互換位置，5和3互換位置馍刮。數(shù)組：7信夫，4，9渠退，12忙迁，21，8碎乃，33姊扔，5，13梅誓，25恰梢，21搞坝，14
2. 第二次：$ gap=\displaystyle\frac{gap}{2}=3 $统刮，差3為一組，7辣苏，12及穗，33摧茴，25一組，4埂陆，21苛白，5，21一組焚虱，9购裙，8，13鹃栽，14一組躏率。每組內(nèi)進行插入排序，25和33換民鼓，31和5換薇芝。數(shù)組：7，4丰嘉，8恩掷，12，5供嚎，9，25，21克滴，13逼争，33，21劝赔，14
3. 第三次：$ gap=\displaystyle\frac{gap}{2}=1 $向下取整誓焦。所以直接對整個數(shù)組進行一次插入排序。
4. 總結(jié)：每次進行組內(nèi)的插入排序着帽，都是為了讓元素距其最終位置更近一步杂伟！

void ShellSort(int arr[],int nLength)
{
    int gap;
    int i; //小組
    int j;//插入排序
    int k;
    int temp;//保存無序數(shù)組的第一個

    if(arr == NULL || nLength <=0)return;

    //定步長
    for(gap = nLength/2 ; gap >0 ; gap/=2)
    {
        //按照步長分組
        for(i = 0;i<gap;i++)
        {
            //各組內(nèi)部插入排序
            for(j = i+gap;j<nLength;j+=gap)
            {
                k = j - gap; //有序數(shù)組的最后一個
                temp = arr[j]; //無序數(shù)組的第一個

                while(arr[k] > temp && k >=i)
                {
                    arr[k +gap] = arr[k];
                    k-=gap;
                }
                arr[k+gap] = temp;
            }
        }
    }
}

希爾排序的優(yōu)化

分組時，讓各組一起進行插入排序仍翰，都只進行一次赫粥，然后循環(huán)進行，代碼看起來簡潔予借，但是實際耗時基本相同越平！

void ShellSort2(int arr[],int nLength)
{
    int gap;
    int i; //小組
    int j;//插入排序
    int k;
    int temp;//保存無序數(shù)組的第一個

    if(arr == NULL || nLength <=0)return;

    //定步長
    for(gap = nLength/2 ; gap >0 ; gap/=2)
    {
        for(i = gap;i<nLength;i++)
        {
            //各組內(nèi)部插入排序
                k = i - gap; //有序數(shù)組的最后一個
                temp = arr[i]; //無序數(shù)組的第一個

                while(arr[k] > temp && k >=0)
                {
                    arr[k +gap] = arr[k];
                    k-=gap;
                }
                arr[k+gap] = temp;
        }
    }
}

MergeSort歸并排序

先拆分再合并。有2路灵迫，3路秦叛，5路等，這里用2路作為舉例說明瀑粥。先將數(shù)組按照二分法（2路）進行遞歸拆分挣跋，
拆分到每個塊里只剩一個元素，然后和相鄰元素進行比較排序合并狞换，在比較在合并避咆。

流程

Alt text

void Merge(int arr[],int nLow,int nHigh)
{
    int nBegin1;
    int nEnd1;
    int nBegin2;
    int nEnd2;
    int *pTemp = NULL;
    int i;

    nBegin1 = nLow;
    nEnd1 = (nLow+nHigh)/2;
    nBegin2 = nEnd1+1;
    nEnd2 = nHigh;

    pTemp = (int *)malloc(sizeof(int ) *(nHigh-nLow+1));

    //合并
    i = 0;
    while(nBegin1 <=nEnd1 && nBegin2 <= nEnd2)
    {
        if(arr[nBegin1] < arr[nBegin2])
        {
            pTemp[i] = arr[nBegin1];
            nBegin1++;
        }
        else
        {
            pTemp[i] = arr[nBegin2];
            nBegin2++;  
        }
        i++;
    }

    //將有剩余的數(shù)組元素放入臨時數(shù)組
    while(nBegin1 <= nEnd1)
    {
        pTemp[i] = arr[nBegin1];
        i++;
        nBegin1++;
    }

    while(nBegin2 <= nEnd2)
    {
        pTemp[i] = arr[nBegin2];
        i++;
        nBegin2++;
    }

    //將臨時數(shù)組元素放回原數(shù)組
    for(i = 0;i < nHigh-nLow +1;i++ )
    {
        arr[i+nLow] = pTemp[i];
    }

    //釋放
    free(pTemp);
    pTemp = NULL;

}

void MergeSort(int arr[],int nLow,int nHigh)
{
    int nMid;
    if(arr == NULL )return;

    //兩路歸并
    nMid = (nLow + nHigh)/2;

    if(nLow < nHigh)
    {
        //先拆分 
        MergeSort(arr,nLow,nMid);
        MergeSort(arr,nMid+1,nHigh);

        //合并
        Merge(arr,nLow,nHigh);
    }
}

HeapSort堆排序

堆排序是順序儲存，分為大根堆（大堆）和小根堆（小堆）哀澈。
大堆：父親結(jié)點一定是三個結(jié)點最大的牌借！
小堆：父親結(jié)點一定是三個結(jié)點最小的！
并且左右兒子結(jié)點并沒有什么大小順序關(guān)系割按，我們只是把這個順序存儲的結(jié)構(gòu)看作是二叉樹的結(jié)構(gòu)膨报，
我們僅僅是看作二叉樹的形式，實際上也是在數(shù)組進行操作适荣，并且根據(jù)完全二叉樹性質(zhì)(第5條)來進行排序现柠，對此我們要先掌握二叉樹的基本知識。

適用場景：在n個元素里找前幾個最大的或最小的弛矛，我們用堆够吩，并且找大的用小堆，找小的用大堆丈氓。

例如：一個數(shù)組｛10周循，2强法，7，4湾笛，6饮怯，12，11嚎研，9蓖墅，8｝

Heap1

1. 首先數(shù)組按照二叉樹的形勢，我們只是按照二叉樹對應(yīng)的性質(zhì)來將數(shù)組假想成二叉樹的樣子（并沒有真正的改變數(shù)組的結(jié)構(gòu)）临扮。
2. 我們按照圖2的方式论矾，從下往上從右往左的調(diào)整結(jié)點的位置，使其遵循大堆的特點杆勇！
3. 圖三是我們第一次調(diào)整好成大堆的樣子贪壳。
4. 圖四我們將堆頂和數(shù)組最后一個元素對換。
5. 然后重新按照前面的步驟調(diào)整成大堆靶橱，最后我們二叉樹的第一個結(jié)點就是最大的數(shù)寥袭，依次類推。二叉樹鏈接

堆排序類型題

類型題小結(jié)：

1. 在一個數(shù)組中找出前4個最大的數(shù)关霸？
   答：首先我們想到的是用小堆传黄，我們建立一個只有四個結(jié)點的小堆(圖在下面)，將數(shù)組元素一次放入小堆队寇，并調(diào)整成小堆膘掰，這是用數(shù)組第五元素和堆頂元素比較，若比堆頂元素大的話佳遣，則把堆頂元素放入小堆识埋，并移走小堆的最后一個元素（左邊最下面），循環(huán)完數(shù)組小堆里的數(shù)就是前4大的零渐！
2. 在50億個數(shù)里找出前50大窒舟？
   答：還是用小堆，建50個結(jié)點诵盼，將數(shù)據(jù)根據(jù)內(nèi)存容量分流惠豺，依次按流通過小堆，每個流里選出前50大的风宁，最后在整合到一起洁墙，在選出前50的數(shù)？
3. 在一個數(shù)據(jù)流中找到中位數(shù)戒财？數(shù)據(jù)流：一直不間斷提供數(shù)據(jù)热监，隨時提供，不是一個固定的數(shù)組饮寞。
   建立一個大堆和小堆孝扛，將數(shù)據(jù)丟入大堆列吼，并且調(diào)整大堆，把大堆堆頂扔小堆里疗琉，當(dāng)來數(shù)據(jù)的時候冈欢，調(diào)整小堆，把小堆堆頂放大堆里盈简，來數(shù)據(jù)時，放入大堆并調(diào)整大堆太示，把大堆堆頂放入小堆里柠贤。依次循環(huán)過程。此時类缤，小堆堆頂是較大數(shù)里最小的臼勉，大堆堆頂是比較小數(shù)里最大的。若數(shù)據(jù)的個數(shù)為奇數(shù)時餐弱，小堆堆頂是其中位數(shù)宴霸。當(dāng)數(shù)據(jù)的個數(shù)為偶數(shù)時，小堆堆頂和大堆堆頂?shù)暮统?是其中位數(shù)膏蚓。

Heap2

堆排序代碼

#define nLeft nRootID*2+1
#define nRight nRootID*2+2

void Adjust2(int arr[],int nLength,int nRootID)
{
    int nMax;

    //在有孩子的情況下  假設(shè)左孩子是大的    
    for(nMax = nLeft;nLeft < nLength;nMax = nLeft /*下一次繼續(xù)假設(shè)左孩子是最大的8*/)
    {
        //兩個孩子
        if(nRight < nLength)
        {
            //右孩子大  
            if(arr[nMax] < arr[nRight])
            {
                nMax = nRight;
            }
        }

        //大的  和父親比較  大  則交換
        if(arr[nMax] > arr[nRootID])
        {
            arr[nMax] = arr[nRootID] ^ arr[nMax];
            arr[nRootID] = arr[nRootID] ^ arr[nMax];
            arr[nMax] = arr[nRootID] ^ arr[nMax];

            nRootID = nMax;
        }
        else
        {
            break;
        }
    }
}

void HeapSort(int arr[],int nLength)
{
    int i;
    if(arr == NULL || nLength <=0)return;
    //建初始堆
    for(i = nLength/2-1;i>=0;i--)
    {
        Adjust2(arr,nLength,i);
    }
    //排序
    for(i = nLength-1;i>0;i--)
    {
        //最大值放后面
        arr[i] = arr[i] ^ arr[0];
        arr[0] = arr[i] ^ arr[0];
        arr[i] = arr[i] ^ arr[0];

        //調(diào)整根節(jié)點
        Adjust2(arr,i,0);
    }
}

BucketSort（桶排序）

基于哈希查找瓢谢，用桶原理進行排序。

哈希查找可以去我的博客,也可以看我的另一篇查找的算法驮瞧。推薦去博客氓扛，因為可以看latex數(shù)學(xué)公式。

桶排序更多時候是用來給小數(shù)排序的论笔。

1. 這里就以整數(shù)舉例說明采郎，例如數(shù)組｛19，27狂魔，55蒜埋，31，47最楷，50整份，16，21管嬉，22皂林，25｝，我們按照每隔十位為一個桶蚯撩。
2. 10_{20础倍，20}30，30_{40胎挎，40}50沟启，50~60忆家，共分為5個桶。
3. 將數(shù)字按照其范圍放入桶內(nèi)德迹。

4. 之后在每個桶內(nèi)進行排序芽卿，排好序之后依次從1桶開始倒回原數(shù)組（不給圖了，讀者可以自行畫下胳搞，很簡單）卸例。這時排序就完成了。

   
   
   BucketSort

由于是鏈表的頭添加肌毅，所以數(shù)字是到過來的順序筷转！

桶排序代碼

typedef struct node
{
    int nValue;
    struct node *pNext;
}MyBucket;

void FindMaxMin(int arr[],int nLength,int *nMin,int* nMax)
{
    int i;
    *nMin = arr[0];
    *nMax = arr[0];
    for(i = 1;i<nLength;i++)
    {
        if(arr[i] < *nMin)
        {
            *nMin = arr[i];
        }
        if(arr[i] > *nMax)
        {
            *nMax = arr[i];
        }
    }
}

void BucketSort(int arr[],int nLength)
{
    int nMax;
    int nMin;
    int i;
    MyBucket **pBucket = NULL;
    int nMinIndex;
    int nMaxIndex;
    int nIndex;
    MyBucket *pTemp = NULL;
    MyBucket *pMark = NULL;
    int temp;

    if(arr == NULL || nLength <=0)return;

    //找到最大值 最小值
    FindMaxMin(arr,nLength,&nMin,&nMax);

    nMinIndex = nMin/10;
    nMaxIndex = nMax/10;

    //桶的確定
    pBucket = (MyBucket **)malloc(sizeof(MyBucket*) *(nMaxIndex-nMinIndex+1));
    memset(pBucket,0,sizeof(MyBucket*) *(nMaxIndex-nMinIndex+1));

    //各元素入桶
    for(i = 0;i<nLength;i++)
    {
        nIndex = arr[i]/10 - nMinIndex;
        pTemp = (MyBucket*)malloc(sizeof(MyBucket) );
        pTemp->nValue = arr[i];

        pTemp->pNext = pBucket[nIndex];
        pBucket[nIndex] = pTemp;
    }

    //各桶內(nèi)排序
    for(i = 0;i<nMaxIndex-nMinIndex +1;i++)
    {
        //冒泡排序
        pMark = pBucket[i];
        
        while(pMark )
        {
            pTemp = pBucket[i];
            while(pTemp->pNext )
            {
                if(pTemp->nValue > pTemp->pNext->nValue)
                {
                    temp = pTemp->nValue;
                    pTemp->nValue = pTemp->pNext->nValue;
                    pTemp->pNext->nValue = temp;
                }
                pTemp = pTemp->pNext;
            }
            pMark = pMark->pNext;
        }
    }

    //倒回原數(shù)組
    i = 0;
    for(temp = 0;temp <nMaxIndex-nMinIndex +1;temp++ )
    {
        //遍歷各個桶
        pMark = pBucket[temp];
        while(pMark)
        {
            arr[i] = pMark->nValue;
            i++;
            pMark = pMark->pNext;
        }
    }

    //釋放空間
    for(temp = 0;temp <nMaxIndex-nMinIndex +1;temp++)
    {
        //釋放每個桶
        pMark = pBucket[temp];
        while(pMark)
        {
            pTemp = pMark;
            pMark = pMark->pNext;
            free(pTemp);
            pTemp = NULL;
        }
    }

    free(pBucket);
    pBucket = NULL;
}

RadinSort(LSD)基數(shù)排序

基數(shù)排序分兩種一種是LSD，一種是MSD悬而，這個就說LSD,因為MSD類似LSD而且使用的不是很頻繁呜舒，如想了解，看完LSD會事半功倍笨奠。LSD也是基于桶原理袭蝗，而且是從位數(shù)開始排序的。

哈希查找可以去我的博客,也可以看我的另一篇查找的算法般婆。推薦去博客到腥，因為可以看latex數(shù)學(xué)公式。

例如數(shù)組：｛124腺兴，11左电，25，3页响，221篓足，215，306闰蚕，35栈拖，23，14没陡，10涩哟，1，111｝
從低位開始算起盼玄，也就是個位開始的贴彼。因為十進制最后也就是0~9十個數(shù)字，所以我們要十個桶埃儿。

1. 按照數(shù)組的順序器仗，依次入桶，所以我們這時應(yīng)該是鏈表的尾添加
   個位：

   
   
   RadinSort-1
2. 將桶內(nèi)元素倒回數(shù)組，順序不可以變精钮，也就是10威鹿，11，221轨香，1忽你，111，3臂容，23科雳，124，14脓杉，25炸渡，215，35丽已，306.這個順序進入鏈表。

3. 按照十位的數(shù)字進行分桶买决，從數(shù)組依次入桶沛婴。
   十位：

   
   
   RadinSort-2
4. 再將桶內(nèi)元素倒入數(shù)組，同樣順序不可以變督赤，也就是1嘁灯，3，306躲舌，10丑婿，11，111没卸，14羹奉，215，221约计，23诀拭，124，25煤蚌，35.這個順序耕挨。

5. 按照百位，依次入桶尉桩。
   百位：

   
   
   RadinSort-3
6. 在倒入數(shù)組中筒占，此時我們的排序就完成了。

代碼

typedef struct node
{
    int nValue;
    struct node *pNext;
}MyRadix;

int FindMax(int arr[],int nLength)
{
    int i;
    int nMax = arr[0];
    for(i = 1;i<nLength;i++)
    {
        if(arr[i] > nMax)
        {
            nMax = arr[i];
        }
    }
    return nMax;
}

int GetLoopTimes(int nMax)
{
    int i = 0;
    while(nMax)
    {
        nMax/=10;
        i++;
    }
    return i;
}

void Sort(int arr[],int nLength,int i)
{
    int nBase = 1;
    MyRadix **pRadix = NULL;
    int j;
    int k;
    MyRadix *pTemp = NULL;
    int nIndex;
    MyRadix *pMark = NULL;

    //申請桶
    pRadix = (MyRadix **)malloc(sizeof(MyRadix*) * 10);
    memset(pRadix,0,sizeof(MyRadix*) * 10);

    //求被除基數(shù)
    while(i > 1)
    {
        nBase *= 10;
        i--;
    }

    //數(shù)字入桶
    for(j = 0;j <nLength; j++)
    {
        nIndex = arr[j]/nBase%10;

        pTemp = (MyRadix*)malloc(sizeof(MyRadix));
        pTemp->nValue = arr[j];
        pTemp->pNext = NULL;

        //尾添加
        if(pRadix[nIndex] == NULL)
        {
            pRadix[nIndex] = pTemp;
        }
        else
        {
            pMark = pRadix[nIndex];
            while(pMark->pNext)
            {
                pMark = pMark->pNext;
            }

            pMark->pNext = pTemp;
        }
    }

    //放回原數(shù)組
    j = 0;
    for(k = 0;k<10;k++)
    {
        pMark = pRadix[k];
        while(pMark)
        {
            arr[j] = pMark->nValue;
            j++;
            pMark = pMark->pNext;
        }
    }

    //空間釋放
    for(k = 0;k<10;k++)
    {
        pMark = pRadix[k];
        while(pMark)
        {
            pTemp = pMark;
            pMark = pMark->pNext;
            free(pTemp);
            pTemp = NULL;
        }
    }

    free(pRadix);
    pRadix = NULL;
}

void RadixSort(int arr[],int nLength)
{
    int i;
    int nMax;
    int nLoopTimes;
    if(arr == NULL || nLength <=0)return;

    //找最大值
    nMax = FindMax(arr,nLength);

    //獲得循環(huán)次數(shù)
    nLoopTimes = GetLoopTimes(nMax);

    //數(shù)組元素按照各位依次入桶
    for(i = 1;i<=nLoopTimes;i++)
    {
        //個 十 百 位處理
        Sort(arr,nLength,i);
    }
}