八大排序算法核心解析与实战实现

void ShellSort(int* a, int n) {
    int gap = n;
    while (gap > 1) {
        gap = gap / 3 + 1;
        for (int i = 0; i <= n - gap - 1; i++) {
            int end = i;
            int tmp = a[end + gap];
            while (end >= 0) {
                if (a[end] > tmp) {
                    a[end + gap] = a[end];
                    end -= gap;
                } else {
                    break;
                }
            }
            a[end + gap] = tmp;
        }
    }
}

属性：

• 时间复杂度：取决于增量序列，Knuth 增量约为 O(n^1.3)
• 空间复杂度：O(1)
• 稳定性：不稳定

选择排序

简单选择排序

思想：每次从未排序部分选出最小元素，放到已排序末尾。

实现：

void SelectSort(int* a, int n) {
    int begin = 0, end = n - 1;
    while (begin < end) {
        int minn = begin, maxx = begin;
        for (int i = begin + 1; i <= end; i++) {
            if (a[i] < a[minn]) minn = i;
            if (a[i] > a[maxx]) maxx = i;
        }
        Swap(&a[minn], &a[begin]);
        if (maxx == begin) maxx = minn;
        Swap(&a[maxx], &a[end]);
        begin++; end--;
    }
}

void Swap(int* a, int* b) {
    int tmp = *a; *a = *b; *b = tmp;
}

属性：

• 时间复杂度：始终 O(n²)
• 空间复杂度：O(1)
• 稳定性：不稳定

堆排序

思想：利用堆结构（完全二叉树）高效选择最大/最小值。

实现：

void AdjustDown(int* a, int parent, int n) {
    int maxChild = (parent << 1) + 1;
    while (maxChild < n) {
        if (maxChild + 1 < n && a[maxChild + 1] > a[maxChild]) {
            maxChild += 1;
        }
        if (a[parent] >= a[maxChild]) return;
        Swap(&a[parent], &a[maxChild]);
        parent = maxChild;
        maxChild = (parent << 1) + 1;
    }
}

void HeapSort(int* a, int n) {
    for (int i = (n - 1 - 1) >> 1; i >= 0; i--) {
        AdjustDown(a, i, n);
    }
    int end = n - 1;
    while (end > 0) {
        Swap(&a[0], &a[end]);
        end--;
        AdjustDown(a, 0, end + 1);
    }
}

属性：

• 时间复杂度：O(n log n)
• 空间复杂度：O(1)
• 稳定性：不稳定

交换排序

冒泡排序

思想：重复比较相邻元素，将较大元素逐步'冒泡'到末尾。

实现：

void BubbleSort(int* a, int n) {
    for (int i = 1; i <= n - 1; i++) {
        int flag = 1;
        for (int j = 1; j <= n - i; j++) {
            if (a[j - 1] > a[j]) {
                Swap(&a[j - 1], &a[j]);
                flag = 0;
            }
        }
        if (flag) break;
    }
}

属性：

• 时间复杂度：最坏 O(n²)，最好 O(n)
• 稳定性：稳定

快速排序

思想：分治法。选基准值将数组分为两部分，递归排序。

分区策略：

1. Hoare 对撞指针：左右指针向中间扫描，相遇处放基准。
2. Lomuto 快慢指针：快指针遍历，慢指针标记小于基准区边界。
3. 挖坑法：填坑挖坑，最后填入基准。

实现（递归）：

int PartSort3(int* a, int left, int right) {
    int mid = GetMid(a, left, right);
    Swap(&a[left], &a[mid]);
    int key = a[left];
    int hole = left;
    int begin = left, end = right;
    while (begin < end) {
        while (begin < end && a[end] >= key) end--;
        a[hole] = a[end]; hole = end;
        while (begin < end && a[begin] <= key) begin++;
        a[hole] = a[begin]; hole = begin;
    }
    a[hole] = key;
    return hole;
}

void QuickSort(int* a, int left, int right) {
    if (left >= right) return;
    int key = PartSort3(a, left, right);
    QuickSort(a, left, key - 1);
    QuickSort(a, key + 1, right);
}

非递归实现：使用栈模拟递归调用过程，避免栈溢出风险。

属性：

• 时间复杂度：平均 O(n log n)，最坏 O(n²)
• 空间复杂度：O(log n)
• 稳定性：不稳定

归并排序

思想：分治法。将数组不断分割直到长度为 1，然后合并有序子数组。

实现（递归）：

void _MergeSort(int* a, int* tmp, int begin, int end) {
    if (begin >= end) return;
    int mid = begin + ((end - begin) >> 1);
    _MergeSort(a, tmp, begin, mid);
    _MergeSort(a, tmp, mid + 1, end);
    
    int begin1 = begin, end1 = mid;
    int begin2 = mid + 1, end2 = end;
    int pos = begin;
    
    while (begin1 <= end1 && begin2 <= end2) {
        if (a[begin1] <= a[begin2]) tmp[pos++] = a[begin1++];
        else tmp[pos++] = a[begin2++];
    }
    while (begin1 <= end1) tmp[pos++] = a[begin1++];
    while (begin2 <= end2) tmp[pos++] = a[begin2++];
    memcpy(a + begin, tmp + begin, (end - begin + 1) * sizeof(int));
}

void MergeSort(int* a, int n) {
    int* tmp = (int*)malloc(n * sizeof(int));
    if (!tmp) { perror("malloc fail"); return; }
    _MergeSort(a, tmp, 0, n - 1);
    free(tmp);
}

属性：

• 时间复杂度：始终 O(n log n)
• 空间复杂度：O(n)
• 稳定性：稳定

计数排序

思想：非比较排序。统计每个元素出现次数，按计数顺序输出。

实现：

void CountSort(int* a, int n) {
    int minn = a[0], maxx = a[0];
    for (int i = 0; i < n; i++) {
        if (a[i] < minn) minn = a[i];
        if (a[i] > maxx) maxx = a[i];
    }
    int range = maxx - minn + 1;
    int* count = (int*)calloc(range, sizeof(int));
    if (!count) { perror("calloc fail"); return; }
    
    for (int i = 0; i < n; i++) count[a[i] - minn]++;
    
    int pos = 0;
    for (int i = 0; i < range; i++) {
        while (count[i]--) a[pos++] = i + minn;
    }
    free(count);
}

属性：

• 时间复杂度：O(n + k)
• 空间复杂度：O(n + k)
• 稳定性：稳定

性能总结

注意：实际应用中需根据数据特征（规模、分布、稳定性要求）选择合适的算法。