冒泡排序
function bubbleSort(arr) {
? ? var len = arr.length;
? ? for (var i = 0; i < len; i++) {
? ? ? ? for (var j = 0; j < len - 1 - i; j++) {
? ? ? ? ? ? if (arr[j] > arr[j+1]) {? ? ? ? //相鄰元素兩兩對比
? ? ? ? ? ? ? ? var temp = arr[j+1];? ? ? ? //元素交換
? ? ? ? ? ? ? ? arr[j+1] = arr[j];
? ? ? ? ? ? ? ? arr[j] = temp;
? ? ? ? ? ? }
? ? ? ? }
? ? }
? ? return arr;
}
選擇排序(在剩下未排序的里面找最小的)
function selectionSort(arr) {
? ? var len = arr.length;
? ? var minIndex, temp;
? ? for (var i = 0; i < len - 1; i++) {
? ? ? ? minIndex = i;
? ? ? ? for (var j = i + 1; j < len; j++) {
? ? ? ? ? ? if (arr[j] < arr[minIndex]) {? ? //尋找最小的數(shù)
? ? ? ? ? ? ? ? minIndex = j;? ? ? ? ? ? ? ? //將最小數(shù)的索引保存
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? temp = arr[i];
? ? ? ? arr[i] = arr[minIndex];
? ? ? ? arr[minIndex] = temp;
? ? }
? ? return arr;
}
插入排序
function insertionSort(arr) {
? ? var len = arr.length;
? ? var preIndex, current;
? ? for (var i = 1; i < len; i++) {
? ? ? ? preIndex = i - 1;
? ? ? ? current = arr[i];
? ? ? ? while(preIndex >= 0 && arr[preIndex] > current) {
? ? ? ? ? ? arr[preIndex+1] = arr[preIndex];
? ? ? ? ? ? preIndex--;
? ? ? ? }
? ? ? ? arr[preIndex+1] = current;
? ? }
? ? return arr;
}
歸并排序
function mergeSort(arr) {
? const len = arr.length;
? if (len < 2) { return arr; }
? const mid = Math.floor(len / 2);
? const left = arr.slice(0, mid);
? const right = arr.slice(mid);
? return merge(mergeSort(left), mergeSort(right));
}
function merge(left, right) {
? const result = [];
? while (left.length > 0 && right.length > 0) {
? ? result.push(left[0] <= right[0] ? left.shift() : right.shift());
? }
? return result.concat(left, right);
}
快速排序（基準思想）
function quickSort(arr) {
? const pivot = arr[0];
? const left = [];
? const right = [];
? if (arr.length < 2) { return arr; }
? for (let i = 1, len = arr.length; i < len; i++) {
? ? arr[i] < pivot ? left.push(arr[i]) : right.push(arr[i]);
? }
? return quickSort(left).concat([pivot], quickSort(right));
}
計數(shù)排序
function countingSort(arr, maxValue) {
? ? var bucket = new Array(maxValue+1),
? ? ? ? sortedIndex = 0;
? ? ? ? arrLen = arr.length,
? ? ? ? bucketLen = maxValue + 1;
? ? for (var i = 0; i < arrLen; i++) {
? ? ? ? if (!bucket[arr[i]]) {
? ? ? ? ? ? bucket[arr[i]] = 0;
? ? ? ? }
? ? ? ? bucket[arr[i]]++;
? ? }
? ? for (var j = 0; j < bucketLen; j++) {
? ? ? ? while(bucket[j] > 0) {
? ? ? ? ? ? arr[sortedIndex++] = j;
? ? ? ? ? ? bucket[j]--;
? ? ? ? }
? ? }
? ? return arr;
}
堆排序
function heapSort(arr) {
? let size = arr.length;
? // 初始化堆，i 從最后一個父節(jié)點開始調(diào)整，直到節(jié)點均調(diào)整完畢
? for (let i = Math.floor(size / 2) - 1; i >= 0; i--) {
? ? heapify(arr, i, size);
? }
? // 堆排序：先將第一個元素和已拍好元素前一位作交換，再重新調(diào)整，直到排序完畢
? for (let i = size - 1; i > 0; i--) {
? ? swap(arr, 0, i);
? ? size -= 1;
? ? heapify(arr, 0, size);
? }
? return arr;
}
function heapify(arr, index, size) {
? let largest = index;
? let left = 2 * index + 1;
? let right = 2 * index + 2;
? if (left < size && arr[left] > arr[largest]) {
? ? largest = left;
? }
? if (right < size && arr[right] > arr[largest]) {
? ? largest = right;
? }
? if (largest !== index) {
? ? swap(arr, index, largest);
? ? heapify(arr, largest, size);
? }
}
// test
const arr = [91, 60, 96, 7, 35, 65, 10, 65, 9, 30, 20, 31, 77, 81, 24];
console.log(heapSort(arr));
