【數據結構】常用比較排序算法（包括：選擇排序，堆排序，冒泡排序，選擇排序，快速排序，歸并排序）

對于非比較排序算法，如計數排序、基數排序，大家如果感興趣，可以查看博客http://10740184.blog.51cto.com/10730184/1782077。本文，我將介紹比較排序算法。

直接插入排序：

在序列中，假設升序排序

1）從0處開始。

1）若走到begin =3處，將begin處元素保存給tmp，比較tmp處的元素與begin--處元素大小關系，若begin處<begin-1處，將begin-1處元素移動到begin；若大于，則不變化。再用tmp去和begin--處的元素用同樣的方法去作比較，直至begin此時減少到數組起始坐標0之前結束。

3）以此類推，依次走完序列。

時間復雜度：O()

代碼如下：

//Sequence in ascending order 
void InsertSort(int* a,int size)
{
    assert(a);
    for (int begin = 0; begin < size ; begin++)
    {
        int tmp = a[begin];
        int end = begin-1;
        while (end >= 0 && tmp < a[end])
        {
            a[end+1] = a[end];
            a[end] = tmp;
            end--;
        }
    }
}

2.希爾排序

希爾排序實際上是直接插入排序的優化和變形。假設升序排序

1）我們先去取一個增量值gap，將序列分為幾組。

2）然后我們分組去排序。當每個分組排序排好后，相當于整個序列的順序就排列好了。

3）比較a[i]，a[i+gap]大小關系，若a[i]>a[i+gap]，則交換。否則不處理。往后走，繼續該步驟……

代碼如下：

//Sequence in ascending order 
void ShellSort(int* a, int size)
{
    assert(a);
    int gap = size;
    while (gap > 1)
    {
        gap = gap / 3 + 1;
        for (int i = 0; i < size - gap; i++)
        {
            int end = i;
            int tmp = a[end + gap];
            while (end >= 0 && a[end] > a[end + gap])
            {
                a[end+gap] = a[end];
                a[end] = tmp;
                end -= gap;
            }
        }
    }
    
}

3.選擇排序

假設升序排序

1）第1次遍歷整個數組，找出最小（大）的元素，將這個元素放于序列為0（size-1）處。此時，未排序的序列不包括0（size-1）處.第2次，同樣的方法找到找到剩下的未排序的序列中的最小的元素，放于序列為1處。

2）重復,直至排到序列結尾處，這個序列就排序好了。

時間復雜度：O(N^2)。

代碼如下：

//Sequence in ascending order 
void SelectSort(int* a, int size)
{
    assert(a);
    
    for (int i = 0; i < size; i++)
    {
        int minnum = i;
        for (int j = i+1; j < size;j++)
        {
            if (a[minnum] > a[j])
            {
                minnum = j;
            }        
        }
        if (i != minnum)
        {
            swap(a[i], a[minnum]);
        }
        
    }
}

4.堆排序

假設升序排序

我們先要思考升序序列，我們需要建一個最大堆還是最小堆？

如果最小堆，那么每個根節點的元素大于它的子女節點的元素。但是，此時卻不能保證她的左右節點一定哪個大于哪一個，且不能保證不同一層的左右子樹的節點元素大小。

所以，要設計升序排序，我們需要建一個最大堆。

1）建一個最大堆。

2）第1次，將根節點的元素與堆的最后一個節點元素交換，這樣肯定保證最大元素在堆的最后一個節點處，然后此時的根節點并不一定滿足大于左右子女節點，因此將其向下調整，至合適位置處。第2次，將根節點的元素與堆的倒數第2個節點元素交換，向下調整交換后的根節點至合適位置……

代碼如下：

void _AdjustDown(int parent, int* a, int size)
{
    int child = 2 * parent + 1;
    while (child < size)
    {
        if (child + 1 < size && a[child + 1] > a[child])
        {
            child++;
        }
        if (a[child] >a[parent])
        {
            swap(a[child], a[parent]);
            parent = child;
            child = 2 * parent + 1;
        }
        else
        {
            break;
        }
    }
}


//Sequence in ascending order 
void HeapSort(int* a, int size)
{
    assert(a);
    for (int i = (size - 2) / 2; i >= 0;i--)
    {
        _AdjustDown(i, a, size);
    }

    for (int i = 0; i < size -1; i++)
    {
        swap(a[0], a[size - i -1]);
        _AdjustDown(0, a, size-i-1);
    }
}

5.冒泡排序

