排序

⭐时间复杂度

1、常数阶O(1)

只要代码中没有复杂的循环条件，无论代码的函数是多少，一律为常数阶O(1)。

1 for(int i=0;i<n;i++){
2     int j=o;
3     j++;
4 }

2、对数阶O(log₂n)

存在循环体，在不考虑循环体的代码执行情况，该循环体本该执行n次，但是循环体将改变循环变量i的大小，每执行一次，i就扩到两倍，即i=i*2,这样就导致循环体会加速趋近终止条件n;假设经过x次后，退出循环体，则有2x>=n,因此,x=log₂n；同理，当i=i∗3时，x=log₃n,退出循环的速度更快，时间复杂度更小。

1 while(i<n){
2     i=i*2;
3 }

3、线性阶O(n)

存在循环体。循环体内代码执行的次数随着规模n的变化而变化，并且是线性变化。

1 for(int i=0;i<n;i++){
2     int j=o;
3     j++;
4 }

4、线性对数阶O(nlog₂n)

将时间复杂度为O(log₂n)的代码重复执行n次，即为线性对数阶O(nlog₂n)。

1 //n为一个固定的常数
2 //i和j均为循环变量
3 while(i<n){//线性节阶
4     while(j<n){//对数阶
5         j=j*2;
6     }
7 }

5、平方阶O(n²)

复杂度为O(n)的代码执行了n次。

1 for(int i=0;i<n;i++){//执行n次
2     for(int j=0;j<n;j++){//执行n次
3         int m=0;
4         m++;
5     }
6 }

6、立方阶O(n³)

和平方阶原理一样，时间复杂度为O(n²)的代码执行n次。

1 for(int i=0;i<n;i++){//执行n次
2     for(int j=0;j<n;j++){//执行n次
3         for(int k=0;k<n;k++){
4             int m=0;
5             m++;
6         }
7     }
8 }

O(1)<O(log₂n)<O(n)<O(nlog₂n)<O(n²)<O(n^k)

⭐空间复杂度

1、O(1)

1 let a = 1;
2 let b = 1;
3 let c = 1;
4 let d = 1;

2、O(n)

1 let arr = Array(n)

3、O(n²)

1 let arr=[]
2 for (var i = 0; i < n; i++) {
3   arr[i]=i
4   for (var j = 0; j < n; j++) {
5     arr[i][j]=j
6   }
7 }

排序前数组的准备：

 1 <!DOCTYPE html>
 2 <html lang="en">
 3 
 4 <head>
 5     <meta charset="UTF-8">
 6     <meta http-equiv="X-UA-Compatible" content="IE=edge">
 7     <meta name="viewport" content="width=device-width, initial-scale=1.0">
 8     <title>Document</title>
 9 </head>
10 
11 <body>
12     <script>
13         let arr = [];
14         for (let i = 0, len = 10; i < len; i++) {
15             let num = Math.floor(Math.random() * 100);
16             arr.push(num);
17         }
18         console.log('arr', arr);
19 
20         console.time('a');
21 
22         //排序算法位置
23         //排序算法位置
24 
25         console.timeEnd('a');
26         console.log('arr', arr);
27     </script>
28 </body>
29 
30 </html>

⭐冒泡排序

从第一个元素开始，把当前元素和下一个索引元素进行比较。如果当前元素大，那么就交换位置，重复操作直到比较到最后一个元素。

