算法(二)
發佈於 2019-03-10
本篇开始，我们来看看在工作中比较常用的两大算法之一的排序算法。
基本概念及分类
假设含有 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);
}腾讯云开发者
