以前也零零碎碎发过一些排序算法，但排版都不太好，又重新整理一次，排序算法是数据结构的重要部分，系统地学习很有必要。
时间、空间复杂度比较
1 冒泡排序
算法思想：
比较相邻的元素。如果第一个比第二个大，就交换他们两个。
对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
针对所有的元素重复以上的步骤，除了最后一个。
持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
代码：
void bubbleSort(int a[], int n) { for(int i =0 ; i< n-1; ++i) { for(int j = 0; j < n-i-1; ++j) { if(a[j] > a[j+1]) { int tmp = a[j] ; //交换 a[j] = a[j+1] ; a[j+1] = tmp; } } } }
2 选择排序
算法思想：
在未排序序列中找到最小（大）元素，存放到排序序列的起始位置
从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾
以此类推，直到所有元素均排序完毕
代码：
function selectionSort(arr) { var len = arr.length; var minIndex, temp; for (var i = 0; i < len - 1; i++) { minIndex = i; for (var j = i + 1; j < len; j++) { if (arr[j] < arr[minIndex]) { // 寻找最小的数 minIndex = j; // 将最小数的索引保存 } } temp = arr[i]; arr[i] = arr[minIndex]; arr[minIndex] = temp; } return arr; }
3 插入排序
算法思想：
从第一个元素开始，该元素可以认为已经被排序
取出下一个元素，在已经排序的元素序列中从后向前扫描
如果该元素（已排序）大于新元素，将该元素移到下一位置
重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
将新元素插入到该位置后
重复步骤2~5
插入排序动图演示
代码：
void print(int a[], int n ,int i){ cout<<i <<":"; for(int j= 0; j<8; j++){ cout<<a[j] <<" "; } cout<<endl; } void InsertSort(int a[], int n) { for(int i= 1; i<n; i++){ if(a[i] < a[i-1]){ //若第i个元素大于i-1元素，直接插入。小于的话，移动有序表后插入 int j= i-1; int x = a[i]; //复制为哨兵，即存储待排序元素 a[i] = a[i-1]; //先后移一个元素 while(x < a[j]){ //查找在有序表的插入位置 a[j+1] = a[j]; j--; //元素后移 } a[j+1] = x; //插入到正确位置 } print(a,n,i); //打印每趟排序的结果 } } int main(){ int a[15] = {2，3,4,5,15，19，16，27，36，38，44，46，47，48，50}; InsertSort(a,15); print(a,15,15); }
4 快速排序
算法思想：
选取第一个数为基准
将比基准小的数交换到前面，比基准大的数交换到后面
对左右区间重复第二步，直到各区间只有一个数
代码：
void QuickSort(vector<int>& v, int low, int high) { if (low >= high) // 结束标志 return; int first = low; // 低位下标 int last = high; // 高位下标 int key = v[first]; // 设第一个为基准 while (first < last) { // 将比第一个小的移到前面 while (first < last && v[last] >= key) last--; if (first < last) v[first++] = v[last]; // 将比第一个大的移到后面 while (first < last && v[first] <= key) first++; if (first < last) v[last--] = v[first]; } // v[first] = key; // 前半递归 QuickSort(v, low, first - 1); // 后半递归 QuickSort(v, first + 1, high); }
5 堆排序
堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。
算法思想：
将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆，此堆为初始的无序区；
将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]<=R[n]；
由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。
代码：
#include <iostream> #include <algorithm> using namespace std; // 堆排序：（最大堆，有序区）。从堆顶把根卸出来放在有序区之前，再恢复堆。 void max_heapify(int arr[], int start, int end) { //建立父节点指标和子节点指标 int dad = start; int son = dad * 2 + 1; while (son <= end) { //若子节点在范围内才做比较 if (son + 1 <= end && arr[son] < arr[son + 1]) //先比较两个子节点指标，选择最大的 son++; if (arr[dad] > arr[son]) //如果父节点大于子节点代表调整完成，直接跳出函数 return; else { //否则交换父子內容再继续子节点与孙节点比較 swap(arr[dad], arr[son]); dad = son; son = dad * 2 + 1; } } } void heap_sort(int arr[], int len) { //初始化，i从最后一个父节点开始调整 for (int i = len / 2 - 1; i >= 0; i--) max_heapify(arr, i, len - 1); //先将第一个元素和已经排好的元素前一位做交换，再从新调整(刚调整的元素之前的元素)，直到排序完成 for (int i = len - 1; i > 0; i--) { swap(arr[0], arr[i]); max_heapify(arr, 0, i - 1); } } int main() { int arr[] = { 3, 5, 3, 0, 8, 6, 1, 5, 8, 6, 2, 4, 9, 4, 7, 0, 1, 8, 9, 7, 3, 1, 2, 5, 9, 7, 4, 0, 2, 6 }; int len = (int) sizeof(arr) / sizeof(*arr); heap_sort(arr, len); for (int i = 0; i < len; i++) cout << arr[i] << ' '; cout << endl; return 0; }
6 归并排序
归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。
算法思想： 1.把长度为n的输入序列分成两个长度为n/2的子序列； 2. 对这两个子序列分别采用归并排序； 3. 将两个排序好的子序列合并成一个最终的排序序列。
代码：
void print(int a[], int n){ for(int j= 0; j<n; j++){ cout<<a[j] <<" "; } cout<<endl; } //将r[i…m]和r[m +1 …n]归并到辅助数组rf[i…n] void Merge(ElemType *r,ElemType *rf, int i, int m, int n) { int j,k; for(j=m+1,k=i; i<=m && j <=n ; ++k){ if(r[j] < r[i]) rf[k] = r[j++]; else rf[k] = r[i++]; } while(i <= m) rf[k++] = r[i++]; while(j <= n) rf[k++] = r[j++]; print(rf,n+1); } void MergeSort(ElemType *r, ElemType *rf, int lenght) { int len = 1; ElemType *q = r ; ElemType *tmp ; while(len < lenght) { int s = len; len = 2 * s ; int i = 0; while(i+ len <lenght){ Merge(q, rf, i, i+ s-1, i+ len-1 ); //对等长的两个子表合并 i = i+ len; } if(i + s < lenght){ Merge(q, rf, i, i+ s -1, lenght -1); //对不等长的两个子表合并 } tmp = q; q = rf; rf = tmp; //交换q,rf，以保证下一趟归并时，仍从q 归并到rf } } int main(){ int a[10] = {2，3,4，5,15,19,26,27,36,38,44,46,47,48,50}; int b[10]; MergeSort(a, b, 15); print(b,15); cout<<"结果："; print(a,10); }
