几种简单排序（冒泡排序，插入排序，选择排序）算法介绍
作者：Grey
原文地址：
博客园：几种简单排序（冒泡排序，插入排序，选择排序）算法介绍
CSDN：几种简单排序（冒泡排序，插入排序，选择排序）算法介绍
说明
主要介绍了几种简单排序算法：『冒泡排序』，『插入排序』，『选择排序』。
冒泡排序
冒泡排序流程
在 arr[0...N-1] 范围上：
arr[0] 和 arr[1]，谁大谁来到 1 号位置；
arr[1] 和 arr[2]，谁大谁来到 2 号位置；
依此类推……
arr[N-2] 和 arr[N-1]，谁大谁来到第 N-1 号位置上；
在 arr[0...N-2] 范围上，重复上面的过程，但最后一步是 arr[N-3] 和 arr[N-2] ，谁大谁来到第 N-2 号位置上；
在 arr[0...N-3] 范围上，重复上面的过程，但最后一步是 arr[N-4] 和 arr[N-3]，谁大谁来到第 N-3 号位置上；
依此类推……
最后在 arr[0...1] 范围上，重复上面的过程，但最后一步是 arr[0] 和 arr[1]，谁大谁来到第 1 号位置上；
示例图如下
冒泡排序完整代码
public static void bubbleSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
for (int i = arr.length - 1; i >= 0; i--) {
for (int j = 0; j < i; j++) {
if (arr[j] > arr[j + 1]) {
swap(arr, j, j + 1);
}
}
}
}
private static void swap(int[] arr, int i, int j) {
if (arr == null || arr.length < 2 || i == j) {
return;
}
arr[i] = arr[i] ^ arr[j];
arr[j] = arr[i] ^ arr[j];
arr[i] = arr[i] ^ arr[j];
}
插入排序
流程如下
想让 arr[0...0] 上有序，这个范围只有一个数，当然是有序的。
想让 arr[0...1] 上有序，所以从 arr[1] 开始往前看，如果 arr[1] < arr[0]，就交换。否则什么也不做。
依此类推……
想让 arr[0...i] 上有序，所以从 arr[i] 开始往前看，arr[i] 这个数不停向左移动，一直移动到左边的数字不再比自己大，停止移动。
最后一步，
想让 arr[0...N-1] 上有序，arr[N-1] 这个数不停向左移动，一直移动到左边的数字不再比自己大，停止移动。
估算时发现这个算法流程的复杂程度，会因为数据状况的不同而不同。如果数组本身是有序的，那么插入排序的过程不需要移动任何数字，但是时间复杂度是以最坏情况估计，所以插入排序的时间复杂度仍然是 O(N^2)。
示例图
插入排序完整代码
public static void insertionSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
for (int i = 1; i < arr.length; i++) {
// 当前数比后一个数大才有必要交换
for (int j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--) {
swap(arr, j, j + 1);
}
}
}
public static void swap(int[] arr, int i, int j) {
if (arr == null || arr.length < 2 || i == j) {
return;
}
arr[i] = arr[i] ^ arr[j];
arr[j] = arr[i] ^ arr[j];
arr[i] = arr[i] ^ arr[j];
}
选择排序
主要流程
arr[0...N-1] 范围上，找到最小值所在的位置，然后把最小值交换到 0 号位置；
arr[1...N-1] 范围上，找到最小值所在的位置，然后把最小值交换到 1 号位置；
arr[2...N-1] 范围上，找到最小值所在的位置，然后把最小值交换到 2 号位置；
依此类推……
arr[N-1...N-1] 范围上，找到最小值位置，然后把最小值交换到 N-1 号位置；
所以选择排序的时间复杂度为 O(N^2)。
示例图
选择排序完整代码
public static void selectionSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
for (int i = 0; i < arr.length - 1; i++) {
int min = i;
for (int j = i + 1; j < arr.length; j++) {
min = arr[j] < arr[min] ? j : min;
}
swap(arr, i, min);
}
}
private static void swap(int[] arr, int i, int j) {
if (arr == null || arr.length < 2 || i == j) {
return;
}
arr[i] = arr[i] ^ arr[j];
arr[j] = arr[i] ^ arr[j];
arr[i] = arr[i] ^ arr[j];
}
本文所有示例图见：processon:简单排序（冒泡，插入，选择）