选择排序

原理：

  1. 找最小（大）元素
  2. 放到最前面
  3. 重复 1， 2步骤
  4. 直到所有元素均排序完毕

时间复杂度：О(n²)

  1. /*选择排序的递归写法*/
  2. let minIndex = (numbers) => {
  3.     let index = 0;
  4.   for(let i=1; i<numbers.length; i++) {
  5.       if(numbers[i] < numbers[index]) {
  6.         index = i;
  7.     }
  8.   }
  9.   return index;
  10. }
  12. let sort= (numbers) => {
  13.     if(numbers.length > 2) {
  14.     let index = minIndex(numbers);
  15.     let min = numbers[index];
  16.     numbers.splice(index, 1); //从numbers里删除min
  17.     return [min].concat(sort(numbers));
  18.     } else {
  19.         return numbers[0] < numbers[1] ? numbers : numbers.reverse();
  20.     }
  21. }
  1. /*选择排序的循环写法*/
  2. let sort = (numbers) => {
  3.   for(let i=0; i< numbers.length -1; i++){
  4.     let index = minIndex(numbers.slice(i))+ i;
  5.     if(index!==i){
  6.       swap(numbers, index, i);
  7.   }
  8. }
  9. return numbers;
  10. }
  12. let swap = (array, i, j) => {
  13.   let temp = array[i];
  14.   array[i] = array[j];
  15.   array[j] = temp;
  16. }
  18. let minIndex = (numbers) => {
  19.   let index = 0;
  20.   for(let i=1; i<numbers.length; i++){
  21.     if(numbers[i] < numbers[index]){
  22.           index = i;
  23.     }
  24.   }
  25.     return index;
  26. }

快速排序

原理：

  1. 选个基准值，随便选
  2. 跟别人比 大的放后面，小的放前面
  3. 重复 1，2步骤
  4. 直到所有元素均排序完毕

时间复杂度：О(n log2 n)

  1. /*快速排序的递归写法*/
  2. let quickSort = arr => {
  3.     if (arr.length <= 1){return arr;}
  4.     let pivotIndex = Math.floor(arr.length / 2);
  5.     let pivot = arr.splice(pivotIndex, 1)[0];
  6.     let left = [];
  7.     let right = [];
  8.     for (let i = 0; i < arr.length; i++) {
  9.         if (arr[i] < pivot) {
  10.             left.push(arr[i]);
  11.             }else{
  12.         right.push(arr[i]);
  13.         }
  14.     }
  15.     return quickSort(left).concat([pivot],quickSort(right));
  16. }

归并排序

原理：

  1. 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
  2. 设定两个指针，最初位置分别为两个已经排序序列的起始位置
  3. 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
  4. 重复步骤3直到某一指针超出序列尾
  5. 将另一序列剩下的所有元素直接复制到合并序列尾

时间复杂度：О(n log2 n)

  1. /*归并排序的递归写法*/
  2. let mergeSort = arr => { 
  3.     let k = arr.length;  
  4.     if (k===1) {return arr;}
  5.     let left = arr.slice(0, Math.floor(k/2));
  6.     let right = arr.slice(Math.floor(k/2));
  7.     return merge(mergeSort(left), mergeSort(right));
  8. }
  10. let merge = (a,b) => { 
  11.     if(a.length === 0) return b;
  12.     if(b.length === 0) return a;
  13.     let sortedArr;
  14.     if(a[0] > b[0]){
  15.         sortedArr = [b[0]].concat(merge(a, b.slice(1)));
  16.           return  sortedArr;
  17.     } else {
  18.         sortedArr = [a[0]].concat(merge(a.slice(1), b));
  19.         return  sortedArr;
  20.     }
  21. }

计数排序

原理：

  1. 先遍历一遍数组，创建空的哈希表
  2. 把遍历的数组元素和计数放入哈希表，记录数组中最大元素
  3. 遍历哈希表，遍历次数为数组中最大元素值，把哈希表中存在的值放入新数组中

时间复杂度：О(n + max)

  1. /*计数排序的循环写法*/
  2. let countSort = arr => {
  3.     let hashTable = {}, max = 0, result = [];
  4.     for(let i=0; i<arr.length; i++) { //遍历数组
  5.         if(!(arr[i] in hashTable)) {
  6.             hashTable[arr[i]] = 1;
  7.         } else {
  8.             hashTable[arr[i]] += 1;
  9.         }
  10.         if(arr[i] > max) {max = arr[i];}
  11.     }
  12.     for(let j=0; j<=max; j++) { //遍历哈希表
  13.             if(j in hashTable) {             
  14.                for(let k=0; k<hashTable[j]; k++) {
  15.                     result.push(j);
  16.                }
  17.             }
  18.     }
  19.     return result;
  20. }