排序算法

发表于 | 分类于

简单记录学习极客时间-数据与结构之美-排序相关的知识记录

tips

排序动画演示 可用手机app

时间复杂度 On2

冒泡排序

冒泡排序只会操作相邻的两个数据。每次冒泡操作都会对相邻的两个元素进行比较，看是否 满足大小关系要求。如果不满足就让它俩互换。一次冒泡会让至少一个元素移动到它应该在 的位置，重复 n 次，就完成了 n 个数据的排序工作。

冒泡排序最不容易出错。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
const arr = [4,5,2,3,8,7,6,1,10]
function bubble(arr) {
  const l = arr.length
  for (let i = 0; i < l - 1; i++) {
    // 没有交换发生 其实代表数组已经是有序的了
    let flag = true;
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[i] > arr[j]) {
        const temp = arr[i]
        arr[i] = arr[j]
        arr[j] = temp
        // 有交换发生
        flag = false;
      }
    }
    if (flag) {
      break;
    }
  }
}
bubble(arr)
console.log(arr);

插入排序

首先，我们将数组中的数据分为两个区间，已排序区间和未排序区间。初始已排序区间只有 一个元素，就是数组的第一个元素。插入算法的核心思想是取未排序区间中的元素，在已排 序区间中找到合适的插入位置将其插入，并保证已排序区间数据一直有序。重复这个过程， 直到未排序区间中元素为空，算法结束。

插入排序写起来比较费劲，要注意的地方比较多

我自己的写的

1
2
3
4
5
6
7
8
9
10
11
12
13
function insert(arr) {
  const l = arr.length
  for (let i = 0; i < l - 1; i++) {
    let j = i + 1
    while (arr[j-1] > arr[j] && j>=0) {
      const temp = arr[j]
      arr[j] = arr[j-1]
      arr[j-1] = temp
      j--
    }
  }
}
insert(arr)

教程写的，已经换成JavaScript，并加了注释

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
function insert2(arr) {
  const l = arr.length;
  for (let i = 1; i < l; ++i) {
    // 缓存当前处理的元素，减少交换次数 
    let value = arr[i];
    // 对比前方排序区，查找插入的位置
    let j = i - 1;
    for ( ; j >= 0; --j) {
      if (arr[j] > value) {
        // 相当于把arr[j]向右移一位
        // 第一次被覆盖掉的元素是当前处理元素，已在顶部缓存
        // 第一次以后被覆盖的元素，实际上已经保存在右侧了
        arr[j + 1] = arr[j]; // 数据移动
      } else {
        // 当前元素已经满足条件，不需要交换
        break;
      }
    }
    // 只在最后交换 j+1 
    arr[j + 1] = value; // 插入数据
  }
}

选择排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
function select(arr) {
  const l = arr.length
  let min, minIndex
  for (let i = 0; i < l - 1; i++) {
   // 起始位置
    min = arr[i]
    minIndex = i
    for (let j = i+1; j < l; j++) {
      if (arr[j] < min) {
        min = arr[j]
        minIndex = j
      }
    }
    const temp = arr[i]
    arr[i] = min
    arr[minIndex] = temp
  }
}
// select(arr)
console.log(arr);

时间复杂度 O nlogn

归并排序(稳定)

自己的代码，未优化的版本，找了好久的错误

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
// 归并排序
function merginInto(arr, l, r) {
  if (l === r) {
    return arr
  }
  const m = (l + r) >> 1 // 相当于除以2 取整
  const left = arr.slice(l, m + 1)
  const right = arr.slice(m + 1, r + 1)
  return sortOrderArr(
    left.length <= 1 ? left: merginInto(
     // 忘了把边界改成新数组的了
      left, 0, m
    ),
    right.length <= 1 ? right : merginInto(
      // 忘了把边界改成新数组的了
      right, 0, r - (m + 1)
    )
  )
}
// 将两个有序数组合并
function sortOrderArr(arr1, arr2) {
  const res = []
  let i1 = i2 = 0, l1 = arr1.length, l2 = arr2.length
  while (i1<l1 || i2<l2) {
    if (i1 === l1) {
      res.push(arr2[i2++])
    } else if(i2===l2) {
      res.push(arr1[i1++])
    }else if (arr1[i1] <= arr2[i2]) {
      res.push(arr1[i1++])
    }else(
      res.push(arr2[i2++])
    )
  }
  return res
}

比较大众的写法，这个类似于二叉树的后续遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
function mergeInto(arr, l, r) {
  if (l >= r) {
    return arr
  }
  const m = (l + r) >> 1;
  // 原地排序 不需要返回
  mergeInto(arr, l, m)
  mergeInto(arr, m + 1, r)
  // 两个已经拍好序的数组
  mergeArr(arr, l, m, r)
  return arr
}
function mergeArr(arr, l, m, r) {
  const res = []
  let i1 = l, i2 = m + 1, l1 = m+1, l2 = r+1
  while (i1<l1 || i2<l2) {
    if (i1 === l1) {
      res.push(arr[i2++])
    } else if(i2===l2) {
      res.push(arr[i1++])
    }else if (arr[i1] <= arr[i2]) {
      res.push(arr[i1++])
    }else(
      res.push(arr[i2++])
    )
  }
  for (let i = l,j=0; i < r+1; i++,j++) {
    arr[i] = res[j]
  }
}

