Skip to content

Commit b1d5b2d

Browse files
hojashojas
committed
sort
1 parent bf3d71e commit b1d5b2d

File tree

25 files changed

+2373
-1117
lines changed

25 files changed

+2373
-1117
lines changed

‎.nvmrc‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1 +1 @@
1-
20
1+
22

‎package.json‎

Lines changed: 6 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -3,17 +3,17 @@
33
"type": "module",
44
"version": "1.0.0",
55
"private": true,
6-
"packageManager": "pnpm@9.6.0",
6+
"packageManager": "pnpm@9.12.3",
77
"license": "MIT",
88
"scripts": {
99
"lint": "eslint .",
1010
"test": "vitest"
1111
},
1212
"devDependencies": {
13-
"@antfu/eslint-config": "^2.24.1",
14-
"eslint": "^9.8.0",
15-
"typescript": "^5.5.4",
16-
"vite": "^5.3.5",
17-
"vitest": "^2.0.5"
13+
"@antfu/eslint-config": "^3.8.0",
14+
"eslint": "^9.13.0",
15+
"typescript": "^5.6.3",
16+
"vite": "^5.4.10",
17+
"vitest": "^2.1.4"
1818
}
1919
}

‎pnpm-lock.yaml‎

Lines changed: 1164 additions & 879 deletions
Some generated files are not rendered by default. Learn more about customizing how changed files appear on GitHub.

‎src/2-algorithms/1-sort/1-bubble-sort/bubble-sort.test.ts‎

Lines changed: 44 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -2,10 +2,52 @@ import { describe, expect, it } from 'vitest'
22
import { bubbleSort } from './bubble-sort'
33

