选择排序

之前入门了数据结构与算法，学了几种经典的排序，今天在这里把他记录下来

选择排序的思想，依次找到最小的数的index，把它取出来，再在去除它的数组中找到它。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


function choseSort(arr){
  for(let i = 0;i<arr.length-1;i++){
    for(let j = i;j<arr.length;j++){
      if(arr[j]<arr[i]){
        [arr[i],arr[j]] = [arr[j],arr[i]]
      }
    }
  }
  return arr
}

console.log(choseSort([1,5,2,3,6,2,3,6]))

快速排序

快速排序的思想，将数组分成两段，抽出一个基准，将其他数与其比较大小，将小的放到它的左边，大的放到它右边，重复此过程

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25


       function quickSort(arr){
  function partition(arr,left,right){
    let pivot = arr[right]
    let storeIndex = left
    for(let i = left;i<right;i++){
      if(arr[i]<pivot){
        [arr[left],arr[storeIndex]] = [arr[storeIndex],arr[left]]
        storeIndex++
      }
    }
    [arr[storeIndex],arr[right]] = [arr[right],arr[storeIndex]]
    return storeIndex
  }
  function sort(arr,left,right){
     if(left>=right) return
     let storeIndex = partition(arr,left,right)
     console.log(storeIndex)
     sort(arr,left,storeIndex-1)
     sort(arr,storeIndex+1,right)
  }
  sort(arr,0,arr.length-1)
  return arr
}

console.log(quickSort([8, 4, 90,1000,29]));

归并排序

归并排序的思路，将数组分成两半（一直分），每次对比两个数组之间的数大小，再把最终结果合并起来

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


        let mergeSort = (arr) => {
            if (arr.length === 1) {
                return arr;
            }
            let left = arr.slice(0, Math.floor(arr.length / 2))
            let right = arr.splice(arr.length / 2)
            return merge(mergeSort(left), mergeSort(right));
        }
        let merge = (a, b) => {
            if (a.length === 0) {
                return b;
            }
            if (b.length === 0) {
                return a;
            }
            return a[0] > b[0] ? [b[0]].concat(merge(a, b.slice(1))) : [a[0]].concat(merge(b, a.slice(1)))
        }
        let arr = [1, 4, 6, 2, 3, 1];

计数排序

计数排序的思路，声明一个哈希表用来存储这个数组并且记录每个数出现的次数，然后再从0开始寻找哈希表中的数，依次把最小的数push到一个新的数组中去。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


    let countSort = (arr) => {
            let hashTable = {},
                max = 0,
                result = [];
            for (let i = 0; i < arr.length; i++) {
                if (!(arr[i] in hashTable)) {
                    hashTable[arr[i]] = 1
                } else {
                    hashTable[arr[i]] += 1
                }
                if (arr[i] > max) {
                    max = arr[i]
                }
            }
            for (let j = 0; j <= max; j++) {
                for (let i = 0; i < hashTable[j]; i++) {
                    result.push(j)
                }
            }
            return result;
        }
    let arr = [2, 5, 4, 3, 2, 1, 3]