排序算法实现
记录排序算法的实现，有空就记录一点。
冒泡排序
- 比较相邻元素，如果第一个元素大于第二个元素，那么交换它们
- 完成上述步骤后，最后的元素是已排序的元素
- 对剩余未排序的元素重复上述步骤
- 排序过程中，如果没有发生至少一次交换，那么完成排序
平均时间复杂度：
最好情况：
最坏情况：
空间复杂度：
排序方式：In-place
稳定性：稳定
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);
}
}
选择排序
- 在未排序的序列中找出最小（大）元素，存放到已排序的序列的末尾
- 再从剩余未排序元素中继续重复上述步骤
平均时间复杂度：
最好情况：
最坏情况：
空间复杂度：
排序方式：In-place
稳定性：不稳定
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);
}
}
插入排序
- 从第二个元素开始，循环到序列结束
- 将每一个元素准确的插入到前面已排序的序列中
每次插入，前面已排序的序列很多元素都可能会发生挪动平均时间复杂度：
最好情况：
最坏情况：
空间复杂度：
排序方式：In-place
稳定性：稳定
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);
}
}
希尔排序
- 希尔排序可以视作冒泡排序或者插入排序的泛化
- 根据间隙序列，对原始序列进行分组，然后应用插入排序
- 例如：希尔间隙序列为
第一个分组的步长为，应用插入排序
第二个分组的步长为，应用插入排序
......
最后一个分组的步长为 1，应用插入排序希尔排序，发明者 Donald Shell
希尔排序有很多著名的间隙序列，不同间隙序列的希尔排序的时间复杂度也不同
参考 https://en.wikipedia.org/wiki/Shellsort 的 Gap sequences平均时间复杂度：依赖间隙序列
最好情况：、
最坏情况：、
空间复杂度：
排序方式：In-place
稳定性：不稳定
public class ShellSort {
public static void shellSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
// 希尔增量，间隙序列 N/(2^k)，最坏时间复杂度是 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，最坏时间复杂度是 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 个元素
- 排序合并序列
平均时间复杂度：
最好情况：
最坏情况：
空间复杂度：
排序方式：Out-place
稳定性：稳定
与快速排序比较类似：
- 归并排序 先将序列从中间递归拆成只剩 1 个元素，然后排序合并序列
- 快速排序 先把基准元素放到正确的位置，然后将序列拆成左右序列，递归排序
- 但是，归并排序的时间复杂度是固定的。因为归并排序总是从中间拆开，而快速排序的基准元素的正确位置却不一定在中间，最坏情况是在端点。
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);
}
}
快速排序
- 将基准值放到正确的位置，假设该位置的索引为 pivot
- 基准值，一般选择 arr[low]
- 以 pivot 为中心，将 arr 分为两部分，进行步骤 1
平均时间复杂度：
最好情况：
最坏情况：
空间复杂度：
排序方式：In-place
稳定性：不稳定提示
在 Java 中，不做额外的配置，2 万个数据左右的快速排序，就会发生 StackOverflowError 异常。这与斐波那契递归不同，因为尾递归很容易被 JIT 优化掉，用斐波那契递归测编程语言的性能，你甚至能得到 Java 性能比 C/C++ 高的错误结论。
实现 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);
}
}
堆排序
基础知识
堆满足下面条件
- 堆是一颗完全二叉树（自己额外补习），可以与一维数组相互转换
- 大顶堆：每个节点的值都大于或等于其子节点的值，用于升序排列
- 小顶堆：每个节点的值都小于或等于其子节点的值，用于降序排列
- 先将序列转为大顶堆（小顶堆）
- 将根节点与最后的节点交换位置
- 如果是大顶堆，交换后，最后元素的值为最大值
- 如果是小顶堆，交换后，最后元素的值为最小值
- 此时只需要将数组长度减 1，重复上述步骤即可完成排序
平均时间复杂度：
最好情况：
最坏情况：
空间复杂度：
排序方式：In-place
稳定性：不稳定
其中，heapifyUp 方法在堆排序中是没有必要的，保留只是个人想记录一下。
public class HeapSort {
public static void sort(final int[] arr) {
if (arr.length < 2) {
return;
}
int len = arr.length;
// 构建堆，因为后续的操作要求必须是堆
buildHeap(arr, len);
for (int size = len - 1; size > 0; size--) {
// 首尾交换
int tmp = arr[0];
arr[0] = arr[size];
arr[size] = tmp;
// 交换后，此时不是一个堆了，所以需要执行 heapify 操作
// 而最后的元素是已排序的，所以这里用 size，而不是 len
heapifyDown(arr, size, 0);
}
}
private static void buildHeap(final int[] arr, int size) {
// 从尾到首执行 heapify 操作
// 因为叶子节点没有 left 和 right 子节点，没有向下执行 heapify 的必要
// 因此可以优化成，从最后一个元素的 parent（即 [size / 2] - 1）开始
for (int i = (int) (Math.floor(size / 2.0) - 1); i >= 0; i--) {
heapifyDown(arr, size, i);
}
}
/**
* 向上执行 heapify 操作。适用场景：原先必须是一个堆，并且仅有索引为 index 的元素发生了变化。
*
* @param arr 完全二叉树
* @param size 二叉树的大小
* @param index 开始节点的索引
*/
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;
}
}
/**
* 向下执行 heapify 操作。适用场景：原先必须是一个堆，并且仅有索引为 index 的元素发生了变化。
*
* @param arr 完全二叉树
* @param size 二叉树的大小
* @param index 开始节点的索引
*/
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);
}
}
网友评论