采用javascript编写排序算法及其时间复杂和空间复杂度（冒泡、快排、直接插入、归并排序等）

正值秋招季，对排序算法进行了总结。

冒泡排序

基本思想：对相邻的元素进行两两比较，顺序相反则交换。
冒泡排序的平均时间复杂度为 O(n²) ，最坏时间复杂度为 O(n²) ，最好的时间复杂度是O(n)，空间复杂度为 O(1) ，是稳定排序。

function swap(arr, index1, index2) {var temp = arr[index1];arr[index1] = arr[index2];arr[index2] = temp;}function bubbleSort(arr) {var len = arr.length;for (let i = 0; i < len; i ++) {for(let j = 0; j < len - i; j ++) {if (!arr[j + 1]) {break;}if (arr[j] > arr[j + 1]) {swap(arr, j, j + 1);}}}console.log(initArr)return initArr;}bubbleSort(initArr)

优化后

function bubbleSort(arr) {if (!Array.isArray(arr) || arr.length <= 1) return;let lastIndex = arr.length - 1;while (lastIndex > 0) { // 当最后一个交换的元素为第一个时，说明后面全部排序完毕let flag = true, k = lastIndex;for (let j = 0; j < k; j++) {if (arr[j] > arr[j + 1]) {flag = false;lastIndex = j; // 设置最后一次交换元素的位置[arr[j], arr[j+1]] = [arr[j+1], arr[j]];}}if (flag) break;}}

快速排序

将一个数据分割成两部分，左边部分比右边部分小。对两部分分别进行快速排序。
快速排序的平均时间复杂度为 O(nlogn) ，最坏时间复杂度为 O(n²) ，最好的时候为 O(logn)，空间复杂度为 O(logn) ，不是稳定排序。

// 快速排序var initArr = [9,8,7,6,5,4,3,2, 12,20,40];function quickSort(arr) {if(arr.length === 0) {return []}if (arr.length === 1) {return arr;}var targetNum = arr[0];var leftArr = [];var rightArr = [];for (var i = 1; i < arr.length; i ++) {var num = arr[i]if (num < targetNum) {leftArr.push(num);} else {rightArr.push(num);}}var newArr = quickSort(leftArr).concat(targetNum, quickSort(rightArr));return newArr;}console.log(quickSort(initArr))

直接插入排序

直接插入排序基本思想是每一步将一个待排序的记录，插入到前面已经排好序的有序序列中去，直到插完所有元素为止。
插入排序的平均时间复杂度为 O(n²) ，最坏时间复杂度为 O(n²) ，最好的时间复杂度 O(n)，空间复杂度为 O(1) ，是稳定排序。

function swap(arr, index1, index2) {var temp = arr[index1];arr[index1] = arr[index2];arr[index2] = temp;}var initArr = [9,8,7,6,5,4,3];// 缺点： 不停的swap影响性能function insertSort(arr) {var len = arr.length;// 边界情况if (len < 2) {return arr;}for(let i = 1; i < len; i ++) {for (var j = i; j > 0; j --) {if (arr[j - 1] > arr[j]) {swap(arr, j , j - 1);}}}console.log(arr);}console.time(\'优化前\');insertSort(window.testArr);console.timeEnd(\'优化前\');console.log(window.count);

方法二

function insertSort(array) {let length = array.length;// 如果不是数组或者数组长度小于等于1，直接返回，不需要排序if (!Array.isArray(array) || length <= 1) return;// 循环从 1 开始，0 位置为默认的已排序的序列for (let i = 1; i < length; i++) {let temp = array[i]; // 保存当前需要排序的元素let j = i;// 在当前已排序序列中比较，如果比需要排序的元素大，就依次往后移动位置while (j -1 >= 0 && array[j - 1] > temp) {array[j] = array[j - 1];j--;}// 将找到的位置插入元素array[j] = temp;}return array;}

希尔排序

希尔排序的基本思想是把数组按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的元 素越来越多，当增量减至1时，整个数组恰被分成一组，算法便终止。
希尔排序的平均时间复杂度为 O(nlogn) ，最坏时间复杂度为 O(n^s) ，空间复杂度为 O(1) ，不是稳定排序。

function hillSort(array) {let length = array.length;// 如果不是数组或者数组长度小于等于1，直接返回，不需要排序if (!Array.isArray(array) || length <= 1) return;// 第一层确定增量的大小，每次增量的大小减半for (let gap = parseInt(length >> 1); gap >= 1; gap = parseInt(gap >> 1)) {// 对每个分组使用插入排序，相当于将插入排序的1换成了 nfor (let i = gap; i < length; i++) {let temp = array[i];let j = i;while (j - gap >= 0 && array[j - gap] > temp) {array[j] = array[j - gap];j -= gap;}array[j] = temp;}}return array;}

归并排序

归并排序是利用归并的思想实现的排序方法，该算法采用经典的分治策略。递归的将数组两两分开直到只包含一个元素，然后 将数组排序合并，最终合并为排序好的数组。
归并排序的平均时间复杂度为 O(nlogn) ，最坏时间复杂度为 O(nlogn) ，空间复杂度为 O(n) ，是稳定排序。

function mergeSort(array) {let length = array.length;// 如果不是数组或者数组长度小于等于0，直接返回，不需要排序if (!Array.isArray(array) || length === 0) return;if (length === 1) {return array;}let mid = parseInt(length >> 1), // 找到中间索引值left = array.slice(0, mid), // 截取左半部分right = array.slice(mid, length); // 截取右半部分return merge(mergeSort(left), mergeSort(right)); // 递归分解后，进行排序合并}function merge(leftArray, rightArray) {let result = [],leftLength = leftArray.length,rightLength = rightArray.length,il = 0,ir = 0;// 左右两个数组的元素依次比较，将较小的元素加入结果数组中，直到其中一个数组的元素全部加入完则停止while (il < leftLength && ir < rightLength) {if (leftArray[il] < rightArray[ir]) {result.push(leftArray[il++]);} else {result.push(rightArray[ir++]);}}// 如果是左边数组还有剩余，则把剩余的元素全部加入到结果数组中。while (il < leftLength) {result.push(leftArray[il++]);}// 如果是右边数组还有剩余，则把剩余的元素全部加入到结果数组中。while (ir < rightLength) {result.push(rightArray[ir++]);}return result;}

堆排序

堆排序的基本思想是：将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行 交换，此时末尾就为最大值。然后将剩余 n-1 个元素重新构造成一个堆，这样会得到 n 个元素的次小值。如此反复执行， 便能得到一个有序序列了。
首先实现一个堆

class Heap {constructor() {this.data = [null];}getData() {console.log(this.data);return this.data;}insert(num) {this.data.push(num);this.shiftUp(this.data.length - 1);}extracMax() {if (this.data.length > 1) {// var resultArr = this.data.splice(1, 1);// debugger;swap(this.data, 1, this.data.length - 1);var result = this.data.pop();this.shiftDown(1);return result;}}shiftUp(currentIndex) {while (currentIndex > 1 && this.data[currentIndex] > this.data[parseInt(currentIndex / 2)]) {swap(this.data, currentIndex, parseInt(currentIndex / 2));currentIndex = parseInt(currentIndex / 2);}}shiftDown(currentIndex) {// debugger;while (this.data[currentIndex * 2] > this.data[currentIndex] || this.data[currentIndex * 2 + 1] > this.data[currentIndex]) {if (this.data[currentIndex * 2] < this.data[currentIndex * 2 + 1]) {swap(this.data, currentIndex * 2 + 1, currentIndex);currentIndex = currentIndex * 2 + 1;} else {swap(this.data, currentIndex * 2, currentIndex);currentIndex = currentIndex * 2;}}}};

再排序

var initArr = [9, 8, 7, 6, 5, 4, 3, 2, 1];  // 测试数据function heapSort() {var heapData = new Heap();var resultArr = [];initArr.forEach((val, index) => {heapData.insert(val);});// console.log(heapData.getData())// debugger;for (var i = 0; i < initArr.length; i++) {// debugger;var result = heapData.extracMax();resultArr.unshift(result);}console.log(resultArr);return resultArr;}heapSort(initArr);

基数排序

基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。排序过程：将 所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样 从最低位排序一直到最高位排序完成以后，数列就变成一个有序序列。
基数排序的平均时间复杂度为 O(nk)，k 为最大元素的长度，最坏时间复杂度为 O(nk)，空间复杂度为 O(n) ，是稳定 排序。

function radixSort(array) {let length = array.length;// 如果不是数组或者数组长度小于等于1，直接返回，不需要排序if (!Array.isArray(array) || length <= 1) return;let bucket = [],max = array[0],loop;// 确定排序数组中的最大值for (let i = 1; i < length; i++) {if (array[i] > max) {max = array[i];}}// 确定最大值的位数loop = (max + \'\').length;// 初始化桶for (let i = 0; i < 10; i++) {bucket[i] = [];}for (let i = 0; i < loop; i++) {for (let j = 0; j < length; j++) {let str = array[j] + \'\';if (str.length >= i + 1) {let k = parseInt(str[str.length - 1 - i]); // 获取当前位的值，作为插入的索引bucket[k].push(array[j]);} else {// 处理位数不够的情况，高位默认为 0bucket[0].push(array[j]);}}array.splice(0, length); // 清空旧的数组// 使用桶重新初始化数组for (let i = 0; i < 10; i++) {let t = bucket[i].length;for (let j = 0; j < t; j++) {array.push(bucket[i][j]);}bucket[i] = [];}}return array;}

排序算法的复杂度