總結(jié)幾種排序算法奥邮。算法在任何一門編程語(yǔ)言都可以實(shí)現(xiàn)腥光，學(xué)好算法重點(diǎn)是思想崔涂，而不是語(yǔ)言阳掐，我們這里使用js進(jìn)行演示。
當(dāng)然js內(nèi)部也提供了Array.prototype.sort方法進(jìn)行排序我們不做具體介紹冷蚂，詳見(jiàn)：
https://developer.mozilla.org/zh-CN/docs/Web/JavaScript/Reference/Global_Objects/Array/sort
1.冒泡排序
實(shí)現(xiàn)原理：
1.依次比較相鄰的兩個(gè)數(shù)缭保，如果第1個(gè)值大于第2個(gè)值，交換位置蝙茶。如果第1個(gè)值小于第2個(gè)值艺骂，不交換位置。一輪下來(lái)隆夯，最后一個(gè)是最大的數(shù)
2.每下一輪開(kāi)始除了最后一個(gè)之外的數(shù)重復(fù)第一步钳恕，直到只剩一個(gè)數(shù)
如圖所示：
代碼：
function bubbleSort(array){
var len = array.length;
var i;
var j;
var stop;
for (i = 0; i < len - 1; i++){
for (j = 0, stop = len - 1 - i; j < stop; j++){
if (array[j] > array[j + 1]){
exchange(array, j, j + 1);
}
}
}
return array;
}
function exchange(array, p1, p2){
var temp = array[p1];
array[p1] = array[p2];
array[p2] = temp;
}
2.快速排序
實(shí)現(xiàn)原理：
1.以一個(gè)數(shù)為基準(zhǔn)(中間的數(shù))别伏，比基準(zhǔn)小的放到左邊，比基準(zhǔn)大的放到右邊
2.再按此方法對(duì)這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序（遞歸原理）
3.不能再分后退出遞歸忧额，并重新將數(shù)組合并
如圖所示:
代碼：
var quickSort = function(array) {
// 當(dāng)被分的數(shù)組只剩一個(gè)時(shí)厘肮，退出遞歸
if (array.length <= 1) {
return array;
}
// 中間基準(zhǔn)值的index
var middleIndex = Math.floor(array.length / 2);
// 基準(zhǔn)值
var middle = array.splice(middleIndex, 1)[0];
var left = [];
var right = [];
// 小的放左邊，大的放右邊
for (var i = 0; i < array.length; i++) {
if (array[i] < middle) {
left.push(array[i]);
} else {
right.push(array[i]);
}
}
// 遞歸
// 把數(shù)組合并在一起
return quickSort(left).concat([middle], quickSort(right));
};
3.選擇排序
實(shí)現(xiàn)原理：
1.找出最小的數(shù)睦番，和第一個(gè)交換位置
2.在剩下的數(shù)中类茂，找出最二小的數(shù)，放在第二個(gè)
3.依次類推托嚣，排出順序
如圖所示：
代碼：
function selectSort(array){
var len = array.length,
min;
for (i=0; i < len; i++){
// 將當(dāng)前位置設(shè)為最小值
min = i;
// 檢查數(shù)組其余部分是否更小
for (j=i+1; j < len; j++){
if (array[j] < array[min]){
min = j;
}
}
// 如果當(dāng)前位置不是最小值巩检，將其換為最小值
if (i != min){
exchange(array, i, min);
}
}
return array;
}
function exchange(array, p1, p2){
var temp = array[p1];
array[p1] = array[p2];
array[p2] = temp;
}
4.插入排序
實(shí)現(xiàn)原理：
1.把數(shù)組分為[已排序]和[未排序]兩部分,第一個(gè)數(shù)為[已排序]，其余為[未排序]
2.從[未排序]抽出第一個(gè)數(shù)示启，和[已排序]部分比較兢哭，插入到合適的位置
如圖所示：
代碼：
function insertSort(array) {
var len = array.length, // 數(shù)組長(zhǎng)度
value, // 當(dāng)前比較的值
i, // 未排序部分的當(dāng)前位置
j; // 已排序部分的當(dāng)前位置
for (i=0; i < len; i++) {
// 儲(chǔ)存當(dāng)前位置的值
value = array[i];
/*
* 當(dāng)已排序部分的當(dāng)前元素大于value，
* 就將當(dāng)前元素向后移一位夫嗓，再將前一位與value比較
*/
for (j=i-1; j > -1 && array[j] > value; j--) {
array[j+1] = array[j];
}
array[j+1] = value;
}
return array;
}
5.合并排序
實(shí)現(xiàn)原理：
1.不斷將數(shù)組對(duì)半分厦瓢，直到每個(gè)數(shù)組只有一個(gè)
2.將分出來(lái)的部分重新合并
3.合并的時(shí)候按順序排列
如圖所示：
// 被拆分的數(shù)組重新合并
function merge(left, right) {
var result = [],
left_index = 0,
right_index = 0;
// 將兩個(gè)數(shù)組合并
// 合并的時(shí)候按從小到大的順序
while (left_index < left.length && right_index < right.length) {
if (left[left_index] < right[right_index]) {
result.push(left[left_index++]);
} else {
result.push(right[right_index++]);
}
}
// 和其他數(shù)組拼接
return result.concat(left.slice(left_index)).concat(right.slice(right_index));
}
function mergeSort(array) {
// 只有一個(gè)數(shù)的時(shí)候退出遞歸
if (array.length < 2) {
return array;
}
var middle = Math.floor(array.length / 2),
left = array.slice(0, middle),
right = array.slice(middle);
// 遞歸
// 不斷拆分只到一個(gè)數(shù)組只有一個(gè)數(shù)
return merge(mergeSort(left), mergeSort(right));
}
