---

前言

算法>排序算法有很多，这里列出最常用的一些，如选择排序、插入、冒泡等。

稳定性：待排序数据中有相同的数，排序之后相同的数与排序前的前后位置关系不变，则成为稳定算法>排序算法。
比如我们有一组数据2,9,3,4,8,3;按照大小排序之后就是2,3,3,4,8,9;两个3的前后顺序在排序前后保持不变，即稳定。

---

一、选择排序

最佳时间复杂度	平均时间复杂度	最坏时间复杂度	稳定性	空间复杂度
O(N^2)	O(N^2)	O(N^2)	不稳定	O(1)

代码：

java">  public void selectSort(int[] arr) {for (int i = 0; i < arr.length - 1; i++) {int min = i;for (int j = i + 1; j < arr.length; j++) {if (arr[min] > arr[j]) {min = j;}}if (min != i) {swap(arr, i, min);}}}private void swap(int[] arr, int i, int j) {int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}

二、插入排序

最佳时间复杂度	平均时间复杂度	最坏时间复杂度	稳定性	空间复杂度
O(N)	O(N^2)	O(N^2)	稳定	O(1)

代码：

java">    public void insertSort(int[] arr) {for (int i = 1; i < arr.length; i++) {int insertNote = arr[i];int j = i - 1;//前一个元素的下标while (j >= 0 && insertNote < arr[j]) {arr[j + 1] = arr[j];j--;}arr[j + 1] = insertNote;}}

三、冒泡排序

最佳时间复杂度	平均时间复杂度	最坏时间复杂度	稳定性	空间复杂度
O(N)	O(N^2)	O(N^2)	稳定	O(1)

代码：

java">    public void bubbleSort(int[] arr) {for (int i = 0; i < arr.length - 1; i++) {boolean swapped = false;for (int j = 0; j < arr.length - 1 - i; j++) {if (arr[j] > arr[j + 1]) {swap(arr, j, j + 1);swapped = true;}}if (!swapped) {break;}}}private void swap(int[] arr, int i, int j) {int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}

四、快速排序

最佳时间复杂度	平均时间复杂度	最坏时间复杂度	稳定性	空间复杂度
O(NlogN)	O(NlogN)	O(N^2)	不稳定	O(logN)

代码：

java">  public void quickSort(int[] arr) {quick(arr, 0, arr.length - 1);}private void quick(int[] arr, int low, int high) {if (low < high) {int pivot = arr[high]; int pivotIndex = low;for (int j = low; j < high; j++) {if (arr[j] < pivot) {swap(arr, pivotIndex++, j);}}swap(arr, pivotIndex, high);quick(arr, low, pivotIndex - 1);quick(arr, pivotIndex + 1, high);}}private void swap(int[] arr, int i, int j) {int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}

五、归并排序

最佳时间复杂度	平均时间复杂度	最坏时间复杂度	稳定性	空间复杂度
O(NlogN)	O(NlogN)	O(NlogN)	稳定	O(N)

代码：

java">public void mergeSort(int[] arr) {mergeSort(arr, 0, arr.length - 1, new int[arr.length]);}private void mergeSort(int[] array, int lo, int hi, int[] aux) {if (lo < hi) {int mid = lo + (hi - lo) / 2;mergeSort(array, lo, mid, aux);mergeSort(array, mid + 1, hi, aux);merge(array, lo, mid, hi, aux);}}private void merge(int[] arr, int lo, int mid, int hi, int[] aux) {if (hi - lo + 1 >= 0) {System.arraycopy(arr, lo, aux, lo, hi - lo + 1);}int leftStartIndex = lo;int rightStartIndex = mid + 1;for (int k = lo; k <= hi; k++) {if (leftStartIndex > mid) {//如果左边元素没了， 直接将右边的剩余元素都合并到到原数组中arr[k] = aux[rightStartIndex++];} else if (rightStartIndex > hi) {//如果右边元素没有了，直接将所有左边剩余元素都合并到原数组中arr[k] = aux[leftStartIndex++];} else if (aux[leftStartIndex] < aux[rightStartIndex]) {//如果左边比右边小，则将左边的元素拷贝到原数组中arr[k] = aux[leftStartIndex++];} else {arr[k] = aux[rightStartIndex++];}}}

六、希尔排序

最佳时间复杂度	平均时间复杂度	最坏时间复杂度	稳定性	空间复杂度
O(N)	O(N^(3/2))	O(N^S)（1<S<2）	不稳定	O(1)

代码：

java">public void shellSort(int[] arr) {for (int gap = arr.length / 2; gap > 0; gap /= 2) {for (int i = gap; i < arr.length; i++) {int insertNote = arr[i];int j = i;while (j >= gap && insertNote < arr[j - gap]) {arr[j] = arr[j - gap];j -= gap;}arr[j] = insertNote;}}}

七、堆排序

最佳时间复杂度	平均时间复杂度	最坏时间复杂度	稳定性	空间复杂度
堆排序	O(NlogN)	O(NlogN)	O(NlogN)	不稳定

代码：

java">  public void heapSort(int[] arr) {log.info("TopMax = {}", top(arr, 5, true));log.info("TopMin = {}", top(arr, 5, false));}private int[] top(int[] input, int topN, boolean topMax) {int[] result = Arrays.copyOf(input, topN);for (int i = 0; i < topN; i++) {int currentIndex = i;while (currentIndex != 0 && topMax ? result[parentIndex(currentIndex)] > result[currentIndex] : result[parentIndex(currentIndex)] < result[currentIndex]) {swap(result, currentIndex, currentIndex = parentIndex(currentIndex));}}for (int i = topN; i < input.length; i++) {if (topMax) {//大顶堆if (input[i] > result[0]) {result[0] = input[i];int from = 0;while ((leftIndex(from) < topN && result[from] > result[leftIndex(from)])|| (rightIndex(from) < topN && result[from] > result[rightIndex(from)])) {if (rightIndex(from) < topN && result[leftIndex(from)] > result[rightIndex(from)]) {swap(result, from, from = rightIndex(from));} else {swap(result, from, from = leftIndex(from));}}}} else {//小顶堆if (input[i] < result[0]) {result[0] = input[i];int from = 0;while ((leftIndex(from) < topN && result[from] < result[leftIndex(from)])|| (rightIndex(from) < topN && result[from] < result[rightIndex(from)])) {if (rightIndex(from) < topN && result[leftIndex(from)] < result[rightIndex(from)]) {swap(result, from, from = rightIndex(from));} else {swap(result, from, from = leftIndex(from));}}}}}return result;}private static int parentIndex(int i) {return (i - 1) / 2;}private static int leftIndex(int i) {return 2 * i + 1;}private static int rightIndex(int i) {return 2 * i + 2;}private void swap(int[] arr, int i, int j) {int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}

总结

算法>排序算法	最佳时间复杂度	平均时间复杂度	最坏时间复杂度	稳定性	空间复杂度
选择排序	O(N^2)	O(N^2)	O(N^2)	不稳定	O(1)
插入排序	O(N)	O(N^2)	O(N^2)	稳定	O(1)
冒泡排序	O(N)	O(N^2)	O(N^2)	稳定	O(1)
快速排序	O(NlogN)	O(NlogN)	O(N^2)	不稳定	O(logN)
归并排序	O(NlogN)	O(NlogN)	O(NlogN)	稳定	O(N)
希尔排序	O(N)	O(N^(3/2))	O(N^S)（1<S<2）	不稳定	O(1)
堆排序	O(NlogN)	O(NlogN)	O(NlogN)	不稳定	O(1)