排序算法（插入，希尔，选择，冒泡，堆，快排，归并）

1.插入排序

插入排序的主要思想是额外申请一个空间cur，让cur一开始等于数组的第1号位置,设置i=1，让i-1的元素与其比较，如果arr[i-1]>arr[i]，就让arr[i+1] = arr[i]，当进行到最后一次对比结束，i=-1,再让arr[i+1] = cur。

​
private static void insertsort(int[] arr) {for (int i = 1; i < arr.length; i++) {int cur = arr[i];int j = i-1;for ( ;j>=0; j--) {if(cur>arr[j]){arr[j+1] = arr[j];}else{break;}}arr[j+1] = cur;}}​

排序算法的特点是序列越有序，时间效率越高，下面的希尔排序也体现出来。

时间复杂度：O(n^2)

空间复杂度：O（1）

是一种稳定的排序算法。

2.希尔排序

希尔排序的思想是设置一个常量gap，将数组每个相距gap距离的两个数进行分组，然后组内进行排序，每进行一次gap排序后，将gap/2，直到gap为1，排序完成。

    private static void shellsort(int[] arr) {int gep = arr.length;while(gep>1){gep/=2;shell(arr,gep);}}private static void shell(int[] arr, int gep) {for(int i = gep;i< arr.length;i++){int cur = arr[i];int j = i-gep;for(;j>=0;j-=gep){if(cur<arr[j]){arr[j+gep] = arr[j];}else{break;}}arr[j+gep] = cur;}}

这里的希尔排序是先拿出gap间距，进行直接插入排序，所以shell方法的实现和插入排序相似。

希尔排序是对插入排序的优化，当gap>1时，都是对序列有序化，直到gap=1时，数组已经趋于有序，就会排序很快，对于整体来说，就有一个优化的效果。

希尔排序的时间复杂度不好计算，因为每次数组长度不确定，gap的取值不确定。

希尔排序的稳定性：不稳定。                                                                           

3.选择排序

选择排序非常好理解，类似于打擂台，取出一个元素，将它设置为擂主，依次取后面的元素进行比较，如果小于擂主，就进行交换，如果大于，就继续遍历，直到遍历结束。

private static void 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 tem = arr[i];arr[i] = arr[j];arr[j] = tem;}}}}

选择排序非常好理解，但效率不是特别高，实际很少使用。

时间复杂度：O（n^2）

空间复杂度：O（1）

不稳定。

4.堆排序

堆排序是基于堆这种数据结构实现的，首先要将数组进行建大堆操作，设置bound记录末尾的位置，然后将数组的头和bound位置元素交换，此时堆中最大的元素在数组末尾，bound--，此时[0，bound]位置就是待排序位置，在进行向下调整，重复过程。

