常见的排序算法——JS实现
图片来源：常用排序算法总结(一) （博主对几种算法的讲解很详细）
一、冒泡排序
1 function bubbleSort(arr) { 2 var i = arr.length, j; 3 while (i > 0) { 4 for (j = 0; j < i - 1; j++) { 5 if (arr[j] > arr[j + 1]) { 6 var temp = arr[j]; 7 arr[j] = arr[j + 1]; 8 arr[j + 1] = temp; 9 } 10 } 11 i--; 12 } 13 return arr; 14 }
二、快速排序
1 function quickSort(array) { 2 function sort(arr, left = 0, right = arr.length - 1) { 3 if (left >= right) { 4 return; 5 } 6 var key = arr[right]; 7 var i = left, j = right; 8 while (i < j) { 9 while (i < j && arr[i] < key) { 10 i++; 11 } 12 arr[j] = arr[i]; 13 while (i < j && arr[j] > key) { 14 j--; 15 } 16 arr[i] = arr[j]; 17 } 18 arr[j] = key; 19 sort(arr, left, j - 1); 20 sort(arr, j + 1, right); 21 } 22 var newArr = array.concat(); // 为了保证这个函数是纯函数拷贝一次数组 23 sort(newArr); 24 return newArr; 25 }
三、插入排序
1 function insertSort(arr) { 2 var resultArr = new Array(); 3 resultArr.push(arr[0]); 4 for (var i=1; i<arr.length; i++){ 5 for (var j=0; j<i; j++){ 6 if (arr[i] <= resultArr[j]){ 7 resultArr.splice(j, 0, arr[i]); 8 break; 9 } else if (j === i - 1){ 10 resultArr.push(arr[i]); 11 } 12 } 13 } 14 return resultArr; 15 }
四、希尔排序
1 function shellSort(arr) { 2 var len = arr.length; 3 // fraction是增量，从长度的一半开始，递减一半 4 for (var fraction = Math.floor(len/2); fraction>0; fraction = Math.floor(fraction/2)){ 5 // i是增量块中的最后一位 6 for (var i = fraction; i<len; i++){ 7 // j是与i对应的增量块中的前一位，j的数据大于增量块中的后一位时交换，j递减一个增量，依次往前 8 for (var j = i-fraction; j>=0&&arr[j]>arr[j+fraction]; j-=fraction){ 9 var temp = arr[j]; 10 arr[j] = arr[j+fraction]; 11 arr[j+fraction] = temp; 12 } 13 } 14 } 15 return arr; 16 }
五、选择排序
1 function selectSort(arr) { 2 var minIndex; 3 var resultArr = new Array(); 4 while (arr.length > 0) { 5 minIndex = 0; 6 for (var j = 1; j < arr.length; j++) { 7 if (arr[j] < arr[minIndex]) { 8 minIndex = j; 9 } 10 } 11 resultArr.push(arr[minIndex]); 12 arr.splice(minIndex, 1); 13 } 14 return resultArr; 15 }
六、堆排序
堆排序详解 （博主详细讲解了堆排序的过程）
1 // 交换两个节点 2 function swap(arr, i, j) { 3 var temp = arr[i]; 4 arr[i] = arr[j]; 5 arr[j] = temp; 6 } 7 // 创建大顶堆:i为父节点位置 8 function heapCreate(arr, i, length) { 9 // 遍历i的子节点 10 for (var j=i*2+1; j<length; j=j*2+1){ 11 var f = (j-1)/2; // j对应的父节点 12 var temp = arr[f]; 13 // 获取两个字节点最大的元素下标 14 if (j+1<length && arr[j]<arr[j+1]){ 15 j++; 16 } 17 // 使父节点是最大值 18 if (temp < arr[j]){ 19 swap(arr, f, j); 20 } else { 21 break; 22 } 23 } 24 } 25 // 堆排序 26 function heapSort(arr) { 27 // 初始化堆 28 for (var i=Math.floor(arr.length/2-1); i>=0; i--){ 29 // 从第一个父节点开始，判断父节点与子节点的大小，令父节点大于子节点 30 heapCreate(arr, i, arr.length); 31 } 32 // 排序 33 for (var j=arr.length-1; j>0; j--){ 34 // 将堆顶的元素（最大）与最后一位交换 35 swap(arr, 0, j); 36 // 将交换后的堆重新创建大顶堆（除有序的元素外） 37 heapCreate(arr, 0, j); 38 } 39 return arr; 40 }
七、归并排序
1. 递归
1 // 比较两个序列，对其归并排序 2 function merge(left, right) { 3 var temp = new Array(); 4 while (left.length>0 && right.length>0){ 5 if (left[0] < right[0]){ 6 temp.push(left.shift()); 7 } else { 8 temp.push(right.shift()); 9 } 10 } 11 return temp.concat(left, right); 12 } 13 // 递归 14 function mergeSort(arr) { 15 if ((arr.length === 1)){ 16 return arr; 17 } 18 var left = arr.slice(0, Math.floor(arr.length/2)); 19 var right = arr.slice(Math.floor(arr.length/2)); 20 return merge(mergeSort(left), mergeSort(right)); 21 }
2. 迭代
1 // 比较两个序列，对其归并排序 2 function merge(left, right) { 3 var temp = new Array(); 4 while (left.length>0 && right.length>0){ 5 if (left[0] < right[0]){ 6 temp.push(left.shift()); 7 } else { 8 temp.push(right.shift()); 9 } 10 } 11 return temp.concat(left, right); 12 } 13 // 迭代 14 function mergeSort(arr) { 15 if ((arr.length === 1)){ 16 return arr; 17 } 18 var temp = new Array(); 19 for (var i=0; i<arr.length; i++){ 20 temp.push([arr[i]]); 21 } 22 temp.push([]); //防止下面j+1时溢出 23 for (var group=arr.length; group>1; group=Math.floor((group+1)/2)) { 24 for (var k=0, j=0; j<group; k++, j+=2){ 25 temp[k] = merge(temp[j], temp[j+1]); 26 } 27 // j是递增2的，k的值比arr.length小，遗留下来的k后面的数据必须清空 28 temp[k] = []; 29 } 30 return temp[0]; 31 }