乱序的数据：arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48];

冒泡排序

实现思路:

对于一组要排序的元素，

1. 依次比较相邻的两个数，
2. 将比较后小的数放在前面，大的数放在后面，
3. 循环往复，直至最后一对，全部排序完成。

动图演示：

程序打印：

0  (15) arr :>> [3, 38, 5, 44, 15, 36, 26, 27, 2, 46, 4, 19, 47, 48, 50]
1  (15) arr :>> [3, 5, 38, 15, 36, 26, 27, 2, 44, 4, 19, 46, 47, 48, 50]
2  (15) arr :>> [3, 5, 15, 36, 26, 27, 2, 38, 4, 19, 44, 46, 47, 48, 50]
3  (15) arr :>> [3, 5, 15, 26, 27, 2, 36, 4, 19, 38, 44, 46, 47, 48, 50]
4  (15) arr :>> [3, 5, 15, 26, 2, 27, 4, 19, 36, 38, 44, 46, 47, 48, 50]
5  (15) arr :>> [3, 5, 15, 2, 26, 4, 19, 27, 36, 38, 44, 46, 47, 48, 50]
6  (15) arr :>> [3, 5, 2, 15, 4, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
7  (15) arr :>> [3, 2, 5, 4, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
8  (15) arr :>> [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
9  (15) arr :>> [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
10 (15) arr :>> [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
11 (15) arr :>> [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
12 (15) arr :>> [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
13 (15) arr :>> [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

时间复杂度

第一趟比较了 14 次，第二躺比较了 13 次， 第 14 趟比较了 1 次，所以时间复杂度就是 14+13+12+ .. + 1 , 即

$$ （n-1）+ (n-2) + ... 2 ++ 1 = n(n-1)/2 = n²/2 - n/2 $$

根据复杂度规则，去掉低阶项（也就是 n/2）,并去掉常数系数（1/2），那复杂度就是 O(n^2) 了

实现过程

// 乞丐版
function bubbleSort(arr) {
  let len = arr.length;
  // 趟数，记录多少趟
  for (let i = 0; i < len - 1; i++) {
    // 每趟比较的次数 len -1 - i
    for (let j = 0; j < len - 1 - i; j++) {
      // 相邻元素两两对比
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]; // 元素交换
      }
    }
    console.log('arr :>> ', i, arr);
  }
  return arr;
}

上面的代码其实已经完成了一个冒泡排序，但是随着冒泡排序趟数的增加，他就逐渐是一个有序数列，对于已经排好序的元素，我们能否不对其进行循环处理，从而减少它的排序时间呢？

那就来优化一下上面的代码，优化思路：

其实我们只要记录一下无序的边界，即上一趟最后一次交换数据的位置，用上一趟的位置来作为下一次循环的边界。

// 进阶版
function bubbleSort(arr) {
  let len = arr.length;
  // 最后交换的位置
  let lastIndex = len;
  // 边界
  let border = len - 1;
  // 趟数，记录多少趟
  for (let i = 0; i < len - 1; i++) {
    // 每趟比较的次数 border
    for (let j = 0; j < border; j++) {
      // 相邻元素两两对比
      if (arr[j] > arr[j + 1]) {
        lastIndex = j;
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]; // 元素交换
      }
    }
    border = lastIndex;
    console.log('arr :>> ', i, arr);
  }
  return arr;
}

注意： lastIndex = j ，后面一定要加分好，不然解析会有问题，lastIndex 会被解析成一个数组，

对于观察比较细致的同学可能发现，上面冒泡排序的时候，从第九次开始，他就已经形成了一个有序数列，后续的排序并不需要，那我们再来优化一版。

优化思路： 判断每一趟是否有元素交换，如果没有元素交换就结束循环。

// 究极进化版
function bubbleSort(arr) {
  const len = arr.length;
  if (!arr || len < 2) {
    return arr;
  }
  // 最后交换的位置
  let lastIndex = len;
  // 边界
  let border = len - 1;
  // 趟数，记录多少趟
  for (let i = 0; i < len - 1; i++) {
    // 是否没有元素交换
    let isNotSwap = true;
    // 每趟比较的次数 border
    for (let j = 0; j < border; j++) {
      // 相邻元素两两对比
      if (arr[j] > arr[j + 1]) {
        isNotSwap = false;
        lastIndex = j;
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]; // 元素交换
      }
    }
    border = lastIndex;
    // 有序的数据
    if (isNotSwap) {
      break;
    }
  }
  return arr;
}

选择排序

实现思路:

1. 找到数组中最小/大的元素，把他放在数组的头部
2. 剩余元素中找到最小/大的元素，依次排在数组的前面
3. 以此类推

动图演示：

程序打印：

arr :>> [2, 44, 38, 5, 47, 15, 36, 26, 27, 3, 46, 4, 19, 50, 48]
arr :>> [2, 3, 38, 5, 47, 15, 36, 26, 27, 44, 46, 4, 19, 50, 48]
arr :>> [2, 3, 4, 5, 47, 15, 36, 26, 27, 44, 46, 38, 19, 50, 48]
arr :>> [2, 3, 4, 5, 47, 15, 36, 26, 27, 44, 46, 38, 19, 50, 48]
arr :>> [2, 3, 4, 5, 15, 47, 36, 26, 27, 44, 46, 38, 19, 50, 48]
arr :>> [2, 3, 4, 5, 15, 19, 36, 26, 27, 44, 46, 38, 47, 50, 48]
arr :>> [2, 3, 4, 5, 15, 19, 26, 36, 27, 44, 46, 38, 47, 50, 48]
arr :>> [2, 3, 4, 5, 15, 19, 26, 27, 36, 44, 46, 38, 47, 50, 48]
arr :>> [2, 3, 4, 5, 15, 19, 26, 27, 36, 44, 46, 38, 47, 50, 48]
arr :>> [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 46, 44, 47, 50, 48]
arr :>> [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 50, 48]
arr :>> [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 50, 48]
arr :>> [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 50, 48]
arr :>> [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

时间复杂度

O(n^2)

$$ （n-1）+ (n-2) + ... 2 ++ 1 = n(n-1)/2 = n²/2 - n/2 $$

实现过程

// 乞丐版
function selectionSort(arr) {
  let len = arr.length;
  let minIndex;
  for (let i = 0; i < len - 1; i++) {
    minIndex = i;
    for (let j = i + 1; j < len; j++) {
      if (arr[j] < arr[minIndex]) {
        minIndex = j; // 将最小数的索引保存
      }
    }
    [arr[minIndex], arr[i]] = [arr[i], arr[minIndex]];
  }
  return arr;
}

选择排序每次都选出最大最小的，那我们能不能每次循环的时候把最大和最小的都找出来，这样子是不是就会更快一点呢？

优化思路：

1. 同时找出最大和最小的值，并记录他们的索引
2. 将最小的放前面，最大的放后面

// 进化版
function selectionSort(arr) {
  let len = arr.length;
  let minIndex, maxIndex;
  // 每次排两个元素，循环的长度要动态减少1
  for (let i = 0; i < len - 1 - i; i++) {
    minIndex = i;
    maxIndex = i;
    for (let j = i + 1; j <= len - 1 - i; j++) {
      if (arr[j] < arr[minIndex]) {
        minIndex = j; // 当前循环最小的索引
      }
      if (arr[j] > arr[maxIndex]) {
        maxIndex = j; // 当前循环最大的索引
      }
    }
    // 交换最小值位置
    [arr[minIndex], arr[i]] = [arr[i], arr[minIndex]];
    // 如果 maxIndex == i 则说明不要排序
    if(maxIndex != i){
      // 交换最大值位置
      [arr[maxIndex], arr[len - 1 - i]] = [arr[len - 1 - i], arr[maxIndex]];
    }
  }
  return arr;
}