Basic Algorithms Tutorials

Relevant source files

• .clang-format
• README.md
• README_EN.md
• basic/README.md
• basic/README_EN.md
• basic/searching/BinarySearch/README.md
• basic/searching/BinarySearch/README_EN.md
• basic/sorting/BubbleSort/BubbleSort.cpp
• basic/sorting/BubbleSort/BubbleSort.java
• basic/sorting/BubbleSort/BubbleSort.js
• basic/sorting/BubbleSort/BubbleSort.rs
• basic/sorting/BubbleSort/README.md
• basic/sorting/CountingSort/CountingSort.go
• basic/sorting/CountingSort/CountingSort.java
• basic/sorting/CountingSort/README.md
• basic/sorting/HeapSort/Main.go
• basic/sorting/HeapSort/Main.rs
• basic/sorting/HeapSort/README.md
• basic/sorting/InsertionSort/InsertionSort.cpp
• basic/sorting/InsertionSort/InsertionSort.cs
• basic/sorting/InsertionSort/InsertionSort.java
• basic/sorting/InsertionSort/InsertionSort.js
• basic/sorting/InsertionSort/InsertionSort.rs
• basic/sorting/InsertionSort/README.md
• basic/sorting/MergeSort/Main.cpp
• basic/sorting/MergeSort/Main.java
• basic/sorting/MergeSort/Main.rs
• basic/sorting/MergeSort/README.md
• basic/sorting/QuickSort/Main.rs
• basic/sorting/QuickSort/README.md
• basic/sorting/SelectionSort/README.md
• basic/sorting/SelectionSort/SelectionSort.cpp
• basic/sorting/SelectionSort/SelectionSort.cs
• basic/sorting/SelectionSort/SelectionSort.js
• basic/sorting/ShellSort/README.md
• basic/sorting/ShellSort/ShellSort.java
• basic/sorting/ShellSort/ShellSort.js
• basic/summary.md
• lcci/17.18.Shortest Supersequence/Solution.cpp
• lcci/17.18.Shortest Supersequence/Solution.go
• lcci/17.18.Shortest Supersequence/Solution.java
• lcci/17.18.Shortest Supersequence/Solution.py
• lcci/17.18.Shortest Supersequence/Solution.ts
• solution/3000-3099/3016.Minimum Number of Pushes to Type Word II/images/keypadv2.png

Purpose and Scope

The basic/ directory contains standalone educational implementations of fundamental algorithms, independent from LeetCode problem solutions. Each algorithm has its own subdirectory under basic/sorting/ or basic/searching/ with:

• README.md - Algorithm explanation with complexity analysis
• Multi-language implementations (.java, .cpp, .py, .go, .rs, .js, .cs)

Sorting Algorithms (basic/sorting/):

Algorithm	Directory	Key Function Names
Bubble Sort	BubbleSort/	bubbleSort(), uses hasChange flag
Insertion Sort	InsertionSort/	insertionSort(), insertsort()
Selection Sort	SelectionSort/	selectionSort(), selectsort()
Shell Sort	ShellSort/	shellSort(), gap sequence n/2
Merge Sort	MergeSort/	mergeSort(), merge_sort(), uses tmp[]
Quick Sort	QuickSort/	quickSort(), quick_sort(), two-pointer partition
Heap Sort	HeapSort/	down(), up(), uses 1-indexed h[] array
Counting Sort	CountingSort/	countingSort(), uses c[] frequency array

Searching Algorithms (basic/searching/):

Algorithm	Directory	Templates
Binary Search	BinarySearch/	Template 1: right = mid, Template 2: left = mid

Sources: basic/README.md1-16 basic/README_EN.md1-16 basic/summary.md1-13

<old_str>

Bubble Sort Implementation

Algorithm: Compares adjacent elements and swaps if out of order. Uses hasChange flag to detect when array is sorted.

Code Entity Mapping:

Implementation Files:

Language	File	Function Signature
Java	basic/sorting/BubbleSort/BubbleSort.java5-16	private static void bubbleSort(int[] nums)
Python	basic/sorting/BubbleSort/README.md25-34	def bubbleSort(arr)
C++	basic/sorting/BubbleSort/BubbleSort.cpp6-18	void bubbleSort(vector<int>& arr)
Go	basic/sorting/BubbleSort/README.md113-124	func bubbleSort(nums []int)
Rust	basic/sorting/BubbleSort/BubbleSort.rs1-12	fn bubble_sort(nums: &mut Vec<i32>)
JavaScript	basic/sorting/BubbleSort/BubbleSort.js1-17	function bubbleSort(inputArr)