private static void heapsort(int[] arr) {//建堆creatheap(arr);int bound = arr.length-1;for (int i = 0; i < arr.length; i++) {int tem = arr[0];arr[0] = arr[bound];arr[bound] = tem;bound--;shifsort(arr,0,bound);}}private static void shifsort(int[] arr, int index, int bound) {int parent = index;int child = 2*parent + 1;while(child<bound){if(child+1<bound&&arr[child+1]>arr[child]){child+=1;}if(arr[child]>arr[parent]){int tem = arr[child];arr[child] = arr[parent];arr[parent] = tem;}else{break;}parent = child;child = 2*parent + 1;}}private static void creatheap(int[] arr) {for(int i = (arr.length-1-1)/2;i>=0;i--){shifsort(arr,i,arr.length);}}

升序要进行建大堆，降序则建小堆。

堆排序使用堆来调整数据，效率就快很多。

时间复杂度：O(n*logn)

空间复杂度：O(1)

稳定性：不稳定。

5.冒泡排序

冒泡排序非常好理解，我们取数组最后一个元素，依次与前面的数对比。

 private static void pooubsort(int[] arr) {for (int i = 0; i < arr.length; i++) {for (int j = arr.length-1; j > 0 ; j--) {if(arr[j-1] > arr[j]){int tem = arr[j-1];arr[j-1] = arr[j];arr[j] = tem;}}}}

时间复杂度：O(n^2)

空间复杂度：O（1）

稳定性：稳定。

6.快速排序

快速排序是一种非常重要的排序，这里提供Hoare法和挖坑法，Hoare法的思想是取数组最左/右边的值，将它设为基准值，先从右边的第一个值开始，找到比基准值小的值，停下，开始从最左边开始找  比基准值大的值，也停下，交换两个数，当left和right重合，交换基准值和两下标重合位置的值。此时就完成了一次寻找。接下来就是对区间[left,pos-1]和[pos+1,right]分别进行上述调整。因此快排要运用到递归。

//快速排序Hoare法private static void quicksort1(int[] arr) {quick(arr,0,arr.length-1);}private static void quick(int[] arr, int left, int right) {if(left>=right){return;}int pos = parttion(arr,left,right);quick(arr,left,pos-1);quick(arr, pos+1, right);}private static int parttion(int[] arr, int left, int right) {int k = arr[left];int i = left;while(left<right){while(left<right&&arr[right]>=k){right--;}while(left<right&&arr[left]<=k){k++;}sweap(arr,left,right);}sweap(arr,left,i);return left;}private static void sweap(int[] arr, int left, int right) {int tem = arr[left];arr[left] = arr[right];arr[right] = tem;}

挖坑法：挖坑法是先将第一个数据放到一个临时变量，形成一个坑位，从最右边开始找比基准值小的数，让它进入坑位，形成新的坑位，再从左边开始找比基准值大的数，进坑。

private static void quicksort2(int[] arr) {quick1(arr,0,arr.length-1);}private static void quick1( int []arr,int left,int right) {if(left>=right){return;}int pos = parttion1(arr,left,right);quick1(arr,left,pos-1);quick1(arr,pos+1,right);}private static int parttion1(int[] arr, int left, int right) {int key = arr[left];while(left<right){while(left<right&&arr[right]>=key){right--;}arr[left] = arr[right];while(left<right&&arr[left]<=key){left++;}arr[right] = arr[left];}arr[left] = key;return left;}

时间复杂度：O（n*logn）

空间复杂度：O（logn）

稳定性：不稳定

7.归并排序

归并排序也是通过递归（分治法）进行排序，通过将数组分组，使子序列有序，然后让子序列合并。

 private static void mergesort(int[] arr) {mergesortfunc(arr,0,arr.length-1);}private static void mergesortfunc(int [] arr,int left,int right) {if(left>=right){return;}int mid = (left+right)/2;mergesortfunc(arr,left,mid);mergesortfunc(arr,mid+1,right);merger(arr,left,mid,right);}private static void merger(int[] arr, int left, int mid, int right) {int s1 = left;int s2 = mid+1;int [] newarry = new int [right-left+1];int k = 0;while(s1<=mid&&s2<=right){if(arr[s1]>=arr[s2]){newarry[k] = arr[s2];k++;s2++;} else if (arr[s2]>arr[s1]) {newarry[k] = arr[s1];k++;s1++;}}while(s1<=mid){newarry[k++] = arr[s1++];}while(s2<=right){newarry[k++] = arr[s2++];}for (int i = 0; i < newarry.length; i++) {arr[i+left] = newarry[i];}}

归并排序的缺点在于空间复杂度为O（N），归并排序的思考更多在于磁盘外的排序，因为内存无法存储这么多数据，所以要进行外部排序，归并排序是最常用的外部排序。

时间复杂度：O(n*logn)

空间复杂度：O(N)

稳定性：稳定

8.快速排序的非递归实现

快排：首先要有一个栈，设置一个内置类，类中有left,right，将初始的范围[0,arr.length-1]入栈。

 public Range(int right, int left) {this.right = right;this.left = left;}}private static void quicksortbyLoop(int[] arr) {Stack<Range> stack = new Stack<>();stack.push(new Range(0,arr.length-1));while(!stack.isEmpty()){Range range = stack.pop();while(range.left>=range.right){continue;}int pos = parttion(arr,range.left, range.right);stack.push(new Range(range.left,pos-1));stack.push(new Range(pos+1,range.right));}}