JavaScript

SunSeekerX ... 2020-4-15 大约 4 分钟

# JavaScript

# 📌 排序

/**
 * @name 数组排序算法(保证数组数据唯一)
 * @author SunSeekerX
 * @time 2019-11-23 16:05:37
 * @LastEditors SunSeekerX
 * @LastEditTime 2019-11-23 18:59:32
 */

/**
 * 冒泡排序
 * 1.比较相邻的元素。如果第一个比第二个大,就交换他们两个。
 * 2.对每一对相邻元素做同样的工作,从开始第一对到结尾的最后一对。在这一点,最后的元素应该会是最大的数。
 * 3.针对所有的元素重复以上的步骤,除了最后一个。
 * 4.持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。
 */

console.log('------------------冒泡排序---------------')
console.time()
const arr = [1, 9, 5, 4, 3, 8]
console.log('排序前>>>', arr)
for (let i = 0; i < arr.length - 1; i++) {
  for (let j = 0; j < arr.length - 1 - i; j++) {
    let temp = null
    if (arr[j] > arr[j + 1]) {
      temp = arr[j]
      arr[j] = arr[j + 1]
      arr[j + 1] = temp
    }
  }
}
console.log('排序后>>>', arr)
console.timeEnd()
console.log('\n')

/**
 * 插入排序
 * 1.依次取出数组中的值
 * 2.更新的数组对比插入到新的数组(抓牌原理一样)
 */

console.log('------------------插入排序,从后往前比(斗地主抓牌)---------------')
// 插入排序,从后往前比(斗地主抓牌)
const arr2 = [1, 9, 5, 4, 3, 8]
console.time()
console.log('排序前>>>', arr2)
// 1.取出第一张牌
const newArr = [arr2[0]]
for (let i = 1; i < arr2.length; i++) {
  // 2.从后面往前插
  for (let j = newArr.length - 1; j >= 0; j--) {
    // 如果取出的牌比当前循环的牌大,就放在这个牌后面
    if (arr2[i] > newArr[j]) {
      // 插入到新的数组
      newArr.splice(j + 1, 0, arr2[i])
      break
    }
    // 比较到第一张牌,放到手里的第一张(最小)
    if (j === 0) {
      newArr.unshift(arr2[i])
    }
  }
}
console.log('排序后>>>', newArr)
console.timeEnd()
console.log('\n')

/**
 * 快速排序
 * 1.首先设定一个分界值,通过该分界值将数组分成左右两部分。
 * 2.将大于或等于分界值的数据集中到数组右边,小于分界值的数据集中到数组的左边。此时,左边部分中各元素都小于或等于分界值,而右边部分中各元素都大于或等于分界值。
 * 3.然后,左边和右边的数据可以独立排序。对于左侧的数组数据,又可以取一个分界值,将该部分数据分成左右两部分,同样在左边放置较小值,右边放置较大值。右侧的数组数据也可以做类似处理。
 * 4.重复上述过程,可以看出,这是一个递归定义。通过递归将左侧部分排好序后,再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后,整个数组的排序也就完成了。
 */

console.log('------------------快速排序---------------')
const arr3 = [1, 9, 5, 4, 3, 8]
console.time()
console.log('排序前>>>', arr3)
function quick(arr) {
  // 4.结束递归(当arr中小于等于一项,则返回)
  if (arr.length <= 1) {
    return arr
  }

  // 1.找到数组的中间项把他删除
  let middleIndex = Math.floor(arr.length / 2)
  let middleValue = arr.splice(middleIndex, 1)[0]

  // 2.准备左右两个数组,循环剩下的数组中的每一项,比中间项小的放左边,反之放右边
  let arrLeft = [],
    arrRight = []
  for (let i = 0; i < arr.length; i++) {
    arr[i] < middleValue ? arrLeft.push(arr[i]) : arrRight.push(arr[i])
  }

  // 3.递归处理左右两边数组,一直到左右两边都排好(左右让左边+中间+右边为最后的结果)
  return quick(arrLeft).concat(middleValue, quick(arrRight))
}
console.log('排序后>>>', quick(arr3))
console.timeEnd()
console.log('\n')

console.log('------------------分割线---------------\n\n')

console.log('------------------(For循环计算1-10累加的和)---------------')
console.time()
let total = 0
for (let i = 1; i <= 10; i++) {
  total = total + i
}
console.log('For循环计算后>>>', total)
console.timeEnd()
console.log('\n')

console.log('------------------(递归计算1-10累加的和)---------------')
console.time()
function sumFun(n) {
  if (n > 10) {
    return 0
  }
  return n + sumFun(n + 1)
}
console.log('递归计算后>>>', sumFun(1))
console.timeEnd()
console.log('\n')

/**
 * 堆栈溢出
 *
 * Uncaught RangeError: Maximum call stack size exceeded
 */

// function fn() {
//   fn();
// }
// fn();

/**
 * 堆栈不溢出
 * 这实际上并不是递归调用,因为fn2的第一次调用实际上在setTimeout()调用下一个调用之前完成。
 * 所以,这不是技术上的递归,并且不会随着时间的推移建立堆栈。它可以在没有任何积聚的情况下永久运行,这是保持反复运行的完美方式。
 * javascript不是多线程的,因此它不会为定时器创建多个线程。
 * 触发的每个定时器事件只是将事件放入事件队列中,并且如果当时没有JS正在运行,则触发该事件(从而调用回调函数)。
 * 如果JS正在运行,那么JS引擎会等待,直到当前正在执行的JS完成,然后为事件队列中的下一个事件提供服务(从而调用回调)。
 *
 * 通俗的说
 *
 * 在执行setTimeout中的函数方法之前,fn()这个方法已经执行完毕了,内存堆栈已经释放了,因此不会内存溢出
 */

// function fn2() {
//   setTimeout(() => fn2(), 0);
// }
// fn2();
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
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
上次编辑于: 2021年7月7日 16:59