The basic/ directory provides educational implementations of fundamental algorithms with detailed explanations, complexity analysis, and multi-language code examples. This material serves as foundational learning content, independent from the LeetCode problem solutions found in other directories (for problem solutions, see pages 3, 4).
The tutorials cover classic computer science algorithms organized into two categories:
| Category | Algorithms Covered | Purpose |
|---|---|---|
| Sorting | 8 algorithms (bubble, insertion, selection, shell, merge, quick, heap, counting) | Teach comparison-based and non-comparison sorting techniques |
| Searching | Binary search with 2 templates | Provide reusable patterns for boundary-finding problems |
Sources: basic/README.md1-32 basic/README_EN.md1-32 basic/summary.md1-13
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.java, .cpp, .py, .go, .rs, .js, .csSources: basic/README.md1-32 basic/summary.md1-13
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
Algorithm Description: Iteratively compares adjacent elements and swaps them if out of order. Optimization: uses a hasChange boolean to terminate early when array becomes sorted.
Key Implementation Pattern:
Language-Specific Implementations:
| Language | File | Key Functions |
|---|---|---|
| Python | basic/sorting/BubbleSort/README.md13-40 | bubbleSort(arr) with list swap |
| Java | basic/sorting/BubbleSort/README.md44-74 | bubbleSort(int[]), swap() helper |
| C++ | basic/sorting/BubbleSort/README.md78-104 | bubbleSort(vector<int>&) with std::swap |
| Go | basic/sorting/BubbleSort/README.md108-131 | bubbleSort(nums []int) with tuple swap |
| Rust | basic/sorting/BubbleSort/README.md135-154 | bubble_sort(nums: &mut Vec<i32>) |
| JavaScript | basic/sorting/BubbleSort/README.md158-181 | bubbleSort(inputArr) returns sorted array |
| C# | basic/sorting/BubbleSort/README.md185-231 | BubbleSortNums(int[]) with ref swap |
Sources: basic/sorting/BubbleSort/README.md1-234
Algorithm Description: Maintains a sorted subarray at the beginning, inserting each new element into its correct position. Efficient for nearly-sorted data.
Core Logic:
The insertion sort divides the array into two regions:
nums[0..i-1] (initially just nums[0])nums[i..n-1]For each element in the unsorted region, find its position in the sorted region by shifting larger elements right.
Java Implementation Pattern:
Key Variables:
i: current element being insertednum: value being insertedj: scanning position in sorted regionSources: basic/sorting/InsertionSort/README.md1-214 basic/sorting/InsertionSort/InsertionSort.java1-21
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:
Sources: basic/sorting/SelectionSort/README.md1-216
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
Algorithm Description: Divide-and-conquer algorithm that recursively splits the array in half, sorts each half, then merges them back together. Guaranteed O(n log n) time complexity.
Algorithm Flow Diagram:
Core Algorithm Template:
The mergeSort() function signature varies by language but follows the same pattern:
| Language | Signature | Global State |
|---|---|---|
| Java | void mergeSort(int[] nums, int left, int right) | static int[] tmp |
| C++ | void merge_sort(int nums[], int left, int right) | int tmp[N] |
| Python | def merge_sort(nums, left, right) | Local tmp = [] |
| Go | func mergeSort(nums []int, left, right int) | Local tmp slice |
Key Variables in Implementation:
Critical Variables:
mid: Split point calculated with unsigned right shift >>> to avoid overflowi, j, k: Three pointers for left subarray, right subarray, and temporary arraytmp[]: Auxiliary array for merging (size N in Java/C++, allocated per-call in Python/Go)Sources: basic/sorting/MergeSort/README.md1-374 basic/sorting/MergeSort/Main.java1-44
Algorithm Description: Partition-based divide-and-conquer algorithm. Selects a pivot, partitions array into elements less than and greater than pivot, then recursively sorts partitions.
Core Algorithm Template:
The quickSort() function uses a two-pointer partitioning scheme:
Partitioning Variables:
i: Left pointer, starts at left - 1 to enable pre-incrementj: Right pointer, starts at right + 1 to enable pre-decrementx: Pivot value (typically nums[left] or nums[(left + right) >> 1])nums[left..j] <= x and nums[j+1..right] >= xLanguage Variations:
| Implementation | Pivot Selection |
|---|---|
| basic/sorting/QuickSort/Main.java1-139 | nums[(left + right) >> 1] |
| basic/sorting/QuickSort/Main.cpp1-176 | nums[left + right >> 1] |
| basic/sorting/QuickSort/Main.rs1-49 | Random index with rand::thread_rng() |
Partition Strategy:
Key Insight: Using i = left - 1 and j = right + 1 with pre-increment/decrement ensures correct handling of edge cases and pivot placement.
Sources: basic/sorting/QuickSort/README.md1-331
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:
Main class with static h[] and sizeh []int and size intheap_sort() and sink() functionsSources: basic/sorting/HeapSort/README.md1-501
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:
c of size max-min+1, count occurrencesc[i] to cumulative countComplexity 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
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
Use Case: When the condition holds at mid, search the left half by setting right = mid.
Template Code:
Template Characteristics:
| Aspect | Template 1 Implementation |
|---|---|
| Mid calculation | mid = (left + right) >> 1 |
When check(mid) true | right = mid (keep mid as candidate) |
When check(mid) false | left = mid + 1 (exclude mid) |
| Loop invariant | Answer is in [left, right] |
| Return value | left (equals right when loop exits) |
Concrete Example - Finding First Occurrence:
Application in Repository:
Sources: basic/searching/BinarySearch/README.md7-24
Use Case: When the condition holds at mid, search the right half by setting left = mid.
Template Code:
Template Characteristics:
| Aspect | Template 2 Implementation |
|---|---|
| Mid calculation | mid = (left + right + 1) >> 1 |
When check(mid) true | left = mid (keep mid as candidate) |
When check(mid) false | right = mid - 1 (exclude mid) |
| Loop invariant | Answer is in [left, right] |
| Critical detail | +1 prevents infinite loop when left = right - 1 |
Why +1 is Required:
When left = right - 1:
+1: mid = (left + right) >> 1 = left, then left = mid = left → infinite loop+1: mid = (left + right + 1) >> 1 = right, allowing progressConcrete Example - Finding Last Occurrence:
Application in Repository:
Sources: basic/searching/BinarySearch/README.md26-43
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:
Problem 34. Find First and Last Position: Uses both templates
Problem 69. Sqrt(x): Uses Template 2 to find rightmost integer where x*x <= target
Problem 278. First Bad Version: Uses Template 1 to find leftmost bad version
Sources: basic/searching/BinarySearch/README.md45-63
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
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:
fmt.ScanfAll implementations follow the same algorithmic logic but adapt to language idioms.
Sources: basic/sorting/MergeSort/README.md72-374
Each algorithm directory provides:
README.md: Complete explanation in Chinese with:
Implementation Files: Standalone, runnable code:
main() functionsIntegration with Main Repository:
Study Progression:
Sources: basic/README.md1-32 README.md39-57
The main README links basic algorithms to specific LeetCode problems for practice:
From README.md43-46:
From README.md46-48:
These problems allow learners to apply the basic algorithms in more complex scenarios.
Sources: README.md39-57 basic/searching/BinarySearch/README.md56-63
Refresh this wiki
This wiki was recently refreshed. Please wait 3 days to refresh again.