O(n^2)

冒泡排序

每个元素与自己的下一个元素进行比较，如果比下个元素大（升序为例），则与下个元素位置互换
当第一轮结束后，数组最后一个元素一定是最大的。然后进行下一轮排序，下一轮的排序只需要排到数组到数第二个元素即可，因为最后一个已经是最大的了。

  1. public class BubbleSort {
  3.     public static void main(String[] args) {
  4.         BubbleSort bubbleSort = new BubbleSort();
  5.         int[] data = {4,1,2,6,7,3,1,3};
  6.         bubbleSort.run(data);
  7.     }
  9.     private void run(int[] data){
  10.         for (int i = data.length-1; i >=0; i--) {
  11.             for (int j = 0; j <i; j++) {
  12.                 if (data[j] > data[j+1]){
  13.                     swap(data,j,j+1);
  14.                 }
  15.             }
  16.         }
  17.     }
  19.     private void swap(int[] data,int a,int b){
  20.         int temp = data[a];
  21.         data[a] = data[b];
  22.         data[b] = temp;
  23.     }
  24. }

优化（1）有序后跳出

假如给一个已经有序的数组，或经过前几次排序后数组已经变的有序了，那么排序动作其实已经可以终止了，但原算法无法做到感知这一点，所以可以对此进行优化。
通过观察排序动作可以得知，如果有乱序情况，一定会进行位置交换，否则只会遍历比对一遍，不会进行交换动作。因此我们可以在每轮开始前设置一个标志位默认为true，假定默认数组已经是有序的了，如果本轮有任何交换动作，则将该标志位置为false，在本轮排序结束后，通过该标志位判断是否有交换动作，没有即表示数组已经是有序状态，可以终止排序。

  1. private void run(int[] data){
  2.         for (int i = data.length-1; i >=0; i--) {
  3.             boolean isOrdered = true;
  4.             for (int j = 0; j <i; j++) {
  5.                 if (data[j] > data[j+1]){
  6.                     int temp = data[j];
  7.                     data[j] = data[j+1];
  8.                     data[j+1] = temp;
  9.                     isOrdered = false;
  10.                 }
  11.             }
  12.             if (isOrdered){
  13.                 break;
  14.             }
  15.         }
  16.     }

优化（2）记录后排有序子序列

对于类似data=[2,1,4,3,6,7,8,9]的情况，后排子序列已经是有序的，即这部分是无需再进行排序动作的。数组实际需要排序的位置是data[0]-data[3]这部分。
从优化（1）中我们可以知道，可以通过记录是否有交换动作来标记是否已经是有序数组了，再延伸一下，每次交换时，记录下当前的位置，如果该位置后面再也没变过，说明后面的子序列已经是有序的了，那么排序终点设置为当前的记录位置即可。

  1.  private void run(int[] data) {
  2.         int lastIndex = 0, bound = data.length - 1;
  3.         for (int i = data.length - 1; i >= 0 && bound > 0; i--) {
  4.             boolean isOrdered = true;
  5.             for (int j = 0; j < bound; j++) {
  6.                 if (data[j] > data[j + 1]) {
  7.                     int temp = data[j];
  8.                     data[j] = data[j + 1];
  9.                     data[j + 1] = temp;
  10.                     isOrdered = false;
  11.                     lastIndex = j;
  12.                 }
  13.             }
  14.             if (isOrdered) {
  15.                 break;
  16.             }
  17.             bound = lastIndex;
  18.         }
  19.     }

优化（3）鸡尾酒排序

对于类似data=[2,3,4,5,6,7,1]的情况，冒泡排序需要经过完整的排序周期才能得到最终有序数组，原因在于冒泡排序每次新一轮的排序都是从数组头部开始的，其排序过程如下：

  1. [2,3,4,5,6,7,1]
  2. [2,3,4,5,6,1,7]
  3. [2,3,4,5,1,6,7]
  4. [2,3,4,1,5,6,7]
  5. [2,3,1,4,5,6,7]
  6. [2,1,3,4,5,6,7]
  7. [1,2,3,4,5,6,7]

