1、冒泡排序
冒泡排序每次都会选出一个最小（或者最大）的数，并且还会把前面的元素排序，因为像是水中的泡泡往上冒，所以叫冒泡排序。
冒泡排序适合用于基本有序，或者想求出前几个最小或最大的数。
最好情况是全部有序，时间复杂度O(n)。
最坏情况是正好与顺序相反，时间复杂度O(n²)。
稳定
public void Sort(int[] arr)
{
for (int i = 0; i < arr.Length; i++)
{
bool b = false;//标记是否已经有序,也就是没有再发生交换
for (int j = 0; j < arr.Length - 1 - i; j++)
{
if (arr[j] > arr[j + 1])//比较
{
int temp = arr[j + 1];
arr[j + 1] = arr[j];
arr[j] = temp;
b = true;//如果发生交换，就让它为真
}
}
if (!b)
{
break;
}
}
//打印输出
for (int k = 0; k < arr.Length; k++)
{
Console.Write(arr[k] + " ");
}
}
2、选择排序
选择排序第一次会在数组中选出最小的，放在第一位，然后从后面的元素选出第二小的，放在第二位，以此类推。
是用于元素比较少的情况。
最好最坏都是O(n²)。
不稳定
public void Sort(int[] arr)
{
for (int i = 0; i < arr.Length - 1; i++)
{
int temp = i;//默认第索引i元素是最小的
for (int j = i + 1; j < arr.Length; j++)
{
if (arr[temp] > arr[j])//寻找最小的元素索引
{
temp = j;//记录最小的元素索引
}
}
int value = arr[temp];
arr[temp] = arr[i];
arr[i] = value;
}
//打印输出
for (int i = 0; i < arr.Length; i++)
{
Console.Write(arr[i] + " ");
}
}
3、插入排序
插入排序是元素与它前面的元素依次比较，找到自己合适的位置，插入到哪里，因此涉及到元素的移动。不要把它和冒泡排序搞混。冒泡排序核心是挨着的两个元素交换，插入排序是选择位置然后其他元素向后移动。
插入排序适用于基本有序，或者往数组中插入元素的情况。，因为需要移动元素，所以在链表上使用更好。
最好情况是全部有序，O(n)。
最坏情况是全部无序，O(n²)。
稳定
public void Sort(int[] arr)
{
for (int i = 1; i < arr.Length; i++)
{
int j = i - 1;//要进行插入的元素索引下表
if (arr[j] > arr[i])//与前一个比较，判断是否需要进行移动
{
int temp = arr[i];
while (j >= 0 && arr[j] > temp)
{
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = temp;
}
}
//打印输出
for (int i = 0; i < arr.Length; i++)
{
Console.Write(arr[i] + " ");
}
}
4、希尔排序
希尔排序的思想其实就是在插入排序的改进版，因为插入排序对有序数组效率更高（达到线性），但是通常情况下还是无序的，因此可以利用希尔排序把数组排的基本有序，希尔排序的最后还是会回归插入排序进行完整的排序。希尔排序说白了就是在插入排序的基础上，间隔n个元素进行插入排序，然后间隔n/2,在插入排序，依次类推，直到n=1，进行依次插入排序，就完成了。
最好情况是O(nlog²n)。
最坏情况是O(nlog²n)。
不稳定
public void Sort(int[] arr)
{
int jump = 4;//间隔增量
while (jump > 0)
{
//下面和插入排序基本相同，区别只有间隔不同
for (int i = jump; i < arr.Length; i++)
{
int j = i - jump;
if (arr[i] < arr[j])
{
int temp = arr[i];
while (j >= 0 && temp < arr[j])
{
arr[j + jump] = arr[j];
j -= jump;
}
arr[j + jump] = temp;
}
}
jump = jump / 2;
}
//打印输出
for (int i = 0; i < arr.Length; i++)
{
Console.Write(arr[i] + " ");
}
}
5、快速排序
快速排序是目前公认的最佳排序法，它的主要思想是“分治递归”，它会先选择一个中间元素，比这个中间元素大的放在中间元素的右边，比这个中间元素小的放在中间元素的左边，这样以中间元素，分割出两个新数组，左边的比中间元素小的数组，右边的比中间元素大的数组，然后在两个数组中继续以这种方式排序，直到数组元素为1。
最好情况：O(nlogn)
最坏情况：O(n²)
不稳定
public void Sort(int[] arr)
{
Sort(arr, 0, arr.Length - 1);
for (int i = 0; i < arr.Length; i++)
{
Console.Write(arr[i] + " ");
}
}
private void Sort(int[] arr,int low,int hight)
{
int pivot = 0;
if (hight > low)
{
pivot = Partition(arr, low, hight);//选出中间点
Sort(arr, low, pivot - 1);//把中间点左部分的数组递归
Sort(arr, pivot + 1, hight);//把中间点有部分的数组递归
}
}
private int Partition(int[] arr, int low,int hight)
{
int temp = arr[low];
while (hight > low)
{
while (hight > low && arr[hight] >= temp)
{
hight--;
}
arr[low] = arr[hight];
while (hight > low && arr[low] < temp)
{
low++;
}
arr[hight] = arr[low];
}
arr[low] = temp;
return low;
}
}
6、堆排序
可以看这篇文章：https://www.cnblogs.com/chengxiao/p/6129630.html
堆排序是利用堆这种数据结构所设计的一种排序算法，它可以减少选择排序中的比较次数，根据需要选择大根堆和小根堆，大根堆就是每个节点的值都大于等与其子节点的值，小根堆与之相反。
算法的步骤：
先建立小根堆（大根堆）
将根节点与最后一个节点交换
打印最后一个节点，然后重新排布小根堆（大根堆）
最好最坏情况都是O(nlogn).
public void Sort(int[] arr)
{
//构建堆
for (int i = arr.Length/2 - 1; i >= 0; i--)
{
Heap(arr,i, arr.Length);
}
//调整
for (int i = arr.Length - 1; i >= 0; i--)
{
Swop(arr, 0, i);
Heap(arr, 0, i);
}
//打印输出
for (int i = arr.Length - 1; i >= 0; i--)
{
Console.Write(arr[i] + " ");
}
}
private void Heap(int[] arr,int i,int length)//调整堆
{
//length / 2是最后面一个拥有子节点的节点
for (int j = i; j < length / 2; j++)
{
int left = 2 * j + 1;//节点最孩子
int right = 2 * j + 2;//节点右孩子
if (left < length)
{
int idx = left;
if (right < length)
idx = arr[left] < arr[right] ? left : right;
if (arr[idx] < arr[j])
Swop(arr, idx, j);
}
}
}
private void Swop(int[] arr, int i, int j)//用于方便交换的函数
{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
7、归并排序
归并排序
8、基数排序
