本文主要回顾了部分常用排序算法，包括冒泡排序，快速排序，选择排序，插入排序，希尔排序，以及归并排序。
- 稳定性和算法复杂度
稳定性：飞机插毛，即归并排序，基数排序，插入排序，冒泡排序是稳定的。
平均算法复杂度：快堆龟，即快速排序，堆排序，归并排序是nlogn。
参考blog，含gif演示，注意：该文章中的算法有误。
本文主要回顾了部分常用排序算法，包括冒泡排序，快速排序，选择排序，插入排序，希尔排序，以及归并排序。
- 稳定性和算法复杂度
稳定性：飞机插毛，即归并排序，基数排序，插入排序，冒泡排序是稳定的。
平均算法复杂度：快堆龟，即快速排序，堆排序，归并排序是nlogn。
参考blog，含gif演示，注意：该文章中的算法有误。
- 冒泡排序
import java.util.Arrays; public class BubbleSort { public static void main(String[] args) { System.out.println(Arrays.toString(bubbleSort(new int[]{5, 10, 25, 1, 9, 8, 15, 30, 28}))); } private static int[] bubbleSort(int[] arr) { if (arr == null || arr.length <= 0) { return arr; } // 用于记录每一轮排序之后，已经确定位置的元素个数 for (int i = 0; i < arr.length; ++i) { // 注意arr.length - i - 1，因为j从0开始 for (int j = 0; j < arr.length - i - 1; ++j) { // 从小到大 if (arr[j + 1] < arr[j]) { arr[j + 1] = arr[j + 1] + arr[j]; arr[j] = arr[j + 1] - arr[j]; arr[j + 1] = arr[j + 1] - arr[j]; } } } return arr; } } - 快速排序
import java.util.Arrays; public class QuickSort { public static void main(String[] args) { int[] arr = new int[]{15, 8, 9, 20, 1, 18, 3, 9, 11, 22}; System.out.println(Arrays.toString(quickSort(arr, 0, arr.length - 1))); } private static int[] quickSort(int[] arr, int start, int end) { if (arr == null || start < 0 || end >= arr.length || start > end) { return null; } int partitionIndex = partition(arr, start, end); if (partitionIndex > start) { quickSort(arr, start, partitionIndex - 1); } if (partitionIndex < end) { quickSort(arr, partitionIndex + 1, end); } return arr; } // 算法参考geeksforgeeks private static int partition(int[] arr, int start, int end) { // 挖坑，用比对比点小的数来填 int biggerIndex = start - 1; // 随机选择一个数作为对比点 int pivot = (int) (start + Math.random() * (end - start + 1)); // 将对比点置于最后一位 swap(arr, pivot, end); for (int i = start; i < end; ++i) { if (arr[i] >= arr[end]) { biggerIndex++; swap(arr, i, biggerIndex); } } biggerIndex++; // 最后需要将对比点归位 swap(arr, biggerIndex, end); return biggerIndex; } private static void swap(int[] arr, int i, int j) { // 如果不加此条件，会出现置换0的情况 if (i == j) { return; } arr[j] = arr[j] + arr[i]; arr[i] = arr[j] - arr[i]; arr[j] = arr[j] - arr[i]; } } - 选择排序
import java.util.Arrays; public class SelectionSort { public static void main(String[] args) { System.out.println(Arrays.toString(selectionSort(new int[]{8, 19, 22, 1, 38, 2, 56, 9, 10, 34}))); } private static int[] selectionSort(int[] arr) { if (arr.length <= 0) { return arr; } // 用于控制位置 for (int i = 0; i < arr.length; ++i) { int minIndex = i; // 每次选最小的替换第一位 for (int j = i + 1; j < arr.length; ++j) { if (arr[j] < arr[minIndex]) { minIndex = j; } } int temp = arr[minIndex]; arr[minIndex] = arr[i]; arr[i] = temp; } return arr; } }
最稳定，无论什么数据，时间复杂度都是n^2。
- 插入排序
import java.util.Arrays; public class InsertionSort { public static void main(String[] args) { System.out.println(Arrays.toString(insertionSort(new int[]{2, 11, 28, 4, 81, 8, 20, 33, 15, 29}))); } private static int[] insertionSort(int[] arr) { if (arr.length <= 0) { return arr; } int current; for (int i = 0; i < arr.length - 1; ++i) { current = arr[i + 1]; int preIndex = i; while (preIndex >= 0 && current < arr[preIndex]) { // 前插，所有数据后移 arr[preIndex + 1] = arr[preIndex]; preIndex--; } arr[preIndex + 1] = current; // 插入 } return arr; } } - 希尔排序
import java.util.Arrays; public class ShellSort { public static void main(String[] args) { System.out.println(Arrays.toString(shellSort(new int[]{33, 18, 2, 30, 21, 8, 9, 65, 29, 38}))); } private static int[] shellSort(int[] arr) { if (arr.length <= 0) { return null; } int temp, gap = arr.length / 2; // 以数组长度的一半作为距离 while (gap > 0) { for (int i = gap; i < arr.length; ++i) { temp = arr[i]; int preIndex = i - gap; while (preIndex >= 0 && arr[preIndex] > temp) { // 同一代内排序，前插 arr[preIndex + gap] = arr[preIndex]; preIndex -= gap; } arr[preIndex + gap] = temp; } gap /= 2; } return arr; } } - 归并排序
import java.util.Arrays; public class MergeSort { public static void main(String[] args) { System.out.println(Arrays.toString(mergeSort(new int[]{18, 28, 8, 11, 20, 37, 52, 1, 89, 21}))); } private static int[] mergeSort(int[] array) { if (array.length < 2) { return array; } int mid = array.length / 2; int[] left = Arrays.copyOfRange(array, 0, mid); int[] right = Arrays.copyOfRange(array, mid, array.length); return merge(mergeSort(left), mergeSort(right)); } private static int[] merge(int[] left, int[] right) { int[] result = new int[left.length + right.length]; for (int index = 0, i = 0, j = 0; index < result.length; ++index) { if (i >= left.length) { result[index] = right[j++]; } else if (j >= right.length) { result[index] = left[i++]; } else if (left[i] > right[j]) { result[index] = right[j++]; } else { result[index] = left[i++]; } } return result; } }
本文内容转自冰部落，仅供学习交流，版权归原作者所有，如涉及侵权，请联系删除。 声明： 本平台/个人所提供的关于股票的信息、分析和讨论，仅供投资者进行研究和参考之用。 我们不对任何股票进行明确的买入或卖出推荐。 投资者在做出投资决策时，应自行进行充分的研究和分析，并谨慎评估自己的风险承受能力和投资目标。 投资有风险，入市需谨慎。请投资者根据自身的判断和风险承受能力，自主决策，理性投资。