curTain

总结常用排序算法.

前言

学数据结构已经是大二上学期的事了,

写一下常用的排序算法。

1. 冒泡排序

1.1 编程思路

使用两层循环,

  • 外层循环:执行 i 次,每一次排好一个元素。
  • 内层循环:每执行一次,就挑选出数组中第 i 个位置的元素,并将该元素放到 i 位置。

1.2 编程要点

在内层循环,相邻元素依次比较,把最大或最小元素放到最后。

1.3 代码实现

冒泡排序
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
let arr = [ 5, 3, 8, 0, 9, 6 ]
/**
*
* @param { array } arr 数组
* @param { boolean } asc 是否升序
*/
function bobble( arr, asc = true ){
for( let i = 0; i < arr.length; i ++ ){
for( let j = 0; j < arr.length; j ++ ){
// 升序
if( asc ){
if( arr[j] < arr[j + 1] ){
[ arr[j+1], arr[j] ] = [ arr[j], arr[j+1] ]
}
// 降序
} else {
if( arr[j+1] < arr[j] ){
[ arr[j+1], arr[j] ] = [ arr[j], arr[j+1] ]
}
}
}
console.log( `外层循环第${ i }次执行的结果:`,arr )
}
return arr
}
console.log( bobble( arr, true ) )

运行结果:

根据代码可知,代码有待优化。

1. 4 代码优化

优化点:

  1. 可知,外层循环每执行一次,就有一个元素在尾部排好序,则在内部循环中,可以减少后面 i 次不必要的比较。
  2. 当外层循环执行到最后一次时,只有一个元素,则可以不必再比较,则外层循环可以减 1
冒泡排序优化
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
function bobble( arr, asc = true ){
for( let i = 0; i < arr.length - 1; i ++ ){
for( let j = 0; j < arr.length - 1 - i; j ++ ){
// 升序
if( asc ){
if( arr[j] < arr[j + 1] ){
[ arr[j+1], arr[j] ] = [ arr[j], arr[j+1] ]
}
// 降序
} else {
if( arr[j+1] < arr[j] ){
[ arr[j+1], arr[j] ] = [ arr[j], arr[j+1] ]
}
}
}
console.log( `外层循环第${ i }次执行的结果:`,arr )
}
return arr
}

运行结果:

2. 选择排序

2.1 编程思路

从未排序的部分选择最大或最小的值,将其排在有序序列的前或后。

  • 升序:选择未排序部分的最小值,与排序部分后第一个元素交换
  • 降序:选择未排序部分的最大值,与排序部分后第一个元素交换

实现:使用两层循环

  1. 外层循环:执行 i - 1 次,将内层循环挑选出的元素放到已排序部分的尾部。
  2. 内层循环:挑选出未排序部分最小值或最大值的下标。

2.2 编程要点

  1. 将数组用外层循环分为两段
  2. 每次外层循环时,使用一个 flagIndex 标记来标记内层循环挑选出来的元素的下标
  3. 外层循环将挑选出来的元素放到排好序的末尾

2.3 代码实现

选择排序
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
let arr = [ 5, 3, 8, 0, 9, 6 ]
/**
*
* @param { array } arr 数组
* @param { boolean } asc 是否升序
*/
function selectSort( arr, asc = true ){
for( let i = 0; i < arr.length - 1; i ++ ){
// 记住未排序部分的最小值或最大值的下标
let flagIndex = i
for( let j = i; j < arr.length; j ++ ){
if( asc ){
if( arr[flagIndex] > arr[j] ){
flagIndex = j
}
} else {
if( arr[flagIndex] < arr[j] ){
flagIndex = j
}
}
}
[ arr[flagIndex], arr[i] ] = [ arr[i], arr[flagIndex] ]
}
return arr
}

console.log( selectSort( arr, false ) )

3. 插入排序

3.1 编程思路

将数组以外层循环次数为基准分成两段,数组前段:已经排好序;数组后端:未排序

将未排序部分的第一个元素插入到排好序的部分中。

实现思路:使用两层循环

  1. 外层循环:执行 i - 1 次,每一次将后面的一个元素排进前面部分。
  2. 内层循环:将未排序部分的第一个元素插入到排好序的部分中

3.2 编程要点

内层循环:已排序部分的后一个元素向前单向冒泡

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
let arr = [ 5, 3, 8, 0, 9, 6 ]
function insetSort( arr ){
for( let i = 0; i < arr.length - 1; i ++ ){
for( let j = i + 1; j >= 0; j -- ){
// 单向冒泡
if( arr[j] < arr[ j - 1 ] ){
[ arr[ j - 1 ], arr[j] ] = [ arr[j], arr[ j - 1 ] ]
break
}
}
}
return arr
}

