說明
主要介紹了冒泡排序，插入排序和選擇排序的流程。
冒泡排序
冒泡排序流程
在
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]
，誰大誰來到第一個位置上
冒泡排序示例圖
冒泡排序源碼
public class Code_0001_Sort {
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]
估算時發現這個算法流程的複雜程度，會因為資料狀況的不同而不同。
插入排序示例圖
插入排序代碼
public class Code_0001_Sort {
public static void insertionSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
int n = arr.length;
for (int i = 1; i < n; i++) {
for (int j = i - 1; j >= 0; j--) {
if (arr[j] > arr[j + 1]) {
swap(arr, j + 1, j);
}
}
}
}
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位置。
選擇排序代碼
public class Code_0001_Sort {
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];
}
}
更多
參考資料
- 程式員代碼面試指南（第2版）
- 算法和資料結構基礎班-左程雲
- 極客時間-資料結構與算法之美-王争
- 算法(第四版)