选择排序算法-Selection Sort

数组：8 6 2 3 1 5 7 4 从小到大排序

思路：

• 遍历数组，找到最小的数1
• 将最小数1与数组第一个位置的数交换，此时数字1就是最终位置

数组：1 6 2 3 8 5 7 4

• 遍历除了数字1剩余的部分，找到最小数2
• 将最小数2与数组的剩余部分的第一个位置的数交换，此时数字2就是最终位置

数组：1 2 6 3 8 5 7 4

实现：

void selectionSort(T array[] ，int n) {
      for(int i = 0; i < n; i++) {
      int minIndex = i;
      for(int j = i + 1; j < n; j++) {
          if(array[j] < array[minIndex]) {
              minIndex = j;
          }
      }
    swap(array[i],array[minIndex]);
  }
}

插入排序算法-Insertion Sort

数组：8 6 2 3 1 5 7 4 从小到大排序

思路：

• 从数组第二元素6开始，与第一个元素8比较，如果小于，则将二者交换位置，此时前两个元素就已经排好序了

数组：6 8 2 3 1 5 7 4

• 第三个元素2，与它前一个元素8比较，如果小于，则二者交换位置

数组：6 2 8 3 1 5 7 4

• 第二个元素2，与前一个元素6比较，如果小于，则二者交换位置,此时前三个元素就已经排序好了

数组：2 6 8 3 1 5 7 4

• 第四个元素3，以前一个元素8比较，如果小于，则二者交换位置

数组：2 6 3 8 1 5 7 4

• 第三个元素3，与前一个元素6比较，如果小于，则二者交换位置

数组：2 3 6 8 1 5 7 4

• 第二个元素3，与前一个元素2比较，不小于，则不进行操作，此时前四个元素就已经排序好了

实现：

void insertionSort(T arr[], int n) {
    for(int i = 1; i < n; i++) {//从第一位置开始，因为第一个位置之前已经没有元素了
        // 寻找元素arr[i]合适的插入位置
        for(int j = i; j > 0 ;j--) {
              if(arr[j] < arr[j-1]) {
                  swap(arr[j] , arr[j-1]);
              }else {
                  break;
              }
        }
    }
}

void insertionSort(T arr[], int n) {
    for(int i = 1; i < n; i++) {
        for(int j = i; j > 0 && arr[j] < arr[j-1] ; j--) {
             swap(arr[j] , arr[j-1]);
        }
    }
}

优化思路：通过赋值操作取代之前的交换操作

• 从数组第二元素6开始，先复制一份，判断6是否应该放在当前的位置，也就是和前一个元素8进行比较，如果小于，说明6不应该放在当前位置，而第一个元素8应该放在当前位置，将8赋值到第二元素的位置

数组：8 8 2 3 1 5 7 4

• 再来看6是不是应该放在前一个位置，此时位置是第一个位置了，直接把6赋值到第一个位置

数组：6 8 2 3 1 5 7 4

• 接下来是第三个元素2，先把2复制一份，判断2是否应该放在当前位置，也就是和前一个元素8比较，如果小于，说明2不应该放在当前位置，那么把当前位置赋值为8

数组：6 8 8 3 1 5 7 4

• 之后判断2是不是应该放在原来8的位置，也就是和前一个元素6比较，如果小于，说明2不应放在原来8的位置，那么把当前位置赋值为6

数组：6 6 8 3 1 5 7 4

• 最后判断2是不是应该放在原来6的位置，此时位置是第一个位置了，直接把2赋值到第一个位置

数组：2 6 8 3 1 5 7 4

实现：

void insertionSort(T arr[], int n) {
    for(int i = 1; i < n; i++) {
        T e = arr[i];
        int j;//j就是用来保存元素e应该插入的位置
        //判断元素e是不是应该放在当前位置
        //判断j前面位置的元素，是不是比e大,说明当前位置不是e的最终位置，循环要继续
        for(j = i; j > 0 && arr[j-1] > e ; j--) {
            arr[j] = arr[j-1];//把前一个位置的元素向后移动
        }
        arr[j] = e;
    }
}

总结：

• 插入排序对于一个近乎有序的数组进行排序，效率非常高，因为插入排序可以根据条件提前结束内层循环，另外不需要进行交换操作

冒泡排序算法-Bubble Sort

数组：3 6 4 2 11 10 5 从小到大排序

思路：

• 首先比较3和6，3小于6，不操作
• 6和4比较，6大于4，6和4交换位置

数组：3 4 6 2 11 10 5

• 6和2比较，6大于2，6和2交换位置

数组：3 4 2 6 11 10 5

• 6和11比较，6小于11，不操作
• 11和10比较，11大于10 ，10和11交换位置

数组：3 4 2 6 10 11 5

• 11和5比较，11大于5，11和5交换位置

数组：3 4 2 6 10 5 11

实现：

for (int i = 0 ; i < n; i++) {
  for(int j = 0 ; j < n-i ; j++) {
  }
}

希尔排序算法-Shell Sort(插入排序的延伸)