快排&&排序算法

Js实现冒泡排序

// 是一种计算机科学领域的较简单的排序算法
// 它重复的走访过要排序的元素列，依次比较两个相邻的元素，如果顺序（如从大到小，首字母）错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是该元素列已经排序完成。

冒泡排序是效率最低的排序算法，由于算法嵌套了两轮循环，所以时间复杂度委O(n^2)

最好的情况给出一个已经排序的数组进行冒泡排序，时间复杂度为O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 冒泡排序
function bubbleSort(arr) {
  let len = arr.length;
  // 遍历数组的长度，以确定循环次数
  for (let i = 0; i < len;i++) {
    // 遍历数组len次，忽略后面的i项
    for (let j = 0; j < len - 1 - i; j++) {
      // 将每一项与后一项进行对比，不符合要求的就换位
      if (arr[j] > arr[j + 1]) {
        <!-- es6数组解构赋值 -->
        [arr[j + 1], arr[j]] = [arr[j], arr[j + 1]]
      }
    }
  }
  return arr
}

实现一个快排

快速排序：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行上述递归排序，以此达到整个数据变成有序序列，时间复杂度为 O(n log n)。

// 1.Quickersort通过数组选取一个元素表示为基准点，把数组中的所有其他元素分为两类-（大于和小于此基准点的数组）
// 2.然后把作为这一轮排序结果的两个数组（数组元素都小于基准点的数组和数组元素都大于基准点的数组）再进行相同的排序。即分别再选个基准点，然后基于基准点分为两个数组元素分别小于和大于基准点的数组。
// 3.最终，由于最后数组中没有元素或只有一个元素，因此不用再比较了。剩下的值都已经基于基准点拍好序了。
（时间复杂度（平均）O(nlogn))

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
const quickSort1 = arr => {
  if (arr.length <= 1) {//数组小于等于1时的情况
    return arr;
  }
  const midIndex = Math.floor(arr.length / 2)//取中间的元素为基准点
   // 使用splice截取中间值，第一个参数为截取的索引，第二个参数为截取的长度；
    // 如果此处使用arrArr=arr[index]; 那么将会出现无限递归的错误；
    // splice影响原数组
  const arrArr = arr.splice(midIndex, 1)
  const midIndexVal = arrArr[0]
  const left = []
  const right = []
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] < midIndexVal) {
      left.push(arr[i]);
    } else {
      right.push(arr[i])
    }
  }
  return quickSort1(left).concat(midIndexVal, quickSort1(right));//重复进行上面的步骤，直到剩下小于等于一个元素。
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 快速排序
const testQuickSort = arr => {
  if (arr.length <= 1) {
    return arr;
  }
  const mid = arr[0];// 基准值
  const left = []
  const right = [];
  for (let i = 1; i < arr.length; i++) {
    if (arr[i] < mid) {
      left.push(arr[i])
    } else {
      right.push(arr[i])
    }
  }
  return [...testQuickSort(left), mid, ...testQuickSort(right)]
}

选择排序 （O^2）

从上面可以看到，对于具有 n 个记录的无序表遍历 n-1 次，第i 次从无序表中第 i 个记录开始，找出后序关键字中最小的记录，然后放置在第 i 的位置上

直至到从第n个和第n-1个元素中选出最小的放在第n-1个位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

// 选择排序
function testSelectSort(arr) {
  let len = arr.length;
  let minIndex;
  for (let i = 0; i < len - 1; i++) {
    minIndex = i;
    for (let j = 0; j < len; j++) {
      if (arr[j] < arr[minIndex]) {  //寻找最小数
        minIndex = j;  //将最小数的索引保存
      }
    }
    [arr[i], arr[minIndex]] = arr[minIndex], arr[i];
  }
  return arr;
}

第一次内循环比较N - 1次，然后是N-2次，N-3次，……，最后一次内循环比较1次 共比较的次数是 (N - 1) + (N - 2) + … + 1，求等差数列和，得 (N - 1 + 1)* N / 2 = N^2 / 2，舍去最高项系数，其时间复杂度为 O(N^2)

从上述也可以看到，选择排序是一种稳定的排序

插入排序

// 插入排序
// 将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。

// 从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置

// 如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面

1
2
3
4
5
6
7
8
9
10
11
12
13
14
function testInsertSort(arr) {
  const len = arr.length;
  let preIndex, current;
  for (let i = 1; i < len; i++) {
    preIndex = i - 1;
    current = arr[i];
    while (preIndex >= 0 && arr[preIndex] > current) {
      arr[preIndex + 1] = arr[preIndex];
      preIndex--;
    }
    arr[preIndex + 1] = current;
  }
  return arr;
}
1
2
3
4
5
6
7
8
9
10
function InsertSort(arr) {
  for (let i = 0; i < arr.length; i++) {
    for (let j = 0; j < i; j++) {
      if (arr[j] > arr[i]) {
        [arr[i], arr[j]] = [arr[j], arr[i]]
      }
    }
  }
  return arr;
}

// 在插入排序中，当待排序数组是有序时，是最优的情况，只需当前数跟前一个数比较一下就可以了，这时一共需要比较N- 1次，时间复杂度为O(n)

// 最坏的情况是待排序数组是逆序的，此时需要比较次数最多，总次数记为：1+2+3+…+N-1，所以，插入排序最坏情况下的时间复杂度为O(n^2)

// 通过上面了解，可以看到插入排序是一种稳定的排序方式

参考文章