排序算法

发表于 | 更新于: | 分类于 | | 阅读次数:
字数统计: 670字 | 阅读时长 ≈ 2分钟
补充关于空间复制度和时间复杂度的概念。

冒泡排序

使用 冒泡排序最重要的思想是: 将一个数和数组中右边的数依次进行比较，如果找到了有左边的数大于右边的数，进行互换，最终一次循环之后，放在左边的数是右边中的最小值，这样依次进行排列，最后得到的左边的数组是已经被排好序之后的数组。
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++) {
    // 保证一轮循环之后 arr[i] 是 i 之后数组的最小值
    for (let j = i + 1; j < len; j++) {
    // 比较相邻两个的大小, 将较大的那个排到后面去
    // 始终保证
      if (arr[j] < arr[i]) {
        // 使用 es6 结构赋值进行交换
		let t = arr[j];
		arr[j] = arr[i];
		arr[i] = t;
      }
    }
  }
}

快速排序

使用快速排序的基本原理是:算法参考某一个值，遍历一个数组，将数组中小于参考值的元素放在左边的数组中，将数组中大于参考值的元素放在右边的数组中，递归左右数组，返回合并之后的数组。合并之后的数组是已经被排好序的数组。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/*
* @description quickSort 用于进行快速排序
* @return {Array} 经过排序之后的数组
*/
function quicksort(arr) {
  if (arr.length <= 1) {
    return arr;    
  }
  let first = arr[0];
  let leftArr = [];
  let rightArr = [];
  let len = arr.length;
  for (let i = 0; i < len; i++) {
    if (arr[i] < first) {
      leftArr.push(arr[i]);  
    }
    if (arr[i] > first) {
      rightArr.push(arr[i]);    
    }
  }
  // 一层一层剥开我的心
  // 一直一直进行递归~~
  return [].concat(quicksort(leftArr), [first], [quicksort(rightArr)]);
}

插入排序

使用 插入排序的基本原理是: 想象一个数组分为两部分，对于整个数组进行遍历的时候，被遍历到的数组元素的左边是已经排好序的，实现的过程是，遍历数组元素左边的元素，和遍历到的元素进行对比，最终将这个新的元素插入到左边元素的合适的位置。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/*
* @description insertSort 用于进行插入排序
* @param {Array} arr 进行排序的数组
* @return {Array} arr 返回进过排序之后的数组
*/
function insertSort(arr) {
  for (let i = 0; i < arr.length; i++) {
    let temp = arr[i];
    for (let j = i - 1; j >= 0; j--) {
      if (arr[j] > temp) {
        // 将大于 temp 的元素向后推一位
        // 这些元素是之前已经被排好序的
        arr[j + 1] = arr[j];
        // 将元素插入到 arr[j] 的位置
        arr[j] = temp;
      }
    }
  }
  return arr;
}