排序算法包括很多，常見(jiàn)的有快排，堆排序，冒泡排序，歸并排序，選擇排序，插入排序等， 各種排序算法經(jīng)常出現(xiàn)在面試題中。

1.快速排序
思想：選擇一個(gè)基準(zhǔn)數(shù)據(jù)（常用數(shù)組中第一個(gè)元素），使得其左邊的元素都小于它，右邊的元素都大于它，然后返回它的位置。

遞歸實(shí)現(xiàn)：

int partition(vector<int> &arr, int begin, int end){
      int i = begin, j = end;
      int x = arr[i];
        while(i < j){
            while(i < j && arr[j] >= x) j --;
            if(i < j){
                arr[i] = arr[j];
                i ++;
            }
            while(i < j && arr[i] < x) i ++;
            if(i < j){
                arr[j] = arr[i];
                j --;
            }
        }
        arr[i] = x;
        return i;
    }

void quicksort1(vector<Comparable> &vec,int low,int high){  
    if(low<high){  
        int mid=partition(vec,low,high);  
        quicksort1(vec,low,mid-1);  
        quicksort1(vec,mid+1,high);  
    }  
}  

使用棧的非遞歸快速排序

void quicksort2(vector<Comparable> &vec,int low,int high){  
    stack<int> st;  
    if(low<high){  
        int mid=partition(vec,low,high);  
        if(low<mid-1){  
            st.push(low);  
            st.push(mid-1);  
        }  
        if(mid+1<high){  
            st.push(mid+1);  
            st.push(high);  
        }  
        //其實(shí)就是用棧保存每一個(gè)待排序子串的首尾元素下標(biāo)，下一次while循環(huán)時(shí)取出這個(gè)范圍，對(duì)這段子序列進(jìn)行partition操作  
        while(!st.empty()){  
            int q=st.top();  
            st.pop();  
            int p=st.top();  
            st.pop();  
            mid=partition(vec,p,q);  
            if(p<mid-1){  
                st.push(p);  
                st.push(mid-1);  
            }  
            if(mid+1<q){  
                st.push(mid+1);  
                st.push(q);  
            }         
        }  
    }  

插入排序
思路：每次將一個(gè)待排序的記錄，按其關(guān)鍵字大小插入到前面已經(jīng)排好序的子序列中的適當(dāng)位置，直到全部記錄插入完成為止。
簡(jiǎn)潔代碼：

void Insertsort3(int a[], int n)  
{  
    int i, j;  
    for (i = 1; i < n; i++)  
        for (j = i - 1; j >= 0 && a[j] > a[j + 1]; j--)  
            Swap(a[j], a[j + 1]);  
}  

常規(guī)代碼

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

冒泡排序
思路：臨近的數(shù)字兩兩進(jìn)行比較,按照從小到大或者從大到小的順序進(jìn)行交換,這樣一趟過(guò)去后,最大或最小的數(shù)字被交換到了最后一位,然后再?gòu)念^開(kāi)始進(jìn)行兩兩比較交換...

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

選擇排序
思路：工作原理是每一次從待排序的數(shù)組中選出最小（或最大）的一個(gè)元素，存放在序列的起始位置，直到全部待排序的數(shù)據(jù)元素排完。

void select_sort(int list[], int n)
{
    int i, j, min, temp;
    for (i = 0; i < n - 1; i++){
        min = i;
        for (j = i + 1; j < n; j++)
        if (list[j] < list[min])
            min = j;
        SWAP(list[i], list[min], temp);
    }
}

隨后更新堆排序和歸并排序