算法复习笔记 | 排序算法比较
最近正好复习复习算法，于是从排序算法开始做一个总结。以下的代码均为原创，如果有任何问题，欢迎指正。简单来讲，排序算法的实质是将长度为n的数组中的数字按照从小到大或者从大到小的顺利排列。
简而言之，在不考虑算法的情况下，我们可以把排序抽象为如下的一个函数：array表示T类型的一个数组，num表示数组的长度。本文假设我们实现的排序算法都是按照从小到大的顺序排列；从大到小的排列类似。
template <class T>
void Order(T array[], int num)
1）选择算法：基本思想是每次从数组中选择最小的数，将这个数与已排序的数组最后一位交换。寻找第一个数时，我们需要遍历num个数才能判断出最小的数；寻找第i个数时，由于我们已经成功的将前i-1个数按序排列，我们只需要遍历num-i+1个数便能找到最小的数。
总而言之，时间复杂度为O(n2)，而空间复杂度为O(1)。
template <class T>2）简单插入算法：基本思想如同整理扑克牌，一开始手中有1张牌，每抽一张牌便将新抽的牌插入到手中有序的牌列种。
总而言之，时间复杂度为O(n2)，而空间复杂度为O(1)。
template <class T>3）折半插入算法：基本思想和简单插入算法相同，但是新牌与手牌比较的时候不必一一比较（因为手牌已经有序排列了），我们可以用二分查找的方法来将新牌左移
总而言之，时间复杂度有所提高，为O(nlogn)，而空间复杂度为O(1)。
template <class T>4）希尔排序：基本思想和简单插入算法类似。简单插入算法每一次从距离为一的位置处抽取新值。如果数据分布比较分散，简单插入算法效率较低。于是，我们可以采用距离（称之为步长）大于一的方式来抽取新值。例如，当步长为n时，数组中相当于有n个平行的子数组在做简单插入算法。运算之后，数组变得更加为有序，于是我们可以不断地缩小步长直到步长为1（简单插入算法），最终完成排序。当数组越有序时，简单插入算法的效率越高。
总而言之，时间复杂度不容易计算，但实验统计结果大约为n1.25到1.6n1.25，而空间复杂度为O(1)。希尔是一种不稳定的算法。
template <class T>5）归并排序：初始时，我们假设我们得到了num个长度为1的子数组；每一次运算时将两个有序的子数组合并成一个父数组。
总而言之，时间复杂度为O(n2)，而空间复杂度为O(n)。
template <class T>
T minValue(T a, T b)
{
return a<b?a:b;
}
//两个值中取较小值
template <class T>
void merge(T from[], T to[], int low, int high, int length)//从数组from中合并从low到high之间的子数组并保存到数组to中：第一个数组长度为length，第二个数组长度可能为length或小于length
{
int first = low;//第一个子数组的开始位置
int second = low + length;//第二个子数组的开始位置
int cur = low;//目标存储数组中的开始位置
while(first < low + length && second <= high)
{
to[cur++] = minValue<T>(from[first],from[second]);
from[first]<from[second]?first++:second++;
};//依次选择两个子数组中较小值添加到目标存储数组中
while(first < low + length)
{
to[cur++] = from[first++];
};//若第一个子数组还有未添加的值，添加到目标存储数组的尾部
while(second <= high)
{
to[cur++] = from[second++];
};//若第二个子数组还有未添加的值，添加到目标存储数组的尾部
}
//归并排序
template <class T>
void mergeSort(T array[], int num)
{
if(num <= 0)
return;
int len = 1;//子数组长度
int cur = 0;//初始化指针
T* tempArray = new T[num];//临时存储数组
while(len<num)//子数组长度小于num时循环，大于num时排序结束
{
while(cur<num)
{
int m = minValue<int>(cur + len * 2, num);
//两个子数组的总长度，考虑越界
for(int i = cur; i < m; i++)
{
tempArray[i] = array[i];
}
//将数值临时存储在临时存储数组中
merge(tempArray, array, cur, m - 1, len);
//合并相邻子数组
cur += len * 2;
//指针指向下一组子数组
};
//依次选择相邻的子数组合并
len *= 2;
cur = 0;
//长度翻倍且重置指针
};
delete tempArray;
}
6）冒泡排序：通过依次交换两个相邻的两个数，遍历num个数后便将最大的数推送到了最后。推送第一个数时，我们需要遍历num个数才能推出最大值；推送第i个数时，由于我们已经成功的将i-1个数按序推出，我们只需要遍历num-i+1个数便能推出当前最大的数。
总而言之，时间复杂度为O(n2)，而空间复杂度为O(1)。
template <class T>7）快速排序：对冒泡排序法的优化，基本思想也是将两个数交换，但是我们希望尽量将较小的数交换到数组左边，将交大的数交换到数组右边。计算时我们从数组中随机选择一个数作为参考数，定义一个指针从左向右遍历，另一个指针从右向左遍历。第一个指针寻找大于参考数的数，第二个指针寻找小于参考数的数，并将两个数交换。当两个指针相遇时一次循环结束，循环结束时相遇位置的左侧的数均小于参考数，右侧的数均大于参考数。我们可以递归地对左侧和右侧的数组运用快速排序算法。
总而言之，时间复杂度为O(nlogn)，而空间复杂度为O(1)。
template <class T>
void quick(T array[], int low, int high)
{
if(high - low > 10)
{
simpleInsertSort(array + low, high - low + 1);
return;
}
//长度小于10时采用简单插入算法
T key = array[low];//利用第一个数作为参考数
int i = low;
int j = high;
while(true)
{
for(;array[i] > key && i <= j;i++);//从左向右选择大于参考数的数
for(;array[j] <= key && j >= i;j--);//从右向左选择小于等于参考数的数
if(i == j)
{
break;
}
//两个指针相遇时这次循环结束
T temp = array[i];
array[i] = array[j];
array[j] = temp;
//交换两个指针的数
};
if(i == j)
{
if(array[i] > key)
{
quick<T>(array, low, i-1);
quick<T>(array, i, high);
}
else
{
quick<T>(array, low, i);
quick<T>(array, i + 1, high);
}
}
//针对左侧右侧循环采用快速循环
}
//快速排序
template <class T>
void quickSort(T array[], int num)
{
int low = 0;
int high = num - 1;
quick<T>(array, low, high);
}
8）堆排序：堆就是一颗树，分为最小化堆与最大化堆，最小化堆的特点是父节点大于等于子节点。堆的存储可以利用数字完成，位置为0的节点表示更节点。对于父节点n，左右子节点为n*2+1与n*2+2。
对于一个父节点两个子节点的子堆，我们可以分成方便的转化使父节点大于等于子节点。整个堆的整理便是循环递归计算。
总而言之，建堆时间复杂度为O(n)，删除、插入等操作时间复杂度为)(logn)。而空间复杂度为O(n)。
template <class T>