前言
在数据结构中，排序是非常重要的内容，也是未来面试和笔试的重点。
本文代码是Java
目录
一、插入排序
（一）直接插入排序
将一条记录插入到已排好的有序表中，从而得到一个新的、记录数量增1的有序表。
适用于顺序表、链表
排序过程如下：
代码：
public static void InlineSort(int[] arr){ for (int i = 1; i < arr.length; i++) { if(arr[i] < arr[i-1]){ int tmp = arr[i]; int j = i-1; for (; j >= 0; j--) { if(arr[j]>tmp){ arr[j+1] = arr[j]; }else{ break; } } arr[j+1] = tmp; } } }
时间复杂度：O(n^2)
空间复杂度：O(1)
稳定性：稳定
（二）希尔排序
仅适用于顺序表，不适用于链表
记录按下标的一定增量分组，对每组使用直接插入排序算法排序
排序过程如下：
代码：
public static void shellSort(int[] arr){ int len = arr.length; int d = len/2;//组数，数据之间的间距 while(d >= 1){ for(int i = 0; i < d; i++){ for (int j = i+d; j < len; j+=d) { int tmp = arr[j]; int k = j-d; for (; k >= 0; k-=d) { if(tmp < arr[k]){ arr[k+d] = arr[k]; }else{ break; } } arr[k+d] = tmp; } } d /= 2; } }
时间复杂度：O(n^1.3)
空间复杂度：O(1)
稳定性：不稳定
二、选择排序
（一）选择排序
在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
顺序表和链表都适用
排序过程：
代码：
public static void selectSort(int[] arr){ int left = 0; int right = arr.length-1; while(left < right){ int min = left; int max = right; for (int i = left; i <= right; i++) { if(arr[i] < arr[min]){ min = i; } if(arr[i] > arr[max]){ max = i; } } //交换 swap(arr,min,left); if(left == max){ max = min; } swap(arr,max,right); left++; right--; } } //交换 public static void swap(int[] arr, int s1, int s2) { int tmp = arr[s1]; arr[s1] = arr[s2]; arr[s2] = tmp; }
时间复杂度：O(n^2)
空间复杂度：O(1)
稳定性：不稳定
该排序与数据是否有序无关
（二）堆排序
建立大根堆 -> 把堆顶与最末尾元素交换，直到建立有序的小根堆
排序过程：
代码：
public static void heapSort(int[] arr){ //使arr成为大根堆 int len = arr.length; for (int i = (len-1-1)/2; i >= 0; i--) { shiftDown(arr, i, len-1); } while(len > 0){ //将堆顶与堆末尾交换 swap(arr,0,len-1); len--; shiftDown(arr,0,len-1); } } //向下调整 public static void shiftDown(int[] arr, int parent, int k){ int child = parent*2+1; while(child <= k){ if(child+1<=k && arr[child+1]>arr[child]){ child++; } if(arr[child] > arr[parent]){ swap(arr,parent,child); parent = child; child = parent*2+1; }else{ break; } } } //交换 public static void swap(int[] arr, int s1, int s2){ int tmp = arr[s1]; arr[s1] = arr[s2]; arr[s2] = tmp; }
