O(n^2)以及O(nlogn)时间复杂度的排序算法

O(n^2)的算法

都是做的升序。

简单选择排序

思路：每次选择还未排序的区间的最小值和未排序区间的第一个值交换。

 function selectSort(arr){

     for(let i = 0; i < arr.length; i++){

         let minIdx = i;

         for(let j = i; j < arr.length; j++){

             if(arr[j] < arr[minIdx]){

                 minIdx = j;

             }

         }

         let tmp = arr[i];

         arr[i] = arr[minIdx];

         arr[minIdx] = tmp;

     }

     return arr;

 }

插入排序（insertion sort）

思路：当前位置的值与前面排好序的区间从后往前对比，找到适合的插入位置并插入。

适用于：近乎有序的排序，在几乎有序的情况下，它的速度会比n(logn)的算法还要快,可以接近O(n)，插入排序要优于选择排序

 function insertSort(arr){

     let tmp;

     for(let i = 0; i < arr.length; i++){

         for(let j = i - 1; j >= 0; j--){

         if(j === 0){

             if(arr[i] < arr[j]){

                 // 在顺序表中，应该使用副本复制当前的值，采用赋值去修改数组，而不是删除和插入，因为在顺序表中删除和插入的时间复杂度是n

                 tmp = arr.splice(i,1)[0];

                 arr.splice(j,0,tmp);

             }

         }else if(arr[i] < arr[j] && arr[i] >= arr[j - 1]){

                 tmp = arr.splice(i,1)[0];

                 arr.splice(j,0,tmp);

             }

         }

         // 做一个当前函数是否有序的判断

         if(isSort(arr)){

             return arr;

         }

     }

     return arr;

 }

冒泡排序

O(nlogn)的算法

归并排序

优化：在待排区间的长度小于100时，可以用插入排序

 // 自下而上的归并算法，自上而下需要用到递归

 function mergeSort(arr){

     let arrSort = [],n = arr.length，count = 0;

     for(let size = 1; size <= n; size += size){ // size表示当前有序区间的长度

         for(let i = 0; i < n; i += size*2){

             // 将[i...i+size-1]和[i+size...i+size*2-1]的两个区间融合成一个有序的并添加到arrSort后面

             arrSort = arrSort.concat(orderMerge(arr.slice(i,i+size),arr.slice(i+size,((i+size*2) > n? n : (i+size*2)))));

         }

         arr = arrSort.slice(0);

         arrSort.length = 0;

     }

     return {arr,count};

     // orderMerger 函数主要是讲有序的两个表融合成一个有序表

     function orderMerge(arr1,arr2){

         let arr = [];

         let idx1 = 0, idx2 = 0;

         while(idx1 < arr1.length && idx2 < arr2.length){

             if(arr1[idx1] <= arr2[idx2]){

                 arr.push(arr1[idx1++]);

             }else{

                // 当arr1[index1] > arr2[idx2]的时候就是一个逆序对

                 arr.push(arr2[idx2++]);

                 count++;

             }

         }

         if(idx1 === arr1.length){

             arr = arr.concat(arr2.slice(idx2));

         }else{

             arr = arr.concat(arr1.slice(idx1));

         }

         return arr;

     }

 }

快速排序

思想：选择待排序的区间中第一个p数作为参照，大于p的放在p的后面，小于p的放前面。最后将p放在两个区间的中间，递归下去。

缺点:: 1 在排近乎有序的数组的时候，时间复杂度趋近于O(n^2)

2 再相同数值很多的数组中，时间复杂度趋近于O(n^2)

解决方案：优化缺点1：随机选择参照数p或者待排数组中间的数作为参照数

优化缺点2-1 ：从待排数组两边进行遍历，从左向右遇到>=p的值停顿，在从右向左遇到<=p的值停顿，将两个数交换并i++，j--，知道i == j为止

