快速导航：

1. 稳定性2 . 插入排序3. 希尔排序4. 选择排序5. 堆排序6 冒泡排序

1. 稳定性

两个相等的数据，如果经过排序后，排序算法能保证其相对位置不发生变化，则我们称该算法是具备稳定性的排序算法。

图中排序后a仍然在b前面，此时这个排序就是稳定的。

常见的排序算法有 ：

2 . 插入排序

步骤：

从第一个元素开始，该元素可以认为已经被排序取下一个元素下标定义为i，并且放到变量tmp中，从已排序的元素序列从后往前扫描如果该元素大于tem，则将该元素移到下一位重复步骤3，直到找到已排序元素中小于等于tem的元素，直接breaktem插入到该元素的后面（array[j+1]=tmp;），如果已排序所有元素都大于tem，则将tem插入到下标为0的位置重复步骤2~5

/*** 直接插入排序* 时间复杂度：O（N^2） 逆序的时候* （最好的情况是O（N）：对于直接插入排序来说，最好的情况就是数组有序的时候）* 根据这个结论：推导出另一个结论：对于直接插入排序来说，数据越有序，越快* 直接插入排序所以也用于其他排序的优化！* 空间复杂度：O（1）* 稳定性：稳定* 一个稳定的排序，可以实现一个不稳定的排序* 但是一个本身就不稳定的排序就不可以变成稳定的排序* 经常使用在 数据量不多 且 整体数据趋于有序了* @param array*/public void insertSort(int[] array){for (int i =1 ; i <array.length ; i++) {int tmp=array[i];int j=i-1;for (; j>=0 ; j--) {if (array[j]>tmp){array[j+1]=array[j];}else {// 只要j回退的时候，遇到了比tmp小的元素，就结束这次的比较break;}}//j回退到了 小于0 的地方array[j+1]=tmp;}}

动图演示如下：

3. 希尔排序

步骤：

先选定一个小于N的整数gap作为第一增量，然后将所有距离为gap的元素分在同一组，并对每一组的元素进行直接插入排序。然后再取一个比第一增量小的整数作为第二增量，重复上述操作…当增量的大小减到1时，就相当于整个序列被分到一组，进行一次直接插入排序，排序完成。

/*** 希尔排序* 时间复杂度：O(N^1.3-N^1.5)* 空间复杂度：O(1)* 稳定性 ： 不稳定的* 看在比较的过程当中，是否发生了跳跃式的交换，如果发生了跳跃式的交换 那么就是不稳定的排序* （基本上没有考过）** @param array* @param gap 组数*/public static void shell(int[] array,int gap){for (int i =gap ; i <array.length ; i++) {int tmp=array[i];int j=i-gap;for (; j>=0 ; j-=gap) {if (array[j]>tmp){array[j+gap]=array[j];}else {// 只要j回退的时候，遇到了比tmp小的元素，就结束这次的比较break;}}//j回退到了 小于0 的地方array[j+gap]=tmp;}}public static void shellSort(int[] array){int gap=array.length;while (gap>1){shell(array,gap);gap/=2;}shell(array,1);}

动图演示如下：

4. 选择排序

思路：

每次从待排序列中选出一个最小值，然后放在序列的起始位置，直到全部待排数据排完即可。

实际上，我们可以一趟选出两个值，一个最大值一个最小值，然后将其放在序列开头和末尾，这样可以使选择排序的效率快一倍。

/*** 选择排序* 时间复杂度：O(N^2)* 空间复杂度：O(1)* 稳定性：不稳定的排序* @param array*/public static void swap(int[] array,int i,int j){int tmp=array[i];array[i]=array[j];array[j]=tmp;}//优化选择排序：每次交换都是当前遍历j时候的最小值public static void selectSort1(int[] array){for (int i = 0; i < array.length; i++) {int minIndex=i;for (int j = i+1; j < array.length ; j++) {if (array[j]<array[minIndex]){minIndex=j;}}swap(array,i,minIndex);}}public static void selectSort(int[] array) {for (int i = 0; i < array.length; i++) {for (int j = i + 1; j < array.length; j++) {if (array[i] > array[j]) {int tmp = array[i];array[i] = array[j];array[j] = tmp;}}}}

动图演示如下 ：

5. 堆排序

基本原理也是选择排序，只是不在使用遍历的方式查找无序区间的最大的数，而是通过堆来选择无序区间的最大的数。

注意： 排升序要建大堆；排降序要建小堆。

堆排序可以参考之前写的一篇博文：堆详解

也可以借鉴大佬的一篇关于堆排的文章，博主看了受益匪浅：堆排序

/*** 堆排序 排升序要建大堆；排降序要建小堆。* 时间复杂度 ：O(N*logN)* 空间复杂度 : O(1)* 稳定性：不稳定的** @param array*/public static void heapSort(int[] array){//1.建堆 O(N)creatHeap(array);int end=array.length-1;//2.交换然后向下调整为大根堆 O(N*logN)while (end>0){swap(array,0,end);shiftDown(array,0,end);end--;}}public static void creatHeap(int[] array){for (int parent = (array.length-1-1)/2; parent >= 0 ; parent--) {shiftDown(array,parent,array.length);}}public static void shiftDown(int[] array,int parent,int len){int child=2*parent+1; //左孩子while (child<len){if (child+1<len && array[child]<array[child+1]){child++; //保证child下标，就是左右孩子最大值下标}if (array[child]>array[parent]){swap(array,child,parent);parent=child;child=2*parent+1;}else {break;}}}

算法图解 ：

6 冒泡排序

原理：

在无序区间，通过相邻数的比较，将最大的数冒泡到无序区间的最后，持续这个过程，直到数组整体有序

思路：

排序一趟可以让最大的数字沉底

排序len-1趟，一趟排序len-1-i次

详细实现看代码

/*** 冒泡排序（未优化）* 时间复杂度：O（N^2）* 空间复杂度：O(1)* 稳定性：稳定的排序* @param array*/public static void bubbleSort(int[] array){for (int i = 0; i < array.length-1; i++) {for (int j = 0; j < array.length-1; j++) {if (array[j]>array[j+1]){swap(array,j,j+1);}}}}/*** 冒泡排序（优化）* 时间复杂度：O（N^2） （最坏的情况）* （最好的情况 ： 有序） O（N）* 空间复杂度：O(1)* 稳定性：稳定的排序* @param array*/public static void bubbleSort2(int[] array){for (int i = 0; i < array.length-1; i++) {boolean flg=false;for (int j = 0; j < array.length-1-i; j++) {if (array[j]>array[j+1]){swap(array,j,j+1);flg=true;}}if (flg==false){//没交换的话说明flg没被制成TRUE，则说明已经有序，可以跳出循环了break;}}}

动图演示如下 ：

如果觉得《【Java】5大排序算法总结（插入排序+希尔排序+选择排序+堆排序+冒泡排序）》对你有帮助，请点赞、收藏，并留下你的观点哦！