Core Algorithm Pattern:

Sources: basic/sorting/BubbleSort/README.md1-234 basic/sorting/BubbleSort/BubbleSort.java1-30 basic/sorting/BubbleSort/BubbleSort.cpp1-26 </old_str> <new_str>

Purpose and Scope

The basic/ directory contains standalone educational implementations of fundamental algorithms, independent from LeetCode problem solutions. Each algorithm has its own subdirectory under basic/sorting/ or basic/searching/ with:

• README.md - Algorithm explanation with complexity analysis
• Multi-language implementations (.java, .cpp, .py, .go, .rs, .js, .cs)

Sorting Algorithms (basic/sorting/):

Algorithm	Directory	Key Function Names
Bubble Sort	BubbleSort/	bubbleSort(), uses hasChange flag
Insertion Sort	InsertionSort/	insertionSort(), insertsort()
Selection Sort	SelectionSort/	selectionSort(), selectsort()
Shell Sort	ShellSort/	shellSort(), gap sequence n/2
Merge Sort	MergeSort/	mergeSort(), merge_sort(), uses tmp[]
Quick Sort	QuickSort/	quickSort(), quick_sort(), two-pointer partition
Heap Sort	HeapSort/	down(), up(), uses 1-indexed h[] array
Counting Sort	CountingSort/	countingSort(), uses c[] frequency array

Searching Algorithms (basic/searching/):

Algorithm	Directory	Templates
Binary Search	BinarySearch/	Template 1: right = mid, Template 2: left = mid

Sources: basic/README.md1-16 basic/README_EN.md1-16 basic/summary.md1-13

---

Directory Structure and Organization

The basic/ directory follows a hierarchical organization where each algorithm has its own subdirectory with implementations in multiple languages:

Each algorithm subdirectory typically contains:

• README.md - Algorithm explanation with Chinese documentation
• Multiple implementation files: .java, .cpp, .py, .go, .rs, .js, .cs

Sources: basic/README.md1-32 basic/summary.md1-13

---

Sorting Algorithms

Overview and Characteristics

The repository implements 8 fundamental sorting algorithms in basic/sorting/ Each algorithm directory contains a README.md with explanations and implementation files in multiple languages.

Algorithm-to-Code Mapping:

Algorithm	Best Case	Average Case	Worst Case	Space	Stable	Notes
Bubble	O(n)	O(n²)	O(n²)	O(1)	Yes	Optimized with hasChange flag
Insertion	O(n)	O(n²)	O(n²)	O(1)	Yes	Good for nearly-sorted data
Selection	O(n²)	O(n²)	O(n²)	O(1)	No	Always scans remaining array
Shell	O(n log n)	O(n log² n)	O(n²)	O(1)	No	Gap sequence variant
Merge	O(n log n)	O(n log n)	O(n log n)	O(n)	Yes	Divide-and-conquer
Quick	O(n log n)	O(n log n)	O(n²)	O(log n)	No	Partition-based
Heap	O(n log n)	O(n log n)	O(n log n)	O(1)	No	Uses heap structure
Counting	O(n+k)	O(n+k)	O(n+k)	O(n+k)	Yes	For integer ranges

Sources: basic/sorting/BubbleSort/README.md1-234 basic/sorting/InsertionSort/README.md1-214 basic/sorting/SelectionSort/README.md1-216 basic/sorting/MergeSort/README.md1-374 basic/sorting/QuickSort/README.md1-331 basic/sorting/HeapSort/README.md1-501 basic/sorting/CountingSort/README.md1-17

---

Insertion Sort Implementation

Algorithm: Maintains sorted region at beginning, inserts each new element into correct position by shifting larger elements right.

Code Entity Mapping:

Implementation Comparison:

