排序作为最入门的算法，说简单也简单，但是初学者不好想象。下面就做一介绍。 针对于排序算法，我主要关注的点是： 1.代码实现（参杂一些个人的理解） 2.时间，空间复杂度（概念就不介绍了） 3.稳定性 ps：稳定的排序，可以通过代码变成不稳定，不稳定的排序无法变成稳定。界定稳定有一个比较好的办法就是判断有没有跳跃式交换，如果有那么就是不稳定的。如果没有就是稳定的。（这是一个小点，后面会有介绍） 1.直接插入排序 思想：接牌思想，第一个数据默认有序，从第二个数据开始遍历。每次把插入的值放入到tmp中，从它的前一个下标开始比，如果小于前一个值那么，把前一个值放在当前位置。然后j–，再比较再前一个位置，如果tmp的值还是小，那么重复，直到tmp遇到一个比它小的值，因为此时j已经–了，所以要放在j+1位置处。 时间复杂度：最坏的情况降序是O (n2)，如果是最好的情况已经有序，则是O（n） 空间复杂度：空间复杂度是O(1)申请了tmp 稳定性：稳定 特点：越有序越快
public static int[] insertSort(int []arr){ int tmp=0; for (int i = 1; i <arr.length ; i++) { tmp=arr[i]; int j=i-1; while (j>-1){ if (arr[j]>tmp){ arr[j+1]=arr[j]; }else { break;//如果tmp 的值已经比前一个大了，说明tmp已经找到了位置，并且可以保证该位置前面的元素都比他小， //直接跳出循环即可 } j--; } arr[j+1]=tmp; } return arr; }插入排序，因为每次插入都要与前面的有序数组进行比较，所以如果优化，可以通过折半方法进行优化。在有序数组定义一个mid。折半查询快速的多。
2.希尔排序 引入希尔排序，是因为在快排的条件下还是效率比较低，希尔的本质就是分组思想,分组的思想适用于多种优化。 思想：分组排序之后，因为直接插入排序是越有序越快，所以分组后，先细致分组，再慢慢扩大分组。然后再进行最后一次排序，比直接插入排序快的多。
分组举例：（15个数组，分5组）
时间复杂度：平均O（n1.3-1.5），最好O（n），最坏O（n2）很难构造 空间复杂度：空间复杂度是O(1)申请了tmp 稳定性：不稳定 特点：分组排序使得插入排序越来越快
public static int[] xierSort(int []arr){ int tmp=0; int[]drr=new int[]{5,3,1}; for (int s = 0; s < drr.length; s++) { for (int i = drr[s]; i < arr.length; i++) { //为什么不是i+gap？是因为+gap，只能保证一组插排结束，所以还是+1，保证每组都排序 tmp = arr[i]; int j = i - drr[s]; while (j > -1) { if (arr[j] > tmp) { arr[j + drr[s]] = arr[j]; } else { break; } j = j - drr[s]; } arr[j + drr[s]] = tmp; } } return arr; }3.选择排序 思想：选择排序的基本思想是，从第一个位置开始。每次与该位置之后的元素作比较，如果大于后面元素则交换 ，直到遍历完该位置后边的所有元素再遍历第二个位置以此类推，选择小数据和当前数据交换 时间复杂度：O（n2），不管有无顺序都会遍历比较 空间复杂度：O（1），申请了额外的tmp空间 稳定性：不稳定
public static int [] selectSort(int []arr){ for (int i = 0; i <arr.length ; i++) { for (int j = i+1; j <arr.length ; j++) { if (arr[i]>arr[j]){ int tmp=arr[i]; arr[i]=arr[j]; arr[j]=tmp; } } } return arr; }4.堆排序（升序为例） 思想：堆排，如果升序需要建立一个大根堆，因为大根堆有父节点一定大于子节点的性质，所以建立大根堆后，需要最后一个元素和0号下标呼唤，然后向下调整成大根堆，继续调整。 时间复杂度：建堆的时间复杂度O（n），O（log n） 空间复杂度：O（1） 稳定性：不稳定 特点：利用二叉堆
public int[] elem;//底层是一个数组 public int usedSize;//存放数据个数 //堆排序 //1.建堆 //从最后一棵子树的根节点开始遍历，创造堆 public void createHeap(int[] arr) { for (int i = 0; i < arr.length; i++) { this.elem[i] = arr[i]; this.usedSize++; } } public void heapSort ( int[] arr){ int end = arr.length - 1; while (end > 0) { int tmp = arr[0]; arr[0] = arr[end]; arr[end] = tmp; adjustDown(0, end); end--; } } public void adjustDown ( int root, int len){//root代表每个子树的开始位置，len代表的是结束位置。 int parent = root; int child = 2 * parent + 1;//左孩子 while (child < len) {//孩子节点的下标一定会小于等总节点的数量-1。 if (child + 1 < len) { //有右孩子 if (elem[child] < elem[child + 1]) {//找到左右孩子的最大值，child保存最大孩子的坐标 child = child + 1; } } //比较child节点和父节点的值，如果大则交换 if (elem[child] > elem[parent]) { int tmp = elem[child]; elem[child] = elem[parent]; elem[parent] = tmp; parent = child; child = 2 * parent + 1; } else {//如果小则不用交换，说明已经调整好了 break; } } }ps：堆排序处理topK问题。找出海量数据的前k个最大或者最小的数据。 eg：前K个最小的元素，建立一个容量为K的大根堆。首先取k个元素建成一个大根堆，接下来遍历剩下的元素，如果遍历的元素比堆定小，就把堆定pop，放入该元素，再调整为大根堆，继续遍历。时间复杂度n*（log 2 k）。 5.冒泡排序 思想：冒泡排序和选择排序非常相像，选择是每个元素和该元素位置后所有元素比较，如果大于后边的元素则交换，而冒泡是每两个相邻的元素进行比较。 时间复杂度：O（n2），有序到达O（n），优化过 空间复杂度：O（1） 稳定性：稳定 特点：相邻的去比较
public static void bubbleSort (int[]arr){ for (int i = 0; i <arr.length ; i++) { boolean flag=false;//进行优化 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; flag=true; } } if (flag==false){//如果一趟走下来没有发生交换则说明已经有序 return; } } }6.快速排序 思想：从待排序的区间选择一个树，作为基准值。遍历整个区间，将比基准值小的放到基准值的左边，比基准值大的放到基准值的右边，采用分治的思想，对左右两个小区间按照同样的方式处理，直到区间长度等于1，则代表有序。区间长度等于0则表示没有数据。 递归+不断找新的基准。什么时候递归满足left==right就代表递归完了。 时间复杂度：O（n log 2 n），快排效率最高，每次划分序列都可以均匀的划分，如果是升序或者逆序数列，每个点都会走一遍，此时时间复杂度就是O（n 的平方） 空间复杂度：递归会保护现场所以每次递归会申请tmp临时空间。最好O（log n），最坏O（n） 稳定性：不稳定 特点：递归+找基准
public static int partition(int[] arr, int left, int right){ int tmp=arr[left]; while (left<right){ while (left<right&&arr[right]>=tmp){//找到右边比tmp小的值 right--; } arr[left]=arr[right];//把当前位置赋值这个找到的小的值 while (left<right&&arr[left]<=tmp) {//找到左边比tmp大的值 left++; } arr[right]=arr[left];//把当前位置赋值给这个找到的大的值 } arr[left]=tmp; return left; } public static void quick(int []arr,int left,int right){ if (left>=right){ return; } int par=partition(arr,left,right); quick(arr,left,par-1); quick(arr,par+1,right); } public static void quickSort(int []arr){ quick(arr,0,arr.length-1); }**PS：堆排和快排的区别：堆排空间复杂度低，快排时间复杂度高。实际上快排还是比堆排快，因为时间复杂度O（n log 2 n）前的倍数不一样
快排再优化直接插入排序。1.如果递归的区间比较小，可以直接插入排序。2.保证基准是中位数。保证两边均匀**
非递归的版本需要用栈
7.归并排序 思想：分治思想，将数组分成若干小数组，等小数组有序合并，最后得到完成的有序数组。通常是二路归并。
时间复杂度：O（n*log n） 空间复杂度：O（n） 稳定性：稳定 特点：分解再合并，主要是合并的步骤
public static void mergeSort(int []arr){ merge1(arr,0,arr.length-1); } private static void merge1(int []arr, int left, int right) {//分解方法 if (left>=right){ return; } int mid=(left+right)/2; merge1(arr,left,mid); merge1(arr,mid+1,right);//两个递归走完代表已经分解成一个一个元素 merge2(arr,mid,left,right);//合并 } private static void merge2(int[] arr, int mid, int left, int right) {//归并方法 int s1=left; int s2=mid+1; int len=right-left+1; int[]ret=new int[len];//归并需要最大的空间，来存储每次归并后的数组 int i=0; while (s1<=mid&&s2<=right){ //证明两段都有数据 if (arr[s1]<=arr[s2]){ ret[i++]=arr[s1++]; }else { ret[i++]=arr[s2++]; } } while (s1<=mid){ ret[i++]=arr[s1++]; } while (s2<=right){ ret[i++]=arr[s2++]; } for (int j = 0; j <ret.length ; j++) {//进行数组拷贝 arr[j+left]=ret[j]; } }