插入排序

算法思想

每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子序列中的适当位置，直到全部记录插入完成为止。

// 举例
int arr[] = { 3, 1, 5, 7, 2, 4, 9, 6 };

// 第一轮替换
int arr[] = { 1, 3, 5, 7, 2, 4, 9, 6 };

// 第二轮替换
int arr[] = { 1, 2, 3, 5, 7, 4, 9, 6 };

// 第三轮替换
int arr[] = { 1, 2, 3, 4, 5, 7, 9, 6 };

// 第四轮替换
int arr[] = { 1, 2, 3, 4, 5, 6, 7, 9 };

// 代码实现 
void insertSort(int *arr, int length) {
    int i, j, temp;
    // 从第二个元素开始，因为第一个元素默认是有序的
    for (i = 1; i < length; ++i) {
        // 如果当前元素比前一个元素小，那么就需要将当前元素插入到前面的有序序列中
        if (arr[i] < arr[i - 1]) {
            // 保存当前元素
            temp = arr[i];
            // 从当前元素的前一个元素开始，依次和当前元素比较，如果比当前元素大，那么就将该元素后移一位
            for (j = i - 1; j >= 0 && arr[j] > temp; --j) {
              //这里将大于temp的数都后移一位
                arr[j + 1] = arr[j];
            }
            // 将当前元素插入到合适的位置
            arr[j + 1] = temp;

        }
    }
}

//第二种实现方式 （这种方式比较好理解）
void insertSort(int *arr, int length) {
    int i, j, temp;
    // 从第二个元素开始，因为第一个元素默认是有序的
    for (i = 1; i < length; ++i) {
        // 如果当前元素比前一个元素小，那么就需要将当前元素插入到前面的有序序列中
        if (arr[i] < arr[i - 1]) {
            // 保存当前元素
            temp = arr[i];
            // 从当前元素的前一个元素开始，依次和当前元素比较，如果比当前元素大，那么就将该元素后移一位
            for (j = i - 1; j >= 0; --j) {
                if (arr[j] > temp) {
                    arr[j + 1] = arr[j];
                } else {
                    break;
                }
            }
            // 将当前元素插入到合适的位置
            arr[j + 1] = temp;

        }
    }
}

// 第三种实现方式 (带哨兵) 这种就是把下表为0的元素当做哨兵，这样就不用每次都判断j>=0了 个人认为没啥必要
void insertSort(int *arr, int length) {
    int i, j;
    // 从第二个元素开始，因为第一个元素默认是有序的
    for (i = 2; i < length; ++i) {
        // 如果当前元素比前一个元素小，那么就需要将当前元素插入到前面的有序序列中
        if (arr[i] < arr[i - 1]) {
            // 将当前元素插入到合适的位置
            arr[0] = arr[i];
            // 从当前元素的前一个元素开始，依次和当前元素比较，如果比当前元素大，那么就将该元素后移一位
            for (j = i - 1; arr[j] > arr[0]; --j) {
                arr[j + 1] = arr[j];
            }
            // 将当前元素插入到合适的位置
            arr[j + 1] = arr[0];

        }
    }
}

算法分析

时间复杂度

最好情况：O(n)

• 一般就是有序的 是不需要移动的 也是常数级别的

最坏情况：O(n^2)

• 一般就是逆序的，每一项都需要移动

平均情况：O(n^2)

空间复杂度

O(1)

稳定性

稳定

折半插入排序

也叫二分插入排序，是对直接插入排序算法的一种改进，由于排序过程中，前面的元素总是已经排好序的，所以可以使用折半查找的方式来减少比较次数，提高效率。

• 只能用于顺序存储结构，不适用于链式存储结构。顺序查找支持下表随时访问
• 个人认为 时间复杂度还是O(n^2) 就是少了一些比较次数

  // 代码实现
  void binaryInsertSort(int *arr, int length) {
      int i, j, temp, low, high, mid;
      // 从第二个元素开始，因为第一个元素默认是有序的
      for (i = 1; i < length; ++i) {
          // 如果当前元素比前一个元素小，那么就需要将当前元素插入到前面的有序序列中
          if (arr[i] < arr[i - 1]) {
              // 保存当前元素
              temp = arr[i];
              // 从当前元素的前一个元素开始，依次和当前元素比较，如果比当前元素大，那么就将该元素后移一位
              low = 0;
              high = i - 1;
              while (low <= high) {
                  mid = (low + high) / 2;
                  if (arr[mid] > temp) {
                      high = mid - 1;
                  } else {
                      low = mid + 1;
                  }
              }
              // 将当前元素插入到合适的位置
              for (j = i - 1; j >= high + 1; --j) {
                  arr[j + 1] = arr[j];
              }
              arr[high + 1] = temp;
  
          }
      }
  }