1. 冒泡排序

基本思想：每次比較兩個相鄰的元素，如果他們的順序錯誤就把他們交換過來。

時間復雜度：

• 最好的情況下，待排序記錄已經(jīng)有序，只需要一趟排序就可以完成，所以冒泡排序的最好時間復雜度為 O(n)。
• 最壞的情況下，待排序記錄反序，這時需要 n - 1 趟排序，每趟排序需要比較 n - i 次比較操作，這時比較和移動的次數(shù)達到最大值，所以冒泡排序的最壞時間復雜度為 O(n ^ 2)。
• 平均時間復雜度為 O(n ^ 2)。因為它移動的次數(shù)較多，其平均時間性能還不如直接插入排序。

void bubble_sort(int s[],int n)
{
    for (int i=0;i<n;i++)
    {
        for (int j=n-1;j>i;j--)
        {
            if (s[j-1]>s[j])
            {
                swap(s[j-1],s[j]);
            }
        }
    }
}

冒泡排序的優(yōu)化：在算法中增加一個標志exchange，用以標識本趟冒泡結(jié)果是否發(fā)生了交換；如果沒有發(fā)生交換則exchange=false，表示全部元素已經(jīng)排好，因而可以結(jié)束算法；如果exchange=true，表示本趟有元素發(fā)生交換，還需執(zhí)行下一趟排序。

void new_bubble_sort(int s[],int n)
{
    bool exchange;
    for (int i=0;i<n;i++)
    {
        exchange = false;
        for (int j=n-1;j>i;j--)
        {
            if (s[j-1]>s[j])
            {
                swap(s[j-1],s[j]);
                exchange =true;
            }
        }
        if(exchange == false)   return;
    }
}

2. 插入排序

基本思想：每次將一個待排序元素按其大小插入到前面已經(jīng)排好的序列中的適當位置，直至元素全部插入為止

時間復雜度分析： 直接插入排序算法主要進行有兩個操作，查找比較，移動記錄。這兩個操作均和記錄長度n相關(guān)。其平均時間復雜度為O(n^2)。這在排序算法里面算慢的，但是當記錄較少時，它的效率還是可以不錯的。

空間復雜度分析：直接插入排序只需要一個元素的輔助空間，用于元素的位置交換O(1)。

直接插入排序是穩(wěn)定排序。它在元素基本有序的情況下（接近最好情況），比較和移動的次數(shù)都較少，效率是很高的。

2.1 直接插入排序

void insert_sort(int s[],int n)
{
    for (int i=1;i<n;i++)
    {
        if (s[i]<s[i-1])
        {
            int temp = s[i], j=i-1;
            do 
            {
                s[j+1] = s[j];
                j--;
            } 
            while (j>=0 && temp<s[j]);
            s[j+1] = temp;
        }
    }
}

2.2 二分插入排序

利用二分查找，查找待插入元素應插入前面有序序列的位置。

3. 選擇排序

基本思想：每次（第i次）在后面待排序元素中選出排序碼最小的元素，作為有序元素序列的第i個元素。待n-2趟作完，待排序元素只剩下1個，就不用排序了。

時間復雜度分析：無論待排序記錄的初始狀態(tài)如何，在第i趟排序中選出最小關(guān)鍵字的記錄，需做n-i次比較，因此，總的比較次數(shù)為：n*(n-1) /2=O(n^2)，當待排序記錄的初始狀態(tài)為正序時，移動次數(shù)為 0；當初始狀態(tài)為反序時，每趟排序均要執(zhí)行交換操作，總的移動次數(shù)取最大值3 *(n-1)。所以，直接選擇排序的平均時間復雜度為O(n^2)。

非穩(wěn)定排序。

void select_sort(int s[],int left,int right)
{
    for (int i=left;i<right;i++)
    {
        int min = i;
        for (int j=i+1;j<=right;j++)
        {
            if(s[j]<s[min]) min = j;
        }
        if(min != i)    swap(s[i],s[min]);
    }
}

4. 快速排序

時間復雜度分析：

• 最壞情況：每次劃分選取的基準都是當前無序區(qū)中關(guān)鍵字最小(或最大)的記錄，劃分的結(jié)果是基準左邊的子區(qū)間為空(或右邊的子區(qū)間為空)，而劃分所得的另一個非空的子區(qū)間中記錄數(shù)目，僅僅比劃分前的無序區(qū)中記錄個數(shù)減少一個。此時，時間復雜度為 O(n ^ 2)。
• 最好情況：每次劃分所取的基準都是當前無序區(qū)的"中值"記錄，劃分的結(jié)果是基準的左、右兩個無序子區(qū)間的長度大致相等。總的關(guān)鍵字比較次數(shù)：0(nlgn)。
• 盡管快速排序的最壞時間為 O(n ^ 2)，但就平均性能而言，它是基于關(guān)鍵字比較的內(nèi)部排序算法中速度最快者，快速排序亦因此而得名。它的平均時間復雜度為 O(nlgn)。

空間復雜度分析：快速排序需要一個棧來實現(xiàn)遞歸。若每次劃分較為均勻（也就是對半分，基準值總是中值），則其遞歸樹的高度為O(lgn)，故遞歸后需?？臻g為O(lgn)。最壞情況下，遞歸樹的高度為O(n)，所需的?？臻g為O(n)。

int partition(int s[],int low,int high)
{
    int key = s[high];
    int piv = low;
    for (int i=low;i<high;i++)
    {
        if (s[i]<=key)
        {
            swap(s[piv],s[i]);
            piv++;
        }
    }
    swap(s[piv],s[high]);
    return piv;
}

void quick_sort(int s[],int left,int right)
{
    if (left<right)
    {
        int piv = partition(s,left,right);
        quick_sort(s,left,piv-1);
        quick_sort(s,piv+1,right);
    }
}

5. 歸并排序

歸并排序是采用分治法的一個非常典型的應用，它要做兩件事情：

• “分”, 就是將數(shù)組盡可能的分，一直分到原子級別；
• “并”，將原子級別的數(shù)兩兩合并排序，最后產(chǎn)生結(jié)果。

至于二個有序數(shù)列合并，只要比較二個數(shù)列的第一個數(shù)，誰小就先取誰安放到臨時隊列中，取了后將對應數(shù)列中這個數(shù)刪除，直到一個數(shù)列為空，再將另一個數(shù)列的數(shù)據(jù)依次取出即可。

void merge(int* array, int tempArray, int left, int middle, int right)
{
    for(int i=left;i<=right;i++)    tempArray[i] = array[i];
    int s1 = left, s2 = mid +1, temp = left;
    while(s1 <=mid && s2 <= right)
    {
        if(tempArray[s1] <= tempArray[s2])
            array[temp++] = tempArray[s1++];
        else    array[temp++] = tempArray[s2++];
    }
    while(s1 <= mid) array[temp++] = tempArray[s1++];
    while(s2 <= right) array[temp] = tempArray[s2++];
}

void merge_sort(int* array, int* tempArray, int left, int right)
{
    if(left >= right)   return ;
    int mid = left + (right - left)/2;
    int tempArray = new int[right-left+1];
    merge_sort(array,tempArray,left,mid);
    merge_sort(array,tempArray,mid+1,right);
    merge(array,tempArray,left,mid,right);
}