而鸡尾酒排序在第一次排序后，转而从末尾开始进行第二轮排序，到数组头部后又从头部开始第三轮排序，向个摆钟一样来回摇摆，其排序效果如下：

  1. [2,3,4,5,6,7,1]
  2. [2,3,4,5,6,1,7]
  3. [1,2,3,4,5,6,7]

在第二轮，从后往前排，再排一次即可完成排序。
鸡尾酒排序大部分已经有序的情况进行排序。

冒泡的特性

冒泡排序的一个很大特点是，每轮排序确定一个最值，其他元素的相对位置保持不变。
如283.移动零题目就很适合使用冒泡排序的方法来做

  1. 给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

选择排序

每次从剩余数组中选择最值元素，放在数组的头尾处，如此反复

  1.  private int[] selectSort(int[] nums){
  2.         for (int i = 0; i < nums.length; i++) {
  3.             int minIndex = findMinIndex(nums, i);
  4.             int temp = nums[minIndex];
  5.             nums[minIndex] = nums[i];
  6.             nums[i] = temp;
  7.         }
  8.         return nums;
  9.     }
  10.     private int findMinIndex(int[] nums,int start){
  11.         int min = Integer.MAX_VALUE, minIndex = -1;
  12.         for (int i = start; i < nums.length; i++) {
  13.             if (nums[i] < min){
  14.                 min = nums[i];
  15.                 minIndex = i;
  16.             }
  17.         }
  18.         return minIndex;
  19.     }

插入排序

循环的位置就是分界线，前面的都排序好了，后面的都没排序呢。
取i的值作为temp，一个一个的和前面的比，如果比前面的小，则前面的往后覆盖一位，直到找到目标位置。

  1. private int[] insertSort(int[] nums){
  2.         for (int i = 1; i < nums.length; i++) {
  3.             int j = i , temp = nums[i];
  4.             while (j >= 1 && temp < nums[j-1]){
  5.                 nums[j] = nums[j-1];
  6.                 j--;
  7.             }
  8.             nums[j] = temp;
  9.         }
  10.         return nums;
  11. }

O(nlogn)

希尔排序

堆排序

快速排序

  1. 选择一个基准值（简单起见选第一个），整个数组中大于该值的，放到左边，否则放到右边。结束后将基准值放在中间
  2. 对基准值左边的子数组，重复步骤1.
  3. 对基准值右边的子数组，重复步骤1.

对于元素的交换方法，有两种：双端法和单端法

双端