44
describe('bubbleSort', () => {
5-
it('should sort an array of numbers', () => {
5+
// 测试普通数组排序
6+
it('应该能正确排序普通数字数组', () => {
67
const nums = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
78
const sortedNums = bubbleSort(nums)
8-
99
expect(sortedNums).toEqual([1, 1, 2, 3, 3, 4, 5, 5, 5, 6, 9])
1010
})
11+
12+
// 测试空数组
13+
it('应该能处理空数组', () => {
14+
const nums: number[] = []
15+
const sortedNums = bubbleSort(nums)
16+
expect(sortedNums).toEqual([])
17+
})
18+
19+
// 测试只有一个元素的数组
20+
it('应该能处理只有一个元素的数组', () => {
21+
const nums = [1]
22+
const sortedNums = bubbleSort(nums)
23+
expect(sortedNums).toEqual([1])
24+
})
25+
26+
// 测试已经排序的数组
27+
it('应该能处理已经排序的数组', () => {
28+
const nums = [1, 2, 3, 4, 5]
29+
const sortedNums = bubbleSort(nums)
30+
expect(sortedNums).toEqual([1, 2, 3, 4, 5])
31+
})
32+
33+
// 测试逆序数组
34+
it('应该能处理逆序数组', () => {
35+
const nums = [5, 4, 3, 2, 1]
36+
const sortedNums = bubbleSort(nums)
37+
expect(sortedNums).toEqual([1, 2, 3, 4, 5])
38+
})
39+
40+
// 测试有重复元素的数组
41+
it('应该能处理有重复元素的数组', () => {
42+
const nums = [3, 3, 3, 1, 1, 2]
43+
const sortedNums = bubbleSort(nums)
44+
expect(sortedNums).toEqual([1, 1, 2, 3, 3, 3])
45+
})
46+
47+
// 测试负数数组
48+
it('应该能处理包含负数的数组', () => {
49+
const nums = [-3, 5, -7, 2, 0, -1, 8]
50+
const sortedNums = bubbleSort(nums)
51+
expect(sortedNums).toEqual([-7, -3, -1, 0, 2, 5, 8])
52+
})
1153
})

‎src/2-algorithms/1-sort/1-bubble-sort/bubble-sort.ts‎

Lines changed: 19 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -1,21 +1,35 @@
11
/**
2-
* Bubble Sort
2+
* 冒泡排序
33
*
4-
* O(n^2)
5-
* stable
4+
* 时间复杂度: O(n^2)
5+
* 特点: 稳定排序
66
*
7-
* @param nums
8-
* @returns sorted nums
7+
* @param nums 待排序的数字数组
8+
* @returns 排序后的数组
99
*/
1010
export function bubbleSort(nums: number[]) {
1111
const len = nums.length
1212

13+
// 外层循环：需要进行 len 轮比较
1314
for (let i = 0; i < len; i++) {
15+
// 优化标志：记录本轮是否发生交换
16+
let swapped = false
17+
18+
// 内层循环：每轮比较相邻的元素
19+
// len-i-1：每轮循环后，最后i个元素已经排好序，不需要再比较
1420
for (let j = 0; j < len - i - 1; j++) {
21+
// 如果前一个元素大于后一个元素，交换它们的位置
1522
if (nums[j] > nums[j + 1]) {
23+
// 使用解构赋值进行交换
1624
[nums[j], nums[j + 1]] = [nums[j + 1], nums[j]]
25+
swapped = true // 标记发生了交换
1726
}
1827
}
28+
29+
// 如果本轮没有发生交换，说明数组已经有序，可以提前退出
30+
if (!swapped) {
31+
break
32+
}
1933
}
2034

2135
return nums

‎src/2-algorithms/1-sort/10-radix-sort/radix-sort.test.ts‎

Lines changed: 65 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -1,11 +1,71 @@
11
import { describe, expect, it } from 'vitest'
22
import { radixSort } from './radix-sort'
33

4-
describe('radix Sort', () => {
5-
it('should sort an array of numbers', () => {
4+
describe('基数排序测试', () => {
5+
it('应该正确排序普通数组', () => {
66
const nums = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
7-
const expected = [1, 1, 2, 3, 3, 4, 5, 5, 5, 6, 9]
8-
const actual = radixSort(nums)
9-
expect(actual).to.deep.equal(expected)
7+
expect(radixSort(nums)).toEqual([1, 1, 2, 3, 3, 4, 5, 5, 5, 6, 9])
8+
})
9+
10+
it('应该处理空数组', () => {
11+
expect(radixSort([])).toEqual([])
12+
})
13+
14+
it('应该处理单个元素的数组', () => {
15+
expect(radixSort([42])).toEqual([42])
16+
})
17+
18+
it('应该处理只包含0的数组', () => {
19+
expect(radixSort([0, 0, 0])).toEqual([0, 0, 0])
20+
})
21+
22+
it('应该处理包含多位数的数组', () => {
23+
const nums = [170, 45, 75, 90, 802, 24, 2, 66]
24+
expect(radixSort(nums)).toEqual([2, 24, 45, 66, 75, 90, 170, 802])
25+
})
26+
27+
it('应该处理重复元素', () => {
28+
const nums = [123, 123, 123, 456, 456, 789]
29+
expect(radixSort(nums)).toEqual([123, 123, 123, 456, 456, 789])
30+
})
31+
32+
it('应该处理已排序的数组', () => {
33+
const nums = [1, 2, 3, 4, 5, 6]
34+
expect(radixSort(nums)).toEqual([1, 2, 3, 4, 5, 6])
35+
})
36+
37+
it('应该处理逆序的数组', () => {
38+
const nums = [6, 5, 4, 3, 2, 1]
39+
expect(radixSort(nums)).toEqual([1, 2, 3, 4, 5, 6])
40+
})
41+
42+
it('应该处理大数据量的数组', () => {
43+
const nums = Array.from({ length: 1000 }, () =>
44+
Math.floor(Math.random() * 10000))
45+
const sorted = radixSort([...nums])
46+
const expected = [...nums].sort((a, b) => a - b)
47+
expect(sorted).toEqual(expected)
48+
})
49+
50+
it('应该保持排序稳定性', () => {
51+
const nums = [111, 211, 121, 11, 21, 11]
52+
const sorted = radixSort(nums)
53+
// 确保两个11的相对位置保持不变
54+
expect(sorted).toEqual([11, 11, 21, 111, 121, 211])
55+
})
56+
57+
it('应该正确处理不同位数的数字', () => {
58+
const nums = [1, 10, 100, 1000, 10000]
59+
expect(radixSort(nums)).toEqual([1, 10, 100, 1000, 10000])
60+
})
61+
62+
it('应该抛出错误当输入包含负数时', () => {
63+
const nums = [-1, 2, 3, 4, 5]
64+
expect(() => radixSort(nums)).toThrow('基数排序不支持负数')
65+
})
66+
67+
it('应该处理较大的数值范围', () => {
68+
const nums = [999999, 1, 45678, 12, 999, 12345]
69+
expect(radixSort(nums)).toEqual([1, 12, 999, 12345, 45678, 999999])
1070
})
1171
})

‎src/2-algorithms/1-sort/10-radix-sort/radix-sort.ts‎

Lines changed: 57 additions & 18 deletions
Original file line numberDiff line numberDiff line change
@@ -1,27 +1,66 @@
11
/**
2-
* Radix Sort
3-
*
4-
* O(n * k)
5-
* Stable
6-
*
7-
* @param nums
8-
* @returns nums
9-
*
2+
* Radix Sort 基数排序
3+
* 时间复杂度: O(n * k)，其中 k 是最大数字的位数
4+
* 空间复杂度: O(n + k)
5+
* 稳定性: 稳定
106
*/
117
export function radixSort(nums: number[]): number[] {
12-
const max = Math.max(...nums)
13-
const digits = Math.floor(Math.log10(max)) + 1
8+
// 处理边界情况
9+
if (nums.length <= 1)
10+
return nums
11+
if (nums.some(num => num < 0)) {
12+
throw new Error('基数排序不支持负数')
13+
}
14+
15+
// 获取最大值和位数
16+
const maxNum = findMax(nums)
17+
const maxDigits = getDigitCount(maxNum)
18+
19+
// 按照每一位进行排序
20+
let result = [...nums]
21+
for (let digit = 0; digit < maxDigits; digit++) {
22+
result = sortByDigit(result, digit)
23+
}
24+
25+
return result
26+
}
1427

15-
for (let i = 0; i < digits; i++) {
16-
const buckets: number[][] = Array.from({ length: 10 }, () => [])
28+
/**
29+
* 找出数组中的最大值
30+
*/
31+
function findMax(nums: number[]): number {
32+
return Math.max(...nums)
33+
}
1734

18-
for (let j = 0; j < nums.length; j++) {
19-
const digit = Math.floor((nums[j] / 10 ** i) % 10)
20-
buckets[digit].push(nums[j])
21-
}
35+
/**
36+
* 获取数字的位数
37+
*/
38+
function getDigitCount(num: number): number {
39+
if (num === 0)
40+
return 1
41+
return Math.floor(Math.log10(num)) + 1
42+
}
43+
44+
/**
45+
* 获取数字在指定位置上的数字（从右往左，个位是0）
46+
*/
47+
function getDigit(num: number, position: number): number {
48+
return Math.floor(num / 10 ** position) % 10
49+
}
50+
51+
/**
52+
* 按照指定位置的数字对数组进行排序
53+
*/
54+
function sortByDigit(nums: number[], position: number): number[] {
55+
// 创建10个桶（0-9）
56+
const buckets: number[][] = Array.from({ length: 10 }, () => [])
2257

23-
nums = buckets.flat()
58+
// 将数字分配到对应的桶中
59+
for (const num of nums) {
60+
const digit = getDigit(num, position)
61+
buckets[digit].push(num)
2462
}
2563

26-
return nums
64+
// 合并所有桶中的数字
65+
return buckets.flat()
2766
}

‎src/2-algorithms/1-sort/2-selection-sort/selection-sort.test.ts‎

Lines changed: 65 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -2,10 +2,73 @@ import { describe, expect, it } from 'vitest'
22
import { selectionSort } from './selection-sort'
33

44
describe('selectionSort', () => {
5-
it('should sort an array of numbers', () => {
5+
// 测试基本排序功能
6+
it('应该能正确排序普通数字数组', () => {
67
const nums = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
78
const sortedNums = selectionSort(nums)
8-
99
expect(sortedNums).toEqual([1, 1, 2, 3, 3, 4, 5, 5, 5, 6, 9])
1010
})
11+
12+
// 测试空数组
13+
it('应该能处理空数组', () => {
14+
const nums: number[] = []
15+
const sortedNums = selectionSort(nums)
16+
expect(sortedNums).toEqual([])
17+
})
18+
19+
// 测试单元素数组
20+
it('应该能处理只有一个元素的数组', () => {
21+
const nums = [42]
22+
const sortedNums = selectionSort(nums)
23+
expect(sortedNums).toEqual([42])
24+
})
25+
26+
// 测试两个元素的数组
27+
it('应该能处理两个元素的数组', () => {
28+
const nums = [2, 1]
29+
const sortedNums = selectionSort(nums)
30+
expect(sortedNums).toEqual([1, 2])
31+
})
32+
33+
// 测试已排序数组
34+
it('应该能处理已经排序的数组', () => {
35+
const nums = [1, 2, 3, 4, 5]
36+
const sortedNums = selectionSort(nums)
37+
expect(sortedNums).toEqual([1, 2, 3, 4, 5])
38+
})
39+
40+
// 测试逆序数组
41+
it('应该能处理逆序数组', () => {
42+
const nums = [5, 4, 3, 2, 1]
43+
const sortedNums = selectionSort(nums)
44+
expect(sortedNums).toEqual([1, 2, 3, 4, 5])
45+
})
46+
47+
// 测试全部元素相同的数组
48+
it('应该能处理所有元素都相同的数组', () => {
49+
const nums = [1, 1, 1, 1, 1]
50+
const sortedNums = selectionSort(nums)
51+
expect(sortedNums).toEqual([1, 1, 1, 1, 1])
52+
})
53+
54+
// 测试包含负数的数组
55+
it('应该能处理包含负数的数组', () => {
56+
const nums = [-3, 5, -7, 2, 0, -1, 8]
57+
const sortedNums = selectionSort(nums)
58+
expect(sortedNums).toEqual([-7, -3, -1, 0, 2, 5, 8])
59+
})
60+
61+
// 测试包含重复元素的数组
62+
it('应该能处理包含重复元素的数组', () => {
63+
const nums = [3, 3, 3, 1, 1, 2]
64+
const sortedNums = selectionSort(nums)
65+
expect(sortedNums).toEqual([1, 1, 2, 3, 3, 3])
66+
})
67+
68+
// 测试较大规模的数组
69+
it('应该能处理较大规模的数组', () => {
70+
const nums = Array.from({ length: 1000 }, () => Math.floor(Math.random() * 1000))
71+
const sortedNums = selectionSort([...nums])
72+
expect(sortedNums).toEqual([...nums].sort((a, b) => a - b))
73+
})
1174
})

0 commit comments

Comments
 (0)