关于每个算法的详细介绍请查看分节介绍，这里对所有的排序算法做一个汇总。
归并排序
简单选择排序与堆排序
冒泡排序与快速排序
直接插入排序，希尔排序
#include <iostream>
#include<vector>
using namespace std;void SI_sort(vector<int>& a,int n){for (int i=1;i<n;i++){int t = i-1;int key = a[i];while(t>=0&&a[t]>key){a[t+1] = a[t];t--;}a[t+1]=key;}
}void shell_sort(vector<int>& a, int n)
{int gap;for(gap = n/2; gap >0; gap = gap/2){for(int i=0; i<gap; i++){for(int j = i+gap; j<n; j=j+gap){if(a[j]<a[j-gap]){int temp = a[j];int k = j-gap;while(k>=0&&a[k]>temp){a[k+gap] = a[k];k = k-gap;}a[k+gap] = temp;}}}}
}
void Bibble_sort(vector<int>& a, int n){for (int i=0;i<n;i++){for(int j = i+1;j<n;j++){if(a[i]>a[j]){int temp = a[i];a[i]= a[j];a[j]= temp;}}}
}
int quick_sort(vector<int>& a, int low,int high);
void quickSort(vector<int>& a, int low, int high) {if (low < high) {int q = quick_sort(a, low, high);quickSort(a, low, q - 1);quickSort(a, q + 1, high);}}int quick_sort(vector<int>& a, int low,int high){int pivorkey =a[low];while(low<high){while(low<high && a[high]>=pivorkey){--high;}a[low] = a[high];while(low<high &&a[low]<=pivorkey){++low;}a[high] = a[low];}a[low] = pivorkey;return low;
}void select_sort(vector<int>& a, int n){int minvalue = a[0];int local = 0;for(int i=0;i<n;i++){minvalue = a[i];for(int j=i;j<n;j++){if(a[j]<=minvalue){minvalue = a[j];local = j;}}if(i!=local){int temp = a[i];a[i]=a[local];a[local] = temp;}}}void Swap(int &a, int &b)
{int temp = a;a = b;b = temp;
}
void headadjust(vector<int>& a, int root, int n){int head = a[root];int i ;for(i = root*2+1;i<n;i=i*2+1){if (i<n-1 && a[i]<a[i+1]) ++i;if (head > a[i]) //不用交换break;a[root] = a[i]; //交换值root = i; //继续查找}a[root] = head;
}void head_sort(vector<int>& a, int n)
{for(int i = n/2-1;i>=0;--i){headadjust(a,i,n);}for(int j = n-1;j>0;--j){Swap(a[0],a[j]);headadjust(a,0,j);}
}
void merge(vector<int>& a,int low,int mid,int high){int* b = new int[high-low+1];int i=low,j=mid+1,k=0;while(i<=mid&&j<=high)if(a[i]<=a[j]){b[k]=a[i];i++;k++;}else{b[k]=a[j];j++;k++;}while (i<=mid) // 将第1 段余下部分复制到b{ b[k]=a[i]; i++;k++; }while (j<=high) // 将第2 段余下部分复制到b{ b[k]=a[j]; j++;k++; }for (k=0,i=low;i<=high;k++,i++) // 将b 复制回a中a[i]=b[k];delete [] b;
}
void mergepass(vector<int>& a,int length,int n){ //length表示每个片段的段长度int i;for(i = 0; i+2*length-1<n;i= i+2*length){ //归并长度为length的两个子序列merge(a,i,i+length-1,i+2*length-1);}if(i+length -1<n) //最后的子表长度可能小于lengthmerge(a,i,i+length-1,n-1);
}
void merge_sort(vector<int>& a, int n){int length;for(length =1;length<n;length = 2*length){//log2(n)趟mergepass(a,length,n);}
}
int main()
{vector<int> data{ 61, 17, 29, 22, 34, 60, 72, 21, 50, 1, 62 };int n = data.size();//SI_sort(data,n);//shell_sort(data,n);//Bibble_sort(data,n);//quickSort(data,0,n-1);//select_sort(data,n);//head_sort(data,n);merge_sort(data,n);for (int i = 0; i < n; i++){cout << data[i]<<" ";}return 0;
}