1         for (let i = arr.length - 1; i > 0; i--) {
2             for (let j = 0; j < i; j++) {
3                 if (arr[j] > arr[j + 1]) {
4                     [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
5                 }
6             }
7         }

⭐插入排序

第一个元素默认是已排序元素，取出下一个元素和当前元素比较，如果当前元素大就交换位置。那么此时第一个元素就是当前的最小数，所以下次取出操作从第三个元素开始，向前对比，重复之前的操作。

自己写的：

 1        for (let i = 1, len = arr.length; i < len; i++) {
 2             for (let j = i - 1; j >= 0; j--) {
 3                 if (arr[i] < arr[0]) {
 4                     let temp = arr[i];
 5                     arr.splice(i, 1);
 6                     arr.unshift(temp);
 7                     break;
 8                 }
 9                 if (arr[i] > arr[j - 1] && arr[i] < arr[j]) {
10                     let temp = arr[i];
11                     arr.splice(i, 1);
12                     arr.splice(j, 0, temp);
13                     break;
14                 }
15             }
16         }

正规的：

 1         for (let i = 1, len = arr.length; i < len; i++) {
 2             let nowPosition = i;
 3             let nowData = arr[i];
 4             for (let j = i - 1; j >= 0; j--) {
 5                 if (arr[j] > nowData) {
 6                     arr[nowPosition] = arr[j];
 7                     arr[j] = nowData;
 8                     nowPosition = j
 9                 }
10             }
11         }

⭐选择排序

遍历数组，设置最小值的索引为0，如果取出的值比当前最小值小，就替换最小值索引，遍历完成后，将第一个元素和最小值索引上的值交换。如上操作后，第一个元素就是数组中的最小值，下次遍历就可以从索引 1 开始重复上述操作。

1         for (let i = 0, len = arr.length - 1; i < len; i++) {
2             for (let j = i + 1, len = arr.length; j < len; j++) {
3                 if (arr[j] < arr[i]) {
4                     let a = arr[j];
5                     arr[j] = arr[i];
6                     arr[i] = a;
7                 }
8             }
9         }

⭐快速排序

在数据集之中，找一个基准点，建立两个数组，分别存储左边和右边的数组，利用递归进行下次比较。

 1        function quickSort(theArr) {
 2             let len = theArr.length;
 3             if (len < 2) {
 4                 return theArr;
 5             };
 6             let middleNum = Math.floor(len / 2);
 7             let left = [];
 8             let right = [];
 9             let middle = theArr[middleNum];
10             for (let i = 0; i < len; i++) {
11                 if (i !== middleNum && theArr[i] < middle) {
12                     left.push(theArr[i]);
13                 } else if (i !== middleNum && theArr[i] >= middle) {
14                     right.push(theArr[i]);
15                 }
16             }
17             return quickSort(left).concat(middle, quickSort(right));
18         }
19         arr = quickSort(arr);

⭐希尔排序

按增量序列个数 k，对序列进行 k 趟排序；

每趟排序，根据对应的增量 ti，将待排序列分割成若干长度为 m 的子序列，分别对各子表进行直接插入排序。仅增量因子为 1时，整个序列作为一个表来处理，表长度即为整个序列的长度。

 1         let gap = Math.floor(arr.length / 2);
 2         do {
 3             for (let i = 0, len = arr.length - gap; i < len; i++) {
 4                 let nowPosition = i;
 5                 let nowData = arr[i];
 6                 for (let j = i + gap, len = arr.length; j < len; j = j + gap) {
 7                     if (nowData > arr[j]) {
 8                         arr[nowPosition] = arr[j];
 9                         arr[j] = nowData;
10                         nowPosition = j;
11                     }
12                 }
13             }
14             gap = Math.floor(gap / 2);
15         } while (gap >= 1);

⭐归并排序

（1）把长度为n的输入序列分成两个长度为n/2的子序列；

（2）对这两个子序列分别采用归并排序；

（3）将两个排序好的子序列合并成一个最终的排序序列。

 1         function Merge(theArr) {
 2             if (theArr.length < 2) {
 3                 return theArr;
 4             }
 5             let middle = Math.floor(theArr.length / 2);
 6             let left = theArr.slice(0, middle);
 7             let right = theArr.slice(middle);
 8             return MergeSort(Merge(left), Merge(right));
 9         }
10 
11         function MergeSort(left, right) {
12             let sortData = [];
13             while (left.length !== 0 && right.length !== 0) {
14                 if (left[0] < right[0]) {
15                     sortData.push(left.shift());
16                 } else {
17                     sortData.push(right.shift());
18                 }
19             }
20             return sortData.concat(left, right);
21         }
22 
23         arr = Merge(arr);

⭐二分排序

在插入第i个元素时，对前面的0～i-1元素进行折半，先跟他们中间的那个元素比，如果小，则对前半再进行折半，否则对后半进行折半，直到left>right，然后再把第i个元素前1位与目标位置之间的所有元素后移，再把第i个元素放在目标位置上。

 1         for (let i = 1, len = arr.length; i < len; i++) {
 2             let temp = arr[i];
 3             if (arr[i] < arr[0]) {
 4                 arr.splice(i, 1);
 5                 arr.unshift(temp);
 6             } else if (arr[i] > arr[i - 1]) {
 7                 continue;
 8             } else {
 9                 let position = DichotomySort(0, i - 1, temp);
10                 arr.splice(i, 1);
11                 arr.splice(position, 0, temp);
12             }
13         }
14 
15         function DichotomySort(left, right, value) {
16             if (left === right) {
17                 return left;
18             }
19             let middle = Math.floor((right + left) / 2);
20             if (value < arr[middle]) {
21                 return DichotomySort(left, middle, value);
22             } else {
23                 return DichotomySort(middle + 1, right, value);
24             }
25         }

⭐Array自带的sort()和reverse()

1、Array.reverse()倒序。

2、Array.sort()：不给参数按ascii码排序。Array.sort(function(a,b){return b - a})：降序。