排序算法—插入排序快速排序

排序算法的分类

什么是线性时间 or 非线性时间

摘自维基百科解释

在计算复杂性理论，一个被称为线性时间或 Ο(n)时间的算法，表示此算法解题所需时间与输入资料的大小成正比，通常以n表示。换句话说，执行时间与输入资料大小为线性比例。例如将一列数字加总的所需时间，正比于串列的长度。

各大排序算法时间、空间复杂度图表：

插入排序

插入排序，意为将待排序的元素插入已经排序好的数列中。假设前面 n-1(其中 n>=2)个数已经是排好顺序的，现将第 n 个数插到前面已经排好的序列中，然后找到合适自己的位置，使得插入第n个数的这个序列也是排好顺序的。按照此法对所有元素进行插入，直到整个序列排为有序的过程，称为插入排序。

/**
 * @description: 插入排序
 * @param {Array}
 * @return {}
 */
function insert (array) {
  for (let i = 1; i < array.length; i++) {
    let item = array[i]
    let j = i - 1
    for (; j >= 0 && item < array[j]; j-- ) {
      array[j+1] = array[j]
    }
    array[j+1] = item
  }
}

let Array = [6, 2, 3, 1, 4, 5]
insert(Array)
console.log(Array)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

快速排序

从数列中挑出一个元素，称为 “基准”,重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面。在这个分区退出之后，该基准就处于数列的中间位置。接下来再递归地把小于基准值元素的子数列和大于基准值元素的子数列排序。

/**
 * @description: 这里是描述
 * @param {type} paramName
 * @return {type} returnName
 */

function quickSort(array, start, end) {
  if (start < end) {
    let base = array[start]
    let left = start
    let right  = end
    while(left < right) {
      while(left < right && array[right] >= base) {
        right--
      }
      array[left] = array[right]
      
      while(left < right && array[left] <= base) {
        left++
      }
      array[right] = array[left]
    }
    array[left] = base
    quickSort(array, start, left-1)
    quickSort(array, left+1, end)
  }
}

let arr = [4, 5, 8, 1, 7, 2, 6, 3];
quickSort(arr, 0, arr.length - 1);
console.log(arr);
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