```java
package util;
import java.util.Arrays;
/**
* 排序
*
* @author zhaoxuyang
*/
public class Sort {
public static void main(String[] args) {
String[] a = {
"1", "2", "3", "a", "a1", "b2", "a0", "_"
};
//Sort.heapSort(a);
//Sort.quickSort3way(a, 0, a.length - 1);
System.out.println(Arrays.toString(a));
}
/**
* 堆排序
*
* @param <T>
* @param a
*/
public static <T extends Comparable> void heapSort(T[] a) {
int n = a.length;
for (int k = n / 2; k >= 1; k--) {
sink(a, k, n);
}
while (n > 1) {
swap(a, 1 - 1, (n--) - 1);
sink(a, 1, n);
}
}
private static <T extends Comparable> void sink(T[] pq, int k, int n) {
while (2 * k <= n) {
int j = 2 * k;
if (j < n && less(pq[j - 1], pq[j])) {
j++;
}
if (!less(pq[k - 1], pq[j - 1])) {
break;
}
swap(pq, k - 1, j - 1);
k = j;
}
}
/**
* 快速排序:在排序前先洗牌（可以參考隨機化算法-舍伍德算法）
* <pre>
* 快速排序的算法改進：
* 【切換到插入排序】【三取樣切分】【熵最優的排序，三向切分】
* <pre>
* 三取樣切分
* (1)使用子數組的一小部分元素的中位數來切分數組，這樣能切分得更好，但是需要計算中位數
* (2)人們發現將大小設為3并用大小居中的元素切分得效果最好
* </pre>
* </pre>
*
*
* @param <T>
* @param a
*/
public static <T extends Comparable> void quickSort(T[] a) {
Shuffle.shuffle(a);
quickSort(a, 0, a.length - 1);
// quickSortInsert(a, 0, a.length - 1);
// quickSort3way(a, 0, a.length - 1);
}
/**
* 快速排序的改進方法-小數據量轉成插入排序
* <pre>
* (1)對于小數組，快速排序比插入排序慢；
* (2)因為遞歸，快速排序的sort方法會調用自己。
* </pre>
*
* @param <T>
* @param a
* @param low
* @param high
*/
public static <T extends Comparable>
void quickSortInsert(T[] a, int low, int high) {
int m = 65535;
if (high <= low + m) {
insertSort(a, low, high);
return;
}
int lt = low;
int i = low + 1;
int gt = high;
T v = a[low];
while (i <= gt) {
int cmp = a[i].compareTo(v);
if (cmp < 0) {
swap(a, lt++, i++);
} else if (cmp > 0) {
swap(a, i, gt--);
} else {
i++;
}
}
quickSort(a, low, lt - 1);
quickSort(a, gt + 1, high);
}
/**
* 快速排序的改進方法-三向切分（可以參考荷蘭國旗問題）
* <pre>
* 對于存在大量重復元素的數組，三向切分比常規快排高效得多。
* </pre>
*
* @param <T>
* @param a
* @param low
* @param high
*/
public static <T extends Comparable>
void quickSort3way(T[] a, int low, int high) {
if (high <= low) {
return;
}
int lt = low;
int i = low + 1;
int gt = high;
T v = a[low];
while (i <= gt) {
int cmp = a[i].compareTo(v);
if (cmp < 0) {
swap(a, lt++, i++);
} else if (cmp > 0) {
swap(a, i, gt--);
} else {
i++;
}
}
quickSort(a, low, lt - 1);
quickSort(a, gt + 1, high);
}
/**
* 常規快速排序的排序方法
*
* @param <T>
* @param a
* @param low
* @param high
*/
public static <T extends Comparable>
void quickSort(T[] a, int low, int high) {
int p;
if (low < high) {
p = partition(a, low, high);
quickSort(a, low, p - 1);
quickSort(a, p + 1, high);
}
}
/**
* 常規快速排序的劃分方法
*
* @param <T>
* @param a
* @param low
* @param high
* @return
*/
private static <T extends Comparable>
int partition(T[] a, int low, int high) {
int i = low;
int j = high;
T p = a[low];
while (i < j) {
while (i < j && (less(p, a[j]) || eq(a[j], p))) {
j--;
}
if (i < j) {
swap(a, i++, j);
}
while (i < j && (less(a[i], p) || eq(a[i], p))) {
i++;
}
if (i < j) {
swap(a, i, j--);
}
}
return j;
}
/**
* 歸并排序所需的輔助數組。不將其聲明為方法內的局部變量，是為了避免重復創建數組
*/
private static Comparable[] mergeAux;
/**
* 自底向上的歸并排序（適用于鏈表組織的數據）
*
* @param <T>
* @param a
*/
public static <T extends Comparable> void mergeSort2(T[] a) {
int N = a.length;
mergeAux = new Comparable[a.length];
for (int i = 1; i < N; i = i + i) {
for (int low = 0; low < N - i; low += i + i) {
merge(a, low, low + i - 1, Math.min(low + i + i - 1, N - 1));
}
}
}
/**
* 自頂向下的歸并排序
*
* @param <T>
* @param a
*/
public static <T extends Comparable> void mergeSort(T[] a) {
mergeAux = new Comparable[a.length];
mergeSort(a, 0, a.length - 1);
}
/**
* 自頂向下的歸并排序
*
* @param <T>
* @param a
* @param low
* @param high
*/
public static <T extends Comparable>
void mergeSort(T[] a, int low, int high) {
if (high <= low) {
return;
}
int middle = low + (high - low) / 2;
mergeSort(a, low, middle);
mergeSort(a, middle + 1, high);
merge(a, low, middle, high);
}
/**
* 歸并排序的合并方法
* <pre>
* 該方法先將所有元素復制到輔助數組中，再歸并回數組a中。
* 在歸并時進行了4個條件判斷：
* - 左半邊用盡（取右半邊的元素）
* - 右半邊用盡（取左半邊的元素）
* - 右半邊當前元素小于左半邊的當前元素（取右半邊的元素）
* - 右半邊當前元素大于等于左半邊的當前元素（取左半邊元素）
* </pre>
*
* @param <T>
* @param a
* @param low
* @param middle
* @param high
*/
private static <T extends Comparable>
void merge(T[] a, int low, int middle, int high) {
int i = low;
int j = middle + 1;
for (int k = low; k <= high; k++) {
mergeAux[k] = a[k];
}
for (int k = low; k <= high; k++) {
if (i > middle) {
a[k] = (T) mergeAux[j++];
} else if (j > high) {
a[k] = (T) mergeAux[i++];
} else if (less(mergeAux[j], mergeAux[i])) {
a[k] = (T) mergeAux[j++];
} else {
a[k] = (T) mergeAux[i++];
}
}
}
/**
* 希爾排序
*
* @param <T>
* @param a
*/
public static <T extends Comparable> void shellSort(T[] a) {
int len = a.length;
int h = 1;
while (h < len / 3) {
h = 3 * h + 1;
}
for (; h >= 1; h /= 3) {
for (int i = h; i < len; i++) {
for (int j = i; j >= h && less(a[j], a[j - h]); j -= h) {
swap(a, j, j - h);
}
}
}
}
/**
* 插入排序
*
* @param <T>
* @param a
*/
public static <T extends Comparable> void insertSort(T[] a) {
insertSort(a, 0, a.length);
}
/**
* 插入排序
*
* @param <T>
* @param a
* @param low
* @param high
*/
public static <T extends Comparable> void insertSort(T[] a, int low, int high) {
for (int i = low + 1; i < high; i++) {
for (int j = i; j > 0 && less(a[j], a[j - 1]); j--) {
swap(a, j, j - 1);
}
}
}
/**
* 選擇排序
*
* @param <T>
* @param a
*/
public static <T extends Comparable> void selectSort(T[] a) {
int len = a.length;
for (int i = 0; i < len; i++) {
int min = i;
for (int j = i + 1; j < len; j++) {
if (less(a[j], a[min])) {
min = j;
}
}
swap(a, i, min);
}
}
/**
* 根據數組的兩個下標交換數組中的元素
*
* @param <T>
* @param array
* @param i
* @param j
*/
private static <T extends Comparable> void swap(T[] array, int i, int j) {
T tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}
/**
* 判斷a是否小于b
*
* @param <T>
* @param a
* @param b
* @return
*/
private static <T extends Comparable> boolean less(T a, T b) {
return a.compareTo(b) < 0;
}
/**
* 判斷a是否等于b
*
* @param <T>
* @param a
* @param b
* @return
*/
private static <T extends Comparable> boolean eq(T a, T b) {
return a.compareTo(b) == 0;
}
/**
* 判斷數組是否排序
*
* @param <T>
* @param array
* @return
*/
public static <T extends Comparable> boolean isSorted(T[] array) {
for (int i = 1; i < array.length; i++) {
if (less(array[i], array[i - 1])) {
return false;
}
}
return true;
}
/**
* 打印數組
*
* @param <T>
* @param array
*/
public static <T extends Comparable> void print(T[] array) {
for (T t : array) {
System.out.print(t + " ");
}
System.out.println();
}
}
```
> 洗牌算法(Shuffle)
```java
package util;
import java.util.Arrays;
/**
* 設計一種公平的洗牌算法（算法導論）
*
* @author zhaoxuyang
*/
public class Shuffle {
public static void main(String[] args) {
Integer[] a = {
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13
};
shuffle(a);
System.out.println(Arrays.toString(a));
}
public static <T extends Comparable> void shuffle(T[] arr) {
for (int i = arr.length - 1; i >= 0; i--) {
swap(arr, i, rand(0, i));
}
}
private static int rand(int begin, int end) {
return (int) (begin + Math.random() * (end - begin + 1));
}
private static <T extends Comparable> void swap(T[] arr, int i, int j) {
T t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}
}
```
- 1 設計接口
- 1.1 容器接口Container
- 1.2 背包接口Bag
- 1.3 棧接口Stack
- 1.4 隊列接口Queue
- 1.5 Union-Find算法接口UF
- 2 實現接口
- 2.1 結點類Node
- 2.2 數組迭代器ArrayIterator
- 2.3 鏈表迭代器ListIterator
- 2.4 背包(Bag)的實現
- 2.4.1 能動態調整數組大小的Bag
- 2.4.2 鏈式Bag的實現
- 2.5 棧(Stack)的實現
- 2.5.1 能動態調整數組大小的Stack
- 2.5.2 鏈式Stack的實現
- 2.6 隊列(Queue)的實現
- 2.6.1 能動態調整數組大小的Queue
- 2.6.2 鏈式Queue的實現
- 2.7 Union-Find算法的實現
- 2.7.1 DefaultUF
- 2.7.2 QuickFindUF
- 2.7.3 QuickUnionUF
- 2.7.4 WeightedQuickUnionUF
- 2.8 測試
- 2.8.1 測試Stack
- 2.8.2 測試Union-Find
- 3 排序算法
- 3.1 定義排序工具的類結構
- 3.2 選擇排序
- 3.3 插入排序
- 3.4 希爾排序
- 3.5 歸并排序
- 3.5.1 歸并排序的合并方法
- 3.5.2 自頂向下的歸并排序
- 3.5.3 自底向上的歸并排序
- 3.6 快速排序
- 3.6.1 常規快速排序
- 3.6.2 排序前先洗牌
- 3.6.3 快速排序的改進方法-小數據量轉成插入排序
- 3.6.4 快速排序的改進方法-三向切分
- 3.7 堆排序
- 3.8 最終的排序工具
- 4 搜索
- 4.1 二分搜索(binarySearch)
- 4.2 優先隊列(MaxPriorityQueue)
- 4.3 二叉查找樹(BST)
- 4.4 紅黑二叉查找樹(RedBlackBST)
- 4.5 B-樹(BTree)
- 5 圖
- 5.1 無向圖(Graph)
- 5.2 有向圖(Digraph)
- 6 貪心
- Dijkstra算法-單元最短路徑
- 7 動態規劃
- 7.1 最長公共子序列問題
- 7.2 0-1背包問題
- 7.3 加工順序問題
- 8 搜索法
- 8.1 圖的著色問題
- 8.2 深度優先搜索
- 8.3 回溯法
- 8.3.1 回溯法的算法框架
- 8.3.2 子集樹
- 8.3.3 排列樹
- 8.3.4 滿m叉樹(組合樹)
- 8.4 廣度優先搜索
- 8.5 分支限界法
- 9 隨機化算法
- 9.1 數值隨機化算法
- 9.2 蒙特卡羅算法
- 9.3 拉斯維加斯算法
- 9.4 舍伍德算法
- 10 數論算法
- 10.1 Stein求最大公約數
- 10.2 矩陣求斐波那切數列
- LeetCode刷題筆記