本文详细解析了JavaScript中六种常用排序算法的实现原理与代码，包括冒泡、选择、插入、希尔、归并及快速排序。通过具体代码示例展示各算法逻辑，并对比分析其执行效率与适用场景，帮助开发者深入理解算法差异并选择合适方案。
JavaScript 排序算法实现概览
本文整理并分享了JavaScript中几种常见排序算法的具体实现方式，内容涵盖核心逻辑与代码示例。
冒泡排序实现
1. 冒泡排序
var bubbleSort = function (arr) {
var flag = true;
var len = arr.length;
for (var i = 0; i < len - 1; i++) {
flag = true;
for (var j = 0; j < len - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
var temp = arr[j+1];
arr[j+1] = arr[j];
arr[j] = temp;
flag = false;
}
}
if (flag) {
break;
}
}
};
选择排序实现
2. 选择排序
var selectSort = function (arr) {
var min;
for (var i = 0; i < arr.length-1; i++) {
min = i;
for (var j = i + 1; j < arr.length; j++) {
if (arr[min] > arr[j]) {
min = j;
}
}
if (i != min) {
swap(arr, i, min);
}
}
};
function swap(arr, index1, index2) {
var temp = arr[index1];
arr[index1] = arr[index2];
arr[index2] = temp;
}; 插入排序实现
3. 插入排序
var insertSort = function (arr) {
var len = arr.length, key;
for (var i = 1; i < len; i++) {
var j = i;
key = arr[j];
while (--j > -1) {
if (arr[j] > key) {
arr[j + 1] = arr[j];
} else {
break;
}
}
arr[j + 1] = key;
}
};
希尔排序实现
4. 希尔排序
var shellSort = function (arr) {
var gaps = [5, 3, 1];
for (var g = 0; g < gaps.length; ++g) {
for (var i = gaps[g]; i < arr.length; ++i) {
var temp = arr[i];
for (var j = i; j >= gaps[g] && arr[j - gaps[g]] > temp; j -= gaps[g]) {
arr[j] = arr[j - gaps[g]];
}
arr[j] = temp;
}
}
};
归并排序实现
5. 归并排序
function mergeSort(arr) {
if (arr.length < 2) {
return;
}
var step = 1;
var left, right;
while (step < arr.length) {
left = 0;
right = step;
while (right + step <= arr.length) {
mergeArrays(arr, left, left + step, right, right + step);
left = right + step;
right = left + step;
}
if (right < arr.length) {
mergeArrays(arr, left, left + step, right, arr.length);
}
step *= 2;
}
}
function mergeArrays(arr, startLeft, stopLeft, startRight, stopRight) {
var rightArr = new Array(stopRight - startRight + 1);
var leftArr = new Array(stopLeft - startLeft + 1);
k = startRight;
for (var i = 0; i < (rightArr.length - 1); ++i) {
rightArr[i] = arr[k];
++k;
}
k = startLeft;
for (var i = 0; i < (leftArr.length - 1); ++i) {
leftArr[i] = arr[k];
++k;
}
rightArr[rightArr.length - 1] = Infinity; // 哨兵值
leftArr[leftArr.length - 1] = Infinity; // 哨兵值
var m = 0;
var n = 0;
for (var k = startLeft; k < stopRight; ++k) {
if (leftArr[m] <= rightArr[n]) {
arr[k] = leftArr[m];
m++;
}
else {
arr[k] = rightArr[n];
n++;
}
}
}
快速排序实现
6. 快速排序
var quickSort = function(arr, left, right) {
var i, j, t, pivot;
if (left >= right) {
return;
}
pivot = arr[left];
i = left;
j = right;
while (i != j) {
while (arr[j] >= pivot && i < j) {
j--;
}
while (arr[i] <= pivot && i < j) {
i++;
}
if (i < j) {
t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}
}
arr[left] = arr[j];
arr[j] = pivot;
quickSort(arr, left, i - 1);
quickSort(arr, i + 1, right);
}
算法效率对比总结
总结：算法效率比较：
以上内容为本文的全部分享，旨在为读者的学习提供参考与帮助，同时也欢迎读者继续支持本站获取更多技术资源。