本文主要回顾了部分常用排序算法，包括冒泡排序，快速排序，选择排序，插入排序，希尔排序，以及归并排序。
- 稳定性和算法复杂度
稳定性：飞机插毛，即归并排序，基数排序，插入排序，冒泡排序是稳定的。
平均算法复杂度：快堆龟，即快速排序，堆排序，归并排序是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 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 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;}// 算法参考geeksforgeeksprivate 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 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 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;}}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; } }
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 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 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 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 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;}}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; } }
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; } }
本文内容转自冰部落，仅供学习交流，版权归原作者所有，如涉及侵权，请联系删除。 声明： 本平台/个人所提供的关于股票的信息、分析和讨论，仅供投资者进行研究和参考之用。 我们不对任何股票进行明确的买入或卖出推荐。 投资者在做出投资决策时，应自行进行充分的研究和分析，并谨慎评估自己的风险承受能力和投资目标。 投资有风险，入市需谨慎。请投资者根据自身的判断和风险承受能力，自主决策，理性投资。