我们选择数组0位作为基准值，并设置指针left=1，right=length-1

  1. 首先对右端，判断值如果大于基准值则将右指针向左移动
  2. 然后对左端，判断如果值小于基准值则将左指针向右移动
  3. 如果此时两指针还没交叉，则应该交换当前左右指针的值
  4. 当左右指针交叉后，注意基准值一直在数组首位没有动过，此时左指针处的值肯定是最接近基准值的，将该值和数组首位交换，此时，基准值来到了当前左指针的位置

  5. 之后以基准值位置分段数组，分别对左右子数组进行排序，注意基准数是中间值，所以该位置处不需要参与排序 ```java public class FastSort {

    public static void main(String[] args) {

    1.  FastSort fastSort = new FastSort();
    2.  int[] data = {4, 1, 6, 3, 2, 8, 5};
    3.  fastSort.run(data);
    4.  System.out.println(data);

    }

    public void run(int[] args) {

    1.  run(args, 0, args.length - 1);

    }

    private void run(int[] args, int start, int end) {

    1.  if (start >= end) {
    2.      return;
    3.  }
    4.  int baseIndex = sort(args,start,end);
    5.  run(args,start,baseIndex-1);
    6.  run(args,baseIndex+1,end);

    }

    private int sort(int[] args, int start, int end) {

    1.  int left = start, right = end, base = args[start];
    2.  while (left < right) {
    3.      //移动的过程中也要检查是否交叉了，所以要判断left<right
    4.      while (left < right && args[right] > base) {
    5.          right--;
    6.      }
    7.      if (left < right){
    8.          args[left] = args[right];
    9.          left++;
    10.      }
    11.      while (left < right && args[left] < base) {
    12.          left++;
    13.      }
    14.      if (left < right){
    15.          args[right] = args[left];
    16.          right--;
    17.      }
    18.  }
    19.  args[left] = base;
    20.  return left;

    }

  1. private void swap(int[] data, int a, int b) {
  2.     int temp = data[a];
  3.     data[a] = data[b];
  4.     data[b] = temp;
  5. }

}

  1. <a name="RllIH"></a>
  2. ##### 单端
  3. 选定数组0位为基准值，设定index作为数组中小于基准值的边界索引，初始值为数组0位。
  5. 1. 从1位开始，如果比基准值大，则继续向右遍历
  6. 1. 如果比基准值小，则让index+1，扩大小于基准值的范围，然后让index与当前位置元素交换。
  7. 1. 注意一遍走完后，基准值始终在数组首位，所以需要与当前index位置交换
  9. 注意index的含义代表所有小于基准值的最右边界，初始设置start，每次需要加入其中时扩大边界再进行交换，结束后index仍然是最右边界。
  10. ```java
  11. public int sort2(int[] args,int start,int end){
  12.         int base = args[start];
  13.         int index = start;
  15.         for (int i = start+1; i <= end; i++) {
  16.             if (args[i] < base){
  17.                 index++;
  18.                 swap(args,index,i);
  19.             }
  20.         }
  21.         args[start] = args[index];
  22.         args[index] = base;
  23.         return index;
  24. }

归并排序

  1. public class MergeSort {
  3.     public static void main(String[] args) {
  4.         MergeSort sort = new MergeSort();
  5.         int[] nums = {3,1,7,4,9,2,5,6};
  6.         sort.run(nums);
  7.         System.out.println();
  8.     }
  10.     public void run(int[] args){
  11.         run(args,0,args.length-1);
  12.     }
  14.     public void run(int[] args,int left,int right){
  15.         if (left >= right){
  16.             return;
  17.         }
  18.         int mid = left + (right - left)/2;
  19.         run(args,left,mid);
  20.         run(args,mid+1,right);
  21.         merge(args,left,mid,right);
  22.     }
  24.     private void merge(int[] args,int left,int mid,int right){
  25.         int[] temp = new int[right-left+1];
  26.         int i = left , j = mid+1, index=0;
  27.         while (i <= mid && j <= right){
  28.             if (args[i] < args[j]){
  29.                 temp[index] = args[i];
  30.                 i++;
  31.             }else {
  32.                 temp[index] = args[j];
  33.                 j++;
  34.             }
  35.             index++;
  36.         }
  37.         while (i <= mid){
  38.             temp[index++] = args[i++];
  39.         }
  40.         while (j <= right){
  41.             temp[index++] = args[j++];
  42.         }
  43.         int t = 0;
  44.         while (left<=right){
  45.             args[left++] = temp[t++];
  46.         }
  47.     }
  48. }

O(n)

计数排序

  1. private int[] countSort(int[] nums){
  2.         int max = Arrays.stream(nums).max().getAsInt();
  3.         int[] bucket = new int[max+1];
  4.         Arrays.fill(bucket,-1);
  5.         for (int i = 0; i < nums.length; i++) {
  6.             bucket[nums[i]] += 1;
  7.         }
  8.         int[] ans = new int[nums.length];
  9.         int index = 0;
  10.         for (int i = 0; i < bucket.length; i++) {
  11.             if (bucket[i] != -1){
  12.                 while (bucket[i] > -1){
  13.                     ans[index++] = i;
  14.                     bucket[i] --;
  15.                 }
  16.             }
  17.         }
  18.         return ans;
  19.     }

基数排序

桶排序