/*
轉自:
http://m.shnenglu.com/chenjt3533/archive/2013/03/25/198815.html 
*/
#include "stdafx.h"



/*
             --- 冒泡排序 --- 
自下而上的兩兩比較，小泡排在大泡前，一趟冒出一個最小泡。
*/

void BubbleSort(int nArray[], int nLength)
{
    int i = nLength - 1;
    int j = 0;
    int temp = 0;

    for (i = nLength - 1; i > 0; --i)
    {
        for (j = i - 1; j >= 0; --j)
        {
            if (nArray[j] > nArray[j + 1])
            {
                temp = nArray[j + 1];
                nArray[j + 1] = nArray[j];
                nArray[j] = temp;
            }
        }
    }
}


/*
                    --- 選擇排序 --- 
自下而上的兩兩比較，記錄最小數的下標，將最上面的數與最小數交換。
*/

void SelectSort(int nArray[], int nLength)
{
    int tempIndex = 0;
    int tempValue = 0;

    for (int i = 0; i < nLength; ++i)
    {
        tempIndex = i;
        for (int j = i + 1; j < nLength; ++j)
        {
            if (nArray[tempIndex] > nArray[j])
            {
                tempIndex = j;
            }
        }
        tempValue = nArray[i];
        nArray[i] = nArray[tempIndex];
        nArray[tempIndex] = tempValue;
    }
}


/*
                    --- 插入排序 --- 
將數據插入到已排序的序列中，邊找合適的位置，邊移動數據，找到合適位置插入數據。
*/

void InsertSort(int nArray[], int nLength)
{
    for (int i = 1; i < nLength; ++i)
    {
        int temp = nArray[i];
        int j = i;
        for (; j > 0 && nArray[j - 1] > temp; --j)
        {
            nArray[j] = nArray[j - 1];
        }
        nArray[j] = temp;
    }    
}


/*
                    --- 快速排序 --- 
是對冒泡排序的改進。
1．先從數列中取出一個數作為基準數;
2．分區過程，將比這個數大的數全放到它的右邊，小于或等于它的數全放到它的左邊;
3．再對左右區間重復第二步，直到各區間只有一個數.

分區過程可以形象的描述為“挖坑填數”：
1．將基準數nBase挖出形成第一個坑nArray[nLow];
2．nHigh--由后向前找比nBase小的數，找到后挖出此數填前一個坑nArray[nLow]中;
3．nLow++由前向后找比nBase大的數，找到后也挖出此數填到前一個坑nArray[nHigh]中;
4．再重復執行2，3二步，直到nLow==nHigh，將基準數nBase填入nArray[nLow]中.
*/

int AdjustArray(int nArray[], int nLow, int nHigh)
{
    int nBase = nArray[nLow];

    while(nLow < nHigh)
    {
        while(nLow < nHigh && nBase <= nArray[nHigh])
            --nHigh;
        if (nLow < nHigh)
        {
            nArray[nLow++] = nArray[nHigh];
        }

        while(nLow < nHigh && nBase > nArray[nLow])
            ++nLow;
        if (nLow < nHigh)
        {    
            nArray[nHigh--] = nArray[nLow];
        }
    }
    nArray[nLow] = nBase;
    return nLow;
}

void QuickSort(int nArray[], int nLow, int nHigh)
{
    if (nLow < nHigh)
    {
        int nMid = AdjustArray(nArray, nLow, nHigh);
        QuickSort(nArray, 0, nMid - 1);
        QuickSort(nArray, nMid + 1, nHigh);
    }
}


/*                
                    --- 希爾排序 --- 
是對直接插入排序算法的改進，又稱縮小增量排序。
1、將數組進行分組，下標相差d的為一組；
2、對每組中全部元素進行排序；
3、然后再用一個較小的增量d, 重復1、2，直到d為1時，排序完成。

一般增量取值為上一次的一半，d = 1/2 d，第一次取值為數組長度的一半。
*/

