冒泡demo:
function bubbleSort(arr) {
let len = arr.length;
for (let i = 0; i < len; i++) {
for (let j = 0; j < len - 1 - i; j++) {
if (arr[j] > arr[j+1]) { //相邻元素两两对比
[arr[j + 1], arr[j]] = [arr[j], arr[j + 1]];
}
}
}
return arr;
}
快速排序demo:
function quickSort(arr, left, right) {
let len = arr.length;
let partitionIndex;
left = typeof left !== 'number' ? 0 : left;
right = typeof right !== 'number' ? len - 1 : right;
if (left < right) {
partitionIndex = partition(arr, left, right);
quickSort(arr, left, partitionIndex - 1);
quickSort(arr, partitionIndex + 1, right);
}
return arr;
}
function partition(arr, left, right) { //分区操作
let pivot = left; //设定基准值(pivot)
let index = pivot + 1;
for (let i = index; i <= right; i++) {
if (arr[i] < arr[pivot]) {
[arr[i], arr[index]] = [arr[index], arr[i]];
index++;
}
}
[arr[pivot], arr[index - 1]] = [arr[index - 1], arr[pivot]];
return index - 1;
}
选择demo:
function selectionSort(arr) {
let len = arr.length;
let minIndex;
for (let i = 0; i < len - 1; i++) {
minIndex = i;
for (let j = i + 1; j < len; j++) {
if (arr[j] < arr[minIndex]) { //寻找最小的数
minIndex = j; //将最小数的索引保存
}
}[arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
}
return arr;
}
插入demo:
function insertionSort(arr) {
let len = arr.length;
let preIndex, current;
for (let 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;
}
归并demo:
function mergeSort(arr) { //采用自上而下的递归方法
let len = arr.length;
if(len < 2) {
return arr;
}
let middle = Math.floor(len / 2),
left = arr.slice(0, middle),
right = arr.slice(middle);
return merge(mergeSort(left), mergeSort(right));
}
function merge(left, right){
let result = [];
while (left.length && right.length) {
if (left[0] <= right[0]) {
result.push(left.shift());
} else {
result.push(right.shift());
}
}
result.push(...left);
result.push(...right);
return result;
}
堆demo:
var len; //因为声明的多个函数都需要数据长度,所以把len设置成为全局变量
function buildMaxHeap(arr) { //建立大顶堆
len = arr.length;
for (let i = Math.floor(len / 2); i >= 0; i--) {
heapify(arr, i);
}
}
function heapify(arr, i) { //堆调整
let left = 2 * i + 1;
let right = 2 * i + 2;
let largest = i;
if (left < len && arr[left] > arr[largest]) {
largest = left;
}
if (right < len && arr[right] > arr[largest]) {
largest = right;
}
if (largest !== i) {
[arr[i], arr[largest]] = [arr[largest], arr[i]];
heapify(arr, largest);
}
}
function heapSort(arr) {
buildMaxHeap(arr);
for (let i = arr.length - 1; i > 0; i--) {
[arr[0], arr[i]] = [arr[i], arr[0]];
len--;
heapify(arr, 0);
}
return arr;
}