排序算法說明:
(1)對于評述算法優(yōu)劣術(shù)語的說明
穩(wěn)定:如果a原本在b前面,而a=b,排序之后a仍然在b的前面幽勒;
不穩(wěn)定:如果a原本在b的前面,而a=b港令,排序之后a可能會出現(xiàn)在b的后面啥容;
內(nèi)排序:所有排序操作都在內(nèi)存中完成;
外排序:由于數(shù)據(jù)太大顷霹,因此把數(shù)據(jù)放在磁盤中咪惠,而排序通過磁盤和內(nèi)存的數(shù)據(jù)傳輸才能進(jìn)行;
時間復(fù)雜度: 一個算法執(zhí)行所耗費(fèi)的時間淋淀。
空間復(fù)雜度: 運(yùn)行完一個程序所需內(nèi)存的大小遥昧。
(2)排序算法圖片總結(jié):
n: 數(shù)據(jù)規(guī)模
k:“桶”的個數(shù)
In-place: 占用常數(shù)內(nèi)存,不占用額外內(nèi)存
Out-place: 占用額外內(nèi)存
穩(wěn)定性:排序后2個相等鍵值的順序和排序之前它們的順序相同
1.冒泡排序:
解析:1.比較相鄰的兩個元素朵纷,如果前一個比后一個大炭臭,則交換位置。
2.第一輪的時候最后一個元素應(yīng)該是最大的一個袍辞。
3.按照步驟一的方法進(jìn)行相鄰兩個元素的比較鞋仍,這個時候由于最后一個元素已經(jīng)是最大的了,所以最后一個元素不用比較搅吁。
var arr = [2, 1, 3, 5, 8, 5, 9, 6];
function bubbleSort(arr) {
var len = arr.length;
for (var i = 0; i < len - 1; i++) {
for (var j = 0; j < arr.length - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
var swap = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = swap;
}
}
}
return arr;
}
console.log(bubbleSort(arr));
2.快速排序:
解析:快速排序是對冒泡排序的一種改進(jìn)威创,第一趟排序時將數(shù)據(jù)分成兩部分,一部分比另一部分的所有數(shù)據(jù)都要小谎懦。然后遞歸調(diào)用肚豺,在兩邊都實(shí)行快速排序。
var arr = [1, 3, 2, 5, 7, 3, 6, 9];
function quickSort(arr) {
if (arr.length <= 1) {
return arr;
}
var pivotIndex = Math.floor(arr.length / 2);
var pivot = arr.splice(pivotIndex, 1)[0];
var left = [],
right = [],
len = arr.length;
for (var i = 0; i < len; i++) {
if (arr[i] < pivot) {
left.push(arr[i]);
} else {
right.push(arr[i]);
}
}
return quickSort(left).concat([pivot], quickSort(right));
}
console.log(quickSort(arr));
歸來仍是少年