快速排序(不稳定)

把比参考位置小的数移到左侧，大的移到右侧，如果不额外占用空间的话，比较难写

空间复杂度 O n 比较容易写出来

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
function fastSort(arr, l, r) {
  if (l >= r) {
    return arr
  }
  const p = fastSortHandle(arr, l, r)
  fastSort(arr, l, p - 1)
  fastSort(arr, p + 1, r)
  return arr
}
// 快排辅助函数 分区 排序
function fastSortHandle(arr, l, r) {
 // 占用了 On的空间
  const res = []
  //随机会好一点
  const rdm = Math.floor(Math.random()*(r-l+1)+l)
  const ref = arr[rdm]
  let li = l, ri = r
  for (let i = l; i < r + 1; i++) {
    if (i === rdm) {
      continue
    }
    if (arr[i] <= ref) {
      res[li] = arr[i]
      li++
    } else {
      res[ri] = arr[i]
      ri--
    }
  }
  res[ri] = ref
  for (let i = l; i < r+1; i++) {
    arr[i] = res[i]
  }
  return ri
}

O1空间复杂度左右归类的算法解释

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
function fastSortHandle(arr, l, r) {
  // const rdm = Math.floor(Math.random()*(r-l+1)+l)
  const rdm = 1
  const ref = arr[rdm]
  let j = l
  for (let i = l; i < r + 1; i++) {
    // 跳过
    if (i === rdm) {
      continue;
    }
    // 跳过
    if (j === rdm) {
      j++
    }
    if (arr[i] <= ref) {
      [arr[i], arr[j]] = [arr[j], arr[i]]
      j++
    }
  }
  if (rdm < j) {
    j--
  }
  [arr[rdm], arr[j]] = [arr[j], arr[rdm]]
  return j
}

当选择一个随机数N，下标INDEX作为参照点的话，程序运行到关键点的情况应该如下图所示

左侧是小于等于N的数，右侧是大于N的数，但是N可能在左侧或者右侧

image-20211112105742642

最好的情况就是 把N的位置放进 j-1 和 j之间，但是这样时间复杂度较高，采取交换替代

如果N在左侧就和J-1交换，N在右侧就和J置换，如果不需要随机选择位置的话，N取最右侧元素，就不需要判断了

1
2
3
4
5
6
if (rdm < j) {
    j--
  }
  
  [arr[rdm], arr[j]] = [arr[j], arr[rdm]]
  return j

更好的随机数左右归类

力扣官方采取先用随机数与最后一位交换位置在进行常规方法，方法容易理解，也不容易出错

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int partition(vector<int>& nums, int l, int r) {
      int pivot = nums[r];
      int i = l - 1;
      for (int j = l; j <= r - 1; ++j) {
          if (nums[j] <= pivot) {
              i = i + 1;
              swap(nums[i], nums[j]);
          }
      }
      swap(nums[i + 1], nums[r]);
      return i + 1;
  }
  int randomized_partition(vector<int>& nums, int l, int r) {
      int i = rand() % (r - l + 1) + l; // 随机选一个作为我们的主元
      swap(nums[r], nums[i]);
      return partition(nums, l, r);
  }

最后总结出JavaScript版本的快速排序

image-20211112112025117

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
function fastSort(arr, l, r) {
  if (l >= r) {
    return arr
  }
  const p = fastSortHandle(arr, l, r)
  // -1 +1 可别忘 会死循环的
  fastSort(arr, l, p - 1)
  fastSort(arr, p + 1, r)
  return arr
}
function fastSortHandle(arr, l, r) {
  const rdm = Math.floor(Math.random() * (r - l + 1) + l)
  // 与最后元素交换
  swap(arr, rdm, r)

  const ref = arr[r]
  let j = l
  for (let i = l; i < r; i++) {
    if (arr[i] <= ref) {
      swap(arr, i, j)
      j++
    }
  }
  swap(arr, r, j)
  return j
}
function swap(arr, p, q) {
  const temp = arr[p]
  arr[p] = arr[q]
  arr[q] = temp
}

归并排序和快速排序的区别与联系

image-20211112112920927

快排和归并用的都是分治思想，递推公式和递归代码也非常相似，那它们的区别在哪里呢?

image-20211112113107064可以发现，归并排序的处理过程是由下到上的，先处理子问题，然后再合并。

而快排正好相反，它的处理过程是由上到下的，先分区，然后再处理子问题。

归并排序虽然是稳定的、时 间复杂度为 O(nlogn) 的排序算法，但是它是非原地排序算法。我们前面讲过，归并之所以 是非原地排序算法，主要原因是合并函数无法在原地执行。快速排序通过设计巧妙的原地分区函数，可以实现原地排序，解决了归并排序占用太多内存的问题。