一、排序的概述
排序就是将一组乱序的数据集合变得有序
排序可以分为：
内部排序：数据全部存放在内存中进行排序。
外部排序：数据太多而不能全部存放在内存，整个排序·过程需要在内外存之间多次交换数据才能进行。
根据排序的策略分为：插入排序、选择排序、交换排序和归并排序。
衡量排序的性能指标：
- 时间复杂度。
- 空间复杂度。
- 稳定性：就是排序前后两个相同元素的相对位置保持不变。一个稳定的算法可以变得不稳定，但是一个不稳定的算法不能变得稳定。
排序在我们日常生活中有很多的应用，例如在购物页面可以选择价格从低到高排序，导航时路程可以根据预测花费时间进行排序。
对于排序算法的时间性能测试，采用如下代码：
public static long testTime(int[] array){ int[] nums = Arrays.copyOf(array, array.length); long begin=System.currentTimeMillis(); sort(nums);//排序算法 long end=System.currentTimeMillis(); return end - begin; }
二、插入排序
1、直接插入排序
算法思想：就是将待排序的元逐个插入到已将排好序的序列的合适位置，该算法就像扑克牌游戏，每次拿到牌就将牌插入到已排好序的牌的合适位置。
动图演示：
代码实现：
public static void insertSort(int[] array){ for(int i=1;i<array.length;i++){ int temp=array[i]; int j=i-1; for(;j>=0;j--){ if(array[j]>temp){ array[j+1]=array[j]; }else{ break; } } array[j+1]=temp; } }
性能分析：
- 时间复杂度：O(n^2)。
- 空间复杂度：O(1)。
- 稳定性：稳定，因为当待插入的元素小于排好序的序列中的元素时才会进行交换，如果相等就不会进行交换，那么连个相同元素的相对位置保持不变。
2、希尔排序
算法思想：按照下标的一定增量进行的分组，对每组使用直接插入排序，增量逐渐减少，当增量减少为1时，整体再进行一次直接插入排序。
过程演示：
动图演示：
代码实现：
// 希尔排序 public static void shellSort(int[] array){ int gap=array.length/3+1; while(gap>1){ shell(array,gap); gap=gap/3+1; } shell(array,gap); } private static void shell(int[] array,int gap){ for(int i=gap;i<array.length;i++){ int temp=array[i]; int j=i-gap; for(;j>=0;j=j-gap){ if(array[j]>temp){ array[j+gap] = array[j]; }else{ break; } } array[j+gap]=temp; } }
性能分析：
- 时间复杂度：O(n^1.3)~O(n^1.5)。
- 空间复杂度：O(1)
- 稳定性：不稳定，因为是先分组排序，两个值相等的元素不在一组那么相对顺序就可能发生改变。
二、选择排序
1、直接选择排序
算法思想：每次从待排序的序列中选出一个最小的元素与与序列的起始位置进行交换，直到全部元素排序完成。
动图演示：
代码实现：
public static void selectSort(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; } } int temp=array[i]; array[i]=array[minIndex]; array[minIndex]=temp; } }
性能分析 ：
- 时间复杂度：O(n^2)
- 空间复杂度：O(1)
- 稳定性：不稳定，因为选择排序会和序列的起始位置发生交换，就可能导致不稳定。
2、堆排序
算法思想：对数组内部进行排序，不能弹出堆顶元素来进行排序，所以如果要使元素从小到大进行排序就将堆顶元素与最后一个元素交换，每次交换完之后最后一个元素就不再改变，指向下调整堆之后，堆顶与上一个最后元素的前一个元素进行交换，依次类推，直到所有位置的元素都已确定。
动图演示：
代码实现：
// 堆排序 public static void heapSort(int[] array){ createHeap(array); int end=array.length-1; for(int i=end;i>0;i--){ int temp=array[i]; array[i]=array[0]; array[0]=temp; shiftDown(array,0,end); end--; } } //创建堆 private static void createHeap(int[] array){ for(int i=(array.length-1-1)/2;i>=0;i--){ shiftDown(array,i,array.length); } } //向下调整 private static void shiftDown(int[] array,int parent,int len){ int child=2*parent+1; while (child < len){ if(child+1 < len &&array[child+1] > array[child]){ child++; } if(array[child]>array[parent]){ int temp=array[child]; array[child]=array[parent]; array[parent]=temp; parent=child; child=2*parent+1; }else{ break; } } }
三、交换排序
1、冒泡排序
算法思想：相邻元素两两进行比较，若发生逆序就进行交换，直至待排序的元素序列中没有逆序。
动图演示：
代码实现：
1.
public static void bubbleSort(int[] array){ for(int i=0;i<array.length;i++){ boolean flag=true; for(int j=0;j<array.length-i-1;j++){ if(array[j]>array[j+1]){ int temp=array[j]; array[j]=array[j+1]; array[j+1]=temp; flag=false; } } if(flag){ break; } } }
性能分析：
- 时间复杂度：O(n^2)。
- 空间复杂度：O(1)。
- 稳定性：稳定。
一文带你秒懂十大排序（下）：https://developer.aliyun.com/article/1521565
