常见的排序算法js+时间空间复杂度+广度深度优先遍历_算法时间优先级 空间优先级

广度优先搜索会根据离起点的距离，按照从近到远的顺序对各节点进行搜索。而深度优先搜索会沿着一条路径不断往下搜索直到不能再继续为止，然后再折返，开始搜索下一条路径。
在广度优先搜索中，有一个保存候补节点的队列，队列的性质就是先进先出，即先进入该队列的候补节点就先进行搜索。 （如果是对于二叉树的运算，二叉树是按层级顺序遍历）
在深度优先搜索中，保存候补节点是栈，栈的性质就是先进后出，即最先进入该栈的候补节点就最后进行搜索。（如果是对于二叉树的运算，二叉树是按照先序遍历）
广度深度优先搜索参考链接

快速排序：最优的情况下空间复杂度为：O(logn)（就是以2为底），每一次都平分数组，即元素非顺序排列 ；最差的情况下空间复杂度为：O( n )，退化为冒泡排序，即元素已按顺序排列。

算法复杂度分为时间复杂度和空间复杂度。其作用： 时间复杂度是指执行算法所需要的计算工作量；而空间复杂度是指执行这个算法所需要的内存空间。（算法的复杂性体现在运行该算法时计算机所需资源的多少上，计算机资源最重要的是时间和空间（即寄存器）资源，因此复杂度分为时间和空间复杂度。）

在计算机科学中，时间复杂性，又称时间复杂度，算法的时间复杂度是一个函数，它定性描述该算法的运行时间。这是一个代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述，不包括这个函数的低阶项和首项系数。使用这种方式时，时间复杂度可被称为是渐近的，亦即考察输入值大小趋近无穷时的情况。

空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度，记做S(n)=O(f(n))。比如直接插入排序的时间复杂度是O(n^2),空间复杂度是O(1) 。而一般的递归算法就要有O(n)的空间复杂度了，因为每次递归都要存储返回信息。一个算法的优劣主要从算法的执行时间和所需要占用的存储空间两个方面衡量。

 <script>
        //冒泡排序
  function bubSort(arr){
   if (!Array.isArray(arr) || arr.length <= 1) return arr;
      let len=arr.length
      for(let i=0;i<len-1;i++)
      {
          for(let j=0;j<len-1-i;j++)
          {
              if(arr[j]>arr[j+1])
              {
                  let temp=arr[j]
                  arr[j]=arr[j+1]
                  arr[j+1]=temp
              }
          }
      }
      return arr
  }
//  console.log(  bubSort([6,5,8,9,74,58,12,43,26,45]));

//选择排序
function choiceSort(arr){
   let len=arr.length
   for(let i=0;i<len-1;i++)
   {
      let minArr=arr.slice(i)
      let min=Math.min(...minArr)   
      let index=minArr.indexOf(min)+i //此处不能用arr的indexOf，因为用arr如果有两个重复的数，如果第一个已经被排序，而indexOf的时候是想找第二个数的，但indexOf只会找第一个数且已被排序
      if(index!=i)
      {
          let temp=arr[i]
          arr[i]=arr[index]
          arr[index]=temp
      }
    
   }

   return arr
}
// console.log(  choiceSort([6,5,8,9,26,26,74,58,26,58,12,43,26,58,45]));

//插入排序
function insertSort(arr){
  let len=arr.length
  for(let i=1;i<len;i++)
  {   
      let temp=arr[i]
      let j=i-1
      while (temp<arr[j]&&j>=0) {   //必须用一个值把arr[i]存起来，不能直接用arr[i]，因为虽然i没变，但是数组内部结构已经被改变，导致值不固定
        
        arr[j+1]=arr[j]
          j--
      }
     

      if (j!=i-1) {
        arr[j+1]=temp
      }

  

  }
  
  return arr
}

// console.log(insertSort([6,5,8,9,26,26,74,58,26,58,12,43,26,58,45]));


//归并排序
function mergeSort(arr){
    
    let rec=(arr)=>{
    
        if (arr.length==1) {
            return arr
        }
        let mid=Math.floor(arr.length/2)
        let left=arr.slice(0,mid)
        let right=arr.slice(mid,arr.length)
          
        let sortLeft=rec(left)
        let sortRight=rec(right)
        let res=[]
        while (sortLeft.length||sortRight.length) {
            if (sortLeft.length&&sortRight.length) {
                sortLeft[0]<sortRight[0]?res.push(sortLeft.shift()):res.push(sortRight.shift())
            }else if(sortLeft.length)
            {
                res.push(sortLeft.shift())
            }else if(sortRight.length)
            {
                res.push(sortRight.shift())
            }
           
        }
       
        return res

    }
   let newarr= rec(arr)
   
   return newarr
}

console.log(mergeSort([6,5,8,9,26,26,74,58,26,58,12,43,26,58,45]));


//快速排序
function fastSort(arr){
      if (!Array.isArray(arr) || arr.length <= 1) return arr;
    let rec=(arr)=>{
        if (arr.length === 1 || arr.length === 0) {
            return arr
        }

        let left=[]
        let right=[]
        let mid=arr[0]
        for (let i = 1; i < arr.length; i++) {
            if (arr[i]>mid) {
                right.push(arr[i])
            }else
            {
                left.push(arr[i])
            }
            
        }
        return[...rec(left),mid,...rec(right)]

    }
    let newarr=rec(arr)
    return newarr
}
console.log(fastSort([9, 4, 3, 1, 6, 3, 8, 7]));
    </script>
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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137

//希尔排序
function shellSort(arr) { // 参数为需要排序的数组

// 获取初始的增量
let gap = Math.floor(arr.length / 2);

while (gap >= 1) { // 增量小于1时结束循环

    // 从gap开始遍历，因为插入排序假设第一个是有序的
    for (let i = gap; i < arr.length; i++) {
        let j = i; // 为插入排序从后向前排序提供条件

        // 如果排序的后面的数字小于前面的，交换两个数的位置，从小到大排序
        while (arr[j] < arr[j - gap] && j - gap >= 0) {
            let temp = arr[j];
            arr[j] = arr[j - gap];
            arr[j - gap] = temp;

            // j减小,依次从后向前比较
            j -= gap;
        }
    }

    // 增量每次都减小一半
    gap = Math.floor(gap / 2);
}

return arr;
} 

 console.log(shellSort( [6,5,8,9,268,26,74,58,26,58,12,43,26,58,45]));
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
26
27
28
29
30
31

//基数排序
function  radixSort(arr){
 // 如果不是数组或者数组长度小于等于1，直接返回，不需要排序
  if (!Array.isArray(arr) || arr.length <= 1) return arr;
let maxvalue=Math.max(...arr)
let mvlen=maxvalue.toString().length

//初始化桶 一行十列，用于每次取出每个数个十百等位上的数直接对应存放即可，不需要再做多余的排序
let conArr=new Array(10).fill().map(item=>new Array())


for(let i=0;i<mvlen;i++)
 {
  for (let index = 0; index < arr.length; index++) {
      
 let value= parseInt(arr[index]/(Math.pow(10,i)))%10
 conArr[value].push(arr[index])

  }

 arr.splice(0,arr.length) //清空arr

 for(let j=0;j<10;j++)
 {
 if (conArr[j].length) {
     
   while (conArr[j].length) {
    arr.push(conArr[j].shift())
   }
 }

}

}

return arr
}
 console.log(radixSort([6,0,8478,9,255,26,74,582,26,58,12,43,26,58,45]));
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
26
27
28
29
30
31
32
33
34
35
36
37
38
39

五种排序参考了该文章
希尔排序参考该文章
基数排序参考该文章