排序算法實(shí)現(xiàn)
記錄排序算法的實(shí)現(xiàn)康谆，有空就記錄一點(diǎn)柄慰。
冒泡排序
- 比較相鄰元素，如果第一個(gè)元素大于第二個(gè)元素哩都，那么交換它們
- 完成上述步驟后魁兼，最后的元素是已排序的元素
- 對(duì)剩余未排序的元素重復(fù)上述步驟
- 排序過(guò)程中，如果沒(méi)有發(fā)生至少一次交換漠嵌，那么完成排序
平均時(shí)間復(fù)雜度：
最好情況：
最壞情況：
空間復(fù)雜度：
排序方式：In-place
穩(wěn)定性：穩(wěn)定
public class BubbleSort {
public static void sort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
for (int i = 0; i < arr.length - 1; i++) {
boolean flag = true;
for (int j = 0; j < arr.length - 1 - i; j++) {
// compare adjacent elements
if (arr[j] > arr[j + 1]) {
int tmp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = tmp;
flag = false;
}
}
// sorted
if (flag) {
break;
}
}
}
public static void main(String[] args) {
int[] arr = new int[]{9, 1, 8, 2, 7, 3, 6, 4, 5, 0, 2, 8, 4, 7};
sort(arr);
}
}
選擇排序
- 在未排序的序列中找出最懈拦（大）元素，存放到已排序的序列的末尾
- 再?gòu)氖Ｓ辔磁判蛟刂欣^續(xù)重復(fù)上述步驟
平均時(shí)間復(fù)雜度：
最好情況：
最壞情況：
空間復(fù)雜度：
排序方式：In-place
穩(wěn)定性：不穩(wěn)定
public class SelectSort {
public static void sort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
for (int i = 0; i < arr.length - 1; i++) {
// select min & index
int minIndex = i;
int min = arr[i];
for (int j = i + 1; j < arr.length; j++) {
if (min > arr[j]) {
minIndex = j;
min = arr[j];
}
}
// swap if needed
if (minIndex != i) {
int tmp = arr[i];
arr[i] = min;
arr[minIndex] = tmp;
}
}
}
public static void main(String[] args) {
int[] arr = new int[]{9, 1, 8, 2, 7, 3, 6, 4, 5, 0, 2, 8, 4, 7};
sort(arr);
}
}
插入排序
- 從第二個(gè)元素開(kāi)始献雅，循環(huán)到序列結(jié)束
- 將每一個(gè)元素準(zhǔn)確的插入到前面已排序的序列中
每次插入碉考，前面已排序的序列很多元素都可能會(huì)發(fā)生挪動(dòng)平均時(shí)間復(fù)雜度：
最好情況：
最壞情況：
空間復(fù)雜度：
排序方式：In-place
穩(wěn)定性：穩(wěn)定
public class InsertionSort {
public static void sort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
int preIndex;
int current;
for (int i = 1; i < arr.length; i++) {
preIndex = i - 1;
current = arr[i];
while (preIndex >= 0 && arr[preIndex] > current) {
// move to right
arr[preIndex + 1] = arr[preIndex];
preIndex--;
}
// insert
arr[preIndex + 1] = current;
}
}
public static void main(String[] args) {
int[] arr = new int[]{9, 1, 8, 2, 7, 3, 6, 4, 5, 0, 2, 8, 4, 7};
sort(arr);
}
}
希爾排序
- 希爾排序可以視作冒泡排序或者插入排序的泛化
- 根據(jù)間隙序列，對(duì)原始序列進(jìn)行分組挺身，然后應(yīng)用插入排序
- 例如：希爾間隙序列為
第一個(gè)分組的步長(zhǎng)為，應(yīng)用插入排序
第二個(gè)分組的步長(zhǎng)為锌仅，應(yīng)用插入排序
......
最后一個(gè)分組的步長(zhǎng)為 1章钾，應(yīng)用插入排序希爾排序，發(fā)明者 Donald Shell
希爾排序有很多著名的間隙序列热芹，不同間隙序列的希爾排序的時(shí)間復(fù)雜度也不同
參考 https://en.wikipedia.org/wiki/Shellsort 的 Gap sequences平均時(shí)間復(fù)雜度：依賴間隙序列
最好情況：贱傀、
最壞情況：、
空間復(fù)雜度：
排序方式：In-place
穩(wěn)定性：不穩(wěn)定
public class ShellSort {
public static void shellSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
// 希爾增量伊脓，間隙序列 N/(2^k)府寒，最壞時(shí)間復(fù)雜度是 O(n^2)
for (int step = arr.length >> 1; step > 0; step >>= 1) {
sort(arr, step);
}
}
public static void hibbardSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
// Hibbard 增量，間隙序列 2^k-1报腔，最壞時(shí)間復(fù)雜度是 O(n^(3/2))
for (int k = (int) Math.sqrt(arr.length + 1); k > 0; k--) {
int step = (int) Math.pow(2, k) - 1;
sort(arr, step);
}
}
// insertion sort with step
private static void sort(int[] arr, int step) {
int preIndex;
int current;
for (int i = step; i < arr.length; i += step) {
preIndex = i - step;
current = arr[i];
while (preIndex >= 0 && arr[preIndex] > current) {
arr[preIndex + step] = arr[preIndex];
preIndex -= step;
}
arr[preIndex + step] = current;
}
}
public static void main(String[] args) {
int[] arr = new int[]{9, 1, 8, 2, 7, 3, 6, 4, 5, 0, 2, 8, 4, 7};
shellSort(arr);
hibbardSort(arr);
}
}
歸并排序
- 將序列從中間分割株搔，遞歸直到只剩 1 個(gè)元素
- 排序合并序列
平均時(shí)間復(fù)雜度：
最好情況：
最壞情況：
空間復(fù)雜度：
排序方式：Out-place
穩(wěn)定性：穩(wěn)定
與快速排序比較類(lèi)似：
- 歸并排序 先將序列從中間遞歸拆成只剩 1 個(gè)元素，然后排序合并序列
- 快速排序 先把基準(zhǔn)元素放到正確的位置纯蛾，然后將序列拆成左右序列纤房，遞歸排序
- 但是，歸并排序的時(shí)間復(fù)雜度是固定的翻诉。因?yàn)闅w并排序總是從中間拆開(kāi)炮姨，而快速排序的基準(zhǔn)元素的正確位置卻不一定在中間捌刮，最壞情況是在端點(diǎn)。
public class MergeSort {
public static int[] sort(final int[] arr) {
if (arr.length < 2) {
return arr;
}
int middle = (int) Math.floor(arr.length / 2.0);
// left
int[] left = sort(Arrays.copyOfRange(arr, 0, middle));
// right
int[] right = sort(Arrays.copyOfRange(arr, middle, arr.length));
// merge
return merge(left, right);
}
private static int[] merge(final int[] left, final int[] right) {
int[] result = new int[left.length + right.length];
int index = 0;
int leftIndex = 0;
int rightIndex = 0;
// merge
while (leftIndex < left.length && rightIndex < right.length) {
if (left[leftIndex] <= right[rightIndex]) {
result[index++] = left[leftIndex++];
} else {
result[index++] = right[rightIndex++];
}
}
// fill
while (leftIndex < left.length) {
result[index++] = left[leftIndex++];
}
// fill
while (rightIndex < right.length) {
result[index++] = right[rightIndex++];
}
return result;
}
public static void main(String[] args) {
int[] arr = new int[]{9, 1, 8, 2, 7, 3, 6, 4, 5, 0, 2, 8, 4, 7};
arr = sort(arr);
}
}
快速排序
- 將基準(zhǔn)值放到正確的位置舒岸，假設(shè)該位置的索引為 pivot
- 基準(zhǔn)值绅作，一般選擇 arr[low]
- 以 pivot 為中心，將 arr 分為兩部分蛾派，進(jìn)行步驟 1
平均時(shí)間復(fù)雜度：
最好情況：
最壞情況：
空間復(fù)雜度：
排序方式：In-place
穩(wěn)定性：不穩(wěn)定提示
在 Java 中俄认，不做額外的配置，2 萬(wàn)個(gè)數(shù)據(jù)左右的快速排序碍脏，就會(huì)發(fā)生 StackOverflowError 異常梭依。這與斐波那契遞歸不同，因?yàn)槲策f歸很容易被 JIT 優(yōu)化掉典尾，用斐波那契遞歸測(cè)編程語(yǔ)言的性能役拴，你甚至能得到 Java 性能比 C/C++ 高的錯(cuò)誤結(jié)論。
實(shí)現(xiàn) 1
public class QuickSort {
public static void sort(int[] arr, int low, int high) {
if (low < high) {
// partition
int pivot = partition(arr, low, high);
// left
sort(arr, low, pivot - 1);
// right
sort(arr, pivot + 1, high);
}
}
private static int partition(int[] arr, int low, int high) {
int pivot = arr[low];
while (low != high) {
// right
while (low < high && arr[high] >= pivot) {
high--;
}
arr[low] = arr[high];
// left
while (low < high && arr[low] <= pivot) {
low++;
}
arr[high] = arr[low];
}
arr[low] = pivot;
return low;
}
public static void main(String[] args) {
int[] arr = new int[]{9, 1, 8, 2, 7, 3, 6, 4, 5, 0, 2, 8, 4, 7};
sort(arr, 0, arr.length - 1);
}
}
堆排序
基礎(chǔ)知識(shí)
堆滿足下面條件
- 堆是一顆完全二叉樹(shù)（自己額外補(bǔ)習(xí)）钾埂，可以與一維數(shù)組相互轉(zhuǎn)換
- 大頂堆：每個(gè)節(jié)點(diǎn)的值都大于或等于其子節(jié)點(diǎn)的值河闰，用于升序排列
- 小頂堆：每個(gè)節(jié)點(diǎn)的值都小于或等于其子節(jié)點(diǎn)的值，用于降序排列
- 先將序列轉(zhuǎn)為大頂堆（小頂堆）
- 將根節(jié)點(diǎn)與最后的節(jié)點(diǎn)交換位置
- 如果是大頂堆褥紫，交換后姜性，最后元素的值為最大值
- 如果是小頂堆，交換后髓考，最后元素的值為最小值
- 此時(shí)只需要將數(shù)組長(zhǎng)度減 1部念，重復(fù)上述步驟即可完成排序
平均時(shí)間復(fù)雜度：
最好情況：
最壞情況：
空間復(fù)雜度：
排序方式：In-place
穩(wěn)定性：不穩(wěn)定
其中，heapifyUp 方法在堆排序中是沒(méi)有必要的氨菇，保留只是個(gè)人想記錄一下儡炼。
public class HeapSort {
public static void sort(final int[] arr) {
if (arr.length < 2) {
return;
}
int len = arr.length;
// 構(gòu)建堆，因?yàn)楹罄m(xù)的操作要求必須是堆
buildHeap(arr, len);
for (int size = len - 1; size > 0; size--) {
// 首尾交換
int tmp = arr[0];
arr[0] = arr[size];
arr[size] = tmp;
// 交換后查蓉，此時(shí)不是一個(gè)堆了乌询，所以需要執(zhí)行 heapify 操作
// 而最后的元素是已排序的，所以這里用 size豌研，而不是 len
heapifyDown(arr, size, 0);
}
}
private static void buildHeap(final int[] arr, int size) {
// 從尾到首執(zhí)行 heapify 操作
// 因?yàn)槿~子節(jié)點(diǎn)沒(méi)有 left 和 right 子節(jié)點(diǎn)妹田，沒(méi)有向下執(zhí)行 heapify 的必要
// 因此可以優(yōu)化成，從最后一個(gè)元素的 parent（即 [size / 2] - 1）開(kāi)始
for (int i = (int) (Math.floor(size / 2.0) - 1); i >= 0; i--) {
heapifyDown(arr, size, i);
}
}
/**
* 向上執(zhí)行 heapify 操作鹃共。適用場(chǎng)景：原先必須是一個(gè)堆鬼佣，并且僅有索引為 index 的元素發(fā)生了變化。
*
* @param arr 完全二叉樹(shù)
* @param size 二叉樹(shù)的大小
* @param index 開(kāi)始節(jié)點(diǎn)的索引
*/
private static void heapifyUp(final int[] arr, final int size, int index) {
while (index < size) {
// parent exists || already a heap
int parentIndex = (int) Math.floor((index - 1) / 2.0);
if (parentIndex < 0 || arr[parentIndex] >= arr[index]) {
return;
}
// swap
int tmp = arr[index];
arr[index] = arr[parentIndex];
arr[parentIndex] = tmp;
// update index
index = parentIndex;
}
}
/**
* 向下執(zhí)行 heapify 操作及汉。適用場(chǎng)景：原先必須是一個(gè)堆沮趣，并且僅有索引為 index 的元素發(fā)生了變化。
*
* @param arr 完全二叉樹(shù)
* @param size 二叉樹(shù)的大小
* @param index 開(kāi)始節(jié)點(diǎn)的索引
*/
private static void heapifyDown(final int[] arr, final int size, int index) {
while (index < size) {
// left child not exists
int leftIndex = 2 * index + 1;
if (leftIndex >= size) {
return;
}
int largerIndex;
int rightIndex = 2 * index + 2;
// right child exists && larger than left child
if (rightIndex < size && arr[leftIndex] < arr[rightIndex]) {
largerIndex = rightIndex;
} else {
largerIndex = leftIndex;
}
// already a heap
if (arr[index] >= arr[largerIndex]) {
return;
}
// swap
int tmp = arr[largerIndex];
arr[largerIndex] = arr[index];
arr[index] = tmp;
// update index
index = largerIndex;
}
}
public static void main(String[] args) {
int[] arr = new int[]{9, 1, 8, 2, 7, 3, 6, 4, 5, 0, 2, 8, 4, 7};
sort(arr);
}
}