Language	File	Key Code Pattern
Java	basic/sorting/InsertionSort/InsertionSort.java6-12	for (j = i-1; j >= 0 && nums[j] > num; --j) nums[j+1] = nums[j]
C++	basic/sorting/InsertionSort/InsertionSort.cpp16-23	for (; j >= 0 && vec[j] > num; j--) vec[j+1] = vec[j]
Python	basic/sorting/InsertionSort/README.md24-32	while array[cur_index-1] > array[cur_index]: swap
Go	basic/sorting/InsertionSort/README.md113-119	for ; j >= 0 && nums[j] > num; j--
Rust	basic/sorting/InsertionSort/InsertionSort.rs4-11	while j >= (0 as usize) && nums[j] > temp

Sources: basic/sorting/InsertionSort/README.md1-214 basic/sorting/InsertionSort/InsertionSort.java1-21 basic/sorting/InsertionSort/InsertionSort.cpp1-37

---

Merge Sort Implementation

Algorithm: Divide-and-conquer with O(n log n) guaranteed complexity. Recursively splits array, sorts halves, then merges.

Code Entity Mapping:

Implementation Files:

Language	File	Function Signature	tmp Array
Java	basic/sorting/MergeSort/Main.java19-42	public static void mergeSort(int[] nums, int left, int right)	static int[] tmp = new int[100010]
C++	basic/sorting/MergeSort/Main.cpp11-26	void merge_sort(int nums[], int left, int right)	int tmp[N] global array
Python	basic/sorting/MergeSort/README.md83-108	def merge_sort(nums, left, right)	tmp = [] local list
Go	basic/sorting/MergeSort/README.md210-238	func mergeSort(nums []int, left, right int)	tmp := make([]int, 0)
Rust	basic/sorting/MergeSort/Main.rs3-37	fn merge_sort(nums: &mut Vec<i32>, left: usize, right: usize)	let mut temp = Vec::new()

Core Merge Logic (Java):

Sources: basic/sorting/MergeSort/README.md1-374 basic/sorting/MergeSort/Main.java1-44 basic/sorting/MergeSort/Main.cpp1-34

---

Selection Sort Implementation

Algorithm Description: Finds the minimum element in the unsorted portion and places it at the end of the sorted portion. Always performs O(n²) comparisons regardless of input.

Comparison with Insertion Sort:

• Insertion Sort: Sorted region grows at the beginning, elements shift right
• Selection Sort: Sorted region grows at the beginning, minimum is swapped into position

Sources: basic/sorting/SelectionSort/README.md1-216

---

Shell Sort Implementation

Algorithm Description: An optimized variant of insertion sort that allows elements to move large distances. Uses a gap sequence (typically n/2, n/4, ..., 1) to perform gapped insertion sorts.

Gap Sequence Strategy:

By the time gap reaches 1, the array is already partially sorted, making the final insertion sort very efficient.

Sources: basic/sorting/ShellSort/README.md1-125

---

Quick Sort Implementation

Algorithm: Partition-based divide-and-conquer. Two-pointer partitioning around pivot, then recursive sorting of partitions.

Code Entity Mapping:

Implementation Files:

Language	File	Pivot Selection	Partition Pattern
Java	basic/sorting/QuickSort/README.md119-138	nums[(left + right) >> 1]	while (nums[++i] < x);
C++	basic/sorting/QuickSort/README.md154-166	nums[left + right >> 1]	while (nums[++i] < x);
Python	basic/sorting/QuickSort/README.md76-93	nums[(left + right) >> 1]	while 1: i += 1; if nums[i] >= x: break
Go	basic/sorting/QuickSort/README.md185-209	nums[(left+right)>>1]	for { i++; if nums[i] >= x { break }}
Rust	basic/sorting/QuickSort/Main.rs4-30	Random with rand::thread_rng().gen_range(left, right+1)	while i < j && nums[j] >= pivot { j -= 1 }

Critical Implementation Detail:

Sources: basic/sorting/QuickSort/README.md1-331 basic/sorting/QuickSort/Main.rs1-49

---

Heap Sort Implementation

Algorithm: Builds min-heap from array, extracts minimum repeatedly. Uses 1-indexed array with parent-child index relationships.

Code Entity Mapping:

Implementation Files:

