今天下午一口气看了四种排序算法，加上之前已经有的三种排序算法，以及拓扑排序，目前我的博客里面已经有八种排序算法。还差两到三种算法也会在后面更出来。由于排序算法已经有很多人总结过了就不一一详细说明。不过我会附上一些优秀博主总结的链接。
一.堆排序
堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。可以利用数组的特点快速定位指定索引的元素。堆分为大根堆和小根堆，是完全二叉树。大根堆的要求是每个节点的值都不大于其父节点的值，即A[PARENT[i]] >= A[i]。在数组的非降序排序中，需要使用的就是大根堆，因为根据大根堆的要求可知，最大的值一定在堆顶。
详细博文：http://blog.csdn.net/morewindows/article/details/6709644/
效率：O（nlogn）
void Adjust(int *arr, int low, int high) {
int i = low, temp = arr[low], j = 2 * i;//j是i的左孩子
while (j <= high) {
if (arr[j] < arr[j + 1] && j < high)//若右孩子大于左孩子，j指向右孩子
++j;
if (temp >= arr[j])
break;
//双亲大于孩子时，将较大孩子的值赋予双亲后继续向下比较
arr[i] = arr[j];
i = j;
j *= 2;
}
arr[i] = temp;
}
void HeapSort(int *arr, int num) {
int i;
int temp;
for (i = num / 2; i >= 1; --i)//初始化最大堆
Adjust(arr, i, num);
for (i = num; i >= 2; --i) {//堆排序
swap(arr[i], arr[1]);
Adjust(arr, 1, i - 1);
}
}
二.希尔排序
希尔排序(Shell Sort)是插入排序的一种。也称缩小增量排序，是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因DL．Shell于1959年提出而得名。
希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。
详细博文：http://blog.csdn.net/morewindows/article/details/6668714
效率：O（nlogn）
//希尔排序
//法一
void ShellSort(int *arr, int num) {
int i, j, k, tmp, gap;
for (gap = num / 2; gap != 0; gap /= 2)
for (i = 0; i < gap; ++i)
for (j = i + gap; j < num; j += gap) {
k = j;
tmp = arr[j];
while (k >= 0 && tmp < arr[k - gap]) {
arr[k] = arr[k - gap];
k -= gap;
}
arr[k] = tmp;
}
}
//法二
void ShellSort0(int *arr, int num) {
int i, j, temp, gap;
for(gap=num/2;gap>0;gap/=2)
for (i = gap; i < num; ++i) {
j = i-gap;
while (arr[j] > arr[j + gap] && j >= 0) {
swap(arr[j], arr[j + gap]);
j -= gap;
}
}
}
//法三
void ShellSort1(int arr[], int num) {
int i, j, k, gap;
for (gap = num / 2; gap > 0; gap /= 2)
for (i = gap; i < num; ++i)
for (j = i - gap; j >= 0 && arr[j] > arr[j + gap]; j -= gap)
swap(arr[j], arr[j + gap]);
}
三.折半插入排序
折半插入排序（binary insertion sort）是对插入排序算法的一种改进，由于排序算法过程中，就是不断的依次将元素插入前面已排好序的序列中。由于前半部分为已排好序的数列，这样我们不用按顺序依次寻找插入点，可以采用折半查找的方法来加快寻找插入点的速度。
我在之前也终结过二分查找：http://blog.csdn.net/weixin_37720172/article/details/70168905
效率：折半插入排序算法是一种稳定的排序算法，比直接插入算法明显减少了关键字之间比较的次数，因此速度比直接插入排序算法快，但记录移动的次数没有变，所以折半插入排序算法的时间复杂度仍然为O(n^2)，与直接插入排序算法相同。附加空间O(1)。
void BinaryInsertSort(int *arr,int length) {
int i, j, temp,low,high,mid;
for (i = 1; i < length; ++i) {//取出arr[i]，并在之前进行二分查找并插入
temp = arr[i];
low = 0;
high = i-1;
if (low <= high) {
while (low <= high) {
mid = (low + high) / 2;
if (arr[mid] > temp)
high = mid - 1;
else
low = mid + 1;
}
for (j = i - 1; j >= high + 1; --j)
arr[j + 1] = arr[j];
arr[high + 1] = temp;
}
}
}
四.直接插入排序
插入排序的基本方法是：每步将一个待排序的记录按其关键字的大小插到前面已经排序的序列中的适当位置，直到全部记录插入完毕为止。
详细博文：http://blog.csdn.net/morewindows/article/details/6665714
效率：O（N^2）
void InsertSort(int *arr, int num) {
int i, j;
int temp;
for (int i = 1; i < num; ++i) {
temp = arr[i];
j = i - 1;
while (temp < arr[j]) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = temp;
}
}
//简化版
void InsertSort1(int *arr, int num) {
int i, j;
int temp;
for (int i = 1; i < num; ++i)
for (j = i - 1; arr[j] > arr[j + 1] && j >= 0; --j)
swap(arr[j], arr[j + 1]);
}