算法复习笔记 | 排序算法比较
最近正好复习复习算法，于是从排序算法开始做一个总结。以下的代码均为原创，如果有任何问题，欢迎指正。简单来讲，排序算法的实质是将长度为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>
void selectSort(T array[], int num)
{
T curItem;//哨兵元素，用于记录遍历时的较小值，将所以为排序数遍历后就是最小值
int cur;//记录较小值或最小值的位置
for(int i = 0; i < num; i++)//i代表当前有多少个元素已经成功排序
{
curItem = array[i];
cur = i;
//寻找未排序数的第一个数
for(int j = i + 1; j < num; j++)
{
if(curItem >= array[j])
{
curItem = array[j];
cur = j;
}
}
//从未排序数种找出最小值
if(cur != i)
{
T temp = array[cur];
array[cur] = array[i];
array[i] = temp;
}
//如果最小值不是未排序数种的第一个，则交换最小值与未排序数的第一个。
}
}
2）简单插入算法：基本思想如同整理扑克牌，一开始手中有1张牌，每抽一张牌便将新抽的牌插入到手中有序的牌列种。
总而言之，时间复杂度为O(n2)，而空间复杂度为O(1)。
template <class T>
void simpleInsertSort(T array[], int num)
{
for(int i = 1; i < num; i++)//初始时有一张牌，每抽取一张是一次循环
{
int cur = i;//当前新抽取的牌
for(int j = i - 1; j >= 0; j--)
{
if(array[j] > array[cur])
{
T temp = array[j];
array[j] = array[cur];
array[cur] = temp;
cur = j;
}
else
{
break;
}
}
//手中的牌是有序的，于是每抽一张就一次往前比较。新牌比前面的牌小便往前移动直到手牌整理完成
}
}
3）折半插入算法：基本思想和简单插入算法相同，但是新牌与手牌比较的时候不必一一比较（因为手牌已经有序排列了），我们可以用二分查找的方法来将新牌左移
总而言之，时间复杂度有所提高，为O(nlogn)，而空间复杂度为O(1)。
template <class T>
void binaryInsertSort(T array[], int num)
{
for(int i = 1; i < num; i++)//初始时有一张牌，每抽取一张是一次循环
{
int low = 0;
int high = i - 1;
//用两个位置坐标来表示手牌
while(low <= high)
{
int middle = low + (high - low) / 2;
if(array[middle] <= array[i])
{
low = middle + 1;
}
else
{
high = middle - 1;
}
};
//利用二分法找到插入的位置
if(low != i)
{
T temp = array[i];
for(int j = i; j > low; j--)
{
array[j] = array[j-1];
}
array[low] = temp;
}
//如果插入的位置与新牌的位置不同，则将新牌插入
}
}
4）希尔排序：基本思想和简单插入算法类似。简单插入算法每一次从距离为一的位置处抽取新值。如果数据分布比较分散，简单插入算法效率较低。于是，我们可以采用距离（称之为步长）大于一的方式来抽取新值。例如，当步长为n时，数组中相当于有n个平行的子数组在做简单插入算法。运算之后，数组变得更加为有序，于是我们可以不断地缩小步长直到步长为1（简单插入算法），最终完成排序。当数组越有序时，简单插入算法的效率越高。
总而言之，时间复杂度不容易计算，但实验统计结果大约为n1.25到1.6n1.25，而空间复杂度为O(1)。希尔是一种不稳定的算法。
template <class T>
void shellSort(T array[], int num)
{
int multipe = 3;//循环次数
int step = 1;
for(; step < num; step = step * multipe + 1);
step = (step - 1) / 3;
//计算出该数组支持的最长步长
while(step >= 1)
{
for(int i = 0; i < step; i++)//给定步长时平行计算的子数组数目
{
for(int j = i + step; j < num; j += step)
{
int cur = j;
for(int k = j - step; k >= i; k--)
{
if(array[k] > array[cur])
{
T temp = array[cur];
array[cur] = array[k];
array[k] = temp;
cur = k;
}
}
}
//步长为step的简单插入算法
}
step = (step - 1) / 3;//缩短步长
}
}
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);
//合并相邻子数组
c
补充：综合编程 , 其他综合 ,
