A Sort Of A Blog
旧游无处不堪寻,无寻处,惟有少年心
算法(二)

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

基本概念及分类


假设含有 n 个记录的序列为 {r1, r2, …, rn},其相应的关键字分别为 {k1, k2, …, kn},需确定 1, 2, …, n 的一种排列 p1, p2, …, pn,使其相应的关键字满足 kp1 <= kp2 <= … <= kpn 非递减(或非递增)关系,即使得序列成为一个按关键字有序的序列 {rp1, rp2, …, rpn},这样的操作就称为排序。

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

排序的稳定性

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

内排序和外排序

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

冒泡排序


冒泡排序(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);
}