排序算法在数据结构中是一块非常重要的组成部门，本篇博文主要讲一下自己对排序算法的理解。

1、冒泡排序

1.1基本介绍

冒泡排序的思想是：通过对待排序序列从前向后（从下标较小的元素开始），依次比较相邻元素的值，若发现逆序则交换，使值较大的元素逐渐从前移向后部，就像水底的气泡一样逐渐向上冒。

因为排序过程中，各元素不断接近自己的位置，如果一趟比较下来没有交换过，说明序列有序，因此要在排序过程中设置一个 flag 判断元素是否进行交换，从而减少不必要的比较。

1.2 代码实现

public static void bubble(int[] arr){
	// flag 用于优化，如果一趟下来没有交换，说明已经排序完成，直接退出就行，不要进行没必要的排序
    boolean flag = false;
	for (int i = 0; i < arr.length - 1; i++) {
     for (int j = 0; j < arr.length - 1 - i; j++) {
       if(arr[j] > arr[j + 1]){
       	 flag = true;
         int temp = arr[j];
         arr[j] = arr[j + 1];
         arr[j + 1] = temp;
       }
     }
   	if(!flag){
        break;
    } else {
        flag = false;
      }
   }
   System.out.println(Arrays.toString(arr));
}

2、选择排序

2.1 基本介绍

选择排序是先确定一个数，认为他是最小的，但是不一定是最小的一个数。一般是确定为数组的第一个元素。我们依次扫描和第一个数进行比较，如果条件成立，两个数交换一下，这样的操作可以使每一轮比较结束以后都会选出来一个最大的或者最小的数。比较 n - 1 轮之后，数组就变成有序数组。

2.2 选择排序图解

2.3 代码实现

public static void selectSort(int[] arr){
// 这里每一轮都确定伪第一个元素为选择的对象
 for (int i = 0; i < arr.length; i++) {
    for (int j = i + 1; j < arr.length; j++) {
      int temp = 0;
      if (arr[i] < arr[j]) {
        temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
      }
    }
    System.out.print(arr[i]+" ");
  }
}

3、插入排序

3.1 插入排序自己的理解

首先插入排序需要进行数组长度减一次 即 arr.length - 1 重第二个数开始进行，一直到最后一个元素。选取的元素默认左边的数字时已经排好序的，然后拿到的数字同左边的依次比较，如果找到插空的位置，插入即可。

3.1.1 具体实现

第一轮： 拿到第二个数据先与第一个数进行比较，如果条件成立，用一个临时变量给第一个数保存下来，再将保存的数字插入第一个位置。
第二轮： 拿着第三个数与前两个进行比较，如果找到的位置应该两个数字之间，那么就需要将第二个是移到第三个位置，再将第三个位置的数字放到到第二个数字处。
。。。。
第 n 轮” 首先因为待插入排序的数字左边的数字已经是排好序的，待插入的数字需要依次比较，有可能会出现的情况是待插入的数字太小，插入位置靠前。因为数组是有序的，两个数字之间不会有一个空挡等待要插入的元素。这个时候的操作相当于将待插入数字原来位置的左边的元素到找到插空位置右边的元素，依次向后移动一个位置。依次向后移动一个位置的操作是将左边的数字赋值给右边相邻的元素，这里我称做为覆盖。最后的时候我们将待插入元素插入到对应的位置即可。

因此我们的代码中会出现如下两行代码
arr[insertindex + 1] = arr[insertIndex]
inesrtIndex --

3.2 代码实现

public static void insertSort(int[] arr){
  for(int i = 1; i < arr.length; i++){
    // 待插入位置的初始下标
    int indexInsert = i - 1;
    // 待插入的元素
    int insertVal = arr[i];
    // 向左找出，下标位置不能小于0，并且待插入比已经排好序的最后一个元素还小再进入循环体中
    while(indexInsert >= 0 && insertVal < arr[indexInsert]){
      // 前一个数将后一个数依次给覆盖掉
      arr[indexInsert + 1] = arr[indexInsert];
      indexInsert--;
    }
    indexInsert+=1;
    arr[indexInsert] = insertVal;
  }
}

插入排序的弊端： 如果后面的数在插入的数特别靠前时，那么将会有大量的步骤进行后移，也就是覆盖的操作；这其中还是存在要提升的空间的。

4、希尔排序

针对插入排序的弊端：希尔排序可以解决这个问题

4.1 希尔排序的思想

希尔排序也是一种插入排序，它是简单插入排序改进之后的一个更高效版本，也成为缩小增量排序

希尔排序时把记录按下标的一定增量分组，对每组使用直接插入排序算法排序，随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。
说白了就是先 两个两个分组比较，如果条件成立进行交换或者平移，一轮以后再进行分组数量时原来的 两倍

希尔排序有两种实现方式：

1. 交换法
2. 平移法

