0、一个非常舒服的视频（来源见水印）
1、冒泡排序
void Bubble_Sort(ElementType A[], int N){
for(int P = N-1; P >= 0; P--){
//每轮排序后，末尾的数字一定是最大的，所以下一轮排序无需遍历到末尾
for(int i = 0; i < P; i++){
//一轮排序中遍历所有的数字
if(A[i] > A[i+1]) //如果顺序是错误的
swap(A[i], A[i + 1])
//交换
}
}
}2、冒泡排序（改进版）
void Bubble_Sort(ElementType A[], int N){
for(int P = N-1; P >= 0; P--){
bool flag = false; //标记
//每轮排序后，末尾的数字一定是最大的，所以下一轮排序无需遍历到末尾
for(int i = 0; i < P; i++){
//一轮排序中遍历所有的数字
if(A[i] > A[i+1]){ //如果顺序是错误的
swap(A[i], A[i + 1])
//交换
flag = true //这一轮中执行了交换操作
}
}
if(flag == false) break;
//如果本轮操作没有执行交换位置的操作，说明已经是顺序了，跳出循环即可
}
}3、选择排序
void Selection_Sort(){
for(int i = 0; i < N; i++){
int MinPosition, min = inf;
//inf是一个很大的数字
for(int j = i; j < N; j++)
if(A[j] < min) min = A[j], MinPosition = j;
//上面这个循环的目的是找到i以后的最小元
swap(A[i], A[MinPosition]); //交换位置
}
}4、堆排序
//非递归写法
void DownAdjust(int low, int high){
int i = low, j = i * 2; //i存放要调整的节点，j存放其左孩子
while(j <= high){ //j没越界，说明存在孩子节点
if(j+1 <= high){ //防止不存在右孩子而导致越界
if(heap[j + 1] > heap[j]) //右孩子更大
j = j + 1; //让j存放右孩子的下标
}
//如果孩子中最大的值比欲调整节点i大
if(heap[j] > heap[i]){
swap(heap[j], heap[i]);//交换最大的孩子与要调整的节点i
i = j; //保持i为要调整的节点
j = i * 2; //j为i的左孩子
}else
break; //孩子都比要调整的i小，调整结束
}
}
//递归写法
void DownAdjust(int low, int high){
int i = low, j = i * 2; //i是要调整的节点，j是左孩子
if(j > high) return; //如果没有左孩子（越界），直接返回
int max_index = heap[i] > heap[j] ? i : j; //在左孩子与要调整的节点中找到最大的下标
//如果存在右孩子，在刚刚找到的最大的下标和右孩子中找最大的
if(j + 1 < high) max_index = heap[max_index] > heap[j + 1] ? max_index : (j + 1);
if(max_index == i) return; //如果要调整的节点已经是最大的了，直接返回
swap(heap[i], heap[max_index]); //执行交换
DownAdjust(max_index, high); //递归调整
}
//建堆
void CreateHeap(){
for(int i = n / 2; i >= 1; i--)
DownAdjust(i, n);
}
//排序函数
void HeapSort(){
CreateHeap();
for(int i = n; i > 1; i--){
swap(heap[i], heap[1]);
DownAdjust(1, i - 1);
}
}5、插入排序
void Insertion_Sort(int a[], int n){
for(int i = 1; i < n; i++){
//越过0，从1开始遍历
for(int j = i; j >= 1; j--){
//从i往前遍历
if(a[j] < a[j-1]) //如果比前一个小
swap(a[j], a[j-1]); //则与前一个交换顺序
else break; //否则跳过这一轮（因为从1开始遍历，保证i前面是有序的）
}
}
}6、归并排序
void Merge(int frist, int mid, int last){ //合并数组到ans数组中
int tmp[N]; //临时数组
int p1 = frist, p2 = mid + 1; //两组数的位置
int p1_max = mid, p2_max = last; //最大位置（位置与最大位置比较，防止越界）
int k = 0; //临时数组位置
while(p1 <= p1_max && p2 <= p2_max){ //在范围内
if(arr[p1] < arr[p2]) //当前左边的数比右边的小
tmp[k++] = arr[p1++]; //将p1位置的数字拷贝过去，并移动一位
else tmp[k++] = arr[p2++] ;
}
//完成后，将剩下的数据直接拷贝到ans中
while(p1 <= p1_max)
tmp[k++] = arr[p1++];
while(p2 <= p2_max)
tmp[k++] = arr[p2++];
//将临时数组中的结果拷贝回去，注意下面的i是偏移量，必须加上frist
for(int i = 0; i < k; i++)
arr[frist + i] = tmp[i];
}
void MergeSort(int frist, int last){
if(frist >= last) return; //frist >= last的时候到达递归终点
int mid = (frist + last) / 2; //计算中间下标
MergeSort(frist, mid); //通过递归，将中心以左的序列 [frist, mid] 进行归并排序
MergeSort(mid + 1, last); //通过递归，将中心以右的序列 [mid + 1, last] 进行归并排序
Merge(frist, mid, last); //合并两组有序数组
}7、快速排序
void QuickSort(int arr[], int left, int right){
if(left >= right) return; //排序终点
int basic = arr[left]; //基数
int i = left, j = right; //左右哨兵
while(i < j){ //如果i>j说明已经全部遍历过了
while(arr[j] >= basic && i < j) j--; //只要大于基数，就--，直到到从右往左第一个小于基数的位置
while(arr[i] <= basic && i < j) i++; //只要小于基数，就++，直到到从左往右第一个大于基数的位置
if(i < j) //如果i>j说明已经全部遍历过了
swap(arr[i], arr[j]);
}
arr[left] = arr[i]; //将中间的数字与基数交换
arr[i] = basic; //将基数归位
QuickSort(arr, left, i - 1); //左边的递归排序
QuickSort(arr, i + 1, right);//右边的递归排序
}写到这，让我们来做一次算法比较吧！
测试代码（省略了排序函数部分）：
#define N 25000
int ori[N], arr[N]; //ori存放原始随机数据，arr存放排序数据，防止排序后污染原始数据
void init(){ //初始化
srand(time(0));
for(int i = 0; i < N; i++)
ori[i] = rand() % 1000 + 1;
}
void copy(){ //拷贝原始数据到排序数组
for(int i = 0; i < N; i++)
arr[i] = ori[i];
}
int main(){
clock_t start, end;
init();
//归并排序
copy();
start = clock();
MergeSort(0, N - 1);
end = clock();
printf("归并排序%d个随机数据用时%d毫秒\n", N, end - start);
//冒泡排序
copy();
start = clock();
BubbleSort();
end = clock();
printf("冒泡排序%d个随机数据用时%d毫秒\n", N, end - start);
//改进冒泡排序
copy();
start = clock();
BubbleSort2();
end = clock();
printf("改进版冒泡排序%d个随机数据用时%d毫秒\n", N, end - start);
//选择排序
copy();
start = clock();
SelectionSort();
end = clock();
printf("选择排序%d个随机数据用时%d毫秒\n", N, end - start);
//插入排序
copy();
start = clock();
InsertionSort();
end = clock();
printf("插入排序%d个随机数据用时%d毫秒\n", N, end - start);
//堆排序
copy();
start = clock();
HeapSort();
end = clock();
printf("堆排序%d个随机数据用时%d毫秒\n", N, end - start);
//std:sort
copy();
start = clock();
sort(arr, arr + N);
end = clock();
printf("std:sort排序%d个随机数据用时%d毫秒\n", N, end - start);
//std:stable_sort
copy();
start = clock();
stable_sort(arr, arr + N);
end = clock();
printf("std:stable_sort排序%d个随机数据用时%d毫秒\n", N, end - start);
//Print();
return 0;
}运行结果：
嗯？好像有几个排序的速度区分不出来，让我们来加一个数量级，重复实验
这次的实验结果就很清晰了。
排序算法只是用来学习排序的各种思想，在算法竞赛或者OJ考试中，最好不要重复造轮子，使用sort或者stable_sort进行排序。