排序算法
-
选择排序 O(n^2)
选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理是：第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。以此类推，直到全部待排序的数据元素的个数为零。选择排序是不稳定的排序方法
代码实现
function selectSort(arr){
if(arr.length<=1)return arr
for(let i=0;i<arr.length;i++){
let minIndex = i
for(let k=i+1;k<arr.length;k++){
if(arr[k]<arr[minIndex]){
minIndex = k
}
}
[arr[i],arr[minIndex]] = [arr[minIndex],arr[i]]
}
return arr
}
console.log(selectSort([3,1,5,2,7]))//[1, 2, 3, 5, 7]
console.log(selectSort([3]))//[3]
-
计数排序 O(n+max)
计数排序是一个非基于比较的排序算法，该算法于1954年由 Harold H. Seward 提出。它的优势在于在对一定范围内的整数排序时，它的复杂度为Ο(n+k)（其中k是整数的范围），快于任何比较排序算法。 [1] 当然这是一种牺牲空间换取时间的做法，而且当O(k)>O(nlog(n))的时候其效率反而不如基于比较的排序（基于比较的排序的时间复杂度在理论上的下限是O(nlog(n)), 如归并排序，堆排序）
代码实现
function countSort(arr){
let length = arr.length
if(length<=1)return arr
let hashTable = {}
let max = arr[0]
for(let i=0;i<length;i++){
let item = arr[i]
hashTable[item] = !hashTable[item]?1:hashTable[item]+1
if(item>max)max = item
}
const result = []
for(let m=1;m<=max;m++){
if(hashTable[m]){
for(let k=0;k<hashTable[m];k++){
result.push(m)
}
}
}
return result
}
console.log(countSort([3,5,6,2,9,1]))
console.log(countSort([1,2,3,1]))
-
冒泡排序 O(n^2)
冒泡排序（Bubble Sort），是一种计算机科学领域的较简单的排序算法。
它重复地走访过要排序的元素列，依次比较两个相邻的元素，如果顺序（如从大到小、首字母从Z到A）错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素列已经排序完成。
这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。
代码实例
function bubbleSort(arr){
const {length} = arr
for(let i=0;i<length-1;i++){
for(let j=0;j<length-i-1;j++){
if(arr[j]>arr[j+1]){
[arr[j],arr[j+1]] = [arr[j+1],arr[j]]
}
}
}
return arr
}
console.log(bubbleSort([3,5,6,2,9,1]))
console.log(bubbleSort([1,2,3,1]))
-
插入排序 O(n^2)
插入排序，一般也被称为直接插入排序。对于少量元素的排序，它是一个有效的算法 [1] 。插入排序是一种最简单的排序方法，它的基本思想是将一个记录插入到已经排好序的有序表中，从而一个新的、记录数增1的有序表。在其实现过程使用双层循环，外层循环对除了第一个元素之外的所有元素，内层循环对当前元素前面有序表进行待插入位置查找，并进行移动 [2] 。
代码实现
function insertSort(arr){
const {length} = arr
if(length<=1)return arr
for(let i=1;i<length;i++){
let now = arr[i]
let s
for(s=i-1;s>=0;s--){
if(now<arr[s]){
arr[s+1] = arr[s]
}else {
break
}
}
arr[s+1] = now
}
return arr
}
console.log(insertSort([3,5,6,2,9,1]))
console.log(insertSort([1,2,3,1]))
console.log(insertSort([3,1]))
-
希尔排序
1959年Shell发明，第一个突破O(n2)的排序算法，是简单插入排序的改进版。它与插入排序的不同之处在于，它会优先比较距离较远的元素。希尔排序又叫缩小增量排序。
代码实现
function shellSort(arr) {
var len = arr.length;
for(var gap = Math.floor(len / 2); gap > 0; gap = Math.floor(gap / 2)) {
// 注意：这里和动图演示的不一样，动图是分组执行，实际操作是多个分组交替执行
for(var i = gap; i < len; i++) {
var j = i;
var current = arr[i];
while(j - gap >= 0 && current < arr[j - gap]) {
arr[j] = arr[j - gap];
j = j - gap;
}
arr[j] = current;
}
}
return arr;
}
let s = shellSort([1,5,7,2,4,3])
console.log(s)
-
二分查找 O(log2n)
二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。
代码实现
var Arr = [3, 5, 6, 7, 9, 12, 15];
function binary(find, arr, low, high) {
if (low <= high) {
if (arr[low] == find) {
return low;
}
if (arr[high] == find) {
return high;
}
var mid = Math.ceil((high + low) / 2);
if (arr[mid] == find) {
return mid;
} else if (arr[mid] > find) {
return binary(find, arr, low, mid - 1);
} else {
return binary(find, arr, mid + 1, high);
}
}
return -1;
}
binary(15, Arr, 0, Arr.length - 1);
function bSearch(arr, n, start, end){
if(end === start) return -1
let mid = parseInt((start + end) / 2)
if(n === arr[mid]){
return mid
}else if(n > arr[mid]){
return bSearch(arr,n,mid+1,end)
}else {
return bSearch(arr,n,start,mid)
}
}
console.log(bSearch([2,2,2,4,5,6,8],7,0,7))
