20231112 - 排序01

冒泡排序

• 每轮比较确定一个数字位置, N 个数字需要比较 N-1 论, 第 i 论比较次数 N-i 此
• 一般形式 (未优化)

  for (int i=0; i < length; i++) {
      for (int j=i+1; j < length; j++) {
          if (array[i] > array[j]) {
              swap(array[i], array[j]);  // std::swap
          }
      }
  }

• 优化后

  for (int i=0; i < length; i++) {
    bool exchanged = false;
    for (int j=0; j < length - i - 1; j++) {
      if (array[j] > array[j+1]) {
        exchanged = true;
        swap(array[j], array[j+1])
      }
    }
    if (!exchanged) {
      // 如果上一次二级循环没有交换即视为后面所有元素已均有序
      break  // 或者 return
    }
  }

插入排序

• 插入排序 (Insertion Sort) 是一直简单直观且稳定的排序算法