优化缺点2-2：三路快速排序，有三个数组，一个数组存放小于p的值，一个存放大于p的值，一个存放等于p的值。

 function quickSort(arr){

     // 终止条件：当数组长度小于等于1是返回该数组

     if(arr.length <= 1){

         return arr;

     }

     // 定义leftSort、rightSort存放小于和大于p的数

     let leftSort = [], rightSort =[], midSort = [], odd = 0;

     // 遍历arr，将大于p的放在rightSort中，小于p的放在leftSort中

     //优化缺点1：选择中间的数做参照并把该数从原数组中删除

     let idx = Math.floor(arr.length/2);

     let p = arr.splice(idx,1)[0];

     for(let i = 0; i < arr.length; i++){

         if(arr[i] > p){

             rightSort.push(arr[i]);

         }else if(arr[i] < p){

             leftSort.push(arr[i]);

         }else{

             // 优化缺点2

             if(odd){

                 leftSort.push(arr[i]);

                   odd = 1;

             }else{

                 rightSort.push(arr[i]);

                 odd = 0;

             }

         }

     }

     // 递归leftSort、rightSort

     leftSort = quickSort(leftSort);

     rightSort = quickSort(rightSort);

     // 将leftSort、midSort、rightSort合并成一个数组并返回。

     arr = leftSort.concat(p,rightSort)

     return arr;

 }

 //优化缺点2-2

 function quickSort(arr){

     if(arr.length <= 1){

         return arr;

     }

     let leftSort = [], rightSort =[], midSort = [];

     let idx = Math.floor(arr.length/2);

     let p = arr[idx]; // 可以不用删除了

     for(let i = 0; i < arr.length; i++){

         if(arr[i] > p){

             rightSort.push(arr[i]);

         }else if(arr[i] < p){

             leftSort.push(arr[i]);

         }else{

             midSort.push(arr[i]);

         }

     }

     arr = quickSort(leftSort).concat(midSort,quickSort(rightSort))

     return arr;

 }

扩展

Merge Sort的思路求逆序对的个数

mergeSort第21行

Qiuck Sort求数组中第n大的数

 function theNumberN(arr,n){

     let p,idx,

         leftSort = [],

            midSort = [],

         rightSort = [];

     while(arr.length > 1){

         idx = Math.floor(arr.length/2);

         p = arr[idx];

         for(let i = 0; i < arr.length; i++){

             if(arr[i] < p){

                 leftSort.push(arr[i]);

             }else if(arr[i] > p){

                 rightSort.push(arr[i]);

             }else{

                 midSort.push(arr[i]);

             }

         }

         if(leftSort.length >= n){

             arr = leftSort.slice(0);

         }

         else if(leftSort.length+midSort.length >= n){

             return midSort[0];

         }

         else{

             arr = rightSort.slice(0);

             n = n - leftSort.length - midSort.length;

         }

             leftSort.length = midSort.length = rightSort.length = 0;

     }

     return arr[0];

 }

或者使用递归

 function theNumberN(arr,n){

     if(arr.length <= 1){

         return arr[0];

     }

     // 选一个基点p

     let p,

         leftSort = [],

         midSort = [],

         rightSort = [];

     // 小于p放leftSort，等于p放midSort，大于放rightSort

         p = arr[Math.floor(arr.length/2)];

         for(let i = 0; i < arr.length; i++){

         if(arr[i] < p){

             leftSort.push(arr[i]);

         }else if(arr[i] > p){

             rightSort.push(arr[i]);

         }else{

             midSort.push(arr[i]);

         }

     }

     // 如果leftSort.length>n则抛弃midSort和rightSort再找leftSort中第n大的数

     if(leftSort.length >= n){

         return theNumberN(leftSort,n);

     }

     // 否则判断leftSort.length+midSort.length>n则抛弃leftSort和rightSort，在midSort中找第n-leftSort.length大的数

     else if(leftSort.length+midSort.length >= n){

         // theNumberN(midSort,n - leftSort.length);

         return midSort[0];

     }

     // 否则抛弃leftSort和midSort，在rightSort中找第n-leftSort.length-midSort.length大的数

     else{

         return theNumberN(rightSort,n - leftSort.length - midSort.length);

     }

 }

巴特西