【JavaGuide】十大经典排序算法总结

冒泡排序

算法步骤

不断的两两比较，这样当前最大的元素总是会排在最后面。所以称为冒泡。

图解算法

代码实现

public static int[] bubbleSort(int[] arr) {// i是排好了几个数for (int i = 1; i < arr.length; i++) {// flag标记当前循环是否调整了顺序，如果没有调整，说明排序完成boolean flag = true;// arr.length - i控制数组尾巴for (int j = 0; j < arr.length - i; j++) {if (arr[j] > arr[j + 1]) {int tmp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = tmp;flag = false;}}if (flag) {break;}}return arr;
}

算法分析

稳定性：稳定
时间复杂度：最佳：$O(n)$ ，最差：$O(n^2)$， 平均：$O(n^2)$
空间复杂度：$O(1)$
排序方式：内部排序

选择排序

算法步骤

不断地选择最小/最大的元素和当前未排序序列的头进行交换

图解算法

代码实现

public static int[] selectionSort(int[] arr) {// 找到的元素放到第i个，未排序序列头for (int i = 0; i < arr.length - 1; i++) {// minIndex记录当前未排序的最小元素的索引int minIndex = i;for (int j = i + 1; j < arr.length; j++) {if (arr[j] < arr[minIndex]) {minIndex = j;}}// 交换if (minIndex != i) {int tmp = arr[i];arr[i] = arr[minIndex];arr[minIndex] = tmp;}}return arr;
}

算法分析

稳定性：不稳定
时间复杂度：最佳：$O(n^2)$ ，最差：$O(n^2)$， 平均：$O(n^2)$
空间复杂度：$O(1)$
排序方式：内部排序

插入排序

算法步骤

就是扑克牌理牌。从前往后读取未排列序列的元素，拿到新元素后从后往前遍历已排序序列找到合适的位置插入。

图解算法

代码实现

public static int[] insertionSort(int[] arr) {for (int i = 1; i < arr.length; i++) {// preindex记录已排序序列的尾int preIndex = i - 1;// current是当前要插入的元素int current = arr[i];while (preIndex >= 0 && current < arr[preIndex]) {// 往后移arr[preIndex + 1] = arr[preIndex];preIndex -= 1;}arr[preIndex + 1] = current;}return arr;
}

算法分析

稳定性：稳定
时间复杂度：最佳：$O(n)$ ，最差：$O(n^2)$， 平均：$O(n^2)$
空间复杂度：$O(1)$
排序方式：内部排序

希尔排序

算法步骤

不断的按照增量来分出子数组的数量，子数组内部进行插入排序，然后缩小增量，减少分子数组的数量，然后接着插入排序，直到增量为1之后再进行一次插入排序即可。

算法图解

代码实现

public static int[] shellSort(int[] arr) {int n = arr.length;int gap = n / 2;while (gap > 0) {for (int i = gap; i < n; i++) {int current = arr[i];int preIndex = i - gap;// 插入排序while (preIndex >= 0 && arr[preIndex] > current) {arr[preIndex + gap] = arr[preIndex];preIndex -= gap;}arr[preIndex + gap] = current;}gap /= 2;}return arr;
}

算法分析

稳定性：不稳定
时间复杂度：最佳：$O(nlogn)$， 最差：$O(n^2)$ 平均：$O(nlogn)$
空间复杂度：$O(1)$
排序方式：内部排序

归并排序

算法步骤

将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。
就是让子数列内部有序，然后让两个子序列段间有序，不断重复直到整个序列有序。

图解算法

代码实现

public static int[] mergeSort(int[] arr) {if (arr.length <= 1) {return arr;}int middle = arr.length / 2;int[] arr_1 = Arrays.copyOfRange(arr, 0, middle);int[] arr_2 = Arrays.copyOfRange(arr, middle, arr.length);return merge(mergeSort(arr_1), mergeSort(arr_2));
}public static int[] merge(int[] arr_1, int[] arr_2) {int[] sorted_arr = new int[arr_1.length + arr_2.length];int idx = 0, idx_1 = 0, idx_2 = 0;while (idx_1 < arr_1.length && idx_2 < arr_2.length) {if (arr_1[idx_1] < arr_2[idx_2]) {sorted_arr[idx] = arr_1[idx_1];idx_1 += 1;} else {sorted_arr[idx] = arr_2[idx_2];idx_2 += 1;}idx += 1;}if (idx_1 < arr_1.length) {while (idx_1 < arr_1.length) {sorted_arr[idx] = arr_1[idx_1];idx_1 += 1;idx += 1;}} else {while (idx_2 < arr_2.length) {sorted_arr[idx] = arr_2[idx_2];idx_2 += 1;idx += 1;}}return sorted_arr;
}

算法分析

稳定性：稳定
时间复杂度：最佳：$O(nlogn)$， 最差：$O(nlogn)$， 平均：$O(nlogn)$
空间复杂度：$O(n)$
排序方式：外部排序

快速排序

算法步骤

从序列中随机挑出一个元素，做为 基准；通过一趟排序将待排序列分隔成独立的两部分，比基准小的在左边，比基准大的在右边，则可分别对这两部分子序列继续进行排序，以达到整个序列有序。

图解算法

代码实现

public static int partition(int[] array, int low, int high) {int pivot = array[high];int pointer = low;for (int i = low; i < high; i++) {if (array[i] <= pivot) {int temp = array[i];array[i] = array[pointer];array[pointer] = temp;pointer++;}System.out.println(Arrays.toString(array));}int temp = array[pointer];array[pointer] = array[high];array[high] = temp;return pointer;
}
public static void quickSort(int[] array, int low, int high) {if (low < high) {int position = partition(array, low, high);quickSort(array, low, position - 1);quickSort(array, position + 1, high);}
}

算法分析

稳定性：不稳定
时间复杂度：最佳：$O(nlogn)$， 最差：$O(n^2)$，平均：$O(nlogn)$
空间复杂度：$O(logn)$
排序方式：内部排序

堆排序

算法步骤

堆排序是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆的性质：即子结点的值总是小于（或者大于）它的父节点。

图解算法

算法分析

稳定性：不稳定
时间复杂度：最佳：$O(nlogn)$， 最差：$O(nlogn)$， 平均：$O(nlogn)$
空间复杂度：$O(1)$
排序方式：内部排序

计数排序

算法步骤