十五周算法訓練營——數組排序
作者：前端點線面
Java數組排序方式一般有四種：冒泡排序法、快速排序法、選擇排序法、插入排序法。
冒泡
冒泡排序的思路：遍歷數組，然后將最大數沉到最底部。
「時間復雜度：O(N^2)；」
「空間復雜度：O(1)」
function swap(arr, i, j) {
const temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
function bubbleSort(arr) {
if (arr == null || arr.length <= 0) {
return [];
}
const len = arr.length;
for (let end = len - 1; end > 0; end--) {
for (let i = 0; i < end; i++) {
if (arr[i] > arr[i + 1]) {
swap(arr, i, i + 1);
}
}
}
return arr;
}
選擇
選擇排序的實現思路：遍歷數組，把最小數放在頭部。
「時間復雜度：O(N^2)；」
「空間復雜度：O(1)」
function selectionSort(arr) {
if (!Array.isArray(arr) || arr.length <= 0) {
return [];
}
const swap = (arr, i, j) => {
const temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
};
for (let i = 0; i < arr.length - 1; i++) {
let minIndex = i;
for (let j = i + 1; j < arr.length; j++) {
minIndex = arr[j] < arr[minIndex] ? j : minIndex;
}
swap(arr, i, minIndex);
}
return arr;
}
插入排序
插入排序實現思路：將一個新的數，和前面的比較，只要當前數小于前一個則和前一個交換位置，否則終止。
「時間復雜度：O(N^2)；」
「空間復雜度：O(1)」
function insertSort(arr) {
if (!Array.isArray(arr) || arr.length <= 0) {
return [];
}
const swap = (arr, i, j) => {
const temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
};
for (let i = 1; i < arr.length; i++) {
for (let j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--) {
swap(arr, j, j + 1);
}
}
return arr;
}
歸并排序
歸并排序的思路：
1.先左側部分排好序。
2.再右側部分排好序。
3.再準備一個輔助數組，用外排的方式，小的開始填，直到有個動到末尾，將另一個數組剩余部分拷貝到末尾。
4.再將輔助數組拷貝回原數組。
「時間復雜度:O(N * logN)」
「空間復雜度:O(N)」歸并排序實際上就是一個二叉樹的后序遍歷過程。
function mergeSort(arr) {
if (arr == null || arr.length <= 0) {
return [];
}
sortProcess(arr, 0, arr.length - 1);
return arr;
}
function sortProcess(arr, L, R) {
// 遞歸的終止條件，就是左右邊界索引一樣
if (L === R) {
return;
}
const middle = L + ((R - L) >> 1); // 找出中間值
sortProcess(arr, L, middle); // 對左側部分進行遞歸
sortProcess(arr, middle + 1, R); // 對右側部分進行遞歸
merge(arr, L, middle, R);
}
function merge(arr, L, middle, R) {
var help = [];
var l = L;
var r = middle + 1;
var index = 0;
while (l <= middle && r <= R) {
help[index++] = arr[l] < arr[r] ? arr[l++] : arr[r++];
}
while (l <= middle) {
help.push(arr[l++]);
}
while (r <= R) {
help.push(arr[r++]);
}
for (let i = 0; i < help.length; i++) {
arr[L + i] = help[i];
}
// arr.splice(L, help.length, ...help); // 利用了ES6的語法
}
快排
快速排序實現思路：隨機取出一個值進行劃分，大于該值放右邊，小于該值放左邊（該算法在經典快排的基礎上經過荷蘭國旗思想和隨機思想進行了改造）。
「時間復雜度：O(N*logN)」
「空間復雜度：O(logN)」快速排序其實就是二叉樹中前序遍歷的處理方式。
function quickSort(arr) {
if (arr == null || arr.length <= 0) {
return [];
}
quick(arr, 0, arr.length - 1);
return arr;
}
function quick(arr, L, R) {
// 遞歸結束條件是L >= R
if (L < R) {
// 隨機找一個值，然后和最后一個值進行交換，將經典排序變為快速排序（因為經典排序每次都取最后一個數據去對比，對應0，1，2……n的情況，其復雜度為O(N^2))
swap(arr, L + Math.floor(Math.random() * (R - L + 1)), R);
//利用荷蘭國旗問題獲得劃分的邊界，返回的值是小于區域的最大索引和大于區域的最小索引，在這利用荷蘭國旗問題將等于區域部分就不用動了
const tempArr = partition(arr, L, R, arr[R]);
quick(arr, L, tempArr[0]);
quick(arr, tempArr[1], R);
}
}
// 返回值是小于區域的最后的索引和大于區域的第一個索引
function partition(arr, L, R, num) {
var less = L - 1;
var more = R + 1;
var cur = L;
while (cur < more) {
if (arr[cur] < num) {
swap(arr, ++less, cur++);
} else if (arr[cur] > num) {
swap(arr, --more, cur);
} else {
cur++;
}
}
return [less, more];
}
function swap(arr, i, j) {
const temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
堆排序
堆排序思路：
1.讓數組變成大根堆。
2.把最后一個位置和堆頂做交換。
3.則最大值在最后，則剩下部分做heapify，則重新調整為大根堆，則堆頂位置和該部分最后位置做交換。
4.重復進行，直到減完，則這樣最后就調整完畢，整個數組排完序（為一個升序）。
「時間復雜度:O(N * logN)」
「空間復雜度:O(1)」
function heapSort(arr) {
if (arr == null || arr.length <= 0) {
return [];
}
// 首先是建立大頂堆的過程
for (let i = 0; i < arr.length; i++) {
heapInsert(arr, i);
}
var size = arr.length;//這個值用來指定多少個數組成堆，當得到一個排序的值后這個值減一
//將堆頂和最后一個位置交換
/**
* 當大頂堆建立完成后，然后不斷將最后一個位置和堆頂交換；
* 這樣最大值就到了最后，則剩下部分做heapify，重新調整為大根堆，則堆頂位置和倒數第二個位置交換，重復進行，直到全部排序完畢*/
//由于前面已經是大頂堆，所以直接交換
swap(arr, 0, --size);
while(size > 0) {
// 重新變成大頂堆
heapify(arr, 0, size);
// 進行交換
swap(arr, 0, --size);
}
return arr;
}
// 加堆過程中
function heapInsert(arr, index) {
//比較當前位置和其父位置，若大于其父位置，則進行交換，并將索引移動到其父位置進行循環，否則跳過
//結束條件是比父位置小或者到達根節點處
while (arr[index] > arr[parseInt((index - 1) / 2)]) {
// 進行交換
swap(arr, index, parseInt((index - 1) / 2));
index = parseInt((index - 1) / 2);
}
}
//減堆過程
/**
* size指的是這個數組前多少個數構成一個堆
* 如果你想把堆頂彈出，則把堆頂和最后一個數交換，把size減1，然后從0位置經歷一次heapify，調整一下，剩余部分變成大頂堆*/
function heapify(arr, index, size) {
let left = 2 * index + 1;
while (left < size) {
let largest = (left + 1 < size && arr[left] < arr[left + 1]) ? left + 1 : left;
largest = arr[index] > arr[largest] ? index : largest;
//如果最大值索引和傳進來索引一樣，則該值到達指定位置，直接結束循環
if (index == largest) {
break;
}
// 進行交換，并改變索引和其左子節點
swap(arr, index, largest);
index = largest;
left = 2 * index + 1;
}
}
function swap(arr, i, j) {
var temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
責任編輯：姜華
來源：
前端點線面