交换法代码实现

public static void shellSort(int[] arr){
  for(int gap = arr.length / 2; gap > 0; gap /= 2){
    for(int i = gap; i < arr.length; i++){
      for (int j = i - gap; j >= 0; j -= gap){
        if(arr[j] > arr[j + gap]){
          int temp = arr[j];
          arr[j] = arr[j + gap];
          arr[j + gap] = temp;
        }
      }
    }
  }
}

平移法代码实现

public static void shellSort2(int[] arr){
  for(int gap = arr.length / 2; gap > 0; gap /= 2){
    for(int i = gap; i < arr.length; i++){
      int j = i;
      int temp = arr[j];
      if(arr[j] < arr[j - gap]){
        while(j - gap >= 0 && temp < arr[j - gap]){
          arr[j] = arr[j - gap];
          j -= gap;
        }
        arr[j] = temp;
      }
    }
  }
}

平移法可以认为是插入排序的升级版本

5、快速排序

5.1 快速排序的基本介绍

快速排序是对冒泡排序的一种改进，基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部门的所有数据都比另外一部门的所有数据都要小，然后按此方法对这两部分数据分别进行快速排序，整个快速排序过程可以递归进行，以此达到整个数据变成有序序列。

步骤：

1. 先选取一个中间值，然后将其他数据比中中间值小的放到左边，比中间值大的放到右边
2. 递归进行中间值的选取

5.2 示例图

5.3 应用实例

要求：对 [-1, 781 0, 23, -567, 70] 进行从小到大的排序，要求使用快速排序
1）如果取消左右递归，结果是：-9 -567 0 23 78 70

2）如果取消右递归，结果是 -567 -9 0 23 78 70

3）如果取消左递归，结果是 -9 567 0 23 70 78

5.4 代码实现

public static void quickSort(int[] arr, int left, int right){
  int l = left;
  int r = right;
  int pivot = arr[(left + right) / 2];
  while(l < r){
    // 在 pivot 左边一直找，找到大于等于pivot值，才退出
    while (arr[l] < pivot){
      l += 1;
    }
    // 在 pivot 右边一直找，找到小于等于pivot值，才退出
    while(arr[r] > pivot){
      r -= 1;
    }
    if(l >= r){
      break;
    }
    // 进行两个值交换
    int temp = arr[r];
    arr[r] = arr[l];
    arr[l] = temp;

    // 如果交换完之后发现这个 arr[l] == pivot 则 r--
    if(arr[l] == pivot){
      r -= 1;
    }
    if(arr[r] == pivot){
      l += 1;
    }
  }
  // 如果 l == r 必须 l++, r--
  if(l == r){
    l += 1;
    r -= 1;
  }
  if(left < r){
    quickSort(arr, left, r);
  }
  if(right > l){
    quickSort(arr, l, right);
  }
}

6、归并排序

6.1 基本介绍

归并排序是利用归并的思想实现的排序方法，该算法采用经典的分治策略（分治法将问题分成一些小的问题然后递归求解，而治的阶段将分的阶段得到的个答案修补在一起，即分而治之）

6.2 示例图

6.3 代码演示

// 分 + 合 方法
public static void mergeSort(int[] arr, int left, int right, int[] temp){
    if(left < right){
        int mid = (left + right) / 2;
        // 向左递归
        mergeSort(arr, left, mid, temp);
        // 向右递归
        mergeSort(arr, mid + 1, right, temp);
        // 合并
        merge(arr, left, mid, right, temp);
    }
}

public static void merge(int[] arr, int left, int mid, int right, int[] temp){
    int i = left;
    int j = mid + 1;
    int t = 0;
    // 先把左右两边的数据按照规则填充到 temp 数组中
    // 直到左右两边的有序序列，有一边处理完毕为止
    while (i <= mid && j <= right) {
        if(arr[i] <= arr[j]){
            temp[t] = arr[i];
            t += 1;
            i += 1;
        }else{
            temp[t] = arr[j];
            t += 1;
            j += 1;
        }
    }

    // 在上面的步骤进行完成之后，可能左右两边会留有元素，这是需要我们依次将留下的数据填充到临时数组
    while(i <= mid){
        temp[t] = arr[i];
        i += 1;
        t += 1;
    }
    while (j <= right){
        temp[t] = arr[j];
        t += 1;
        j += 1;
    }

    // 将临时数组 copy 到原来的数组
    // 注意：并不是每次都要拷贝所有
    t = 0;
    int tempLeft = left;
    while(tempLeft <= right){
        arr[tempLeft] = temp[t];
        tempLeft += 1;
        t += 1;
    }
}

以上 6 种排序十分重要，一般情况下学习1遍是不够的，主要是在于理解，排序的思想，只有在自己理解的前提下，自己独立的写出来才算是领会其中的奥秘，因此，隔断时间重新写一下还是很有必要的。