1、概要说明
8大排序算法：
交换排序（冒泡排序、快速排序）
插入排序（直接插入、shell排序）
选择排序（直接选择、堆排序）
归并排序
基数排序
* 术语解释：
? 1、稳定排序：如果 a 原本在 b 的前面，且 a == b，排序之后 a 仍然在 b 的前面，则为稳定排序。
? 2、非稳定排序：如果 a 原本在 b 的前面，且 a == b，排序之后 a 可能不在 b 的前面，则为非稳定排序。
? 3、原地排序：原地排序就是指在排序过程中不申请多余的存储空间，只利用原来存储待排数据的存储空间进行比较和交换的数据排序。
? 4、非原地排序：需要利用额外的数组来辅助排序。
? 5、时间复杂度：一个算法执行所消耗的时间。
? 6、空间复杂度：一个算法运行所需的内存大小。
2、源代码
创建类文件SortHelper.cs，代码如下：
public class SortHelper
{
/// <summary>
/// 交换排序 - 冒泡排序
/// 描述：首先从数组的第一个元素开始到数组最后一个元素为止，对数组中相邻的两个元素进行比较，如果位于数组左端的元素大于数组右端的元素，
/// 则交换这两个元素在数组中的位置。这样操作后数组最右端的元素即为该数组中所有元素的最大值，接着对该数组除最右端的n-1个元素进行同样的
/// 操作，再接着对剩下的n-2ge元素做同样的操作，直到整个数组有序排列。
///
/// 算法：
/// 时间复杂度为 O(n^2)
/// 空间复杂度为 O(1)
/// </summary>
public void bubbleSort(int[] arr)
{
//控制共比较多少轮
for (int i = 0; i < arr.Length; i++)
{
//控制比较的次数
for (int j = 0; j < arr.Length - 1 - i; j++)
{
if (arr[j] > arr[j + 1])
{
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
/// <summary>
/// 交换排序 - 快速排序
/// 描述：左右两端选择一个数作为游标，在挑选第一个数字为基准数，比较两端的值是否比基准数大，大的放右边，小的放左边。然后两端的游标往中间靠拢，
/// 直到游标的值重合，停止。然后再次选择第二个数字为基准数，反复刚才的操作。
///
/// 算法：
/// 时间复杂度为 O(nlog2n)
/// 空间复杂度为 O(1)
/// </summary>
/// <param name="arr"></param>
public void quickSort(int[] arr, int start, int end)
{
if (start < end)//结束标记，中间要有 元素
{
//把数组中的第0个数字作为标准数
int stard = arr[start];
//记录需要排序的游标
int low = start;
int high = end;
//循环找比标准数大的数和比标准数小的数
while (low < high)
{
//右边的数字比标准数大
while (low < high && stard <= arr[high])
{
high--;
}
//使用右边的数字替换左边的数
arr[low] = arr[high];
//如果左边的数字比标准数小
while (low < high && arr[low] <= stard)
{
low++;
}
arr[high] = arr[low];
}
//把标准数赋给低所在的位置的元素
arr[low] = stard;
//处理所有的小的数字
quickSort(arr, start, low);
//处理所有的大的数字
quickSort(arr, low + 1, end);
}
}
/// <summary>
/// 插入排序--直接插入排序
/// 描述;从第二个数开始，依次比较前面的数是否比自己大，大的插入到前面，再依次比较，直到不比自己大。
/// 处理过程，比自己大的数字依次后移，然后拿临时变量中的值，替换最初移动的那个
///
/// 算法：
/// 时间复杂度为 O(n^2)
/// 空间复杂度为 O(1)
/// </summary>
/// <param name="arr"></param>
public void insertSort(int[] arr)
{
//遍历所有的数字
for (int i = 1; i < arr.Length; i++)
{
//如果当前数字比前一个数字小
if (arr[i] < arr[i - 1])
{
//把当前遍历数字存起来
int temp = arr[i];
int j;
//遍历当前数字前面所有的数字
for (j = i - 1; j >= 0 && temp < arr[j]; j--)
{
//把前一个数字赋给后一个数
arr[j + 1] = arr[j];
}
//把临时变量（外层for循环的当前元素）赋给不满足条件的后一个元素。
arr[j + 1] = temp;
}
}
}
/// <summary>
/// 插入排序--希尔排序
/// 描述：解决直接插入排序较慢的问题，假设有一组顺序的数，突然来了一个元素比较小，依旧需要挨个比较前面的值，插入最前面，效率不高。
/// 希尔排序引入步长概念，按步长划分组，组内进行排序
///
/// 算法：
/// 时间复杂度为 O(n^2)
/// 空间复杂度为 O(1)
/// </summary>
/// <param name="arr"></param>
public void shellSort(int[] arr)
{
//遍历所有的步长
for (int d = arr.Length / 2; d > 0; d /= 2)
{
//遍历所有元素
for (int i = d; i < arr.Length; i++)
{
//遍历本组中所有的元素
for (int j = i - d; j >= 0; j -= d)
{
//如果当前元素大于加上步长后的那个元素
if (arr[j] > arr[j + d])
{
int temp = arr[j];
arr[j] = arr[j + d];
arr[j + d] = temp;
}
}
}
}
}
/// <summary>
/// 选择排序--简单选择排序
/// 说明：找一个最小的数，移动到第一个位置，然后依次找其后第二小的数字移动到前面。
///
/// 算法：
/// 时间复杂度为 O(n^2)
/// 空间复杂度为 O(1)
/// </summary>
/// <param name="arr"></param>
public void choiseSort(int[] arr)
{
//遍历所有的数
for (int i = 0; i < arr.Length; i++)
{
int minIndex = i;
//把当前遍历的数和后面所有的数依次进行比较，并记录下最小的数的下标
for (int j = i + 1; j < arr.Length; j++)
{
//如果后面比较的数比记录的最小的数小
if (arr[minIndex] > arr[j])
{
//记录下最小的那个数的下标
minIndex = j;
}
}
//如果最小的数和当前遍历数的下标不一致，说明下标为minindex的数比当前遍历的数更小。
if (i != minIndex)
{
int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}
}
//选择排序--堆排序
}3、使用说明
本帮助类已封装进 通用库中Geyc.Utils.dll，引入命名空间可以直接使用。如有错误请联系作者修改，为底层建设类库贡献力量，让编程变成一种享受。
static void Main(string[] args)
{
int[] arr = {5,7,2,9,4,1,0,5,7 };
Console.WriteLine("排序前：");
Console.WriteLine(string.Join(",", arr));
SortHelper sortHelper = new SortHelper();
//sortHelper.BubbleSort(arr);
//sortHelper.quickSort(arr,0,arr.Length-1);
//sortHelper.insertSort(arr);
//sortHelper.shellSort(arr);
sortHelper.choiseSort(arr);
//输出结果
Console.WriteLine("排序后：");
Console.WriteLine(string.Join(",", arr));
Console.ReadLine();
}
