五种排序算法的比较：
冒泡排序、插入排序、选择排序均是原地排序，即空间复杂度为O(1)，平均时间复杂度O(n^2) 其中选择排序最好最坏均是O(n*n)，但它不是稳定的，因此不如插入排序更受欢迎/******************************************** * All Rights Reserved By www.laughing.ren * @author:Laughing_Lz * @version:2018年11月21日 下午9:47:08 * ******************************************/package ren.laughing.code.Sort;public class Sort { /** * 冒泡排序 * * @param arr arr */ public static void bubbleSort(int[] arr) { int length = arr.length; if (length <= 1) { return; } for (int i = 0; i < length; i++) { for (int j = 0; j < length - i - 1; j++) { // 循环判断，把大数浮上去 if (arr[j + 1] < arr[j]) { // swap int temp = arr[j + 1]; arr[j + 1] = arr[j]; arr[j] = temp; } } } } /** * 插入排序 * * @param arr */ public static void insertSort(int[] arr) { int length = arr.length; if (length <= 1) { return; } for (int i = 0; i < length - 1; i++) { int j = i + 1; int flag = arr[j]; for (; j > 0; j--) { if (arr[j - 1] > flag) { // 每次插入前，较大的其他元素均后移 arr[j] = arr[j - 1]; } else { break; } } arr[j] = flag; } } /** * 选择排序：交换的是位置 * * @param arr */ public static void selectSort(int[] arr) { int length = arr.length; if (length <= 1) { return; } for (int i = 0; i < length - 1; i++) { // 记录最小值的位置 int index = i; for (int j = i + 1; j < length; j++) { if (arr[j] < arr[index]) { index = j; } } // 交换值,不稳定的排序 int temp = arr[i]; arr[i] = arr[index]; arr[index] = temp; } } /** * 归并排序 递归 * * @param arr arr * @param start start * @param end end */ public static void mergeSort(int[] arr, int start, int end) { if (start >= end) { return; } int middle = start + (end - start) / 2; mergeSort(arr, start, middle); mergeSort(arr, middle + 1, end); merge(arr, start, middle, end); } /** * 归并方法,将两个数组归并成一个有序数组 * * @param arr arr * @param start start * @param middle middle * @param end end */ private static void merge(int[] arr, int start, int middle, int end) { // 申请临时空间保存排序后的数组，排序后再还原至原数组arr int[] temp = new int[end - start + 1]; int i = start, j = middle + 1, k = 0; while (i <= middle && j <= end) { if (arr[i] <= arr[j]) { temp[k++] = arr[i++]; } else { temp[k++] = arr[j++]; } } while (i <= middle) { temp[k++] = arr[i++]; } while (j <= end) { temp[k++] = arr[j++]; } // 赋值给原数组 for (int t = 0; t < temp.length; t++) { arr[start + t] = temp[t]; } } public static void quickSort(int[] arr, int start, int end) { if (start >= end) { return; } // 先找出中间点 int partition = partition(arr, start, end); quickSort(arr, start, partition - 1); quickSort(arr, partition + 1, end); } private static int partition(int[] arr, int start, int end) { // 分区点的选取是重点，这里选择末尾的点 int flag = arr[end]; int j = start;// 分区的最终位置 for (int i = start; i < end; i++) { if (arr[i] < flag) { // 交换arr[i]和arr[j] int temp1 = arr[i]; arr[i] = arr[j]; arr[j] = temp1; j++; } } // 交换arr[j]和arr[end] int temp2 = arr[end]; arr[end] = arr[j]; arr[j] = temp2; return j; } public static void main(String[] args) { int[] arr = { 2, 4, 5, 2, 6, 7, 2, 8, 0, 3 }; // bubbleSort(arr); // insertSort(arr); // selectSort(arr); // mergeSort(arr, 0, arr.length - 1); quickSort(arr, 0, arr.length - 1); for (int i = 0; i < arr.length; i++) { System.out.print(arr[i] + " "); } }}复制代码