本文使用 JavaScript 实现的基础的 8 种排序算法，复杂度归纳如下：
O(n^2) ——冒泡排序、插入排序、选择排序
O(nlongn) ——归并排序、快速排序
O(n) ——桶排序、计数排序和基数排序
排序算法归纳
1. 冒泡排序
// 基础冒泡
function bubble(arr) {
if (arr.length <= 1) return;
for(let i = 0; i < arr.length; i++) {
// 第一次冒泡，将最大的元素冒泡到最后一位；第二次冒泡到倒数第二位；因此内部循环只需遍历到arr.length-i-1位
for(let j = 0; j < arr.length-i-1; j++) {
if(arr[j] > arr[j+1]) {
let temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
return arr;
}
// 优化后的冒泡
function improved_bubble(arr) {
// 标记上一次最后交换的位置作为下一次冒泡的边界，后续则不需要再检查标志位后面的元素
if (arr.length <= 1) return;
let sortBoder = arr.length - 1,
lastChangeIndex = 0;
for(let i = 0; i < arr.length; i++) {
let isSorted = true;
for(let j = 0; j < sortBoder; j++) {
if(arr[j] > arr[j+1]) {
let temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
isSorted = false;
lastChangeIndex = j;
}
}
sortBoder = lastChangeIndex;
if(isSorted) break;
}
return arr;
}
/****************测试***************/
// 1. 生成测试数据
let aTest = [], start, end;
for (let i = 0; i < 2000; i++) {
aTest.push(Math.round(Math.random()*2000));
}
// 2. 排序并计算排序时间
console.log('***********普通冒泡排序***********');
start = new Date().getTime();
bubble([...aTest]);
end = new Date().getTime();
console.log(`${(end-start)} ms`)
console.log('***********优化后的冒泡排序***********');
start = new Date().getTime();
improved_bubble([...aTest]);
end = new Date().getTime();
console.log(`${(end-start)} ms`)
2. 插入排序
// 将数组分隔为已排序区和未排序区，每次从未排序区中取一个元素，放到已排序区合适的位置上
function insertionSort(arr) {
if (arr.length <= 1) return;
for(let i = 1; i < arr.length; i++) {
let value = arr[i];
let j = i -1;
for(; j >= 0; j--) {
if(arr[j] > value) { // 大于该值时，元素后移
arr[j+1] = arr[j]
} else { // 找到元素应该插入的位置：当前元素小于value值，因此应该将value值放于j+1处
break;
}
}
arr[j+1] = value;
}
return arr;
}
3. 选择排序
// 类似于插入排序，不同的是每次从未排序中找到最小的数，与已排序区后的首个元素交换
function selectionSort(arr) {
if (arr.length <= 1) return;
for(let i = 0; i< arr.length-1; i++) {
let min = arr[i], minIndex = i;
for(let j = i+1; j < arr.length; j++) { // 遍历未排序区域，获取最小值
if(arr[j] < min) {
min = arr[j];
minIndex = j;
}
}
arr[minIndex] = arr[i]; // 将最小值放置到排序区的后面
arr[i] = min;
}
return arr;
}
4. 归并排序
// 分区排序之后合并
function mergeSort(arr) {
if(arr.length <= 1) return arr;
let middle = Math.floor(arr.length/2); // 取数组的中点
// 分区进行排序
let leftPart = arr.slice(0, middle);
let rightPart = arr.slice(middle);
return mergeArr(mergeSort(leftPart), mergeSort(rightPart));
}
function mergeArr(leftArr, rightArr) {
let leftIndex = rightIndex = 0;
let tmp = [];
// 依次比较两个数组的元素，按顺序插入
while(leftIndex < leftArr.length && rightIndex < rightArr.length) {
if(leftArr[leftIndex] <= rightArr[rightIndex]) {
tmp.push(leftArr[leftIndex]);
leftIndex ++;
} else {
tmp.push(rightArr[rightIndex]);
rightIndex ++;
}
}
// 合并多余数组
return tmp.concat(leftArr.slice(leftIndex)).concat(rightArr.slice(rightIndex));
}
5. 快速排序
// 取任意一个元素作为分区点，小于分区点的数据放左侧，大于分区点的数据放右侧，分区点放中间。先分区，再排序
function quickSort(arr) {
if(arr.length <= 1) return arr;
let pivot = arr[arr.length - 1];
let pivotIndex = partition(arr);
return [...quickSort(arr.slice(0, pivotIndex)), pivot, ...quickSort(arr.slice(pivotIndex+1))];
}
// 获取分区后交换的index
function partition(arr) {
let pivot = arr[arr.length - 1];
let lessIndex = 0;
// 将小于pivot的值放到lessIndex的左侧，即arr[0...lessIndex-1]的数据小于pivot, arr[lessIndex...]的数据大于pivot
for(var j = 0; j < arr.length - 1; j++) {
// arr[j]小于pivot则需要交换，交换之后已处理区长度加一，lessIndex需要后移一位
if(arr[j] <= pivot) {
let temp = arr[lessIndex];
arr[lessIndex] = arr[j];
arr[j] = temp;
lessIndex++;
}
}
// 将分区点交换到中间
arr[j] = arr[lessIndex];
arr[lessIndex] = pivot;
return lessIndex;
}
6. 桶排序
function bucketSort(arr) {
if(arr.length <=1 ) return arr;
// 寻找数组中的最大值，方便分桶
let max = 0, bucketNum = 100;
for(let i = 0; i < arr.length; i++) {
if(arr[i] > max) {
max = arr[i];
}
}
// 对数组进行分桶操作
let aBucket = new Array(bucketNum),
bucketRange = Math.ceil((max+1)/bucketNum);
for(let i = 0; i < arr.length; i++) { // 遍历元素
for(let j = 0; j < bucketNum; j++) { // 遍历所有的桶，看元素满足那个桶的数据范围
if(arr[i] >= bucketRange*j && arr[i] < bucketRange*(j+1)) {
if(!aBucket[j]) { // 若该桶为空，则创建并添加进元素，否则直接插入
aBucket[j] = [arr[i]];
} else {
aBucket[j].push(arr[i]);
}
}
}
}
// 对每个桶内元素进行快排并按顺序连接输出
return aBucket.reduce((ret, a)=>{
return ret.concat(quickSort(a));
});
}
7. 计数排序
function countingSort(arr) {
if(arr.length <=1 ) return arr;
// 寻找数组中的最大值，方便分桶
let max = 0;
for(let i = 0; i < arr.length; i++) {
if(arr[i] > max) {
max = arr[i];
}
}
// 对数组进行分桶操作
let aBucket = new Array(max+1);
for(let i = 0; i < arr.length; i++) { // 遍历元素
for(let j = 0; j < aBucket.length; j++) { // 遍历所有的桶，看元素满足那个桶的数据范围
if(arr[i] == j) {
if(!aBucket[j]) { // 若该桶为空，则创建并添加进元素，否则直接插入
aBucket[j] = [arr[i]];
} else {
aBucket[j].push(arr[i]);
}
}
}
}
// 按顺序取出元素
return aBucket.reduce((ret, a)=>{
return ret.concat(a);
});
}
8. 基数排序
function radixSort(arr) {
if(arr.length <=1 ) return arr;
// 从低位开始进行计数排序，排序过程需要保证稳定性
let i = arr[0].length-1;
while(i >= 0) {
arr = countingSort(arr, i);
i --;
}
return arr;
}
/****************测试***************/
// 1. 生成测试数据
let aTest = [], start, end;
for (let i = 0; i < 2000; i++) {
// 生成15位的字符串数据
let num = [];
for (let j = 0; j < 15; j++) {
num.push(Math.round(Math.random()*9))
}
aTest.push(num.join(''));
}
console.log(aTest);
// 2. 排序并计算时间
console.log('***********基数排序***********');
start = new Date().getTime();
console.log(radixSort([...aTest]));
end = new Date().getTime();
console.log(`${(end-start)} ms`)