void ShellSort(int nArray[], int nLength)
{
    for (int nDifference = nLength / 2; nDifference > 0; nDifference = nDifference / 2)
    {
        for (int i = nDifference; i < nLength; ++i)
        {
            int temp = nArray[i];
            int j = i;
            for (; j > 0 && nArray[j - 1] > temp; --j)
            {
                nArray[j] = nArray[j - 1];
            }
            nArray[j] = temp;
        }
    }
}


/*                
                    --- 歸并排序 --- 
是將兩個已經排序的序列合并成一個有序序列。
1、待排序序列分為兩個子序列;
2、每個子序列重復步驟1，直到每個子序列只有一個元素;
3、按大小順序合并兩個子序列;
4、重復步驟3，直到合并為一個整體有序序列，排序完成。
*/

void Merge(int nArray[], int nLow, int nHigh)
{
    int nFirst = nLow;
    int nMid = (nLow + nHigh) / 2;
    int nSecond = nMid + 1;
    int* p = (int*)malloc(sizeof(int) * (nHigh - nLow + 1));
    int nIndex = 0;

    while(nFirst <= nMid && nSecond <= nHigh)
    {
        if (nArray[nFirst] > nArray[nSecond])
        {
            p[nIndex] = nArray[nSecond++];
        }
        else
        {
            p[nIndex] = nArray[nFirst++];
        }
        ++nIndex;
    }

    while (nFirst <= nMid)
    {    
        p[nIndex++] = nArray[nFirst++];
    }

    while (nSecond <= nHigh)
    {    
        p[nIndex++] = nArray[nSecond++];
    }

    for (int i = 0; i <= nIndex && nLow <= nHigh;)
    {
        nArray[nLow++] = p[i++];
    }
    free(p);
}

void MergeSort(int nArray[], int nLow, int nHigh)
{
    if (nLow < nHigh)
    {
        int nMid = (nLow + nHigh) / 2;
        MergeSort(nArray, nLow, nMid);
        MergeSort(nArray, nMid+1, nHigh);
        Merge(nArray, nLow, nHigh);
    }
}


/*            
                    --- 堆排序 --- 
1、先將數組轉換為完全二叉樹；
2、調整二叉樹形如大頂堆；
3、將根結點與最后一個葉子結點互換，即將最大元素放在數組的末尾，數組的長度減一；
4、再重復2、3，直到數組長度為1，排序完成。
*/

void AdjustHeap(int nArray[], int nLength, int nIndex)
{
    int nLeft = nIndex * 2 + 1;
    int nRight = nIndex * 2 + 2;
    int nParent = nIndex;

    while(nLeft < nLength && nRight < nLength)
    {
        int nBigIndex = (nArray[nLeft] > nArray[nRight] ? nLeft : nRight);
        if (nArray[nParent] < nArray[nBigIndex])
        {
            int temp = nArray[nParent];
            nArray[nParent] = nArray[nBigIndex];
            nArray[nBigIndex] = temp;

            nLeft = nBigIndex * 2 + 1;
            nRight = nBigIndex * 2 + 2;
        }
        break;
    }
}

void BuildHeap(int nArray[], int nLength)
{
    for (int i = nLength / 2 - 1; i >= 0; --i)
    {
        AdjustHeap(nArray, nLength, i);
    }
}

void HeapSort(int nArray[], int nLength)
{
    BuildHeap(nArray, nLength);

    while(nLength > 1)
    {
        int temp = nArray[0];
        nArray[0] = nArray[nLength - 1];
        nArray[nLength - 1] = temp;
        AdjustHeap(nArray, --nLength, 0);
    }
}

void Test_Sort()
{
    int nArray[5] = {1,3,2,5,4};
    BubbleSort(nArray, 5);
    //SelectSort(nArray, 5);
    //InsertSort(nArray, 5);
    //QuickSort(nArray, 0, 4);
    //ShellSort(nArray, 5);
    //MergeSort(nArray, 0, 4);
    //HeapSort(nArray, 5);
    for (int n = 0; n < 5; ++n)
    {
        std::cout << nArray[n] << " ";
    }
    std::cout << std::endl;
}
int main()
{
    Test_Sort();
    system("pause");
    return 0;
}