选择排序

image.png
遍历，两两交换

插入排序

冒泡排序

image.png
相邻接点进行比较。

  1. function(nums, k) {
  2. //冒泡排序
  3.   const length= nums.length
  4.   for(let i=0;i<nums.length;i++){
  5.     for(let j=0;j<length-i;j++){
  6.       if(nums[j]>nums[j+1]){
  7.          const temp=nums[j+1]
  8.          nums[j+1]=nums[j]
  9.          nums[j]=temp
  10.       }
  11.     }
  12.   }
  13.   return nums;
  14. };

快速排序

http://data.biancheng.net/view/117.html
当遇到有序数组时，时间复杂度最坏情况退化成O（N2），所以可以取中间值。
912.排序数组

  1. var quickSort=function(nums,begin,end){
  2.     if (begin < end) {
  3.         const index=Math.floor((begin+end)/2)
  4.         let key = nums[index];
  5.         nums[index]=nums[begin]
  6.         nums[begin]=key;
  7.         let i = begin;
  8.         let j = end;
  9.         while (i < j) {
  10.             while (i < j && nums[j] >= key) {
  11.                 j--;
  12.             }
  13.             nums[i] = nums[j];
  14.             while (i < j && nums[i] < key) {
  15.                 i++;
  16.             }
  17.             nums[j] = nums[i];
  18.         }
  19.         nums[i] = key;
  20.         quickSort(nums, begin, i - 1);
  21.         quickSort(nums, i + 1, end);
  22.     } 
  23. }
  24. var sortArray = function(nums) {
  25.     quickSort(nums,0,nums.length-1)
  26.     return nums
  27. };

215. 数组中的第K个最大元素

  1. var findKthLargest = function(nums, k) {
  2.     const len = nums.length;
  3.     let l = 0 ,r = len - 1;
  4.     let target = len - k;
  5.     while(l < r) {
  6.         let idx = getPartion(nums, l, r);  //分治思想
  7.         if(idx === target){  
  8.             return nums[idx]
  9.         }else if(idx < target) {
  10.             l = idx + 1;  //二分法，缩小范围
  11.         }else {
  12.             r = idx - 1;
  13.         }
  14.     }
  16.     return nums[l];
  18. };
  20. function getPartion(nums, start, end) {
  21.     const povit = nums[start]; //基准值
  22.     while(start < end){
  23.         while(start < end && nums[end] >= povit){
  24.             end --; 
  25.         }
  26.         nums[start] = nums[end]; //找到右边比基准值小的，与基准值交换
  27.         while(start < end && nums[start] < povit){
  28.             start ++;
  29.         }
  30.          nums[end] = nums[start];//找到左边比基准值大的，与基准值交换
  31.     }
  32.     nums[start] = povit;
  33.     return start
  34. }

归并排序

https://www.cnblogs.com/chengxiao/p/6194356.html
归并排序使用分而治之的概念对给定的元素列表进行排序。它将问题分解为较小的子问题，直到它们变得足够简单以至可以直接解决为止。
以下是归并排序的步骤：

  1. 将给定的列表分为两半（如果列表中的元素数为奇数，则使其大致相等）。
  2. 以相同的方式继续划分子数组，直到只剩下单个元素数组。
  3. 从单个元素数组开始，排序合并子数组。
  4. 重复第 3 步单元，直到最后得到一个排好序的数组。

排序 - 图3
排序 - 图4
排序 - 图5
912.排序数组

  1.  var merge = function (nums, begin, end, mid) {
  2.     let temp = [];
  3.     let i = begin,
  4.       j = mid + 1,
  5.       res = 0;
  6.     while (i <= mid && j <= end) {
  7.       if (nums[i] <= nums[j]) {
  8.         temp[res++] = nums[i++];
  9.       } else {
  10.         temp[res++] = nums[j++];
  11.       }
  12.     }
  13.     // 右子数组完了
  14.     while (i <= mid) {
  15.       temp[res++] = nums[i++];
  16.     }
  17.     // 右子数组没完
  18.     while (j <= end) {
  19.       temp[res++] = nums[j++];
  20.     }
  21.     // 将 temp 数组的内容赋值回原数组中
  22.     for (let k = begin; k <= end; k++) {
  23.       nums[k] = temp[k - begin];
  24.     }
  25.   };
  27.   var mergeSort = function (nums, begin, end) {
  28.     if (begin < end) {
  29.       const mid = Math.floor((begin + end) / 2);
  30.       mergeSort(nums, begin, mid);
  31.       mergeSort(nums, mid + 1, end);
  32.       merge(nums, begin, end, mid);
  33.     }
  34.     return;
  35.   };
  37.   var sortArray = function (nums) {
  38.     mergeSort(nums, 0, nums.length - 1);
  39.     return nums;
  40.   };

将整个排序序列看成一个二叉树分解，首先将树分解到每一个子节点，树的每一层都是一个归并排序的过程，每一层归并的时间复杂度为O（n），因为整个树的高度为lgn 所以归并排序的时间复杂度不管在什么情况下都是O（nlogn）
归并排序的平均时间复杂度为 O(nlogn) ，最坏时间复杂度为 O(nlogn) ，空间复杂度为 O(n) ，是稳定排序。

希尔排序

排序 - 图6

堆排序

https://www.cnblogs.com/chengxiao/p/6129630.html

347. 前 K 个高频元素

  1. //方法一：哈希表
  2. var topKFrequent = function (nums, k) {
  3.     let map = {}
  4.     for (let num of nums) {
  5.         map[num] = (map[num] || 0) + 1
  6.     }
  7.     let arry = Object.keys(map).sort((a, b) => {
  8.         if (map[b] == map[a]) {
  9.             return a > b ? 1 : -1
  10.         } else {
  11.             return map[b] - map[a]
  12.         }
  13.     })
  14.     return arry.splice(0, k)
  15. };
  16. //方法二：堆排序

https://www.cnblogs.com/rungang/p/11391221.html

image.png