冒泡排序
原理：比较两个相邻的元素，将值大的元素交换至右端
思路：依次比较相邻的两个数，将小数放在前面，大数放在后面。即在第一趟：首先比较第1个和第2个数，将小数放前，大数放后。然后比较第2个数和第3个数，将小数放前，大数放后，如此继续，直至比较最后两个数，将小数放前，大数放后。重复第一趟步骤，直至全部排序完成。
public static void bubbleSort(int[] arr) {
// 外层循环代表总共排了多少次
// 最后一次排序可以排出两个值的大小，所以写了 arr.length - 1 中的 - 1
for (int i = 0; i < arr.length - 1; i++) {
// 设定一个标记，若为true，则表示此次循环没有进行交换，
// 也就是待排序列已经有序，排序已然完成。
boolean flag = true;
// 内层循环代表一次排序，选出当前最大数
for (int j = 0; j < arr.length - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
swap(arr, j, j + 1);
flag = false;
}
}
if (flag) {
break;
}
}
}
若原数组本身就是有序的（这是最好情况），仅需n-1次比较就可完成；若是倒序，比较次数为 n-1+n-2+...+1=n(n-1)/2，交换次数和比较次数等值。所以，其时间复杂度依然为O(n2）。综合来看，冒泡排序性能还还是稍差于上面那种选择排序的。
选择排序
简单选择排序是最简单直观的一种算法，基本思想为每一趟从待排序的数据元素中选择最小（或最大）的一个元素作为首元素，直到所有元素排完为止，简单选择排序是不稳定排序。
在算法实现时，每一趟确定最小元素的时候会通过不断地比较交换来使得首位置为当前最小，交换是个比较耗时的操作。其实我们很容易发现，在还未完全确定当前最小元素之前，这些交换都是无意义的。我们可以通过设置一个变量min，每一次比较仅存储较小元素的数组下标，当轮循环结束之后，那这个变量存储的就是当前最小元素的下标，此时再执行交换操作即可。
public static void selectSort(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
// 每一趟循环比较时，min用于存放较小元素的数组下标，
// 这样当前批次比较完毕最终存放的就是此趟内最小的元素的下标，
// 避免每次遇到较小元素都要进行交换。
int min = i;
for (int j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[min]) {
min = j;
}
}
// 进行交换，如果min发生变化，则进行交换
if (min != i) {
swap(arr,min,i);
}
}
}
简单选择排序通过上面优化之后，无论数组原始排列如何，比较次数是不变的；对于交换操作，在最好情况下也就是数组完全有序的时候，无需任何交换移动，在最差情况下，也就是数组倒序的时候，交换次数为n-1次。综合下来，时间复杂度为O(n^2)
插入排序
直接插入排序基本思想是每一步将一个待排序的记录，插入到前面已经排好序的有序序列中去，直到插完所有元素为止。
public static void insertionSort(int[] arr) {
// i 代表的是无序数组的起始点
for (int i = 1; i < arr.length; i++) {
int j = i;
// 从小到大排序
// j 代表的是将 i 所在的位置的元素不断和前边的元素进行比较
while (j > 0 && arr[j] < arr[j - 1]) {
swap(arr,j,j-1);
j--;
}
}
}
如果目标是把 n 个元素的序列升序排列，那么采用插入排序存在最好情况和最坏情况。最好情况就是，序列已经是升序排列了，在这种情况下，需要进行的比较操作需（n-1）次即可。最坏情况就是，序列是降序排列，那么此时需要进行的比较共有n(n-1)/2次。平均来说插入排序算法的时间复杂度为O(n^2）。因而，插入排序不适合对于数据量比较大的排序应用。但是，如果需要排序的数据量很小，例如，量级小于千，那么插入排序还是一个不错的选择
网友评论