Skip to content

Commit 19ef0e8

Browse files
author
hojas
committed
sort
1 parent 05d6041 commit 19ef0e8

File tree

17 files changed

+407
-96
lines changed

17 files changed

+407
-96
lines changed

‎README.md

Lines changed: 6 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -14,6 +14,12 @@
1414
1. [Bubble Sort](https://github.com/hojas/typescript-algorithms/tree/main/src/2-algorithms/1-sort/1-bubble-sort)
1515
2. [Selection Sort](https://github.com/hojas/typescript-algorithms/tree/main/src/2-algorithms/1-sort/2-selection-sort)
1616
3. [Insertion Sort](https://github.com/hojas/typescript-algorithms/tree/main/src/2-algorithms/1-sort/3-insertion-sort)
17+
4. [Shell Sort](https://github.com/hojas/typescript-algorithms/tree/main/src/2-algorithms/1-sort/4-shell-sort)
18+
5. [Merge Sort](https://github.com/hojas/typescript-algorithms/tree/main/src/2-algorithms/1-sort/5-merge-sort)
19+
6. [Quick Sort](https://github.com/hojas/typescript-algorithms/tree/main/src/2-algorithms/1-sort/6-quick-sort)
20+
7. [Heap Sort](https://github.com/hojas/typescript-algorithms/tree/main/src/2-algorithms/1-sort/7-heap-sort)
21+
8. [Counting Sort](https://github.com/hojas/typescript-algorithms/tree/main/src/2-algorithms/1-sort/8-counting-sort)
22+
9. [Bucket Sort](https://github.com/hojas/typescript-algorithms/tree/main/src/2-algorithms/1-sort/9-bucket-sort)
1723

1824
### Search
1925

‎package.json

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -3,7 +3,7 @@
33
"type": "module",
44
"version": "1.0.0",
55
"private": true,
6-
"packageManager": "pnpm@9.3.0",
6+
"packageManager": "pnpm@9.4.0",
77
"license": "MIT",
88
"scripts": {
99
"lint": "eslint .",
@@ -12,7 +12,7 @@
1212
"devDependencies": {
1313
"@antfu/eslint-config": "^2.21.1",
1414
"eslint": "^9.5.0",
15-
"typescript": "^5.4.5",
15+
"typescript": "^5.5.2",
1616
"vite": "^5.3.1",
1717
"vitest": "^1.6.0"
1818
}

‎pnpm-lock.yaml

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

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

Whitespace-only changes.

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

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -2,7 +2,7 @@
22
* Selection Sort
33
*
44
* O(n^2)
5-
* Stable
5+
* Unstable
66
*
77
* @param nums
88
* @returns sorted nums

‎src/2-algorithms/1-sort/4-shell-sort/shell-sort.test.ts

Lines changed: 11 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,11 @@
1+
import { describe, expect, it } from 'vitest'
2+
import { shellSort } from './shell-sort'
3+
4+
describe('shell Sort', () => {
5+
it('should sort an array of numbers', () => {
6+
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 = shellSort(nums)
9+
expect(actual).toEqual(expected)
10+
})
11+
})

‎src/2-algorithms/1-sort/4-shell-sort/shell-sort.ts

Lines changed: 32 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,32 @@
1+
/**
2+
* Shell Sort
3+
*
4+
* O(nlogn)
5+
* Unstable
6+
*
7+
* @param nums
8+
* @returns nums
9+
*/
10+
export function shellSort(nums: number[]) {
11+
const len = nums.length
12+
let temp
13+
let gap = 1
14+
15+
while (gap < len / 3) { // 动态定义间隔序列
16+
gap = gap * 3 + 1
17+
}
18+
19+
for (; gap > 0; gap = Math.floor(gap / 3)) {
20+
for (let i = gap; i < len; i++) {
21+
temp = nums[i]
22+
23+
let j
24+
for (j = i - gap; j >= 0 && nums[j] > temp; j -= gap) {
25+
nums[j + gap] = nums[j]
26+
}
27+
nums[j + gap] = temp
28+
}
29+
}
30+
31+
return nums
32+
}

‎src/2-algorithms/1-sort/5-merge-sort/merge-sort.test.ts

Lines changed: 10 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,10 @@
1+
import { describe, expect, it } from 'vitest'
2+
import { mergeSort } from './merge-sort'
3+
4+
describe('mergeSort', () => {
5+
it('should sort an array of numbers', () => {
6+
const nums = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
7+
const sorted = mergeSort(nums)
8+
expect(sorted).toEqual([1, 1, 2, 3, 3, 4, 5, 5, 5, 6, 9])
9+
})
10+
})

‎src/2-algorithms/1-sort/5-merge-sort/merge-sort.ts

Lines changed: 44 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,44 @@
1+
/**
2+
* Merge Sort
3+
*
4+
* O(nlogn)
5+
* Stable
6+
*
7+
* @param nums
8+
*/
9+
export function mergeSort(nums: number[]): number[] {
10+
const len = nums.length
11+
12+
if (len <= 1) {
13+
return nums
14+
}
15+
16+
const mid = len >> 1
17+
const left = nums.slice(0, mid)
18+
const right = nums.slice(mid)
19+
20+
return merge(mergeSort(left), mergeSort(right))
21+
}
22+
23+
function merge(left: number[], right: number[]): number[] {
24+
const result: number[] = []
25+
26+
while (left.length && right.length) {
27+
if (left[0] < right[0]) {
28+
result.push(left.shift() as number)
29+
}
30+
else {
31+
result.push(right.shift() as number)
32+
}
33+
}
34+
35+
while (left.length) {
36+
result.push(left.shift() as number)
37+
}
38+
39+
while (right.length) {
40+
result.push(right.shift() as number)
41+
}
42+
43+
return result
44+
}

‎src/2-algorithms/1-sort/6-quick-sort/quick-sort.test.ts

Lines changed: 10 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,10 @@
1+
import { describe, expect, it } from 'vitest'
2+
import { quickSort } from './quick-sort'
3+
4+
describe('quickSort', () => {
5+
it('should sort an array of numbers', () => {
6+
const nums = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
7+
const sortedNums = quickSort(nums)
8+
expect(sortedNums).toEqual([1, 1, 2, 3, 3, 4, 5, 5, 5, 6, 9])
9+
})
10+
})

‎src/2-algorithms/1-sort/6-quick-sort/quick-sort.ts

Lines changed: 30 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,30 @@
1+
/**
2+
* Quick Sort
3+
*
4+
* O(nlogn)
5+
* Unstable
6+
*
7+
* @param nums
8+
*/
9+
export function quickSort(nums: number[]): number[] {
10+
const len = nums.length
11+
12+
if (len <= 1) {
13+
return nums
14+
}
15+
16+
const pivot = nums[0]
17+
const left = []
18+
const right = []
19+
20+
for (let i = 1; i < len; i++) {
21+
if (nums[i] < pivot) {
22+
left.push(nums[i])
23+
}
24+
else {
25+
right.push(nums[i])
26+
}
27+
}
28+
29+
return [...quickSort(left), pivot, ...quickSort(right)]
30+
}

‎src/2-algorithms/1-sort/7-heap-sort/heap-sort.test.ts

Lines changed: 11 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,11 @@
1+
import { describe, expect, it } from 'vitest'
2+
import { heapSort } from './heap-sort'
3+
4+
describe('heap Sort', () => {
5+
it('should sort an array of numbers', () => {
6+
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 = heapSort(nums)
9+
expect(actual).toEqual(expected)
10+
})
11+
})

‎src/2-algorithms/1-sort/7-heap-sort/heap-sort.ts

Lines changed: 51 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,51 @@
1+
/**
2+
* Heap Sort
3+
*
4+
* O(nlogn)
5+
* Unstable
6+
*
7+
* @param nums
8+
*/
9+
export function heapSort(nums: number[]): number[] {
10+
const n = nums.length
11+
12+
// Build max heap
13+
for (let i = (n >> 1) - 1; i >= 0; i--) {
14+
heapify(nums, n, i)
15+
}
16+
17+
// Extract elements from heap one by one
18+
for (let i = n - 1; i >= 0; i--) {
19+
// Move current root to end
20+
[nums[0], nums[i]] = [nums[i], nums[0]]
21+
22+
// call max heapify on the reduced heap
23+
heapify(nums, i, 0)
24+
}
25+
26+
return nums
27+
}
28+
29+
function heapify(nums: number[], n: number, i: number) {
30+
let largest = i // Initialize largest as root
31+
const left = 2 * i + 1 // left = 2*i + 1
32+
const right = 2 * i + 2 // right = 2*i + 2
33+
34+
// If left child is larger than root
35+
if (left < n && nums[left] > nums[largest]) {
36+
largest = left
37+
}
38+
39+
// If right child is larger than largest so far
40+
if (right < n && nums[right] > nums[largest]) {
41+
largest = right
42+
}
43+
44+
// If largest is not root
45+
if (largest !== i) {
46+
[nums[i], nums[largest]] = [nums[largest], nums[i]] // swap
47+
48+
// Recursively heapify the affected sub-tree
49+
heapify(nums, n, largest)
50+
}
51+
}

‎src/2-algorithms/1-sort/8-counting-sort/counting-sort.test.ts

Lines changed: 11 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,11 @@
1+
import { describe, expect, it } from 'vitest'
2+
import { countingSort } from './counting-sort'
3+
4+
describe('counting Sort', () => {
5+
it('should sort an array of numbers', () => {
6+
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 = countingSort(nums)
9+
expect(actual).toEqual(expected)
10+
})
11+
})

‎src/2-algorithms/1-sort/8-counting-sort/counting-sort.ts

Lines changed: 28 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,28 @@
1+
/**
2+
* Counting Sort
3+
*
4+
* O(n+k)
5+
* Stable
6+
*
7+
* @param nums
8+
*/
9+
export function countingSort(nums: number[]): number[] {
10+
const max = Math.max(...nums)
11+
const counts: number[] = Array(max + 1).fill(0)
12+
const result: number[] = []
13+
14+
for (let i = 0; i < nums.length; i++) {
15+
counts[nums[i]]++
16+
}
17+
18+
for (let i = 1; i < counts.length; i++) {
19+
counts[i] += counts[i - 1]
20+
}
21+
22+
for (let i = nums.length - 1; i >= 0; i--) {
23+
result[counts[nums[i]] - 1] = nums[i]
24+
counts[nums[i]]--
25+
}
26+
27+
return result
28+
}

‎src/2-algorithms/1-sort/9-bucket-sort/bucket-sort.test.ts

Lines changed: 10 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,10 @@
1+
import { describe, expect, it } from 'vitest'
2+
import { bucketSort } from './bucket-sort'
3+
4+
describe('bucket Sort', () => {
5+
it('should sort array', () => {
6+
const nums = [19, 27, 35, 43, 31, 22, 54, 66, 78]
7+
const sorted = bucketSort(nums)
8+
expect(sorted).to.deep.equal([19, 22, 27, 31, 35, 43, 54, 66, 78])
9+
})
10+
})

‎src/2-algorithms/1-sort/9-bucket-sort/bucket-sort.ts

Lines changed: 57 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,57 @@
1+
/**
2+
* Bucket Sort
3+
* 桶排序
4+
*
5+
* O(n+k)
6+
* Stable
7+
*
8+
*
9+
* @param nums
10+
*/
11+
export function bucketSort(nums: number[]): number[] {
12+
const len = nums.length
13+
14+
if (len <= 1) {
15+
return nums
16+
}
17+
18+
let minValue = nums[0]
19+
let maxValue = nums[0]
20+
for (let i = 1; i < len; i++) {
21+
minValue = Math.min(minValue, nums[i])
22+
maxValue = Math.max(maxValue, nums[i])
23+
}
24+
25+
// Create buckets
26+
// 创建桶
27+
const bucketSize = Math.floor((maxValue - minValue) / len) + 1
28+
const bucketCount = Math.floor((maxValue - minValue) / bucketSize) + 1
29+
const buckets = Array(bucketCount)
30+
for (let i = 0; i < buckets.length; i++) {
31+
buckets[i] = []
32+
}
33+
34+
// Divide the range of input values into k equal-sized buckets
35+
// 将数组元素分配到各个桶中
36+
for (let i = 0; i < len; i++) {
37+
const index = Math.floor((nums[i] - minValue) / bucketSize)
38+
buckets[index].push(nums[i])
39+
}
40+
41+
// Sort each bucket using any sorting algorithm
42+
// 对各个桶执行排序
43+
for (const bucket of buckets) {
44+
bucket.sort((a: number, b: number) => a - b)
45+
}
46+
47+
// Merge the sorted buckets into a single array
48+
// 遍历桶合并结果
49+
let i = 0
50+
for (const bucket of buckets) {
51+
for (const n of bucket) {
52+
nums[i++] = n
53+
}
54+
}
55+
56+
return nums
57+
}

0 commit comments

Comments
 (0)