排序是前端面試與日常開發都很常碰到的題目。下面把幾種常見的排序方式整理成一個 sorting 物件,每個方法都接收陣列並回傳排序後的結果,方便直接替換比較。
window.onload = function () {
var array = [0, 1, 2, 44, 4, 324, 5, 65, 6, 6, 34, 4, 5, 6, 2, 43,
5, 6, 62, 43, 5, 1, 4, 51, 56, 76, 7, 7, 2, 1, 45, 4, 6, 7, 8];
console.log('原始陣列');
console.log(array);
array = sorting.shellSort(array);
console.log('排序後的陣列');
console.log(array);
}
var sorting = {
// 利用原生 sort 排序
systemSort: function (arr) {
return arr.sort(function (a, b) { return a - b; });
},
// 氣泡排序
bubbleSort: function (arr) {
var len = arr.length, tmp;
for (var i = 0; i < len - 1; i++) {
for (var j = 0; j < len - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
tmp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = tmp;
}
}
}
return arr;
},
// 快速排序
quickSort: function (arr) {
var low = 0, high = arr.length - 1;
sort(low, high);
function sort(low, high) {
if (low < high) {
var mid = (function (low, high) {
var tmp = arr[low];
while (low < high) {
while (low < high && arr[high] >= tmp) { high--; }
arr[low] = arr[high];
while (low < high && arr[low] <= tmp) { low++; }
arr[high] = arr[low];
}
arr[low] = tmp;
return low;
})(low, high);
sort(low, mid - 1);
sort(mid + 1, high);
}
}
return arr;
},
// 插入排序
insertSort: function (arr) {
var len = arr.length;
for (var i = 1; i < len; i++) {
var tmp = arr[i];
for (var j = i - 1; j >= 0; j--) {
if (tmp < arr[j]) {
arr[j + 1] = arr[j];
} else {
arr[j + 1] = tmp;
break;
}
}
}
return arr;
},
// 希爾排序
shellSort: function (arr) {
var h = 1;
while (h <= arr.length / 3) {
h = h * 3 + 1; // O(n^(3/2)) by Knuth, 1973
}
for (; h >= 1; h = Math.floor(h / 3)) {
for (var k = 0; k < h; k++) {
for (var i = h + k; i < arr.length; i += h) {
for (var j = i; j >= h && arr[j] < arr[j - h]; j -= h) {
var tmp = arr[j];
arr[j] = arr[j - h];
arr[j - h] = tmp;
}
}
}
}
return arr;
}
}
sort() 預設是字串比較,數字排序一定要傳比較函式。以上就是這次整理的內容,希望對大家有幫助。