Data Structure - Sort (Sort) Full Tutor
For examination / final examination, covering all core knowledge of the ranking chapter Points
Contents
1. Basic concepts
1.1 Definition of sorting
Adjusts a sequence of unsequenced records to a sequence by keyword.
1.2 Classification of sorting
| Categorical dimensions | Type |
|---|---|
| Stability | Stable Sorting / Unstable Sorting ** |
| ** Storage medium** | Internal sorting (RAM) / external sorting (ERA) |
| ** Basic operations** | Comparative / Non-comparable (base figure sorting) |
1.3 Stability
Stabilized sorting: The records of the same keyword remain relatively unchanged after sorting.
| ♪ Stable sort of ♪ |-----------|-------------| | Directly insert, bubbles, amalgamation, base figure | Hill, simple selection, speed, pile
Memorials: unstable ** “Shill Clip”**
2. Order of insertion
2.1 Order of direct insertion
** Ideas**: insert sequences to be sorted into sequences.
Similar to playing cards, touch cards, insert cards.
初始： [5] 2 8 1 9第1趟： [2 5] 8 1 9 ← 2 插入到 5 前面第2趟： [2 5 8] 1 9 ← 8 比 5 大，在末尾第3趟： [1 2 5 8] 9 ← 1 插入到最前面第4趟： [1 2 5 8 9] ← 9 比 8 大，在末尾** Algorithmic realization (C language)**
void InsertSort(int a[], int n) { int i, j, temp; for (i = 1; i < n; i++) { if (a[i] < a[i-1]) { // 当前元素比前一个小 temp = a[i]; // 暂存当前元素 for (j = i-1; j >= 0 && a[j] > temp; j--) a[j+1] = a[j]; // 大于 temp 的元素后移 a[j+1] = temp; // 插入到正确位置 } }}** Performance analysis**:
| Indicator Best (Order) Worst (Reverse) Average |------|----------------|----------------|---------| | Number of comparisons $n-1$ | $\frac{n(n-1)}{2}$ | $O(n^2)$ | | Number of moves $0$ | $\frac{n(n-1)}{2}$ | $O(n^2)$ | | Time complexity $O(n)$ | $O(n^2)$ | $O(n^2)$ | | Space complexity $O(1)$ | $O(1)$ | $O(1)$ |
** Critical nature**:
- Stable Sorting
- Data suitable for basic order**, efficiency close $O(n)$
- Also suited to the case of small data**
2.2 Order of half-insertion
In the search for insertions, a half of** is used to find** (diversely) and to reduce the number of comparisons, but** the number of moves remains unchanged**.
void BinaryInsertSort(int a[], int n) { int i, j, low, high, mid, temp; for (i = 1; i < n; i++) { temp = a[i]; low = 0; high = i - 1; // 折半查找插入位置 while (low <= high) { mid = (low + high) / 2; if (a[mid] > temp) high = mid - 1; else low = mid + 1; } // 移动元素 for (j = i - 1; j >= low; j--) a[j+1] = a[j]; a[low] = temp; }}| Compare | Directly insert | |------|---------|---------| | Number of comparisons $O(n^2)$ | $O(n\log n)$ | | Number of moves $O(n^2)$ | $O(n^2)$(No change) | Time complexity $O(n^2)$ | $O(n^2)$(continued) $O(n^2)$） |
3. Hill sorting
** Hill Sort = Insert Sort + Incremental Group. It’s essentially an improvement in the order of insertion!**
3.1 Core thinking
Direct insertion is efficient when it is generally orderly**$O(n)$) is also efficient when the amount of data is small**.
Hill uses both:
- Subsequences divided into several ** increment intervals**
- Sort each subsequence** Insert directly**
- Gradually down the increment until the increment is 1 (at this point the normal direct insertion is sorted, but the data is largely orderly)
3.2 Process indicators
原序列： 49 38 65 97 76 13 27 49 55 04增量 d=5（每隔5个一组）： 49 ─────────── 13 → [13, 49] 38 ─────────── 27 → [27, 38] 65 ─────────── 49 → [49, 65] 97 ─────────── 55 → [55, 97] 76 ─────────── 04 → [04, 76]结果： 13 27 49 55 04 49 38 65 97 76
增量 d=3（每隔3个一组）： 13 ───── 55 ───── 38 ───── 76 → [13, 38, 55, 76] 27 ───── 04 ───── 65 → [04, 27, 65] 49 ───── 49 ───── 97 → [49, 49, 97]结果： 13 04 49 38 27 49 55 65 97 76
增量 d=1（普通插入排序）： （此时序列已基本有序，插入排序效率极高）结果： 04 13 27 38 49 49 55 65 76 973.3 Algorithmic realization (C language)
void ShellSort(int a[], int n) { int d, i, j, temp; // 增量序列：每次除以 2 for (d = n / 2; d >= 1; d /= 2) { // 对每个子序列做直接插入排序 for (i = d; i < n; i++) { if (a[i] < a[i-d]) { temp = a[i]; for (j = i - d; j >= 0 && a[j] > temp; j -= d) a[j+d] = a[j]; a[j+d] = temp; } } }}3.4 Incremental sequences
| Incremental sequences, gills, formulas, gills, worst time complexity, gibberish. |----------|------|--------------| | Shell Original $d_k = \lfloor n/2^k \rfloor$ | $O(n^2)$ | | Hibbard | $d_k = 2^k - 1$（1, 3, 7, 15…） | $O(n^{1.5})$ | | Sedgewick | 1, 5, 19, 41, 109… | $O(n^{4/3})$ |
Shell original increments (half times each) are used for examinations.
3.5 Nature
| Nature Value |------|-----| | Time complexity $O(n^{1.3}) \sim O(n^2)$, depending on the incremental sequence | Space complexity $O(1)$ | | Stable ** Unstable**
3.6 Hill Sorting vs Insert Sorting
| ♪ Into the sorting ♪ |---|---------|---------| | The basic operation, the twilight, the movement, the twilight, the movement. | Initial order, no requirements, use of gradual order, | Stability ** stability ** instability ** instability ** stability ** stability | Efficiency $O(n^2)$ Convention $O(n^{1.3})$ |
**Conclusion : Hill ranking is the insertion of an improved version of ranking under ** big data volume in exchange for a small incremental multiple ranking for overall efficiency improvement.
4. Bubble sequencing
4.1 Basic thinking
Two relatively adjacent elements from the back forward (or from the back) are exchanged in reverse order and each trip determines the position of the highest value.
原序列： 49 38 65 97 76 13 27 49
第1趟：（从后往前冒） 49↔38 → 38 49 65 97 76 13 27 49 （38冒到最前面） 结果：[13] 38 49 65 97 76 27 49 ← 13 确定
第2趟： 结果：[13 27] 38 49 65 97 76 49 ← 27 确定
...最终：[13 27 38 49 49 65 76 97]4.2 Algorithmic realization (C language)
void BubbleSort(int a[], int n) { int i, j, temp; int flag; // 标记本趟是否发生交换 for (i = 0; i < n - 1; i++) { flag = 0; for (j = n - 1; j > i; j--) { if (a[j-1] > a[j]) { // 逆序则交换 temp = a[j]; a[j] = a[j-1]; a[j-1] = temp; flag = 1; } } if (flag == 0) // 没有交换 → 已经有序 break; }}4.3 Performance Analysis
| Indicator | Best (Order) | Worst (Reverse) | Average |
|---|---|---|---|
| Number of comparisons $n-1$ | $\frac{n(n-1)}{2}$ | $O(n^2)$ | |
| Number of exchanges $0$ | $\frac{n(n-1)}{2}$ | $O(n^2)$ | |
| Time complexity $O(n)$ | $O(n^2)$ | $O(n^2)$ | |
| Space complexity $O(1)$ |
- Stable Sorting thallium (the same value is not exchanged)
5. Rapid sequencing
Based on** partition**, which is the best algorithm for average performance in internal ranking.
5.1 Basic thinking
- Select an element from the sequence as ** pivot**
- ** Division**: two parts of the sequence - all pivot on the left, all pivot on the right
- Recursively sort both sides
原序列： 49 38 65 97 76 13 27 49 ↑ pivot=49
一趟划分后： [27 38 13] 49 [76 97 65 49] 左边 ≤ 49 右边 ≥ 49
递归对左右排序...最终：[13 27 38 49 49 65 76 97]5.2 Step-by-step (core operations)
int Partition(int a[], int low, int high) { int pivot = a[low]; // 选第一个元素为枢轴 while (low < high) { // high 向左找比 pivot 小的 while (low < high && a[high] >= pivot) high--; a[low] = a[high]; // 将此小的移到左边
// low 向右找比 pivot 大的 while (low < high && a[low] <= pivot) low++; a[high] = a[low]; // 将此大的移到右边 } a[low] = pivot; // 枢轴归位 return low; // 返回枢轴位置}5.3 Recursive realization
void QuickSort(int a[], int low, int high) { if (low < high) { int pivotPos = Partition(a, low, high); QuickSort(a, low, pivotPos - 1); // 递归左半部分 QuickSort(a, pivotPos + 1, high); // 递归右半部分 }}5.4 Performance Analysis
| Indicator | Best | Worst | Average |
|---|---|---|---|
| Time complexity $O(n\log n)$ | $O(n^2)$ | $O(n\log n)$ | |
| Space complexity $O(\log n)$ | $O(n)$ | $O(\log n)$ | |
| Stable, unstable, unstable. |
- Best/average: each axis is exactly equal to the sequence** and reverts to tree height $\log n$
- ** Worst-case scenario**: sequence** positive or reverse** with each split empty and degraded $O(n^2)$
- Space complexity from ** Recursive Workplace**
5.5 Optimizing methods
- ** Three to one**: Selection
low, mid, highThe median of three positions is the axis. - ** Randomly selected axis**
- Switch small to ** Insert Sort**
6. Simple selection sequencing
6.1 Basic thinking
The smallest (or maximum)** of the elements to be sorted at the end of the sequence.
原序列： 49 38 65 97 76 13 27 49
第1趟：在 [49 38 65 97 76 13 27 49] 中找最小 → 13，与 49 交换 [13] 38 65 97 76 49 27 49
第2趟：在 [38 65 97 76 49 27 49] 中找最小 → 27，与 38 交换 [13 27] 65 97 76 49 38 49
第3趟：在 [65 97 76 49 38 49] 中找最小 → 38，与 65 交换 [13 27 38] 97 76 49 65 49
...最终：[13 27 38 49 49 65 76 97]6.2 Algorithmic realization (C language)
void SelectSort(int a[], int n) { int i, j, min, temp; for (i = 0; i < n - 1; i++) { min = i; for (j = i + 1; j < n; j++) { if (a[j] < a[min]) min = j; } if (min != i) { temp = a[i]; a[i] = a[min]; a[min] = temp; } }}6.3 Performance Analysis
| Indicator Value |------|-----| | Time complexity $O(n^2)$(not related to initial sequence) | Number of comparisons $\frac{n(n-1)}{2}$(Standing) zirconium | Number of exchanges $0 \sim n-1$ | | Space complexity $O(1)$ | | Stability ** Unstable** (exchange may destroy relative order) **
Like what?
[5, 5, 2], the 1st switch between 2 and the first 5 changes the relative position of both 5.
7. Stacking
7.1 Definition of stacks
** Large piles**: the value of each node ≥ the value of the child to his or her left or to his lefta[i] ≥ a[2i+1] 且 a[i] ≥ a[2i+2]）
** Little pile**: the value of each node ≤ the value of the child to the left or the right
大根堆示例： 97 / \ 76 65 / \ / \ 49 38 13 27
数组存储：[97, 76, 65, 49, 38, 13, 27]7.2 Core Operations
** Stack Sorting = Stacking + Repeated Output Stack + Adjustment Stack**
7.3 Stack adjustments (core)
// 将 a[k] 为根的子树调整为大根堆// n 是堆的大小void HeapAdjust(int a[], int k, int n) { int root = a[k]; // 暂存根结点 int i; for (i = 2 * k + 1; i < n; i = 2 * i + 1) { // i 指向左孩子 // 选左右孩子中较大的 if (i + 1 < n && a[i] < a[i+1]) i++; // 根已经大于最大的孩子 → 调整完成 if (root >= a[i]) break; // 孩子上移 a[k] = a[i]; k = i; // 继续向下调整 } a[k] = root;}7.4 Stacking and sorting
void HeapSort(int a[], int n) { int i, temp; // 1. 建堆：从最后一个非叶结点开始调整 // 最后一个非叶结点下标 = n/2 - 1 for (i = n / 2 - 1; i >= 0; i--) HeapAdjust(a, i, n);
// 2. 排序：反复取出堆顶（与最后一个交换），调整堆 for (i = n - 1; i > 0; i--) { temp = a[0]; // 堆顶（最大值）与最后元素交换 a[0] = a[i]; a[i] = temp; HeapAdjust(a, 0, i); // 调整剩余元素为新堆 }}7.5 An indicative stacking process
初始序列：[49, 38, 65, 97, 76, 13, 27, 49]
建堆后： [97, 76, 65, 49, 38, 13, 27, 49] ↑ ↑ 堆顶 末尾
第1趟：交换堆顶 97 和末尾 49，调整 → [76, 49, 65, 49, 38, 13, 27 | 97]
第2趟：交换堆顶 76 和末尾 27，调整 → [65, 49, 27, 49, 38, 13 | 76, 97]
...最终：[13, 27, 38, 49, 49, 65, 76, 97]7.6 Performance Analysis
| Indicator Value |------|-----| | Complexity of construction time $O(n)$ | | Each adjustment $O(\log n)$ | | Total time complexity $O(n\log n)$ | | Space complexity $O(1)$ | | Stability ** Unstable** **
7.7 Pocket insertion and deletion
** Insert**: New elements end, then ** up** (comparison to parent, floating) ** Deleted**: replace deleted elements with the last element, then adjust downward** (sink)
8. Grouping
8.1 Fundamentals
Merge two or more orderly tables** into a new orderly table.
2 Reconsolidation: merge the sequence and repeat it until the whole sequence is orderly.
初始: 49 38 65 97 76 13 27 49
第1趟： [38 49] [65 97] [13 76] [27 49] → 每2个归并第2趟： [38 49 65 97] [13 27 49 76] → 每4个归并第3趟： [13 27 38 49 49 65 76 97] → 全部归并8.2 Consolidation of two orderly sub-watches
// 合并 a[low..mid] 和 a[mid+1..high]void Merge(int a[], int low, int mid, int high) { int *temp = (int *)malloc((high - low + 1) * sizeof(int)); int i = low, j = mid + 1, k = 0;
while (i <= mid && j <= high) { if (a[i] <= a[j]) temp[k++] = a[i++]; else temp[k++] = a[j++]; } while (i <= mid) temp[k++] = a[i++]; // 左边剩余 while (j <= high) temp[k++] = a[j++]; // 右边剩余
for (i = low, k = 0; i <= high; i++, k++) a[i] = temp[k]; free(temp);}8.3 Recursive realization
void MergeSort(int a[], int low, int high) { if (low < high) { int mid = (low + high) / 2; MergeSort(a, low, mid); // 递归排序左半 MergeSort(a, mid + 1, high); // 递归排序右半 Merge(a, low, mid, high); // 合并两个有序子表 }}8.4 Performance Analysis
| Indicator Value |------|-----| | Time complexity $O(n\log n)$(not related to initial sequence) | Combined number $\lceil \log_2 n \rceil$ | | Space complexity $O(n)$(Auxiliary array required) | Stable Stable Stable |
9. Sorting of the base figure
9.1 Basic thinking
Not based on comparison, but based on keyword values** assigned and collected**.
9.2 LSD (lowest priority) process
序列：278 109 063 930 589 184 505 269 008 083
按个位分配： 桶0：930 桶3：063, 083 桶4：184 桶5：505 桶8：278, 008 桶9：109, 589, 269收集： 930 063 083 184 505 278 008 109 589 269
按十位分配： 桶0：505, 008, 109 桶3：930 桶6：063, 269 桶7：278 桶8：083, 184, 589收集： 505 008 109 930 063 269 278 083 184 589
按百位分配： 桶0：008, 063, 083 桶1：109, 184 桶2：269, 278 桶5：505, 589 桶9：930收集： 008 063 083 109 184 269 278 505 589 9309.2 Performance Analysis
| Indicator Value |------|-----| | Time complexity $O(d(n + r))$ | | Space complexity $O(r)$ | | Stable Stable Stable |
- $d$Key bits
- $n$Number of elements
- $r$Base figure (number of barrels)
10. Summary of ranking comparisons
| The method of sorting, the mean time, the best time, the worst time, the space, the stability, the stability. |----------|---------|---------|---------|------|--------| | Directly insert | $O(n^2)$ | $O(n)$ | $O(n^2)$ | $O(1)$ Stable | Hill sorted. $O(n^{1.3})$ | — | $O(n^2)$ | $O(1)$ ♪ Unstable ♪ | Bubble Sorting $O(n^2)$ | $O(n)$ | $O(n^2)$ | $O(1)$ Stable | Quick Sorting $O(n\log n)$ | $O(n\log n)$ | $O(n^2)$ | $O(\log n)$ ♪ Unstable ♪ | Simple selection $O(n^2)$ | $O(n^2)$ | $O(n^2)$ | $O(1)$ ♪ Unstable ♪ | Sort stacks $O(n\log n)$ | $O(n\log n)$ | $O(n\log n)$ | $O(1)$ ♪ Unstable ♪ | Sort in group $O(n\log n)$ | $O(n\log n)$ | $O(n\log n)$ | $O(n)$ Stable | Sorting of base numbers $O(d(n+r))$ | $O(d(n+r))$ | $O(d(n+r))$ | $O(r)$ Stable
10.1 Basis for selection of ranking methods
| The scene, the table, the recommended sequence, the table. |------|---------| | $n$ Small ( 5050) | Directly insert, simple selection | | $n$ It’s big. $O(n\log n)$ Algorithm | It’s basically orderly. | REQUESTS STAMMING, COMPREHENSION, PUTTING, FLOOD, BASY | We need less space. | Complex keyword structure Simple selection (lower number of comparisons)
10.2 Memory skills
插入冒泡归并基 —— 稳定希尔快选堆 —— 不稳定
n² 三兄弟：插入、冒泡、选择nlogn 三兄弟：快速、堆、归并
"快选堆" = 不稳定 = 内部排序中效率最高的三个11. Examination focus
Type I: Manual simulation sorting process
Order
{49, 38, 65, 97, 76, 13, 27, 49}, writes:
- Sort the results quickly.
- Stack sorting (stacking + results per trip)
- Hill sorted the results.
- Sort the results together.
Topic II: Determination of ranking stability
Determines whether a sorting algorithm changes its relative position when you have the same keyword in the sequence.
Type III: Time complexity analysis
The initial sequence status (reverse/reverse/random) is given, and the number of comparisons and moves of the sorting algorithms is analysed.
Type IV: Pocket adjustments
Sets a complete series of fork trees, starting with the last non-leaf node, and writes each step.
Topic V: Base figures and special problems of aggregation
- Why don’t you compare the base figure?
- How much support space is required for the grouping?
** The final findings of the ranking in Hill**: it is an improvement in the order of insertion**, allowing data to be sequenced gradually through incremental grouping, thus taking advantage of the insertion of “generally orderly and efficient” ranking. Not select an optimisation of sorting!
