经典排序之比较类排序：交换排序（冒泡排序、快速排序）、插入排序（简单插入、希尔排序）、选择排序（简单选择、堆排序）、归并排序

比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn)，因此也称为非线性时间比较类排序。 非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此也称为线性时间非比较类排序。

本文先介绍比较排序的八种算法：

一、交换排序——冒泡排序

时间复杂度：最坏情况下：O(n²)；最好情况下：O(n)；平均：O(n²) 稳定

import java.util.Arrays; public class BubbleSort { public static void main(String[] args) { int[] arr = {2, 3, 23, 43, 19, 25, 87, 23, 41}; arr = bubbleSort(arr); System.out.println(Arrays.toString(arr)); } public static int[] bubbleSort(int[] arr) { for(int i=0; i<arr.length-1; ++i){ for(int j=0; j<arr.length-1-i; ++j){ if(arr[j] > arr[j+1]){ int tmp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = tmp; } } } return arr; } }

二、交换排序——快速排序

import java.util.Arrays; public class QuickSort { public static void main(String[] args) { int[] arr = {2, 3, 23, 43, 19, 25, 87, 23, 41}; arr = quickSort(arr, 0, arr.length-1); System.out.println(Arrays.toString(arr)); } public static int[] quickSort(int[] arr, int low, int high){ int start = low; // 从左往右比较的索引 int end = high; // 从右往左的索引 int key = arr[low]; // 基准值 while(end > start){ // 从右往左比较，直到找到比基准值小的数 while (end>start && arr[end]>=key){ end--; } // 找到了比基准值小的数，交换位置 if(arr[end] < key){ int tmp = arr[end]; arr[end] = arr[start]; arr[start] = tmp; } // 然后从左往右比较，直到找到比基准值大的数 while (end>start && arr[start]<=key){ start++; } // 找到了比基准值大的数，交换位置 if(arr[start]>key){ int tmp = arr[start]; arr[start] = arr[end]; arr[end] = tmp; } } // 完成了一次排序，基准值的位置以及确定，左边的值都比基准值大，右边的值都比基准值小 // 然后分别递归左边序列和右边序列 if (start > low) arr = quickSort(arr, low, start-1); if (end < high) arr = quickSort(arr, end+1, high); return arr; } }

三、插入排序——简单插入排序

---

【数据规模越小或者越有序，简单插入算法越高效】 时间复杂度：最坏情况下：O(n²)；最好情况下：O(n)；平均：O(n²) 简单插入算法 稳定

---

import java.util.Arrays; public class InsertSort { public static void main(String[] args) { int[] arr = {2, 3, 23, 43, 19, 25, 87, 23, 41}; System.out.println(Arrays.toString(arr)); } public static int[] insertSort(int[] arr){ for(int i=1; i<arr.length; i++){ int insertVal = arr[i]; // 插入的数 int index = i - 1; // 准备插入的位置的索引，初始为插入数的前面一位 // 从右往左找比插入数大的数，直到没有大于插入数的数为止 while (index>=0 && insertVal<arr[index]) { // 比插入数大的数统统往前移 arr[index+1] = arr[index]; index--; } arr[index+1] = insertVal; } return arr; } }

四、插入排序——希尔排序

---

希尔排序的时间复杂度跟增量序列有关 不稳定

---

import java.util.Arrays; public class ShellSort { public static void main(String[] args) { int[] arr = {21, 25, 49, 26, 16, 8}; shellSort(arr); System.out.println(Arrays.toString(arr)); } public static void shellSort(int[] arr) { int dk = arr.length/2; while (dk > 0) { shellInsertSort(arr, dk); dk = dk/2; } shellInsertSort(arr, dk); } public static void shellInsertSort(int[] arr, int dk) { for (int i=dk; i<arr.length; i++){ int insertVal = arr[i]; int index = i - dk; while(index >= 0 && arr[index] > insertVal) { arr[index + dk] = arr[index]; index -= dk; } arr[index+dk] = insertVal; } } }

五、选择排序——简单选择排序

import java.text.SimpleDateFormat; import java.util.Arrays; import java.util.Date; public class SelectSort { public static void main(String[] args) { int[] arr = new int[80000]; for(int i=0; i<arr.length; ++i){ arr[i] = (int)(Math.random()*800000); } SimpleDateFormat sdf = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss"); Date date1 = new Date(); String time1 = sdf.format(date1); System.out.println("排序前时间为："+time1); selectSort(arr); System.out.println(Arrays.toString(arr)); Date date2 = new Date(); String time2 = sdf.format(date2); System.out.println("排序前时间为："+time2); } public static void selectSort(int[] arr) { for(int i=0; i<arr.length-1; ++i){ int minIdx = i; for(int j=i; j<arr.length; ++j){ if(arr[j] < arr[minIdx]){ minIdx = j; } } if(i != minIdx) { int temp = arr[i]; arr[i] = arr[minIdx]; arr[minIdx] = temp; } } } }

六、选择排序——堆排序

堆排序详细讲解参考这篇博客

---

因为堆排序无关乎初始序列是否已经排序已经排序的状态，始终有两部分过程，构建初始的大顶堆的过程时间复杂度为O(n)，交换及重建大顶堆的过程中，需要交换n-1次，重建大顶堆的过程根据完全二叉树的性质，[log2(n-1),log2(n-2)…1]逐步递减，近似为nlogn。所以它最好和最坏的情况时间复杂度都是O(nlogn)，空间复杂度O(1)。不稳定

---

import java.util.Arrays; public class HeapSort { public static void main(String[] args) { int[] arr = {2, 3, 73, 12, 93, 23, 36, 21};; heapSort(arr); System.out.println(Arrays.toString(arr)); } public static void heapSort(int[] arr) { if(arr==null || arr.length == 0) { return; } int len = arr.length; // 构建大顶堆，将未排序序列变成一个大顶堆结构的数组 buildMaxHeap(arr, len); // 交换顶堆和当前末尾的节点，重置大顶堆 for (int i=len-1; i>0; i--) { swap(arr, 0, i); len--; heapify(arr, 0, len); } } public static void buildMaxHeap(int[] arr, int len) { // 从最后一个非叶子节点开始遍历，调整节点性质，使之成为大顶堆 for(int i=len/2-1; i>=0; --i) { heapify(arr, i, len); } } public static void heapify(int[] arr, int i, int len) { // 先根据堆性质，找出它左右节点的索引 int left = 2 * i + 1; int right = 2 * i + 2; // 默认当前节点（父节点）为最大值； int largestIdx = i; if (left < len && arr[left] > arr[largestIdx]) { // 如果存在左节点且左节点的值更大，更新最大值的索引 largestIdx = left; } if (right < len && arr[right] > arr[largestIdx]) { // 如果存在右节点且右节点的值更大，更新最大值的索引 largestIdx = right; } if (largestIdx != i) { // 如果最大值不是当前父节点的值，那么就把当前父节点的值与是最大值的子节点的值交换 swap(arr, i, largestIdx); // 因为互换之后，子节点的值变了，如果该子节点也有自己的子节点，则任需递归调整 heapify(arr, largestIdx, len); } } public static void swap(int[] arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } }

七、归并排序

归并排序是一种稳定的排序方法。和选择排序一样，归并排序的性能不受输入数据的影响，但表现比选择排序好的多，因为始终都是O(nlogn) 的时间复杂度。代价是需要额外的内存空间。

import java.util.Arrays; public class MergeSort { public static void main(String[] args) { int[] arr = {2, 3, 23, 43, 19, 25, 87, 23, 41}; int[] temp = new int[arr.length]; mergeSort(arr, 0, arr.length-1, temp); System.out.println(Arrays.toString(arr)); } public static void mergeSort(int[] arr, int left, int right, int[] temp) { if (left < right) { int mid = (right + left) / 2; // 中间索引 // 向左递归进行分解 mergeSort(arr, left, mid, temp); // 向右递归进行分解 mergeSort(arr, mid+1, right, temp); // 合并 merge(arr, left, mid, right, temp); } } public static void merge(int[] arr, int left, int mid, int right, int[] temp) { int i = left; int j = mid+1; int t = 0; while (i<=mid && j<=right) { if (arr[i] <= arr[j]){ temp[t] = arr[i]; i++; t++; } else { temp[t] = arr[j]; j++; t++; } } while (i <= mid) { temp[t] = arr[i]; i++; t++; } while (j <= right) { temp[t] = arr[j]; j++; t++; } int s = 0; for(int w=left; w<=right; ++w) { arr[w] = temp[s]; s++; } } }