console.log( insetSort( arr ) )

4. 快速排序

4.1 编程思路

寻找一个中点,将原数组分为三部分

  1. 第一部分:元素的值都比中点的值小
  2. 第二部分:当前元素
  3. 第三部分:元素的值都比中点的值大

依次递归,当分出数组的长度小于等于 1 时,返回数组

最后把三部分合并到一起。

实现思路:

使用三个变量保存三部分的结果,最后合并到一起。

4.2 编程要点

将原数组分成三部分保存下来,返回合并的值。

4.3 代码实现

快速排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
let arr = [ 5, 3, 8, 0, 9, 6 ]

function quick( arr ){
if( arr.length <= 1 ){
return arr
}
let pointIndex = Math.floor( arr.length / 2 )
let pointValue = arr.splice( pointIndex, 1 )[0]
let lArr = []
let rArr = []
for( let i = 0; i < arr.length; i ++ ){
arr[i] > pointValue ? rArr.push( arr[i] ) : lArr.push( arr[i] )
}
return [ ...quick(lArr), pointValue, ...quick(rArr) ]
}

console.log( quick( arr ) )

5. 快速排序(原数组操作方式)

5.1 编程思路

在原数组上操作,取一个中值,操作原素组,将原数组以该中值为基点分成两部分,记录下标,重复进行此操作,当开始的下标和结束的下标相等时结束递归,最后,整个数组就排序成功。

5.2 编程要点

  1. 将原数组以中值为基点分成三部分。
  2. 每次递归,传入正确的下标
  3. 获取中值下标函数的编写

获取中值下标函数

作用:将数组段以左起点为中点,将此段数组分成三段,返回中值的下标。

思路:

  1. 取出起点的值作为中点
  2. 使用变量 j 为起始值的下标
  3. 使用一个循环,循环将此段数组分为三段(满足条件–>交换位置–>j++)
  4. 返回中值下标 j

5.3 代码实现

快速排序(操作原数组方式)
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
let arr = [ 5, 3, 8, 0, 9, 6 ];

/**
* 函数的作用:获取中值下标
* 以该段数组尾部的值作为基准,将数组分为两半,返回基准值的下标
* @param { Array } arr 原素组
* @param { number } start 操作开始的地方
* @param { number } end 操作结束的地方
*/
function getCenterIndex( arr, start, end ){
let j = start
let pValue = arr[end]
for( let i = start; i <= end; i ++ ){
if( arr[i] <= pValue ){
[ arr[i], arr[j] ] = [ arr[j], arr[i] ]
j ++
}
}
return j - 1
}

function quickSort( arr, start = 0, end = arr.length -1 ){
if( end - start < 1 ) return arr
let centerIndex = getCenterIndex( arr, start, end )
// 将左右两边依次排序
quickSort( arr, start, centerIndex - 1 )
quickSort( arr, centerIndex + 1, end )
return arr
}

console.log( quickSort( arr ) )

6. 归并排序

6.1 编程思路

  1. 使用递归将数组递归拆分直至只有一个元素
  2. 将数组依次合并

6.2 编程要点

使用两个函数:

  1. 分函数:将数组进行拆分,直到只有一个元素为止
  2. 合函数:使用队列的思想,将两个两个的数组合并成一个数组

6.3 代码实现

归并排序
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
let arr = [ 5, 3, 8, 0, 9, 6 ];

// 归并排序
function mergeSort( arr ){
if( arr.length < 2 ){
return arr
}
let middle = Math.floor( arr.length / 2 )
let left = arr.slice( 0, middle )
let right = arr.slice( middle )
// 先分再和
return merge( mergeSort( left ), mergeSort( right ) )
}
// 将分开的数组合并
function merge( l, r ){
let res = []
// 依次用第一个元素对比 小的元素放到
while( l.length && r.length ){
if( l[0] <= r[0] ){
res.push( l.shift() )
} else {
res.push( r.shift() )
}
}
// 将剩下的元素放到 res 中
while( l.length ) res.push( l.shift() )
while( r.length ) res.push( r.shift() )

return res
}

console.log( mergeSort( arr ) )

7. 未完待续……

7.1 桶排序

7.2 计数排序

7.3 希尔排序

8. 参考材料

JavaScript 数据结构与算法之美 - 归并排序、快速排序、希尔排序、堆排序

手写算法并记住它:快速排序(最易理解版)

手写算法并记住它:快速排序(5行代码简单版)

手写算法并记住它:插入排序

手写算法并记住它:选择排序


 评论