1. 冒泡
// 冒泡 - 每次循环, 将两两中偏大的元素移动到右边for (let i = 0; i < arr.length - 1; i++) {for (let j = i; j < arr.length; j++) {if (arr[i] > arr[j]) {[arr[i], arr[j]] = [arr[j], arr[i]]}}}console.log(arr)
2. 选择排序
选择排序算法是一种原址比较排序算法。选择排序大致的思路是找到数据结构中的最小值并将其放置在第一位，接着找到第二小的值并将其放在第二位。
// 选择 - 找到最小的, 放在第一位; 找到第二小的, 挡在第二位for (let i = 0; i < arr.length; i++) {let min_index = i;for (let j = i; j < arr.length; j++) {if (arr[min_index] > arr[j]) {min_index = j}}if (i !== min_index) {[arr[i], arr[min_index]] = [arr[min_index], arr[i]]}}console.log(arr)
3. 插入排序
// 插入 - 找到合适的位置, 把它插进去for (let i = 0; i < arr.length; i++) {let j = i;let tmp = arr[i]while (j > 0 && arr[j - 1] > tmp) {arr[j] = arr[j - 1];j--;}arr[j] = tmp;}console.log(arr)
4. 归并排序
// 归并 - 采用分治思想, 将原数组分成只有一个位置的小数组, 接着讲小数组归并成大数组let mergeSortRec = function (arr) {let length = arr.length;if (length === 1) {return arr;}let mid = Math.floor(length / 2);let left_array = arr.slice(0, mid);let right_array = arr.slice(mid, length);return merge(mergeSortRec(left_array), mergeSortRec(right_array));}let merge = function (left_array, right_array) {let result = [];let il = 0;let ir = 0;while (il < left_array.length && ir < right_array.length) {if (left_array[il] < right_array[ir]) {result.push(left_array[il++])} else {result.push(right_array[ir++])}}while (il < left_array.length) {result.push(left_array[il++])}while (ir < right_array.length) {result.push(right_array[ir++])}return result;}console.log(mergeSortRec(arr))
5. 快速排序
// 快排 - 采用分治思想, 划分主元let quick = function (arr, left_ptr, right_ptr) {let index;if (arr.length > 1) {// 划分主元, 并执行交换index = partition(arr, left_ptr, right_ptr);if (left_ptr < index - 1) {quick(arr, left_ptr, index - 1);}if (index < right_ptr) {quick(arr, index, right_ptr);}}}let partition = function (array, left_ptr, right_ptr) {let pivot = array[Math.floor((left_ptr + right_ptr) / 2)];let i = left_ptr;let j = right_ptr;while (i <= j) {while (array[i] < pivot) {i++;}while (array[j] > pivot) {j--;}if (i <= j) {[aarrayrr[i], array[j]] = [array[j], array[i]];}i++;j--;}return i;}quick(arr, 0, arr.length - 1)console.log(arr)