假設升序排序

冒泡，顧名思義，像泡一樣慢慢地沉。

1）第一次，比較a[0],a[1]大小，若a[0]>a[1]，則交換它們。再比較a[1],a[2]，若a[1]>a[2]，則交換……這樣一直到比較a[size-1]，a[size]結束，此時已經將一個最大的元素沉到序列的最尾端size-1處了。

2）第二次，重復上述操作，可將次最大的元素沉到size-2處。

3）重復，完成排序。

比較：

冒泡排序是兩兩比較，每次將最大的元素往后沉。而選擇排序不同的是，每次遍歷選擇出最大元素放到最后。

代碼如下：

//Sequence in ascending order 
void BubbleSort(int* a, int size)
{
    assert(a);
    for (int i = 0; i < size; i++)
    {
        for (int j = 0; j < size - i -1; j++)
        {
            if (a[j] > a[j + 1])
            {
                swap(a[j], a[j + 1]);
            }
        }
    }
}

6.快速排序

快速排序，顧名思義，排序算法很快，它是最快的排序。時間復雜度為：O(n*lgn).適合于比較亂的 序列。假設升序排序

這兩種方法都挺簡單的，相比而言，方法2代碼更短，更加簡單！！！大家自己斟酌使用！！！

方法1：

我們這里先介紹快速排序的挖坑法。（每次數據被挪走后都相當于挖出了一個坑，這個坑可以把其他數據挪過來放。）

對于序列：{ 5, 1，8,12, 19, 3, 7, 2, 4 ，11}

1）我們取序列的第一個數據當做比較的基準，并且設定序號為0的位置為低位置low，序號為size-1的位置為高位置high。

2）取出序列的基準元素key，此刻的5.

     在high位置從右往左找直到找到比基準值5小的元素，即此刻的元素4處停止。

     然后，在low位置從左往右找直到找到比基準值5大的元素，即此刻的元素8停止。

由于此時的基準元素key被取出,存放它的位置就空下來了。將找到的元素4賦值給此刻的這個位置.

3）此時元素4存放的位置空下來了，將找到的低位置的8放到這個位置去。

4）重復這樣的動作，2放到基準位置，12放到原來2的位置……

5）直到low>=high時停止。

以上是一次快速排序，在經過一次快速排序后，high與low相遇左右各形成有序序列。再將這個相遇位置左右各當成一個序列，繼續進行快速排序，最終可以將序列排序好。

代碼如下：

void QuickSort(int* a, int left,int right)
 {
    assert(a);
    int low = left;
    int high = right;
    int key = a[low];

    while (low < high)
    {                
        while (low < high && key <= a[high])
        {
            high--;
        }
        a[low] = a[high];

        while (low <high && key >= a[low])
        {
            low++;
        }
        a[high] = a[low];
    }
    a[low] = key;

    if (left <= high)
    {
        QuickSort(a, left, low - 1);
        QuickSort(a, low + 1, right);
    }
}

方法2：

快速排序的prev、cur法：

為了方便給大家分享，我把它稱之為prev、cur法。

1）引入兩個位置，prev、cur,cur首先指向序列的初始位置，prev指向cur的前面（即：若cur=0,則prev=-1位置處）。

2）我們將基準key取成序列的最后一個位置right處的元素。

3）cur從初始位置處開始，（因為要排成升序），找一個cur處的值大于key的值停止，否則小于key的值的話，就一直繼續cur往前走，此時prev是不動的。但是當找到cur處的值大于key的值時，++prev，再將prev處的值與cur的值進行交換。（注意，prev前置加加，即prev先往后走一步再交換值）。

4）cur繼續往前走，繼續重復第3）條步驟，直到遇到right-cur=1，馬上就要相交時停止。

5）停止后，遞歸左右區間，重復上述步驟，直至區間只剩下一個元素時無需繼續劃分區間遞歸，排序結束。

代碼如下：

int QuickSort(int* a, int left, int right)
{
    assert(a);
    int cur = left;
    int prev = cur - 1;
    int key = mid(a,left,right);
    swap(key, a[right]);

    while (cur < right)
    {
        if (a[cur] <= a[right])
        {
            swap(a[++prev], a[cur]);
        }
        cur++;
    }
    swap(a[++prev], a[right]);
    
    if (prev - 1 > left)
    {
        QuickSort(a, left, prev - 1);
    }

    if (prev + 1 < right)
    {
        QuickSort(a, prev + 1, right);
    }
}