Language	File	Key Functions	Array Type
Java	basic/sorting/HeapSort/README.md139-158	down(int u), up(int u)	static int[] h = new int[100010]
Go	basic/sorting/HeapSort/Main.go12-29	func up(u int), func down(u int)	var h []int = make([]int, N)
Rust	basic/sorting/HeapSort/Main.rs15-34	fn sink(nums: &mut Vec<i32>, mut i: usize, n: usize)	Vec<i32> (0-indexed)

Core down() Function (Java):

Heap Construction:

Extract Minimum:

Sources: basic/sorting/HeapSort/README.md1-501 basic/sorting/HeapSort/Main.go1-51 basic/sorting/HeapSort/Main.rs1-41

---

Heap Sort Implementation

Algorithm Description: Builds a min-heap (or max-heap) from the array, then repeatedly extracts the minimum (or maximum) element to achieve sorted order. Uses the heap property: parent node is smaller (or larger) than its children.

Heap Structure and Operations:

Heap Data Structure and Operations:

The heap is stored in a 1-indexed array h[] with the following index relationships:

Heap Operations Mapping:

Operation	Function	Time Complexity	Use Case
Insert	up(size++)	O(log n)	Add element to heap
Extract Min	swap(1, size--); down(1)	O(log n)	Remove root element
Build Heap	for (i=n/2; i>0; i--) down(i)	O(n)	Initial heap construction

Implementation Files:

• Java: basic/sorting/HeapSort/README.md116-165 - Uses Main class with static h[] and size
• Go: basic/sorting/HeapSort/Main.go1-51 - Package-level h []int and size int
• Rust: basic/sorting/HeapSort/Main.rs1-41 - heap_sort() and sink() functions

Sources: basic/sorting/HeapSort/README.md1-501

---

Counting Sort Implementation

Algorithm Description: Non-comparison based sorting for non-negative integers. Counts occurrences of each value, then reconstructs sorted array. Achieves O(n+k) time complexity where k is the range of values.

Algorithm Steps:

1. Count frequencies: Create array c of size max-min+1, count occurrences
2. Compute prefix sums: Transform c[i] to cumulative count
3. Place elements: Use cumulative counts to place elements in correct positions

Complexity Analysis:

Metric	Complexity	Explanation
Time	O(n+k)	Where n = array length, k = value range (max-min+1)
Space	O(n+k)	Requires count array and result array
Best Case	When k < n	O(n) when value range is small
Worst Case	When k >> n	O(k) dominates when range is large

Use Case: Optimal for sorting integers within a known, limited range. Not suitable for large value ranges or non-integer data.

Sources: basic/sorting/CountingSort/README.md1-17 basic/sorting/CountingSort/CountingSort.java1-39

---

Binary Search Templates

Two-Template Approach

The basic/searching/BinarySearch/ directory provides two reusable binary search templates. The key insight is that binary search's essence is not "monotonicity" but "boundary-finding": any property that divides an interval into two parts enables binary search.

Sources: basic/searching/BinarySearch/README.md1-63

---

Template 1: Finding Left Boundary (right = mid)

Use Case: Find leftmost position where condition becomes true. When check(mid) is true, search left by right = mid.

Template Code:

Template 1 Characteristics:

Variable/Expression	Value/Meaning
mid	(left + right) >> 1 - no +1
check(mid) == true	right = mid (keep mid as candidate)
check(mid) == false	left = mid + 1 (exclude mid)
Loop invariant	Answer in [left, right]
Return	left or right (equal at end)

Example Application:

Used In:

• Problem 34: Find first occurrence of target
• Problem 278: Find first bad version
• Problem 1064: Fixed point (leftmost i where arr[i] == i)

Sources: basic/searching/BinarySearch/README.md10-24 basic/searching/BinarySearch/README_EN.md10-24

---

Template 2: Finding Right Boundary (left = mid)

Use Case: Find rightmost position where condition is true. When check(mid) is true, search right by left = mid.

Template Code:

Template 2 Characteristics:

Variable/Expression	Value/Meaning
mid	(left + right + 1) >> 1 - +1 required
check(mid) == true	left = mid (keep mid as candidate)
check(mid) == false	right = mid - 1 (exclude mid)
Loop invariant	Answer in [left, right]
Why +1?	Prevents infinite loop when left = right - 1

Why +1 is Critical:

When left = right - 1:
  Without +1: mid = (left + right) >> 1 = left
              If check(mid) true: left = mid = left → STUCK
  With +1:    mid = (left + right + 1) >> 1 = right
              Loop can progress

