排序算法包括很多，常见的有快排，堆排序，冒泡排序，归并排序，选择排序，插入排序等， 各种排序算法经常出现在面试题中。
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);
}
}
随后更新堆排序和归并排序
