阅读目录
1. 冒泡排序
2. 选择排序
3. 插入排序
4. 希尔排序
5. 快速排序：初始快速排序、三向切分的快速排序（快速排序的优化版）
6. 堆排序
7. 归并排序：数组版本、List版本
8. 桶排序
下面所有的代码，都已经经过Visual Studio测试。
首先，通用的交换函数Swap：
private static void Swap(ref int a, ref int b)
{
int temp = a;
a = b;
b = temp;
}
1. 冒泡排序
基本思想：依次比较相邻的两个元素，如果前面的数据大于后面的数据，就将两个数据进行交换
C#算法实现：
/// <summary>
/// 冒泡排序
/// 依次比较相邻的两个元素，如果前面的数据大于后面的数据，就将两个数据进行交换
/// 测试用例：4 3 2 1
/// i = 0;
/// j = 1; 3 4 2 1
/// j = 2; 3 2 4 1
/// j = 3; 3 2 1 4
///
/// i = 1;
/// j = 1; 2 3 1 4
/// j = 2; 2 1 3 4
///
/// i = 2;
/// j = 1; 1 2 3 4
/// </summary>
private static void BubbleSort(int[] arr, int length)
{
for (int i = 0; i < length - 1; i++)
{
for (int j = 1; j < length - i; j++)
{
if (arr[j] < arr[j - 1])
{
Swap(ref arr[j - 1], ref arr[j]);
}
}
}
}
2. 选择排序
基本思想：在要排序的一组数中，假设第一个元素时最小值，依次与后面的元素比较，如果有更小的值，交换。继续遍历元素，依次找到最小的值，进行交换，最后完成排序。
C#算法实现：
/// <summary>
/// 选择排序
/// 在要排序的一组数中，选出最小的一个数与第i个位置的数交换，之后依次类推(i=0,1,2,3...)
/// 测试用例：49 38 65 32
/// i = 0，min = 3, 32 38 65 49
/// i = 1, min = 1, 32 38 65 49
/// i = 2, min = 3, 32 38 49 65
/// </summary>
private static void SelectSort(int[] arr, int length)
{
for (int i = 0; i < length - 1; i++)
{
int min = i;
for (int j = i + 1; j < length; j++)
{
if (arr[j] < arr[min])
{
min = j;
}
}
//当在此次遍历中，如果没有比arr[i]更小的值，则不用交换
if (min != i)
{
Swap(ref arr[i], ref arr[min]);
}
}
}
3. 插入排序
基本思想：将原来的无序数列看成含有一个元素的有序序列和一个无序序列，将无序序列中的值依次插入到有序序列中，完成排序。
C#算法实现：
/// <summary>
/// 插入排序
/// 将原来的无序数列看成含有一个元素的有序序列和一个无序序列，将无序序列中的值依次插入到有序序列中，完成排序
/// 测试用例： 49 38 65 32
/// i = 1, j = 0; a[0] > a[1] YES 交换 38 49 65 32
/// i = 2, j = 1; a[1] > a[2] NO 不交换
/// i = 2, j = 0; a[0] > a[1] NO 不交换
/// i = 3, j = 2; a[2] > a[3] YES 交换 38 49 32 65
/// i = 3, j = 1; a[1] > a[2] YES 交换 38 32 49 65
/// i = 3, j = 0; a[0] > a[1] YES 交换 32 38 49 65
/// </summary>
private static void InsertionSort(int[] arr, int length)
{
//将a[0]作为有序序列，从索引1开始遍历无序序列
for (int i = 1; i < length; i++)
{
for (int j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--)
{
Swap(ref arr[j], ref arr[j + 1]);
}
}
}
4. 希尔排序
基本思想：在插入排序的基础上加入了分组策略，将数组序列分成若干子序列分别进行插入排序。
C#算法实现：
/// <summO，有时平均时间复杂度高的算法可能更适合某些特殊情况。同时，选择算法时还得考虑它的可读性，以利于软件的维护。一般而言，需要考虑的因素有以下四点：
（1）待排序的记录数目n的大小；
（2）记录本身数据量的大小，也就是记录中除关键字外的其他信息量的大小；
（3）关键字的结构及其分布情况；
（4）对排序稳定性的要求。
设待排序元素的个数为n.
（1）当n较大，则应采用时间复杂度为O(n*logn)的排序方法：快速排序、堆排序或归并排序。
快速排序：是目前基于比较的内部排序中被认为是最好的方法，当待排序的关键字是随机分布时，快速排序的平均时间最短；
堆排序：如果内存空间允许且要求稳定性的；
归并排序：它有一定数量的数据移动，所以我们可能过与插入排序组合，先获得一定长度的序列，然后再合并，在效率上将有所提高。
（2）当n较大，内存空间允许，且要求稳定性：归并排序
（3）当n较小，可采用直接插入或直接选择排序。
直接插入排序：当元素分布有序，直接插入排序将大大减少比较次数和移动记录的次数。
直接选择排序：当元素分布有序，如果不要求稳定性，选择直接选择排序。
（4）一般不使用或不直接使用传统的冒泡排序。
最后附上，旧金山大学计算机系的一个网站，可以用非常形象的动画展示，各种排序算法的执行过程，
超链接地址www.cs.usfca.edu
除了以上这些排序算法，其实还有很多其他的算法，比如C#List的排序，内省排序：
- 如果分区大小少于16个元素，则使用插入排序算法。
- 如果分区数量超过2 * LogN，其中N是输入数组的范围，则它使用Heapsort算法。
- 否则，它使用Quicksort算法。
附上：前辈大神的博客，更详细的算法细节，可以参考。
[Data Structure & Algorithm] 八大排序算法www.cnblogs.com
【经典排序算法】八大排序对比总结_wenqian 'blog-CSDN博客blog.csdn.net
转播