Example Application:

Used In:

• Problem 34: Find last occurrence of target
• Problem 69: Sqrt(x) - find rightmost x where x*x <= target
• Problem 162: Find peak element

Sources: basic/searching/BinarySearch/README.md28-43 basic/searching/BinarySearch/README_EN.md28-43

---

Template Selection Strategy

Template Selection Algorithm:

Template Selection Rules:

Scenario	Template	Reason
Move right = mid	Template 1	No +1 in mid calculation
Move left = mid	Template 2	Requires +1 in mid calculation
Find first occurrence	Template 1	Want leftmost boundary
Find last occurrence	Template 2	Want rightmost boundary

Common Applications:

1. Problem 34. Find First and Last Position: Uses both templates

   • Template 1: Find first occurrence
   • Template 2: Find last occurrence

2. Problem 69. Sqrt(x): Uses Template 2 to find rightmost integer where x*x <= target

3. Problem 278. First Bad Version: Uses Template 1 to find leftmost bad version

Sources: basic/searching/BinarySearch/README.md45-63

---

Multi-Language Implementation Patterns

Language Support Matrix

Each algorithm is implemented in 6-8 programming languages with consistent patterns:

Language	File Extension	Key Language Features Used
Python	.py	List comprehension, tuple unpacking, slicing
Java	.java	Static methods, arrays, Scanner for I/O
C++	.cpp	vector<int>, references, std::swap
Go	.go	Slices, tuple swap, fmt package
Rust	.rs	Mutable references &mut, Result type, iterators
JavaScript	.js	Arrow functions, destructuring, array methods
C#	.cs	ref parameters, static methods, namespaces

Common Implementation Structure:

Sources: basic/sorting/BubbleSort/README.md9-233 basic/sorting/MergeSort/README.md74-373

---

Example: MergeSort Across Languages

Comparison of Core Algorithm:

Language	Function Signature	Memory Management
Python	merge_sort(nums, left, right)	Local tmp list in each call
Java	mergeSort(int[] nums, int left, int right)	Static tmp array reused
C++	void merge_sort(int nums[], int left, int right)	Static tmp[N] array
Go	func mergeSort(nums []int, left, right int)	Local tmp slice
Rust	fn merge_sort(nums: &mut Vec<i32>, left: usize, right: usize)	Local Vec::new()

Key Differences:

1. Python basic/sorting/MergeSort/README.md78-113: Uses list methods, dynamic typing
2. Java basic/sorting/MergeSort/README.md117-162: Class-based, static temporary array
3. C++ basic/sorting/MergeSort/README.md166-201: Raw arrays, manual memory
4. Go basic/sorting/MergeSort/README.md205-255: Slice syntax, fmt.Scanf
5. Rust basic/sorting/MergeSort/README.md259-314: Ownership system, explicit bounds

All implementations follow the same algorithmic logic but adapt to language idioms.

Sources: basic/sorting/MergeSort/README.md72-374

---

Learning Resources and Usage

How to Use These Tutorials

Each algorithm directory provides:

1. README.md: Complete explanation in Chinese with:

   • Algorithm description and intuition
   • Complexity analysis
   • Tabbed code examples in 6+ languages
   • Example inputs/outputs

2. Implementation Files: Standalone, runnable code:

   • Can be compiled/run independently
   • Include test cases in main() functions
   • Follow language-specific conventions

3. Integration with Main Repository:

   • Linked from README.md39-57 "Algorithm Improvement Topics" section
   • Cross-referenced with relevant LeetCode problems
   • Serve as templates for solving similar problems

Study Progression:

Sources: basic/README.md1-32 README.md39-57

---

Related LeetCode Problems

The main README links basic algorithms to specific LeetCode problems for practice:

Binary Search Applications

From README.md43-46:

• Problem 34 - Uses both templates
• Problem 1870 - Binary search on answer
• Problem 1898 - Binary search optimization

Sorting Applications

From README.md46-48:

• Problem 912 - Demonstrates quick sort and merge sort
• Problem 415 - High-precision addition
• Problem 43 - High-precision multiplication

These problems allow learners to apply the basic algorithms in more complex scenarios.

Sources: README.md39-57 basic/searching/BinarySearch/README.md56-63