这里讨论的排序还有如下两个特点：
- 只讨论基于比较的排序（> = < 有定义）
- 只讨论内部排序（排序工作能够在主存中完成）
大多数情况下，为简单起见，讨论从小大的整数排序。这里使用的函数模型是：
void xSort(vector<int> &arr)
除了面试外，在日常的工作中，我们是不可能去手写排序算法了，但是了解排序算法的工作原理还是很有意义的，里面使用的一些技巧很值得借鉴。
在排序算法中，有一个稳定性的概念，即任意两个相等的数据， 排序前后的相对位置不发生改变。
先给出我用于测试排序函数正确性的测试函数，本文所有的排序算法都只通过了这个测试函数，所有有可能有一些BUG。
void testSortFunc(void(*sortFunc)(vector<int>&)){
int TIMES = 10000;
int SIZE = 100;
for(int i=0;i<TIMES;i++){
vector<int> arr;
for(int j=0;j<SIZE;j++){
arr.push_back(rand());
}
vector<int> arr1 = arr, arr2 = arr;
sort(arr1.begin(),arr1.end());
sortFunc(arr2);
for(int j=0;j<SIZE;j++){
if(arr1[j] != arr2[j]){
cout<<"error"<<endl;
return;
}
}
}
cout<<"pass all test"<<endl;
}
选择排序
选择排序非常简单，每次选择最大的一个数，放到指定的位置即可。
void selectSort(vector<int> &arr){
for(int i=arr.size()-1;i>0;i--){
int maxPos = 0;
for(int j=1;j<=i;j++){
if(arr[j] > arr[maxPos]){
maxPos = j;
}
}
swap(arr[i],arr[maxPos]);
}
}
冒泡排序
冒泡排序的思想十分简单，就是每次找到最大/最小的数，然后重复N次。所以，写这种程序还是比较简单的，下面直接给出冒泡排序的代码：
void bubbleSort(vector<int> &arr){
for(int i = arr.size()-1;i>0;i--){
//通过交换，每次将剩余的最大数调整到i
for(int j=0;j<i;j++){
if(arr[j] > arr[j+1]){
swap(arr[j],arr[j+1]);
}
}
}
}
插入排序
插入排序的算法就好像打牌的时候，摸牌之后的操作。这个算法个人感觉比冒泡排序要难一点。
void insertSort(vector<int> &arr){
for(int i = 1;i<arr.size();i++){
int num = arr[i];
int j;
//如果前一个数大于当前数，将前一个数后移一位，然后继续和下一个数比较
for(j = i;j>0 && arr[j-1] > num;j--){
arr[j] = arr[j-1];
}
//停止的时候就到了正确的位置
arr[j] = num;
}
}
希尔排序
希尔排序其实和简单排序差不多，只不过是每次是个n个进行排序。这个我已经空了很久了，在K&R那本书里面看到了这个算法，然后就搬到了这里。下面是具体的代码：
void shellSort(vector<int> &arr){
for(int gap = arr.size() / 2; gap > 0; gap /= 2){
for(int i = gap;i < arr.size(); i++){
for(int j = i - gap;j >= 0 && arr[j] > arr[j + gap];j -= gap){
swap(arr[j],arr[j+gap]);
}
}
}
}
快速排序
快速排序是现在常用的算法，其核心是在线性时间内将一个数组以pivot(自己选择)为中点，使得比它大的都在其右边，比它小的都在其左边，然后进行递归调用，直到只剩下一个数字。
void quickSort(vector<int> &arr, int left, int right){
if(left >= right){ //递归出口
return;
}
//随机选一个数作为参考数
int len = right - left + 1;
int randPos = rand() % len + left;
swap(arr[left],arr[randPos]);
//partition操作，执行之后，左边的数小于参考数，右边的数大于参考数
int pos = left; //pos表示在pos右边的数都要大于arr[left]
for(int i=left+1;i<=right;i++){
if(arr[i] < arr[left]){
swap(arr[i],arr[++pos]);
}
}
swap(arr[left],arr[pos]);
quickSort(arr,left,pos-1);
quickSort(arr,pos+1,right);
}
void quickSort(vector<int> &arr){
quickSort(arr,0,arr.size()-1);
}
归并排序
归并排序和快速排序的复杂度都是O(nlogn) ，它的基本思想是，在线性时间内，对已经排序的数组合在一起。为了这样做，它需要额外的空间。它的代码如下：
void mergeSort(vector<int> &arr1, vector<int> &arr2, int left, int right){
if(left >= right){
return;
}
int mid = left + (right - left) / 2;
mergeSort(arr1,arr2,left,mid);
mergeSort(arr1,arr2,mid+1,right);
//到这里的时候可以认为，两个数组都排好序了，执行merge操作
int k = left;
int i = left;
int j = mid + 1;
while(i <= mid && j <= right){
if(arr1[i] <= arr1[j]){
arr2[k++] = arr1[i++];
}else{
arr2[k++] = arr1[j++];
}
}
while(i <= mid){
arr2[k++] = arr1[i++];
}
while(j <= right){
arr2[k++] = arr1[j++];
}
for(i=left;i<=right;i++){
arr1[i] = arr2[i];
}
}
void mergeSort(vector<int> &arr){
vector<int> arr2(arr.size(),0);
mergeSort(arr,arr2,0,arr.size()-1);
}
堆排序
可以利用堆的性质来进行排序。代码如下：
//堆的下沉操作
void heapSink(vector<int> &arr, int pos, int len){
int parent = pos;
int child = parent * 2 + 1;
int num = arr[pos];
while(child < len){
if(child + 1 < len && arr[child+1] > arr[child]){
child++;
}
if(num > arr[child]){
break;
}
arr[parent] = arr[child];
parent = child;
child = parent * 2 + 1;
}
arr[parent] = num;
}
void heapSort(vector<int> &arr){
for(int i=arr.size()/2;i>=0;i--){
heapSink(arr,i,arr.size()); //通过有规律的下沉操作，迅速构造堆
}
for(int i=arr.size()-1;i>0;i--){
swap(arr[0],arr[i]); //每次弹出最大的一个数
heapSink(arr,0,i); //执行下沉操作
}
}
桶排序
以上的排序都是基于比较，但如果在取值比较少的情况下，可以用桶排序实现线性时间的排序。桶排序主要思想是，先按照值将数据放在桶里，然后按照值的大小依次统计每个桶的数量，实现排序。这种排序方式只适用于值的取值范围比较小的情况。
void bucketSort(vector<int> &arr){
//假设arr[i]的取值范围为0 - 100
vector<int> bucket(101,0);
for(int num : arr){
bucket[num]++;
}
int k = 0;
for(int i=0;i<=100;i++){
for(int j=0;j<bucket[i];j++){
arr[k++] = i;
}
}
}
