# 数组的排序算法
# 0. 辅助工具类
交换数组 array 的 x 和 y 这两个位置的元素。
生成一个有 N 个元素的数组，从 1 到 N，乱序，数据内容无重复。
public class SortUtil {
/**
* 交换数组 array 的 x 和 y 这两个位置的元素。
*/
public static void swap(int[] array, int x, int y) {
int temp = array[x];
array[x] = array[y];
array[y] = temp;
}
public static int[] initArray(int size) {
int[] array = new int[size];
for (int i = 0; i < size; i++) {
array[i] = i + 1;
}
/**
* 随机生成有 size 个元素的数组。
* 其中无零，且无重复数值，以便于演示。
*/
Random rand = new Random();
/* 开始 Knuth 洗牌算法，基本流程是这样的：
* 从最后一个数开始，往前遍历，每一次，从当前数和第 1 个数之间，随机选择一个数，与当前数字进行交换
* 这里的随机选择就直接使用程序语言中的 Random 随机一个索引即可。
*/
int last = array.length - 1;
for (int i = last; i >= 0; --i) {
// 从 [0 ~ 当前索引位) 之间，选择一个数
int selection = rand.nextInt(i + 1);
// 索引位对应的数据交换
swap(array, i, selection);
}
return array;
}
}
# 1. 选择排序（必背）
热身：实现一个算法 doSomething(int array[], int index) 在 [index, array.length) 之中选择最小的元素，交换到 index 位置。
public class SelectSort {
public static void main(String[] args) {
int[] array = Arrays.copyOf(initArray(40), 20); // 加大数据间隙
System.out.println("before: " + Arrays.toString(array));
sort(array);
System.out.println(" after: " + Arrays.toString(array));
}
public static void sort(int[] array) {
// i 的值是每一轮的【坑位】，
for (int i = 0; i < array.length; i++) {
// 用于记录本轮无序部分的最小值的下标索引。
int minIdx = i;
// j 的值是数组无序部分的第一个下标。
for (int j = i; j < array.length; j++) {
if (array[j] < array[minIdx]) {
minIdx = j;
}
}
// 将最小值【换】到它该待的【坑位】上。
swap(array, i, minIdx);
}
}
}
# 2. 插入排序（了解）
public class InsertSort {
public static void main(String[] args) {
int[] array = initArray(20);
//int[] array = new int[]{5, 4, 1, 3, 2};
System.out.println("before: " + Arrays.toString(array));
sort(array);
System.out.println(" after: " + Arrays.toString(array));
}
public static void sort(int[] array) {
for (int i = 0; i < array.length; i++) {
int j = i;
int temp = array[j];
while (j > 0 && array[j - 1] > temp) {
array[j] = array[j - 1];
j--;
}
array[j] = temp;
}
}
}
# 3. 二路归并排序（了解）
public class MergeSort {
public static void main(String[] args) {
int array[] = SortUtil.initArray(20);
//int[] array = new int[]{7, 3};
System.out.println("before: " + Arrays.toString(array));
sort(array);
System.out.println(" after: " + Arrays.toString(array));
}
public static void sort(int[] array) {
tempArray = new int[array.length];
sort(array, 0, array.length - 1);
}
public static void sort(int[] array, int left, int right) {
if (left >= right)
return;
int mid = left + (right - left) / 2;
sort(array, left, mid);
sort(array, mid + 1, right);
merge(array, left, mid, right);
}
private static int[] tempArray; // 辅助数组
/**
* 数组 array 的左右半区分别有序：array[left, mid] 和 array[mid+1, right]
* 现在要将这两个半区合并，使他们全区有序：array[left, right]
*/
public static void merge(int[] array, int left, int mid, int right) {
int i = left, j = mid + 1;
for (int k = left; k <= right; k++) {
tempArray[k] = array[k];
}
for (int k = left; k <= right; k++) {
if (i > mid) array[k] = tempArray[j++];
else if (j > right) array[k] = tempArray[i++];
else if (tempArray[i] < tempArray[j]) array[k] = tempArray[i++];
else array[k] = tempArray[j++];
}
}
}
# 4. 快速排序（必背）
热身：实现一个算法 doSomething(int[] array) 为数组中的第一个元素找它该待的位置。
public class QuickSort {
public static void main(String[] args) {
int array[] = SortUtil.initArray(20);
//int[] array = new int[]{7, 3};
System.out.println("before: " + Arrays.toString(array));
sort(array);
System.out.println(" after: " + Arrays.toString(array));
}
public static void sort(int[] array) {
sort(array, 0, array.length - 1);
}
private static void sort(int[] array, int left, int right) {
if (left >= right)
return;
int j = partition(array, left, right);
sort(array, left, j - 1);
sort(array, j + 1, right);
}
/**
* 将数组切分成：array[left...i-1], array[i], array[i+1, right]
*/
private static int partition(int[] array, int left, int right) {
int i = left, j = right + 1;
int pivot = array[left]; // pivot 变量可以省略，始终使用 array[left] 来代替它
/**
* 以下 i 和 j 在移动、交换过程中有几点注意的地方：
* - 极端情况下（数组天然有序），i 会一直走到数组的右边界（right）才停下，此时 j 会走到 i 的前面（i - 1）处停下。
* - 极端情况下（数组天然逆序），i 一开始就会停在起始位置（left + 1）处，j 会一直走到数组的左边界（left）才停下，正好也是在 i 的前面。
* - i、j 相交后不会间隔太远，j 一定是在 i 的前面，即，j = i - 1 。
*/
while (true) {
while (array[++i] < pivot) { // 从左往右第一个 >= pivot 的数字
if (i == right)
break;
}
while (pivot < array[--j]) { // 从右往左第一个 <= pivot 的数字
if (j == left)
break;
}
/**
* i、j 在这种情况下会相等：i 一直走到了数组范围的右边界，
* 而有边界的数字正好就是一个比 pivot 小的数字，也就是 j 要找的数字，
* 例如： 8, 1, 2, 3, 5, 6, 7, 4
* i 在 4 那里，因为 4 是右边界，i 最远只能走到这里；
* j 在 4 这里，因为 4 是 j 找到的第一个比 8 小的数字。
*/
if (i >= j)
break;
SortUtil.swap(array, i, j);
}
/**
* 为什么是 arr[j] 和 arr[left] 换，而不是 arr[i] 换？
* 因为 j 在 i 的前面（或者在一起）。
* arr[j] 一定是一个 比 arr[left] 小的数字，或者就是 arr[left] 自身。而 arr[i] 则不是。
*/
SortUtil.swap(array, left, j); // pivot == array[j] 交换位置
return j;
}
}