算法(二) 2019-03-10

本篇开始，我们来看看在工作中比较常用的两大算法之一的排序算法。

基本概念及分类

---

假设含有 n 个记录的序列为 {r₁, r₂, …, r_n}，其相应的关键字分别为 {k₁, k₂, …, k_n}，需确定 1, 2, …, n 的一种排列 p₁, p₂, …, p_n，使其相应的关键字满足 k_p1 <= k_p2 <= … <= k_pn 非递减(或非递增)关系，即使得序列成为一个按关键字有序的序列 {r_p1, r_p2, …, r_pn}，这样的操作就称为排序。

注意: 我们在排序问题中，通常将数据元素称为记录。

排序的稳定性

假设 k_i = k_j (1 <= i <= n, 1 <= j <= n, i 不等于 j)，且在排序前的序列中 r_i 领先于 r_j(即 i < j)。如果排序后 r_i 仍领先于 r_j，则称所用的排序方法时稳定的，反之，则称所用的排序方法时不稳定的。

内排序和外排序

根据排序过程中待排序的记录是否全部放置于内存中，排序分为: 内排序和外排序。
内排序是在排序整个过程中，待排序的所有记录全部被放置在内存中。
外排序是由于待排序的记录个数太多，不能同时放置在内存，整个排序过程需要在内外存之间多次交换数据才能进行。

冒泡排序

---

冒泡排序(Bubble Sort): 一种交换排序，他的基本思想是，两两比较相邻记录的关键字，如果反序则交换，知道没有反序记录为止。

简单实现

class SqList
{
    public const int MaxSize = 20;
    public int[] Data = new int[MaxSize];
    public int Length;

    public SqList(int[] data)
    {
        var length = (data.Length > MaxSize ? MaxSize : data.Length);
        Length = length;
        for (var i = 0; i < length; i++)
        {
            Data[i] = data[i];
        }
    }
    public void Swap(ref int a, ref int b)
    {
        var temp = a;
        a = b;
        b = temp;
    }
    /// <summary>
    /// 只能算是简单交换排序，经历一遍内存循环，将最小值置于第 i 位
    /// </summary>
    public void BubbleSort0()
    {
        for (var i = 0; i < Length; i++)
        {
            for (var j = i + 1; j < Length; j++)
            {
                if (Data[i] > Data[j])
                {
                    Swap(ref Data[i], ref Data[j]);
                }
            }
        }
    }
    
    public void ShowDatas()
    {
        var data = new int[Length];
        for (var i = 0; i < Length; i++)
        {
            data[i] = Data[i];
        }
        Console.WriteLine(string.Join("->", data));
    }

}

经典冒泡排序

/// <summary>
/// 经典冒泡排序，从后向前依次比较，较小值上浮
/// </summary>
public void BubbleSort1()
{
    for (var i = 0; i < Length; i++)
    {
        for (var j = Length -1; j > i; j--)
        {
            if (Data[j] < Data[j-1])
            {
                Swap(ref Data[j], ref Data[j-1]);
            }
        }
    }
}

优化冒泡排序

/// <summary>
/// 优化冒泡排序，设置标记，当存在交换时，设置标记，否则退出循环
/// </summary>
public void BubbleSort2()
{
    var flag = false;
    for (var i = 0; i < Length && !flag; i++)
    {
        flag = true;
        for (var j = Length - 1; j > i; j--)
        {
            if (Data[j] >= Data[j - 1]) continue;
            Swap(ref Data[j], ref Data[j - 1]);
            flag = false;
        }
    }
}

简单选择排序

---

简单选择排序(Simple Selection Sort)就是通过 n - i 次关键字间的比较，从 n - i + 1 个记录中选出关键字最小的记录，并和第 i 个记录交换。

/// <summary>
/// 简单选择排序，通过比较第 i 位与其之后的最小值，若存在，则交换
/// </summary>
public void SelectionSort()
{
    for (var i = 0; i < Length; i++)
    {
        var minIndex = i;
        for (var j = i + 1; j < Length; j++)
        {
            if (Data[minIndex] > Data[j])
            {
                minIndex = j;
            }
        }

        if (minIndex != i)
        {
            Swap(ref Data[i], ref Data[minIndex]);
        }
    }
}

直接插入排序

---

直接插入排序(Straight Insertion Sort)的基本操作是将一个记录插入到已经排序好的有序表中，从而得到一个新的、记录数加一的有序表。

/// <summary>
/// 每次遍历将第 i 位记录取出，将之前的记录后移，再将第 i 位记录置于正确位置
/// </summary>
public void InsertionSort()
{
    for (var i = 1; i < Length; i++)
    {
        if (Data[i] >= Data[i - 1]) continue;
        var temp = Data[i];
        for (var j = i-1; j >=0 && Data[j] > temp; j--)
        {
            Swap(ref Data[j+1], ref Data[j]);
        }
    }
}

快速排序

---

快速排序(Quick Sort)的基本思想是: 通过一趟排序将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分继续进行排序，以达到整个序列有序的目的。

public void QuickSort(int left, int right)
{
    var low = left;
    var high = right;
    var temp = Data[left];

    if (left > right)
    {
        return;
    }

    while (low != high)
    {
        while (Data[high] >= temp && low < high)
        {
            high--;
        }

        while (Data[low] <= temp && low < high)
        {
            low++;
        }

        if (low < high)
        {
            Swap(ref Data[low], ref Data[high]);
        }
    }

    Swap(ref Data[low], ref Data[left]);
    QuickSort(left, low - 1);
    QuickSort(low + 1, right);
}