1、冒泡排序
只会操作相邻的两个数据。每次冒泡操作都会对相邻的两个元素进行比较，看是否满足大小关系要求。如果不满足就让它俩互换。一次冒泡会让至少一个元素移动到它应该在的位置，重复 n 次，就完成了 n 个数据的排序工作。
/// <summary>
/// 冒泡排序
/// </summary>
/// <param name="a"></param>
public static void BubbleSort(int[] a)
{
int n = a.Length;
for (int i = 0; i < n; i++)
{
bool flag = false;//提前退出冒泡循环的标志位
for (int j = 0; j < n - i - 1; j++)
{
if (a[j] > a[j + 1])
{
int temp = a[j];
a[j] = a[j + 1];
a[j + 1] = temp;
flag = true;//表示有数据交换
}
}
if (!flag)
{
break;//没有数据交换，提前退出
}
}
}
image
image
2、插入排序
首先，我们将数组中的数据分为两个区间， 已排序区间和 未排序区间。初始已排序区间只有一个元素，就是数组的第一个元素。插入算法的核心思想是取未排序区间中的元素，在已排序区间中找到合适的插入位置将其插入，并保证已排序区间数据一直有序。重复这个过程，直到未排序区间中元素为空，算法结束。
public static void InsertionSort2(int[] arr)
{
for (int i = 1; i < arr.Length; i++)
{
int insertVal = arr[i];//要插入的值
int insertIndex = i - 1;
//查找插入的位置
while (insertIndex >= 0 && insertVal < arr[insertIndex])
{
arr[insertIndex + 1] = arr[insertIndex];
insertIndex--;
}
//插入数据
arr[insertIndex + 1] = insertVal;
}
}
image
3、选择排序
选择排序算法的实现思路有点类似插入排序，也分已排序区间和未排序区间。但是选择排序每次会从未排序区间中找到最小的元素，将其放到已排序区间的末尾。
public static void SelectSort(int[] arr)
{ for (int i = 0; i < arr.Length - 1; i++)
{ int minVal = arr[i]; //先假设最小值
int minIndex = i; //先假设最小值的下标 //找出这一趟最小的数值并记录下它的下标
for (int j = i + 1; j < arr.Length; j++)
{ if (minVal > arr[j])
{
minVal = arr[j];
minIndex = j;
}
} //最后把最小的数与已排序的末尾交换
int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}
image
总结
冒泡排序、插入排序、选择排序这三种排序算法，它们的时间复杂度都是 O(n 2 ) ，比较高，适合小规模数据的排序。从代码实现上来看，冒泡排序的数据交换要比插入排序的数据移动要复杂，冒泡排序需要 3 个赋值操作，而插入排序只需要 1 个，插入排序比冒泡排序更受欢迎。
image
