数据结构与算法C#版笔记--排序(Sort)-上
数据结构与算法C#版笔记--排序(Sort)-上
这里讨论的仅限于内部排序(即全部数据都在内存中，通过CPU运算处理元素排序)，而且仅限顺序表排序（即不讨论链表，树状结构等结构的排序）
注：排序后的结果可以从小到大，或者从大到小，这只是一个相反的处理而已，为方便起见，本文中的方法都是从小到大排序
1、直接插入排序(InsertOrder)
思路：从第二个元素开始向后遍历，检查本身(后面称之为tmp)与前面相邻元素的大小，如果发现前面的元素更大，则依次从近及远（即倒序遍历）检查前面的所有元素，将比自身元素大的元素依次后移，这样最终将得到一个空位，将tmp元素插在这个位置即可.
/// <summary>
/// 直接插入排序法
/// </summary>
/// <param name="lst"></param>
static void InsertSort(int[] lst)
{
int _circleCount = 0;
//外循环从第二个元素开始从前向后遍历
for (int i = 1; i < lst.Length; i++)
{
_circleCount++;
//Console.WriteLine("外循环i=" + i);
//如果发现某元素比前一个元素小
if (lst[i] < lst[i - 1])
{
int tmp = lst[i];
int j = 0;
//则该元素前面的元素，从后到前遍历，依次后移，直接找到应该插入的空档在哪里(这样tmp元素就找到了自己的位置)
for (j = i - 1; j >= 0 && tmp < lst[j]; j--)
{
//如果发现有比tmp小的元素，则将元素后移一位(从而把自身空出来，形成一个空档，以方便如果前面还有更小的元素时，可以继续向后面的空档移动)
lst[j + 1] = lst[j];
_circleCount++;
//Console.WriteLine("内循环i=" + i + "，内循环j=" + j);
}
//Console.WriteLine("j={0}", j);
//运行到这里时，j已经是空档的前一个下标
lst[j + 1] = tmp;
}
}
Console.WriteLine("InsertOrder共循环了{0}次", _circleCount);
}点评：最好情况下，如果所有元素(N个)已经排好序了，则外循环跑N-1次，内循环一次也进不了，即0次，时间复杂度为O(N)；最坏情况下，所有元素反序，外循环N-1次，内循环为i（i从1到N-1），时间复杂度为O(N*N)；所以元素越有序列，该方法效率越高，其时间复杂度从O(N)到O(N*N)之间，此外，该方法是一种稳定排序。(注：若数组中有相同值的元素时，经过某方法排序后，这二个相同值的元素先后顺序仍然不变，则称这种排序方法为稳定的，反之为不稳定排序方法)
2、冒泡排序法(BubbleSort)
思路：从最后一个元素开始向前遍历，依次检查本元素与前面相邻元素的大小，如果前面的元素更大，则交换位置，如此反复，直到把自己前移到合适的位置（即 相当于后面的元素，通过这种比较，按照从小到大将不断移动前面来，就象气泡从下面向上冒一样）
/// <summary>
/// 冒泡排序法
/// </summary>
/// <param name="lst"></param>
static void BubbleSort(int[] lst)
{
int _circleCount = 0;//辅助用，可以去掉
int tmp;
for (int i = 0; i < lst.Length; i++)
{
for (int j = lst.Length - 2; j >= i; j--)
{
if (lst[j + 1] < lst[j])
{
tmp = lst[j + 1];
lst[j + 1] = lst[j];
lst[j] = tmp;
}
_circleCount++;
}
}
Console.WriteLine("BubbleOrder共循环了{0}次", _circleCount);
}点评：与插入排序法类似，最好情况是所有元素已经排好序，这样只跑外循环，内循环因为if判断不成立，直接退出；最坏情况是所有元素反序，外循环和内循环每次都要处理，因此时间复杂度跟插入排序法完全相同，同样这也是一种稳定排序。
3、简单选择排序法 (SimpleSelectOrder)
思路：先扫描整个数组，找出最小的元素，然后跟第一个元素交换(这样，第一个位置的元素就排好了)，然后从第二个元素开始继续扫描，找到第二小的元素，跟第二个元素交换（这样，第二个位置的元素也排好了）...如此反复
/// <summary>
/// 简单选择排序法
/// </summary>
/// <param name="lst"></param>
static void SimpleSelectSort(int[] lst)
{
int _circleCount = 0;//辅助用
int tmp = 0;
int t = 0;
for (int i = 0; i < lst.Length; i++)
{
t = i;
//内循环，找出最小的元素下标
for (int j = i + 1; j < lst.Length; j++)
{
if (lst[t] > lst[j])
{
t = j;
}
_circleCount++;
}
//将最小元素[下标为t]与元素i互换
tmp = lst[i];
lst[i] = lst[t];
lst[t] = tmp;
}
Console.WriteLine("SimpleSelectSort共循环了{0}次", _circleCount);
}点评：跟冒泡法很类似，不过应该注意到，这里的元素交换操作是在内循环外，即不管如何这个交换操作是省不了的，所以其时间复杂度均为O(N*N)，同样这也是一个稳定排序。
4、快速排序(QuickOrder)
思路：以数组中间的元素做为分界线（该元素称为支点），扫描其它元素，比支点小的放在左侧，比支点大的放在右侧，这样就把数组分成了二段(即做了一次粗放的大致排序)，然后对每一段做同样的处理（即二段变四段，4段变8段...），直到最后每一段只有一个元素为止(没错，该方法是一个递归调用)
/// <summary>
/// 快速排序
/// </summary>
/// <param name="arr">待排序数组</param>
/// <param name="left">数组第一个元素索引Index</param>
/// <param name="right">数组最后一个元素索引Index</param>
static void QuickSort(int[] arr, int left, int right)
{
//左边索引小于右边，则还未排序完成
if (left < right)
{
//取中间的元素作为比较基准，小于他的往左边移，大于他的往右边移
int middle = arr[(left + right) / 2];
//因为while中要做++与--的操作，所以这里先将i,j各自换外扩张一位
int i = left - 1;
int j = right + 1;
while (true)
{
while (arr[++i] < middle) ;//如果前半部的元素值本身就比支点小，则直接跳过
while (arr[--j] > middle) ;//如果后半部的元素值本身就比支点大，则直接跳过
//因为前半段是向后遍历，而后半段是向前遍历，所以如果二者碰到了，
//则说明所有元素都被扫过了一遍，完成退出
if (i >= j)
{
break;
}
//经过前面的处理后，如果发现有放错位置的元素，则将二者对换
int tmp = arr[i];
arr[j] = arr[i];
arr[i] = tmp;
}
//经过上面的while循环后，元素已被分成左右二段（左段小于支点，右段大于支点）
//递归调用，处理左段
QuickSort(arr, left, i - 1);
//递归调用，处理右段
QuickSort(arr, j + 1, right);
}
}点评：每次从中间分成二段，然后再中分为二段，如此反复...这跟二叉树很相似（每次分段，相当于树中的某个节点分成二叉），最好情况下所有元素已经排好序，最终树的左右分支数大致相同（即左右分支长度大致相同），所以分解次数为树的高度log2N，而最坏情况下，所有元素反序，这时分解得到的树相当于一个单右支二叉树（即一个右分支超级长，没有左分支的怪树），即时间复杂度范围为nLog2N 至 N*N。此外，快速排序是一种不稳定的排序（从代码就能看出来，即使是二个相同值的节点，在分段过程中，也有可能被交换顺序）
本来想将堆排序与归并排序一起写在这篇文章里的，今天看了看堆排序，还有点小复杂，完全可以另起一篇详解原理了，下篇将专门学习堆排序及归并排序。