数据结构与算法：19 排序
19 排序
知识结构：
1. 排序的基本概念与术语
假设含有个记录的序列为，其相应的关键字分别为，需确定 的一种排列，使其相应的关键字满足的关系，即使得序列成为一个按关键字有序的序列 ，这个样的操作就称为 排列。
能唯一标识某一记录的关键字称为 主关键字。
假设，且在排序前的序列中领先于（即$i<j$ ）。如果排序后$r_i$仍领先于$r_j$，则称所用的排序方法是领先于，则称所用的排序方法是不稳定的。
例如：
待排序序列： 稳定的排序结果： 不稳定的排序结果：
内部排序：排序过程都在内存中进行的排序。
外部排序：排序过程需要在内存和外存之间不断交换数据的排序。
根据排序过程中借助的主要操作，我们把内排序分为：插入排序、选择排序、交换排序和并归排序。可以说，这些都是比较成熟的排序技术，已经被广泛地应用于许许多多的程序语言或数据库当中，甚至它们都已经封装了关于排序算法的实现代码。因此，我们学习这些排序算法的目的不是为了去现实排序算法，而是通过学习来提高我们编写算法的能力，以便于去解决更多复杂和灵活的应用性问题。
2. 插入排序
2.1 直接插入排序
将一个记录插入到已经排好序的有序表中，从而得到一个新的记录增1的有序表。
即：先将序列的第1个记录看成是一个有序的子序列，然后从第2个记录逐个进行插入，直至整个序列有序为止。
如：int[] Key = new int[]{45,34,78,12,34,32,29,64};
排序过程：
程序代码：
/// <summary>
/// 直接插入排序
/// </summary>
/// <typeparam name="T">需要排序记录的类型</typeparam>
/// <param name="array">需要排序的记录集合</param>
public static void StraightInsertSort<T>(T[] array) where T : IComparable<T>
{
for (int i = 1; i < array.Length; i++)
{
int j = i - 1;
T current = array[i];
while (j >= 0 && array[j].CompareTo(current) > 0)
{
array[j + 1] = array[j];
j--;
}
array[j + 1] = current;
}
}
如果碰见一个和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面，所以，相等元素的前后顺序没有改变，从原无序序列出去的顺序就是排好序后的顺序，所以直接插入排序是稳定的。
2.2 希尔插入排序
希尔排序是1959年由D.L.Shell提出来的，相对直接插入排序有较大的改进。希尔插入排序又叫做缩小增量排序。
直接插入排序的效率在某些时候是很高的，比如我们的记录本身就是基本有序的，我们只需要少量的插入操作，就可以完成整个记录集的排序工作，此时直接插入排序很高效。还有就是记录数比较少时，直接插入的优势也比较明显。可问题在于，两个条件本身就过于苛刻，现实中记录少或者基本有序都属于特殊情况。
不过别着急，有条件当然是好，条件不存在，我们创造条件也是可以去做的。于是科学家希尔研究出了一种排序方法，对直接插入排序改进后可以增加效率。
思想：按待排序列下标的一定增量分组（如：增量序列，其中，），将整个待排序列分割成若干子序列，分别进行直接插入排序，随着增量逐渐减少，所分组包含的记录越来越多，到增量值减至1时，整个记录集被分成一组（这时待排序列“基本有序”），再对全体记录进行直接插入排序，算法终止（对待排序列进行了趟直接插入排序）。
我所理解Shell Insertion Sort最牛的地方是，让排序算法能够并行化。
希尔插入排序增量的取法：
即：先将要排序的一组记录按某个增量（ ，为要排序数的个数）分成若干组子序列，每组中记录的下标相差。对每组中全部元素进行直接插入排序，然后在用一个较小的增量（ ）对它进行分组，在每组中再进行直接插入排序。继续不断缩小增量直至为1，最后使用直接插入排序完成排序。
如：int[] Key = new int[]{45,34,78,12,34,32,29,64};
排序过程：
程序代码：
private static void Shell<T>(int delta, T[] array) where T : IComparable<T>
{
//带增量的直接插入排序
for (int i = delta; i < array.Length; i++)
{
int j = i - delta;
T current = array[i];
while (j >= 0 && array[j].CompareTo(current) > 0)
{
array[j + delta] = array[j];
j = j - delta;
}
array[j + delta] = current;
}
}
/// <summary>
/// 希尔插入排序
/// </summary>
/// <typeparam name="T">需要排序记录的类型</typeparam>
/// <param name="array">需要排序的记录集合</param>
public static void ShellInsertSort<T>(T[] array) where T : IComparable<T>
{
for (int delta = array.Length/2; delta > 0; delta = delta/2)
{
Shell(delta, array);
}
}
希尔插入排序时效分析很难，关键码的比较次数与记录移动次数依赖于增量因子序列的选取。目前还没有人给出选取最好的增量因子序列的方法。希尔插入排序方法是一个不稳定的排序方法。
3. 选择排序
3.1 直接选择排序
思想：每一趟在个记录中选取关键字最小的记录作为有序序列中第个记录。（在要排列的一组数中，选出最小的一个数与第1个位置的数交换；然后在剩下的数当中再找最小的与第2个位置的数交换，依次类推，直到第个元素和第个元素比较为止。）
如：int[] Key = new int[]{45,34,78,12,34,32,29,64};
排序过程：
程序代码：
/// <summary>
/// 直接选择排序
/// </summary>
/// <typeparam name="T">需要排序记录的类型</typeparam>
/// <param name="array">需要排序的记录集合</param>
public static void StraightSelectSort<T>(T[] array) where T : IComparable<T>
{
for (int i = 0; i < array.Length - 1; i++)
{
int minIndex = i;
T min = array[i];
for (int j = i + 1; j < array.Length; j++)
{
if (array[j].CompareTo(min) < 0)
{
min = array[j];
minIndex = j;
}
}
if (minIndex != i)
{
array[minIndex] = array[i];
array[i] = min;
}
}
}
直接选择排序是不稳定的。
3.2 堆选择排序
直接选择排序并没有把每一趟的比较结果保存下来，在后一趟的比较中，许多比较在前一趟已经做过了，但由于前一趟排序时未保存这些比较结果，所以后一趟排序时又重复执行了这些比较操作，因而执行的比较次数较多。
如果可以做到每次在选择到最小记录的同时，并根据比较结果对其他记录做出相应的调整，那样排序的总体效率就会非常高了。而堆选择排序是一种树形选择排序，是对直接选择排序的有效改进。堆选择排序算法是Floyd和Williams在1964年共同发明的，同时，他们也发明了“堆”这样的数据结构。
堆的概念：具有个元素的序列当且仅当满足
时称之为堆。
若关键码的集合，把它们按照完全二叉树的顺序存放在一维数组中。
若满足且则称作小根堆。 若满足且则称作大根堆。
小根堆：int[] Key = new int[]{9,17,65,23,45,78,87,53,31,58,64};
大根堆：int[] Key = new int[]{94,93,75,91,85,44,51,18,48,58,10,34};
思想（以大根堆为例）：构建大根堆之后，输出堆顶记录，对剩余的个记录接着构建大根堆，便可得到个记录的次大值，如此反复执行，就能得到一个有序序列，这个过程称为堆选择排序。
堆选择排序需解决的两个问题：
问题1：如何建堆，对初始序列建堆的过程，就是一个反复进行筛选的过程。
（1）对一棵具有个结点的完全二叉树来说最后一个结点是第个结点的子树。 （2）筛选从第个结点为根的子树开始，该子树成为堆。 （3）之后向前依次对各结点为根的子树进行筛选，使之成为堆，直到根结点。
即把序号为，的记录作为根的子树都调整为堆。
问题2：输出堆顶元素后，如何调整新堆。
（1）设有个元素的堆，输出堆顶元素后，剩下个元素。将堆底元素送入堆顶（最后一个元素与堆顶进行交换），堆被破坏，其原因仅是根结点不满足堆的性质。 （2）将根结点与左，右子树中较大元素进行交换。 （3）若与左子树交换：如果左子树堆被破坏，即左子树的根结点不满足堆的性质，则重复第二步。 （4）若与右子树交换：如果右子树堆被破坏，即右子树的根结点不满足堆的性质，则重复第二步。 （5）继续对不满足堆性质的子树进行上述操作，直到叶子结点，堆被重建成。
即：输出堆顶元素，将最后一个叶子结点放在堆顶，重新构建大根堆。
如：int[] Key = new int[]{45,34,78,12,34,32,29,64};
排序过程：
初始时：
建堆后：
堆重建后：
程序代码：
private static void Restore<T>(T[] array, int j, int vCount) where T : IComparable<T>
{
//构建以结点j为根,一共有vCount个结点的大根堆
while (j <= vCount / 2)
{
int m = (2 * j + 1 <= vCount && array[2 * j + 1].CompareTo(array[2 * j]) > 0)
? 2 * j + 1
: 2 * j;
if (array[m].CompareTo(array[j]) > 0)
{
T temp = array[m];
array[m] = array[j];
array[j] = temp;
j = m;
}
else
{
break;
}
}
}
/// <summary>
/// 堆选择排序
/// </summary>
/// <typeparam name="T">需要排序记录的类型</typeparam>
/// <param name="array">需要排序的记录集合</param>
public static void HeapSelectSort<T>(T[] array) where T : IComparable<T>
{
int vCount = array.Length;
T[] tempArray = new T[vCount + 1];
for (int i = 0; i < vCount; i++)
tempArray[i + 1] = array[i];
//初建大根堆
for (int i = vCount / 2; i >= 1; i--)
Restore(tempArray, i, vCount);
//大根堆的重构与排序
for (int i = vCount; i > 1; i--)
{
T temp = tempArray[i];
tempArray[i] = tempArray[1];
tempArray[1] = temp;
Restore(tempArray, 1, i - 1);
}
for (int i = 0; i < vCount; i++)
array[i] = tempArray[i + 1];
}
4. 交换排序
4.1 冒泡交换排序
思想：通过相邻记录之间的比较和交换，使关键字较小的记录如气泡一般逐渐向上漂移直至水面。
如：int[] Key = new int[]{45,34,78,12,34,32,29,64};
程序代码：
/// <summary>
/// 冒泡交换排序
/// </summary>
/// <typeparam name="T">需要排序记录的类型</typeparam>
/// <param name="array">需要排序的记录集合</param>
public static void BubbleExchangeSort<T>(T[] array) where T : IComparable<T>
{
for (int i = 0; i < array.Length - 1; i++)
{
for (int j = array.Length - 1; j > i; j--)
{
if (array[j].CompareTo(array[j - 1]) < 0)
{
T temp = array[j - 1];
array[j - 1] = array[j];
array[j] = temp;
}
}
}
}
对冒泡排序常见的改进方法是加入一个标志性变量flag，用于标志某一趟排序过程是否有数据交换，如果进行某一趟排序时并没有进行数据交换，则说明数据已经按要求排列好，可立即结束排序，避免不必要的比较过程。
程序代码：
/// <summary>
/// 改进的冒泡交换排序
/// </summary>
/// <typeparam name="T">需要排序记录的类型</typeparam>
/// <param name="array">需要排序的记录集合</param>
public static void BubbleExchangeSortImproved<T>(T[] array) where T : IComparable<T>
{
for (int i = 0; i < array.Length - 1; i++)
{
bool flag = false;
for (int j = array.Length - 1; j > i; j--)
{
if (array[j].CompareTo(array[j - 1]) < 0)
{
T temp = array[j - 1];
array[j - 1] = array[j];
array[j] = temp;
flag = true;
}
}
if (flag == false)
break;
}
}
4.2 快速交换排序
快速交换排序是由图灵奖获得者Tony Hoare（东尼.霍尔）所发展的一种排序算法，是采用分治策略的一个非常典型的应用。快速交换排序虽然高端，但其思想是来自冒泡交换排序的，冒泡交换排序是通过相邻元素的比较和交换把最小的冒泡到最顶端，而快速交换排序是比较和交换小数和大数，这样一来不仅小数冒泡到上面的同时也把大数沉到下面。
其基本思想如下：
（1）选择一个基准元素，通常选择第一个元素或者最后一个元素。 （2）通过一趟排序将待排序的记录分割成独立的两部分，其中一部分记录的元素值均比基准元素值小，另一部分记录的元素值比基准值大。 （3）此时基准元素在其排好序的正确位置。 （4）然后分别对这两部分记录用同样的方法继续进行排序，直到整个序列有序。
即：从待排记录中选一记录，将其放入正确的位置，然后以该位置为界，对左右两部分再做快速排序，直到划分的长度为1。
如：int[] Key = new int[]{45,34,78,12,34,32,29,64};
程序代码：
private static void QuickSort<T>(T[] array, int left, int right) where T : IComparable<T>
{
//快速排序递归函数
if (left < right)
{
T current = array[left];
int i = left;
int j = right;
while (i < j)
{
while (array[j].CompareTo(current) > 0 && i < j)
j--;
while (array[i].CompareTo(current) <= 0 && i < j)
i++;
if (i < j)
{
T temp = array[i];
array[i] = array[j];
array[j] = temp;
j--;
i++;
}
}
array[left] = array[j];
array[j] = current;
if (left < j - 1) QuickSort(array, left, j - 1);
if (right > j + 1) QuickSort(array, j + 1, right);
}
}
/// <summary>
/// 快速交换排序
/// </summary>
/// <typeparam name="T">需要排序记录的类型</typeparam>
/// <param name="array">需要排序的记录集合</param>
public static void QuickExchangeSort<T>(T[] array) where T : IComparable<T>
{
QuickSort(array, 0, array.Length - 1);
}
其实上面的代码还可以再优化，上面代码中基准元素已经在current中保存了，所以不需要每次交换都设置一个temp变量，在交换的时候只需要先后覆盖就可以了。这样既能较少空间的使用还能降低赋值运算的次数。
优化代码如下：
private static void QuickSortImproved<T>(T[] array, int left, int right) where T : IComparable<T>
{
//快速排序递归函数
if (left < right)
{
T current = array[left];
int i = left;
int j = right;
while (i < j)
{
while (array[j].CompareTo(current) > 0 && i < j)
j--;
array[i] = array[j];
while (array[i].CompareTo(current) <= 0 && i < j)
i++;
array[j] = array[i];
}
array[j] = current;
if (left < j - 1) QuickSortImproved(array, left, j - 1);
if (right > j + 1) QuickSortImproved(array, j + 1, right);
}
}
/// <summary>
/// 快速交换排序
/// </summary>
/// <typeparam name="T">需要排序记录的类型</typeparam>
/// <param name="array">需要排序的记录集合</param>
public static void QuickExchangeSortImproved<T>(T[] array) where T : IComparable<T>
{
QuickSortImproved(array, 0, array.Length - 1);
}
5. 并归排序
我们首先先看两个有序序列合并的例子，如：
int[] Key1 = new int[]{1,3,5,7,9};
int[] Key2 = new int[]{2,4,6,8,10,12,14}
int[] temp = new int[Key1.Length + Key2.Length];
程序代码：
/// <summary>
/// 合并排序
/// </summary>
/// <typeparam name="T">需要排序记录的类型</typeparam>
/// <param name="array1">有序记录集合1</param>
/// <param name="array2">有序记录集合2</param>
/// <returns>合并后的有序记录集合</returns>
public static T[] MergeSort<T>(T[] array1,T[] array2) where T : IComparable<T>
{
T[] temp = new T[array1.Length + array2.Length];
int i = 0, j = 0, k = 0;
while (i < array1.Length && j < array2.Length)
{
if (array1[i].CompareTo(array2[i]) < 0)
{
temp[k++] = array1[i++];
}
else
{
temp[k++] = array2[j++];
}
}
while (i < array1.Length)
{
temp[k++] = array1[i++];
}
while (j < array2.Length)
{
temp[k++] = array2[j++];
}
return temp;
}
我们接着看一个序列的并归排序。
首先递归划分子问题，然后合并结果。把待排序列看成由两个有序的子序列构成，然后合并两个子序列，接着把子序列看成由两个有序序列组成……。倒过来看，其实就是先两两合并，然后四四合并……最终形成有序序列。该算法是采用分治策略的一个非常典型的应用，俗称 2-路并归。
如：int[] Key = new int[]{45,34,78,12,34,32,29,64};
程序代码：
/// <summary>
/// 合并排序的递归合并函数
/// </summary>
/// <typeparam name="T">需要排序记录的类型</typeparam>
/// <param name="array">需要排序的记录集合</param>
/// <param name="left">起点位置</param>
/// <param name="mid">中间位置</param>
/// <param name="right">终点位置</param>
private static void Merge<T>(T[] array, int left, int mid, int right) where T : IComparable<T>
{
T[] temp = new T[right - left + 1];
int i = left;
int j = mid + 1;
int k = 0;
while (i <= mid && j <= right)
{
if (array[i].CompareTo(array[j]) < 0)
{
temp[k++] = array[i++];
}
else
{
temp[k++] = array[j++];
}
}
while (i <= mid)
{
temp[k++] = array[i++];
}
while (j <= right)
{
temp[k++] = array[j++];
}
for (int n = 0; n < temp.Length; n++)
{
array[left + n] = temp[n];
}
}
/// <summary>
/// 合并排序的递归分治函数
/// </summary>
/// <typeparam name="T">需要排序记录的类型</typeparam>
/// <param name="array">需要排序的记录集合</param>
/// <param name="left">起点位置</param>
/// <param name="right">终点位置</param>
private static void MergeSort<T>(T[] array, int left, int right) where T : IComparable<T>
{
if (left >= right)
return;
int mid = (left + right) / 2;
MergeSort(array, left, mid); //递归排序左边
MergeSort(array, mid + 1, right); //递归排序右边
Merge(array, left, mid, right); //合并
}
/// <summary>
/// 合并排序
/// </summary>
/// <typeparam name="T">需要排序记录的类型</typeparam>
/// <param name="array">需要排序的记录集合</param>
public static void MergeSort<T>(T[] array) where T : IComparable<T>
{
MergeSort(array, 0, array.Length - 1);
}