# 冒泡排序 O(n²) 比较所有相邻的两个项,如果第一个比第二个大,则交换他们.元素项向上移动至正确位置. ## 代码示例 ```js const bubbleSort = (array) => { const {length} = array; for(let i = 0; i < length; i++) { for(let j = 0; j < length - 1 - i; j ++){ if (array[j] > array[j + 1]) { [array[j], array[j + 1]] = [array[j + 1], array[j]]; } } } return array; } bubbleSort([5, 3, 1, 6]); // [1, 3, 5, 6] ``` # 选择排序 O(n²) **选择排序**算法是一种原址比较排序算法。 ## 思路 找到数据结构中的最小值并将其放置在第一位，接着找到第二小的值将其放在第二位，以此类推。 ## 代码示例 ```js function selectSort (array) { const {length} = array; let indexMin; for(let i = 0; i < length; i++) { indexMin = i; for(let j = i; j < length; j ++){ if (array[indexMin] > array[j]) { indexMin = j; } } if (i !== indexMin) { [array[i], array[indexMin]] = [array[indexMin], array[i]]; } } return array; } selectSort([5,3, 1, 6]); // [1, 3, 5, 6] ``` # 插入排序 **插入排序**每次排一个数组项，以此方式构建最后的排序树组。 ## 思路 假定第一项已经排序了。接着，它和第二项进行比较————第二项是应该待在原位还是插到第一项之前呢？这样，头两项就已正确排序，接着和第三项比较（它时该插入到第一、第二还是第三的位置呢），以此类推。 ## 代码示例 ```js function insertSort (array) { const {length} = array; let temp; for(let i = 0; i < length; i++) { let j = i; temp = array[i]; while(j > 0 && (array[j - 1] > temp)) { // j > 0 且 前一个项大于后一项 array[j] = array[j - 1]; j--; } array[j] = temp; } return array; } insertSort([3, 5, 1, 4, 2]); // [1, 2, 3, 4, 5] ``` # 归并排序 O(nlog(n)) **归并排序**是一个可以实际使用的排序算法。是一种分而治之算法。 **Array.sort**是有浏览器厂商自行实现的算法，例如：Mozilla Firefox使用归并排序算法作为Array.prototype.sort的实现,而Chrome（V8引擎）使用了快速排序的变体。 ## 思路 将原始数组切分成较小的数组，直至每个小数组只有一个位置，接着将小数组归并成较大的数组，直到最后只有一个排序完毕的大数组。 ## 代码示例 ```js function mergeSort(array) { const { length } = array; if (length > 1) { let middle = Math.floor(length / 2); const left = mergeSort(array.slice(0, middle)); const right = mergeSort(array.slice(middle, length)); array = merge(left, right); } console.log(array) return array; } function merge(left, right) { let i = 0; let j = 0; const result = []; while(i < left.length && j<right.length) { result.push(left[i] < right[j] ? left[i++] : right[j++]) } return result.concat( i < left.length ? left.slice(i) : right.slice(j)); } mergeSort([3, 5, 1, 4, 2]); // [1, 2, 3, 4, 5] ``` # 快速排序 O(nlog(n)) 快速排序也许是最常用的排序算法了。且性能通常比其他复杂度为O(nlog(n))的排序算法要好。和归并排序一样，快速排序也是用分而治之的方法，将原始数组分为较小的数组。 ## 思路 1. 首先，从数组中选择一个值作为**主元(pivot)**,也就是数组中间的值. 2. 创建两个指针(引用),左边一个指向数组第一个值,右边一个指向数组最后一个值.移动左指针直到我们找到一个比主元**大**的值，移动右指针直到找到一个比主元小的值，然后交换它们，重复这个过程，直到左指针超过了右指针。这个过程将使得比主元小的值都排在主元之前，比主元大的值都排在主元之后。这一步叫做**划分**操作。 3. 接着，算法对划分后的小数组（较主元小的值组成的子数组，以及较主元大的值组成的子数组）重复之前的两个步骤，直至数组已完全排序。 ## 代码示例 ```js function quickSort(array) { return quick(array, 0, array.length - 1); } function quick(array, left, right) { let index; if (array.length > 1) { index = partition(array, left, right); if (left < index - 1) quick(array, left, index - 1); if (index < right) quick(array, index, right); } return array; } function partition(array, left, right) { let pivot = array[Math.floor((left + right) / 2)]; let i = left; let j = right; while (i <= j) { while (pivot > array[i]) i++; while (array[j] > pivot) j--; if (i <= j) { [array[j], array[i]] = [array[i], array[j]]; i++; j--; } } return i; } quickSort([3, 5, 1, 4, 2]); // [1, 2, 3, 4, 5] ```