冒泡排序

外循环–，内循环 ++（从后往前排好）

#include <stdio.h>
#include <stdbool.h>

#define DATA_SIZE 15

int bubble_sort(int *data, int len)
{
    int temp;
    bool swap_flag = true;
    for (int i = len - 1; i > 0; i--) { // NOTE:NUN个数要比较NUM-1次，//后面先排好 
        swap_flag = false;
        for (int j = 0; j < i; j++) { // NOTE:大的数放到后面，小的数放到前面，i之后的已经排好，i之前的需要排序
            if (data[j] > data[j + 1]) {
                temp = data[j];
                data[j] = data[j + 1];
                data[j + 1] = temp;
                swap_flag = true;
            }
        }
        if (swap_flag == false) //加入标志位，若已无需再排序，则直接结束排序
            return 0;
    }
    return 0;
}

int main()
{
    int data[DATA_SIZE] = {2, 5, 10, 34, 21, 6, 345, 12, 87, 1, 80, 54, 78, 32, 76};
    bubble_sort(data, DATA_SIZE);
    for (int i = 0; i < DATA_SIZE;i++)
        printf("%d\t", data[i]);
    return 0;
}

选择排序

双循环都是 ++（从前往后排好）

#include <stdio.h>

#define DATA_SIZE 15

int select_sort(int *data,int len)
{
    int temp;
    for (int i = 0; i < len - 1;i++){//前面先排好
        for (int j = i + 1; j < len;j++){
            if(data[j]<data[i]){
                temp = data[j];
                data[j] = data[i];
                data[i] = temp;
            }
        }
    }
    return 0;
}

int main()
{
    int data[DATA_SIZE] = {2, 5, 10, 34, 21, 6, 345, 12, 87, 1, 80, 54, 78, 32, 76};
    select_sort(data, DATA_SIZE);
    for (int i = 0; i < DATA_SIZE; i++)
        printf("%d\t", data[i]);
    return 0;
}

插入排序

外循环–，内循环 ++

#include <stdio.h>

#define DATA_SIZE 15

int insert_sort(int *data, int len)
{
    int j;
    int temp;
    for (int i = 1; i < len; i++) { // 从左到右遍历，第一个位置不用动
        temp = data[i];//不可省
        for (j = i - 1; j >= 0; j--) { // 从前面已经排好的数组的最后一位开始向前比较
            if (data[j] <= temp)
                break;
            else
                data[j + 1] = data[j];//整体后移
        }
        data[j + 1] = temp;//插入
    }
    return 0;
}

int main()
{
    int data[DATA_SIZE] = {2, 5, 10, 34, 21, 6, 345, 12, 87, 1, 80, 54, 78, 32, 76};
    insert_sort(data, DATA_SIZE);
    for (int i = 0; i < DATA_SIZE; i++)
        printf("%d\t", data[i]);
    return 0;
}

希尔排序

先分组，后排序

#include <stdio.h>

#define DATA_SIZE 15

int group_sort(int *data, int len, int pos, int step)
{   
    int i, j, temp;
    for (i = pos + step; i < len; i = i + step) {
        temp = data[i];
        for (j = i - step; j >= 0; j=j-step) {
            if (data[j] <= temp) {
                break;
            }
            else {
                data[j + step] = data[j];//逐步后移
            }
        }
        data[j + step] = temp;
    }
}

int shell_sort(int *data, int len)
{
    int i;
    int step;
    for (step = len / 2; step > 0; step = step / 2) { // 分组,最后一次必定为1
        for (i = 0; i < step; i++) {                  // 对每一组
            group_sort(data, len, i, step);
        }
    }
    return 0;
}

int main()
{
    int data[DATA_SIZE] = {2, 5, 10, 34, 21, 6, 345, 12, 87, 1, 80, 54, 78, 32, 76};
    shell_sort(data, DATA_SIZE);
    for (int i = 0; i < DATA_SIZE; i++)
        printf("%d\t", data[i]);
    return 0;
}

归并排序

#define DATA_SIZE 15
int temp[DATA_SIZE] = {0};
void merge(int *data, int l, int mid, int r)
{
    int i = l;
    int j = mid + 1;
    int k = l;
    
    while (i <= mid && j <= r) {
        if (data[i] <= data[j])
            temp[k++] = data[i++];
        else
            temp[k++] = data[j++];
    }
    while(i<=mid)
        temp[k++] = data[i++];
    while (j <= r)
        temp[k++] = data[j++];
    for (int i = l; i <= r;i++){ //易错
        data[i] = temp[i];
    }
}
void merge_sort(int *data, int l, int r)
{
    if(l>=r)
        return;
    int mid = (r + l) / 2;
    merge_sort(data, l, mid);
    merge_sort(data, mid + 1, r);
    merge(data, l, mid, r);
}
int main(void)
{
    int data[DATA_SIZE] = {2, 5, 10, 34, 21, 6, 345, 12, 87, 1, 80, 54, 78, 32, 76};
    merge_sort(data, 0, DATA_SIZE - 1);
    for (int i = 0; i < DATA_SIZE; i++)
        printf("%d\t", data[i]);
    return 0;
}

快速排序

  1. 取 data[0]作为基准
  2. 扫描数列，将比基准数小的元素全部放到它的左边，大于或等于基准数的元素全部放到它的右边，得到左右两个区间。
  3. 再对左右区间重复第二步，直到各区间少于两个元素。（右边找到并排序后换到左边，左右交替）
