總結幾種排序算法。算法在任何一門編程語言都可以實現,學好算法重點是思想,而不是語言,我們這里使用js進行演示。
當然js內部也提供了Array.prototype.sort方法進行排序我們不做具體介紹,詳見:
https://developer.mozilla.org/zh-CN/docs/Web/JavaScript/Reference/Global_Objects/Array/sort
1.冒泡排序
實現原理:
1.依次比較相鄰的兩個數,如果第1個值大于第2個值,交換位置。如果第1個值小于第2個值,不交換位置。一輪下來,最后一個是最大的數
2.每下一輪開始除了最后一個之外的數重復第一步,直到只剩一個數
如圖所示:
冒泡排序
代碼:
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.快速排序
實現原理:
1.以一個數為基準(中間的數),比基準小的放到左邊,比基準大的放到右邊
2.再按此方法對這兩部分數據分別進行快速排序(遞歸原理)
3.不能再分后退出遞歸,并重新將數組合并
如圖所示:
快速排序
代碼:
var quickSort = function(array) {
// 當被分的數組只剩一個時,退出遞歸
if (array.length <= 1) {
return array;
}
// 中間基準值的index
var middleIndex = Math.floor(array.length / 2);
// 基準值
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]);
}
}
// 遞歸
// 把數組合并在一起
return quickSort(left).concat([middle], quickSort(right));
};
3.選擇排序
實現原理:
1.找出最小的數,和第一個交換位置
2.在剩下的數中,找出最二小的數,放在第二個
3.依次類推,排出順序
如圖所示:
選擇排序
代碼:
function selectSort(array){
var len = array.length,
min;
for (i=0; i < len; i++){
// 將當前位置設為最小值
min = i;
// 檢查數組其余部分是否更小
for (j=i+1; j < len; j++){
if (array[j] < array[min]){
min = j;
}
}
// 如果當前位置不是最小值,將其換為最小值
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.插入排序
實現原理:
1.把數組分為[已排序]和[未排序]兩部分,第一個數為[已排序],其余為[未排序]
2.從[未排序]抽出第一個數,和[已排序]部分比較,插入到合適的位置
如圖所示:
插入排序
代碼:
function insertSort(array) {
var len = array.length, // 數組長度
value, // 當前比較的值
i, // 未排序部分的當前位置
j; // 已排序部分的當前位置
for (i=0; i < len; i++) {
// 儲存當前位置的值
value = array[i];
/*
* 當已排序部分的當前元素大于value,
* 就將當前元素向后移一位,再將前一位與value比較
*/
for (j=i-1; j > -1 && array[j] > value; j--) {
array[j+1] = array[j];
}
array[j+1] = value;
}
return array;
}
5.合并排序
實現原理:
1.不斷將數組對半分,直到每個數組只有一個
2.將分出來的部分重新合并
3.合并的時候按順序排列
如圖所示:
合并排序
// 被拆分的數組重新合并
function merge(left, right) {
var result = [],
left_index = 0,
right_index = 0;
// 將兩個數組合并
// 合并的時候按從小到大的順序
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++]);
}
}
// 和其他數組拼接
return result.concat(left.slice(left_index)).concat(right.slice(right_index));
}
function mergeSort(array) {
// 只有一個數的時候退出遞歸
if (array.length < 2) {
return array;
}
var middle = Math.floor(array.length / 2),
left = array.slice(0, middle),
right = array.slice(middle);
// 遞歸
// 不斷拆分只到一個數組只有一個數
return merge(mergeSort(left), mergeSort(right));
}
版權聲明:本文內容由互聯網用戶自發貢獻,該文觀點僅代表作者本人。本站僅提供信息存儲空間服務,不擁有所有權,不承擔相關法律責任。如發現本站有涉嫌抄襲侵權/違法違規的內容, 請發送郵件至 舉報,一經查實,本站將立刻刪除。
發表評論
請登錄后評論...
登錄后才能評論