排序算法之冒泡、选择、插入
冒泡排序
冒泡排序，顾名思义，就像在水里水泡会一个一个往上冒，先冒出来的是小的，然后逐渐变大。基本思路就是：
- 数组中的两个元素两两比较，如果前面的数比后面大就交换
- 每一轮中对每一对相邻的元素作比较，每一轮比较过后，右边的数总是最大的。
- 每次比较可以把右边已经有序的元素排除，重复上面的步骤。直到没有元素需要比较。
public class BubbleSort {
public static void main(String[] args) {
int[] array = {4, 2, 8, 9, 5, 7, 6, 1, 3};
sort(array);
}
static void sort(int[] arr) {
// 外层的循环表示要比较多少轮，因为是两两比较，所以 比较的轮数=数组大小-1
for (int i = 1; i < arr.length; i++) {
// 设定一个标记，若为true，表名此次循环没有交换，说明已经有序，可以减少循环次数
boolean flag = true;
// 内层for循环表示参与比较的元素下标，从第一个开始
// 需要排除右边已经比较过的数
for (int j = 0; j < arr.length - i; j++) {
if (arr[j] > arr[j + 1]) {
swap(arr, j, j + 1);
flag = false;
}
}
if (flag) {
break;
}
System.out.print(String.format("第%s趟排序过后：", i));
display(arr);
}
}
static void swap(int[] num, int left, int right) {
int temp = num[left];
num[left] = num[right];
num[right] = temp;
}
//遍历显示数组
static void display(int[] array) {
for (int i = 0; i < array.length; i++) {
System.out.print(array[i] + " ");
}
System.out.println();
}
}
输出结果：
第1趟排序过后：2 4 8 5 7 6 1 3 9
第2趟排序过后：2 4 5 7 6 1 3 8 9
第3趟排序过后：2 4 5 6 1 3 7 8 9
第4趟排序过后：2 4 5 1 3 6 7 8 9
第5趟排序过后：2 4 1 3 5 6 7 8 9
第6趟排序过后：2 1 3 4 5 6 7 8 9
第7趟排序过后：1 2 3 4 5 6 7 8 9
如果不加flag，会进行8趟排序，最坏的情况下，数组元素完全无序，冒泡排序的时间复杂度是O(N2)
选择排序
选择排序在每一轮中都从待排序元素中找出最小的元素放在组前面，直到所有元素排完。基本思路是：
- 把待排序元素的第一个元素标为最小元素
- 依次把这个元素和后面的每个元素比较，找到比它小的元素，如果找到的这个元素不是第一个元素，那么就和第一个元素交换
public class SelectSort {
public static void main(String[] args) {
int[] array = {4, 2, 8, 9, 5, 7, 6, 1, 3};
sort(array);
}
static void sort(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
// 记录要交换的位置
int min = i;
for (int j = i + 1; j < arr.length; j++) {
if (arr[min] > arr[j]) {
min = j;
}
}
// 找到更小的数才交换
if (i != min) {
swap(arr, min, i);
}
System.out.print(String.format("第%s趟排序过后：", i + 1));
display(arr);
}
}
static void swap(int[] num, int left, int right) {
int temp = num[left];
num[left] = num[right];
num[right] = temp;
}
//遍历显示数组
static void display(int[] array) {
for (int i = 0; i < array.length; i++) {
System.out.print(array[i] + " ");
}
System.out.println();
}
}
选择排序实际上是对冒泡排序的优化，冒泡排序需要两两交换，选择排序减少了交换的次数，但是选择排序的时间复杂度也是O(N2)。
直接插入排序
直接插入排序是每一步把一个待排序元素，插入到前面已经排好序的元素中，就像玩扑克牌的时候，需要对牌堆进行整理一样，基本思路是：
- 从第二个元素开始（默认第一个元素已经有序），记录插入的位置。
- 把记录位置的元素依次和前面的元素比较，每找到一个比他大的数就把数组右移，直到找到大于前面的元素并且小于后面的元素的位置，这时候进行交换。
- 重复上面的步骤，直到所有的元素排序完成。
public class InsertSort {
public static void main(String[] args) {
int[] array = {4, 2, 8, 9, 5, 7, 6, 1, 3};
sort(array);
}
static void sort(int[] arr) {
int j;
// 从1开始选择元素插入，因为第一个元素默认有序
for (int i = 1; i < arr.length; i++) {
// 记录插入的位置
int insertNum = arr[i];
j = i;
// 从有序序列的右边开始找，找到比他小的数
while (j > 0 && arr[j - 1] > insertNum) {
// 右移
arr[j] = arr[j - 1];
j--;
}
arr[j] = insertNum;
System.out.print(String.format("第%s趟排序过后：", i));
display(arr);
}
}
//遍历显示数组
static void display(int[] array) {
for (int i = 0; i < array.length; i++) {
System.out.print(array[i] + " ");
}
System.out.println();
}
}
总结
冒泡、选择、插入用大O表示法都需要O(N2) 时间级别。一般不会选择冒泡排序，虽然冒泡排序书写是最简单的，但是平均性能是没有选择排序和插入排序好的。
选择排序把交换次数降低到最低，但是比较次数还是挺大的。当数据量小，并且交换数据相对于比较数据更加耗时的情况下，可以应用选择排序。
在大多数情况下，假设数据量比较小或基本有序时，插入排序是三种算法中最好的选择。
使用高级排序的话用大O表示法，时间级别会比O(N2)小。
