时间复杂度汇总：

直接插入排序

import java.util.Arrays;public class InsertSort {public static void main(String[] args){int[] a={12,15,9,20,6,31,24};Sort(a);//调用方法}public static void Sort(int[] s){for (int i=1;i< s.length;i++){//注意i不能等于数组长度，因为数组下标从零开始而不是从1.int temp=s[i];//存储待插入数的数值int j;//j必须在此声明，如果在for循环内声明，j就不能拿出for循环使用，最后一步插入就无法执行for (j=i-1;j>=0&&temps[j+1]=s[j];//如果大于temp，往前移动一个位置}s[j+1]=temp;//将temp插入到适当位置}System.out.println(Arrays.toString(s));//输出排好序的数组}
}

时间复杂度：正序时O(n) 逆序时O(n[^2])

当待排元素已经为正序时，或者接近正序时所比较的次数和移动次数比较少。对于小规模来说，插入排序是一个快速的排序法。

空间复杂度：O(1) 只需要一个监视哨arr[0]

希尔排序

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

当增量的大小减到1时，就相当于整个序列被分到一组，进行一次直接插入排序，排序完成。

我的理解就是先分组，再进行直接插入排序或折半插入排序，直至步长为一

package Sort;import java.util.Arrays;public class ShellSort {public static void main(String[] args) {int[] a = {49, 38, 65, 97, 76, 13, 27, 49};System.out.println("原始数组为" + Arrays.toString(a));shellSort(a);System.out.println("最终排序的结果为" + Arrays.toString(a));}public static void shellSort(int[] a){int gap=a.length; //步长初始时等于数组长度while (gap>1){ //当步长大于一时继续循环gap=gap/2; //步长每次缩短为一半for (int i=0;i //对每一组进行插入排序int end=i; //end表示前驱元素的下标int temp=a[end+gap]; //end+gap表示end之后元素的下标while (end>=0){if(temp //如果end的后继元素小于a[end],则将前驱元素后移（插入排序）a[end+gap]=a[end];a[end]=temp; //将两个元素交换位置end=end-gap;} else {break;}}}}}
}

冒泡排序

冒泡排序（Bubble Sort）算法是所有排序算法中最简单、最基础的一个，它的实现思路是通过相邻数据的交换达到排序的目的。
冒泡排序的执行流程是：

• 对数组中相邻的数据，依次进行比较；
• 如果前面的数据大于后面的数据，则把前面的数据交换到后面。经过一轮比较之后，就能把数组中最大的数据排到数组的最后面了；再用同样的方法，把剩下的数据逐个进行比较排序，最后得到就是从小到大排序好的数据

    private static void bubbleSort(int[] nums) {int temp;for (int i = 1; i < nums.length; i++) {for (int j = 0; j < nums.length - i; j++) {if (nums[j] > nums[j + 1]) {temp = nums[j];nums[j] = nums[j + 1];nums[j + 1] = temp;}}System.out.print("第" + i + "次排序：");System.out.println(Arrays.toString(nums));}}

快速排序

• 首先设定一个分界值，通过该分界值把数组分为左右两个部分；
• 将大于等于分界值的元素放到分界值的右边，将小于分界值的元素放到分界值的左边；
• 然后对左右两边的数据进行独立的排序，在左边数据中取一个分界值，把小于分界值的元素放到分界值的左边，大于等于分界值的元素，放到数组的右边；右边的数据也执行同样的操作；
• 重复上述操作，当左右各数据排序完成后，整个数组也就完成了排序。

quickRow(quickNums, 0, quickNums.length - 1);public static void quickRow(int[] array, int low, int high){int i,j,pivot;//结束条件if (low >= high) {return;}i = low;j = high;//选择的节点，这里选择的数组的第一数作为节点pivot = array[low];while (i < j){//从右往左找比节点小的数，循环结束要么找到了，要么i=jwhile (array[j] >= pivot && i < j){j--;}//从左往右找比节点大的数，循环结束要么找到了，要么i=jwhile (array[i] <= pivot && i < j){i++;}//如果i!=j说明都找到了，就交换这两个数if (i < j){int temp = array[i];array[i] = array[j];array[j] = temp;}}//i==j一轮循环结束，交换节点的数和相遇点的数array[low] = array[i];array[i] = pivot;//数组“分两半”,再重复上面的操作quickRow(array,low,i - 1);quickRow(array,i + 1,high);}

选择排序

其实现思路是每一轮循环找到最小的值，依次排到数组的最前面，这样就实现了数组的有序排列。

 private static void selectSort(int[] nums) {int index;int temp;for (int i = 0; i < nums.length - 1; i++) {index = i;for (int j = i + 1; j < nums.length; j++) {if (nums[j] < nums[index]) {index = j;}}if (index != i) {temp = nums[i];nums[i] = nums[index];nums[index] = temp;}System.out.print("第" + i + "次排序：");System.out.println(Arrays.toString(nums));}}

堆排序

堆排序（Heap Sort）算法是利用堆结构和二叉树的一些特性来完成排序的。 其实每次堆排序就是将无序的堆排成大根堆或者小根堆。