#include <stdio.h>

#define DATA_SIZE 15

int quick_sort(int *data, int len)
{
    int temp, left, right;
    temp = data[0];
    left = 0;
    right = len - 1;
    int flag = 2;
    if (len < 2)
        return 0;
    while (right > left) {
        if (flag == 2) {
            if (data[right] < temp) { // 把右边比轴小的移到轴左边
                data[left] = data[right];
                flag = 1; // 换边
            }
            else {
                right--;
            }
        }
        else {
            if (data[left] > temp) { // 把左边比轴大的移到轴右边
                data[right] = data[left];
                flag = 2; // 换边
            }
            else {
                left++;
            }
        }
    }
    data[left] = temp;
    quick_sort(data, left);                      // 对左边操作
    quick_sort(data + left + 1, len - left - 1); // 对右边操作
}

int main()
{
    int data[DATA_SIZE] = {2, 5, 10, 34, 21, 6, 345, 12, 87, 1, 80, 54, 78, 32, 76};
    quick_sort(data, DATA_SIZE);
    for (int i = 0; i < DATA_SIZE; i++)
        printf("%d\t", data[i]);
    return 0;
}

改进

选取中间值作为参考

仅有开头一个等号

void func(int *data,int l,int r)
    {
        if(l>=r)
            return;
        int i =l-1;            //不可省
        int j = r+1;           //不可省
        int mid = (l+r)/2;
        int val = data[mid];   //不可省
        while(i<j){
            do{                //不可省
                i++;
            }while(data[i]<val);
            do{                //不可省
                j--;
            }while(data[j]>val);
            if(i<j)
                swap(data[i],data[j]);
        }
        func(data,l,j);
        func(data,j+1,r);
    }

堆排序

理解

堆排序就像整理一堆书：

  1. 建堆：先把所有书按照 “大的放上面” 的规则叠成一堆（构建最大堆）
  2. 取最大：每次从最上面拿走最大的书，放到书架的最后一格
  3. 重新整理：把剩下的书重新叠好，保持 “大的放上面” 的规则
  4. 重复：不断重复取最大和重新整理的步骤，直到所有书都按顺序排好

堆排序的特点是稳定可靠（相等元素不会乱序），时间复杂度始终是 O (n log n)，但实际运行速度通常比快排稍慢。

重要结论

最后一个非叶子节点：

$$
i = \left( \frac{n}{2} \right)-1
$$

当前节点 i 的左孩子节点：

$$
left = 2*i+1
$$

当前节点 i 的右孩子节点：

$$
right = 2*i+2
$$

#include <iostream>
#include <vector>

// 调整堆，使以i为根的子树成为最大堆
void heapify(std::vector<int>& arr, int n, int i) {
    int largest = i;         // 初始化最大值为根节点
    int left = 2 * i + 1;    // 左子节点索引
    int right = 2 * i + 2;   // 右子节点索引
    
    // 如果左子节点存在且大于根节点
    if (left < n && arr[left] > arr[largest])
        largest = left;
    
    // 如果右子节点存在且大于当前最大值
    if (right < n && arr[right] > arr[largest])
        largest = right;
    
    // 如果最大值不是根节点
    if (largest != i) {
        std::swap(arr[i], arr[largest]);  // 交换根节点和最大值节点
        
        // 递归调整受影响的子树
        heapify(arr, n, largest);
    }
}

// 堆排序主函数
void heapSort(std::vector<int>& arr) {
    int n = arr.size();
    
    // 1. 构建最大堆（从最后一个非叶子节点开始）
    // 最后一个非叶子节点的索引 = (n/2) - 1
    for (int i = n / 2 - 1; i >= 0; i--) {
        heapify(arr, n, i);
    }
    
    // 2. 逐个提取堆顶元素（最大值）并调整堆
    for (int i = n - 1; i > 0; i--) {
        // 将当前堆顶（最大值）与数组末尾元素交换
        swap(arr[0], arr[i]);
        
        // 对剩余元素重新堆化（堆大小减1）
        heapify(arr, i, 0);
    }
}

// 辅助函数：打印数组
void printArray(const std::vector<int>& arr) {
    for (int num : arr)
        std::cout << num << " ";
    std::cout << std::endl;
}

// 测试
int main() {
    std::vector<int> arr = {12, 11, 13, 5, 6, 7};
    
    std::cout << "原始数组: ";
    printArray(arr);
    
    heapSort(arr);
    
    std::cout << "排序后数组: ";
    printArray(arr);
    
    return 0;
}

堆排和快排分析

为什么堆排序是稳定的？

堆排序的稳定性源于其操作特性：

  1. 堆排序通过比较和交换操作来排序，当元素值相等时，不会改变它们的相对顺序
  2. 在堆的调整过程中，相等元素的父节点和子节点关系保持不变
  3. 每次提取堆顶元素后，只与末尾元素交换，不影响其他相等元素的相对位置

为什么快排是不稳定的？

快速排序的不稳定性主要由以下原因造成：

  1. 基准元素的选择和交换可能会破坏相等元素的相对顺序
  2. 分区过程中，相等元素可能被分到基准元素的两侧
  3. 例如：数组 [3, 2, 2]，如果选择第一个 3 作为基准，经过一次分区后可能变成 [2, 2, 3]，虽然结果正确，但如果原来的两个 2 有其他关联信息，它们的相对位置可能改变