排序
排序：将一组杂乱无章的数据排列成一个按关键字有序的序列。
数据表(datalist)：待排序数据对象的有限集合。
关键字(key)：通常数据对象有多个属性域，即多个数据成员组成，其中有一个属性域可用来区分对象，作为排序依据。该域即为关键字。
稳定性：序列中两个元素i、j，若关键字i<=j，并且在排序过程中两个关键字的相对次序始终没有变化（即i始终在j的前面），则这个排序算法是稳定的。
内排序与外排序：内排序是指在排序期间数据对象全部存放在内存的排序；外排序是指在排序期间全部对象个数太多，不能同时存放在内存，必须根据排序过程的要求，不断在内、外存之间移动的排序。
排序时间开销：数据比较次数、数据移动次数，一般按平均情况估算，若排序算法受初始序列、对象个数影响较大，可按最好情况、最坏情况进行估算。
衡量排序方法的标准：平均比较次数、平均移动、平均辅助存储空间、稳定性
一、插入排序
1、算法思路
每步将一个待排序的对象，按关键字大小插入到前面已经排序完成序列的适当位置上。当插入第i个对象时，前面的v[0], v[1], …, v[i-1]已经排好序。
这时，用v[i]的关键字与v[i-1], v[i-2], …的关键字顺序进行比较，找到插入位置即将v[i]插入，原来位置上之后的所有对象依次向后顺移。
2、代码实现
void InsertSort(SqList &L){
for(int i=2 ; i<=L.length ; i++){
if(L.r[i].key < L.r[i-1].key){
L.r[0] = L.r[i]; // 监视哨
int j=i-1;
for(; L.r[0].key < L.r[j].key && j>0; j—){
L.r[j+1] = L.r[j];
}//依次向后移位
L.r[j+1]=L.r[0];
}
}
}
3、算法分析
辅助空间：1（监视哨）
设有n个元素，则算法进行n-1趟排序。最好情况下，排序前序列已经有序，则每一趟只需要与需与前面的有序对象序列的最后一个对象的关键字比较 1 次，移动 2 次对象，总的关键字比较次数为 n-1，对象移动次数为 2(n-1)。
最坏情况下，序列恰为逆序，每次需要比较i-1次，总的比较次数为$\frac{n(n-1)}{2}$，移动次数为$\frac{n(n-1)}{2}+n-1$。
平均情况下比较次数、移动次数约为$\frac{n^2}{4}$，时间复杂度为$O(n^2)$。
稳定，数据规模较小。
二、希尔排序
1、算法思路
先将整个序列按照一定间隔分割成若干子序列，在子序列中分别进行直接插入排序。然后缩小间隔，重复以上划分子序列、分别排序堆过程直至间隔为1。最后进行一次直接插入排序。
开始时gap（间隔值）的值较大，子序列中的对象较少，排序速度较快；随着排序进展，gap 值逐渐变小，子序列中对象个数逐渐变多，由于前面工作的基础，大多数对象已基本有序，所以排序速度仍然很快。
2、代码实现
void ShellSort(int *num, int dlta[] , int t){
//dlta[]={5,3,2,1};
for(int k = 0 ; k < t ; k++){
ShellSort(num,dlta[k]);
}
}
void ShellSort(int* num,int k){
int temp;
for(int i=k+1; i<n ;i++){
if(num[i] < num[i-k]){
temp = num[i];//监视哨
int j = i-k;
for(; j>=0 && temp < num[j];j-=k ){//条件为>=0且需要移动
num[j+k] = num[j];
}
num[j+k]=temp;
}
}
}
3、算法分析
辅助空间：1（监视哨）
当 n 很大时，关键字平均比较次数和对象平均移动次数大约在$n^{1.25}$到$1.6n^{1.25}$ 的范围内。
不稳定排序。
三、冒泡排序（比较排序）
1、算法思路
设待排序对象序列中的对象个数为 n，最多作 n-1 趟排序。
比较相邻的元素。如果第一个比第二个大，就交换他们两个。
对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。每一次排序后，最后的元素应该会是最大的数。
针对所有的元素重复以上的步骤，除了最后一个。
持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
2、代码实现
void BubbleSort(int* num){
int temp;
bool change=1;
for(int i=0; i<n-1 && change;i++){
change=0;
for(int j=1;j<n-i;j++){
if(num[j]<num[j-1]){
swap(num[j],num[j-1]);
change=1;
}
}
}
}
3、算法分析
注意引入了变量change，当已经排序完成时自动结束排序。
辅助空间：1（temp）
每次确定一个元素的位置；
可以实现部分排序；
稳定排序。
a、当对象的初始排列已经按关键字从小到大排好序时，此算法只执行一趟冒泡，做n-1次关键字比较，不移动对象。这是最好的情形。
b、最坏的情形是算法执行了n-1趟冒泡，第 i 趟做了n- i 次关键字比较，执行了n-i 次对象交换。这样在最坏情形下总的关键字比较次数KCN和对象移动次数RMN为：
$KCN = \sum^{n-1}_{i=1}(n-i)=\frac{n(n-1)}{2}$
$RMN = 3\sum^{n-1}_{i=1}(n-i)=\frac{3n(n-1)}{2}$
四、快速排序（比较排序）
1、算法思路
通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
排序流程如下：
(1)首先设定一个分界值，通过该分界值将数组分成左右两部分。
(2)将大于或等于分界值的数据集中到数组右边，小于分界值的数据集中到数组的左边。此时，左边部分中各元素都小于或等于分界值，而右边部分中各元素都大于或等于分界值。
(3)然后，左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理。
(4)重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后，整个数组的排序也就完成了。
在具体的排序实现过程中，调整思路为让基准数来回跳动。
2、代码实现
void QuickSort(int R[],int low,int high)
{
int i,j,temp;
i=low;
j=high;
if(low<high)
{
temp=R[low];//设置枢轴
while(i!=j)
{
while(i<j && R[j]>=temp)//枢轴为左边的值时，从右边开始寻找
{
--j;
}
if(i<j)//找到小于枢轴量的值，交换
{
R[i]=R[j];
++i;
}
while(i<j && R[i]<temp)//从左边开始寻找
{
++i;
}
if(i<j)//找到大于枢轴量的值，交换
{
R[j]=R[i];
--j;
}
}
R[i]=temp;//结束是i、j为枢轴量的位置
QuickSort(R,low,i-1);
QuickSort(R,i+1,high);
}
}
3、算法分析
快速排序是不稳定的。
辅助空间：$\log{n}$。（递归函数）最坏是$n^2$
快速排序的一次划分算法从两头交替搜索，直到low和high重合，因此其时间复杂度是O(n)；而整个快速排序算法的时间复杂度与划分的趟数有关。
理想的情况是，每次划分所选择的中间数恰好将当前序列几乎等分，经过log2n趟划分，便可得到长度为1的子表。这样，整个算法的时间复杂度为$O(nlog_2n)$。
最坏的情况是，每次所选的基准数是当前序列中的最大或最小元素，这使得每次划分所得的子表中一个为空表，另一子表的长度为原表的长度-1。这样，长度为n的数据表的快速排序需要经过n趟划分，使得整个排序算法的时间复杂度为$O(n^2)$。
改进思路：若能更合理地选择基准数，使得每次划分所得的两个子序列中的对象个数尽可能地接近，可以加速排序速度。
改进办法：取每个待排序对象序列的第一个对象、最后一个对象和位置接近正中的3个对象，取其关键字大小居中者作为基准数。
五、选择排序
1、代码实现
void SelectSort(SqList &L){
int len = arr.length;
int minIndex, temp;
for (int i = 0; i < len - 1; i++) {
minIndex = i;
for (int j = i + 1; j < len; j++) {
if (arr[j] < arr[minIndex]) { // 寻找最小的数
minIndex = j; // 将最小数的索引保存
}
}
swap(arr[i],arr[minIndex]);
}
return arr;
}
2、算法分析
不稳定。
总的关键字比较次数KCN和对象移动次数RMN为：
$KCN = \sum^{n-2}_{i=0}(n-i-1)=\frac{n(n-1)}{2}$
最好情况：$RMN = 0$
最坏情况：$RMN = 3(n-1)$
时间复杂度为$O(n^2)$。
六、堆排序
1、算法思路
堆顶的元素为序列的最大/最小值。
利用堆的概念，可以很容易地实现选择排序的思路。堆排序分为两个步骤：第一步，根据初始输入数据，利用堆的调整算法形成初始堆，输出堆顶元素。第二步，重新调整剩余元素使之成为堆。重复以上操作。
构建堆参照查找中的优先队列。
不稳定排序。
辅助空间：1（temp）
$O(n\log{n})$（递归）
七、归并排序
1、算法思路
归并，是将两个或两个以上的有序表合并成一个新的有序表。
外排序只能用归并排序。
基本思想：（每次都进行两两归并）
假设初始对象序列有 n 个对象，首先把它看成是 n 个长度为 1 的有序子序列 (归并项)，先做两两归并，得到n / 2（向上取整）个长度为 2 的归并项 (如果 n 为奇数，则最后一个有序子序列的长度为1)；再做两两归并，…，如此重复，最后得到一个长度为 n 的有序序列。
2、代码实现
void Merge(int r[],int r1[],int s,int m,int t)
{
int i=s;
int j=m+1;
int k=s;
while(i<=m && j<=t)
{
if(r[i]<=r[j])
r1[k++]=r[i++];
else
r1[k++]=r[j++];
}
while(i<=m)
r1[k++]=r[i++];
while(j<=t)
r1[k++]=r[j++];
for(int l=0; l<8; l++)
r[l]=r1[l];
}
void MergeSort(int r[],int r1[],int s,int t)
{
if(s==t)
return;
else
{
int m=(s+t)/2;
MergeSort(r,r1,s,m);//子序列排序
MergeSort(r,r1,m+1,t);//子序列排序
Merge(r,r1,s,m,t);//该序列排序
}
}
3、算法分析
稳定排序。
辅助空间：n，一个与原待排序对象数组同样大小的辅助数组。
归并排序算法中，递归深度为O(logn)，对象关键字的比较次数为O(nlogn)。算法总的时间复杂度为O(nlogn)。
八、基数排序
1、算法思路
基数排序是采用“分配”与“收集”的办法，用对多关键字进行排序的思想实现对单关键字进行排序的方法。
多关键字排序：
假定一个n个对象的序列：{$v_0,v_1….v_{n-1}$}，每个对象都含有d个关键字：$(k_i^1,k_i^2….k_i^d)$，如果对序列内任意一对元素$v_i,v_j(i<j)$，都满足：
$(k_i^1,k_i^2….k_i^d)<(k_j^1,k_j^2….k_j^d)$
则该序列对关键字：$(k^1,k^2….k^d)$有序，序列第一位关键字$k^1$为最高位关键字，最后一位关键字$k^d$为最低位关键字。
多关键字排序方法：
- 最高位优先MSD (Most Significant Digit first)
- 最低位优先LSD (Least Significant Digit first)
基数排序为最低位优先LSD排序算法，先根据最低位关键字进行分配和收集，再依次对高一位的关键字进行分配和收集。（例如先从个位，再到十位、百位）
2、算法分析
若有d个关键字，则需要d趟分配与搜集；每趟对n个元素进行分配，分配结果分为radix个队列；对radix个队列进行收集。
稳定排序。
时间复杂度$O(d(n+radix))$
辅助空间：radix
链式基数排序：各队列采用链式队列结构，分配到同一队列的关键字用链接指针链接起来。每一队列设置两 个队列指针：int front [radix]指示队头， int rear [radix] 指向队尾。附加n+2radix个链接指针
排序小结
| 排序 | 比较次数(最好/最坏) | 移动次数(最好/最坏) | 空间复杂度(最好/最坏） | 稳定性 |
|---|---|---|---|---|
| 插入排序 | n/$n^2$ | 2(n-1)/$n^2$ | 1 | ✔ |
| 希尔排序 | $n^{1.25}$到$1.6n^{1.25}$ | $n^{1.25}$到$1.6n^{1.25}$ | 1 | × |
| 冒泡排序 | n/$n^2$ | 0/$n^2$ | 1 | ✔ |
| 快速排序 | nlogn/$n^2$ | nlogn/$n^2$ | logn/$n^2$ | × |
| 选择排序 | $n^2$ | 0/n | 1 | × |
| 堆排序 | nlogn | nlogn | 1 | × |
| 归并排序 | nlogn | nlogn | n | ✔ |
| 基数排序 | d(n+radix) | d(n+radix) | radix | ✔ |
