排序算法
排序算法没有优劣之分，在不同的场景中，不同的排序算法执行效率不同。
1.选择排序 Selection Sort
一次选择排序，可以将某个区间的最小值排列到该区域的第一位，具体的方式是：
1.找出该区域的最小值
2.将该值与该区域第一个值交换
3.对下一个区域重复上述过程，直到排序完成
let arr = [3, 2, 4, 6, 7, 9, 3, 1, 4]; /** * 选择排序 * @param asc {Boolean} 是否升序 * @returns {Array} */ Array.prototype.chooseSort = function (asc = true) { if (this.length < 1) return this; // 选择排序以升序为例： 从左侧选择一个值的索引进行对比，如果值大，那么交换索引，每一圈拿一个最大的索引，然后通过索引来交换位置 for (let i = 0, l = this.length; i < l; i++) { let index = 0; // 获取一个索引，然后通过索引的值来进行对比 for (let j = 1, jl = l - i; j < jl; j++) { if (asc && this[j] > this[index]) { index = j; } else if (!asc && this[j] < this[index]) { index = j; } } // 进行交换位置，每一圈拿一个最大或者最小值和数组最右边的一位交换 [this[index], this[l - i - 1]] = [this[l - i - 1], this[index]] } return this; } // console.log(arr.chooseSort()); console.time('选择排序用时') console.log(arr.chooseSort()); console.log(arr.chooseSort(false)); console.timeEnd('选择排序用时')
2.冒泡排序 Bubble Sort
一次冒泡排序，可以将某个区域序列的最大值排序到该区域的最后一位，具体的方式是：
1.将第1位和第2位比较，如果前者比后者大则交换
2.将第2位和第3位比较，如果前者比后者大则交换
3.依次类推，直到比较到该区域的最后两位
4.重复上述过程，直到序列排序完成
let arr = [3, 2, 4, 6, 7, 9, 3, 1, 4]; /** * 冒泡排序 * @param asc {Boolean} 是否升序 * @returns {Array} */ Array.prototype.bubbleSort = function (asc = true) { if (this.length < 1) return this; // 快速排序以升序为例，每一次选择前两个进行比较，大的放在前面，小的放后面，每一圈拿一个最大值， for (let i = 0, l = this.length; i < l; i++) { for (let j = 1, jl = l - i; j < jl; j++) { if (asc && this[j - 1] > this[j]) { // 交换位置 [this[j - 1], this[j]] = [this[j], this[j - 1]] } else if (!asc && this[j - 1] < this[j]) { [this[j - 1], this[j]] = [this[j], this[j - 1]] } } } return this; } console.time('冒泡排序用时') console.log(arr.bubbleSort()); console.log(arr.bubbleSort(false)); console.timeEnd('冒泡排序用时')
3.插入排序 Insertion Sort
将序列分为两个部分，一部分是有序的，一部分是无序的，现在要做的是，就是不断的从无序的部分取出数据，加入到有序的部分，直到整个排序完成
例如：序列[5, 7, 2, 3, 6]
1.分为有序的序列和无序的序列 (5) (7 2 3 6)
2.不断的扩充有序序列 (5 7) (2 3 6)
3.不断的扩充有序序列 (2 5 7) (3 6)
4.不断的扩充有序序列 (2 3 5 7) (6)
5.不断的扩充有序序列 (2 3 5 6 7)
6.排序完成
let arr = [3, 2, 4, 6, 7, 9, 3, 1, 4]; /** * 插入排序 * @param asc {Boolean} 是否升序 * @returns {Array} */ Array.prototype.insertionSort = function (asc = true) { if (this.length < 1) return this; // 插值排序以升序为例：把数据分为两个部分，先从无序部分取出数据到有序那部分进行排序 for (let i = 1, l = this.length; i < l; i++) { // 获取第一位的数据， 如果不满足排序条件，需要插入到对应的位置 if (asc && this[i] < this[i - 1]) { let temp = this[i]; // 把后面的这一位需要排到前面的合适位置 for (let j = i; j >= 0; j--) { if (j > 0 && this[j - 1] > temp) { this[j] = this[j - 1]; } else { this[j] = temp; break } } } else if (!asc && this[i] > this[i - 1]) { let temp = this[i]; for (let j = i; j >= 0; j--) { if (j > 0 && this[j - 1] < temp) { this[j] = this[j - 1]; } else { this[j] = temp; break; } } } } return this; } // console.log(arr.insertionSort(false)); console.time('插入排序用时') console.log(arr.insertionSort()); console.log(arr.insertionSort(false)); console.timeEnd('插入排序用时')
4.快速排序 Quick Sort
选择一个数（比如序列的最后一位）作为基准数，将整个序列排序成两部分，一部分比该数小，另一部分比该数大，基准数在中间，然后对剩余的序列做同样的事情，直到排序完成
例如：序列[5, 7, 2, 3, 6, 4]
1.选择4作为基准数，排序成为：(3, 2) 4 (7, 6, 5)
2.对于3,2， 继续使用该方式排序，得到： (2, 3) 4 (7,6,5)
3.对于7,6,5，继续使用该方式排序，得到： (2, 3) 4 (5,6,7)
4.排序完成
let arr = [3, 2, 4, 6, 7, 9, 3, 1, 4]; // 快速排序 /** * 快速排序 * @param asc {Boolean} 是否升序 * @returns {Array} */ Array.prototype.quickSort = function (asc = true) { if (this.length < 1) return this; // 快速排序：以升序为例， 获取中间的一个基线， 分为两边，小的在左，大的在右边， 左右两边继续选基线排序 function __quickSort(arr, start, end) { if (start >= end || start >= arr.length - 1) return arr; let low = start, high = end, key = arr[end]; while (low < high) { // 升序， if (asc) { // 地位小于高位 并且 当前的值小于基线 while (low < high && arr[low] <= key) low++; // 否则当前地位不动，移动并且把当前低位指向的值赋值给高位 arr[high] = arr[low]; // 移动高位 while (low < high && arr[high] > key) high--; // 否在赋值给低位，从新移动低位指针 arr[low] = arr[high]; } else { // 降序 while (low < high && arr[low] >= key) low++; arr[high] = arr[low]; while (low < high && arr[high] < key) high--; arr[low] = arr[high]; } } // low === high,当两根指针重合， 把中间的值赋值 arr[high] = key; __quickSort(arr, start, low - 1); __quickSort(arr, low + 1, end) } __quickSort(this, 0, this.length - 1); return this; } // console.log(arr.quickSort(false)); console.time('快速排序用时') console.log(arr.quickSort()); console.log(arr.quickSort(false)); console.timeEnd('快速排序用时')
结果如下：
[ 1, 2, 3, 3, 4, 4, 6, 7, 9 ] [ 9, 7, 6, 4, 4, 3, 3, 2, 1 ] 冒泡排序用时: 11.315ms [ 1, 2, 3, 3, 4, 4, 6, 7, 9 ] [ 9, 7, 6, 4, 4, 3, 3, 2, 1 ] 选择排序用时: 0.473ms [ 1, 2, 3, 3, 4, 4, 6, 7, 9 ] [ 9, 7, 6, 4, 4, 3, 3, 2, 1 ] 插入排序用时: 0.359ms [ 1, 2, 3, 3, 4, 4, 6, 7, 9 ] [ 9, 7, 6, 4, 4, 3, 3, 2, 1 ] 快速排序用时: 0.415ms
