各种排序算法

排序算法包括很多，常见的有快排，堆排序，冒泡排序，归并排序，选择排序，插入排序等， 各种排序算法经常出现在面试题中。

1.快速排序
思想：选择一个基准数据（常用数组中第一个元素），使得其左边的元素都小于它，右边的元素都大于它，然后返回它的位置。

递归实现：

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);  
        }  
        //其实就是用栈保存每一个待排序子串的首尾元素下标，下一次while循环时取出这个范围，对这段子序列进行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);  
            }         
        }  
    }  

插入排序
思路：每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子序列中的适当位置，直到全部记录插入完成为止。
简洁代码：

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]);  
}  

常规代码

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;  
        }  
}  

冒泡排序
思路：临近的数字两两进行比较,按照从小到大或者从大到小的顺序进行交换,这样一趟过去后,最大或最小的数字被交换到了最后一位,然后再从头开始进行两两比较交换...

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;
            }
        }
} 

选择排序
思路：工作原理是每一次从待排序的数组中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。

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);
    }
}

随后更新堆排序和归并排序