算法 学习 排序 2025年6月16日10:25:37

比较排序 

简单排序 

• 冒泡排序

重点：相邻元素两两比较，大的往后移动
使用场景：教学使用，实际应用较少（效率低）
时间复杂度：O(n²)（最坏和平均），O(n)（最好，已排序时）

void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n-1; i++) {       // 外层循环控制轮数
        int swapped = 0;                  // 优化：标记是否发生交换
        for (int j = 0; j < n-i-1; j++) { // 内层循环控制比较次数
            if (arr[j] > arr[j+1]) {      // 前一个比后一个大
                // 交换相邻元素
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
                swapped = 1;
            }
        }
        if (!swapped) break; // 本轮无交换，说明已有序
    }
}

冒泡排序调用示例(直观展示)

int arr[] = {64, 34, 25, 12, 22, 11, 90};
int n = sizeof(arr)/sizeof(arr[0]);

printf("原始数组: ");
printArray(arr, n); // 输出: 64 34 25 12 22 11 90

bubbleSort(arr, n);

printf("排序后数组: ");
printArray(arr, n); // 输出: 11 12 22 25 34 64 90

//流程变化
第1轮: 34 25 12 22 11 64 90 (最大的90已到位)
第2轮: 25 12 22 11 34 64 90 
第3轮: 12 22 11 25 34 64 90
...

• 选择排序

重点：每次选择最小元素放到已排序序列末尾
使用场景：小规模数据或内存受限环境
时间复杂度：O(n²)

void selectionSort(int arr[], int n) {
    for (int i = 0; i < n-1; i++) {
        int min_idx = i; // 记录最小元素位置
        for (int j = i+1; j < n; j++) {
            if (arr[j] < arr[min_idx]) {
                min_idx = j; // 更新最小元素位置
            }
        }
        // 将最小元素交换到已排序序列末尾
        int temp = arr[i];
        arr[i] = arr[min_idx];
        arr[min_idx] = temp;
    }
}

选择排序调用示例(直观展示)

  int arr[] = {64, 25, 12, 22, 11};
    int n = sizeof(arr)/sizeof(arr[0]);
    
    printf("原始数组: ");
    for (int i = 0; i < n; i++) printf("%d ", arr[i]);
    printf("\n\n");
    
    selectionSort(arr, n);
    
    printf("\n最终结果: ");
    for (int i = 0; i < n; i++) printf("%d ", arr[i]);

//流程
原始数组: 64 25 12 22 11 

第1轮选择: [11] 25 12 22 64  // 最小11交换到首位
第2轮选择: 11 [12] 25 22 64  // 最小12交换到第2位
第3轮选择: 11 12 [22] 25 64  // 最小22交换到第3位
第4轮选择: 11 12 22 [25] 64  // 最小25交换到第4位

最终结果: 11 12 22 25 64

• 插入排序

重点：将未排序元素插入到已排序序列的合适位置
使用场景：小规模或基本有序数据
时间复杂度：O(n²)（最坏和平均），O(n)（最好）

void insertionSort(int arr[], int n) {
    for (int i = 1; i < n; i++) {  // 从第二个元素开始
        int key = arr[i];          // 当前待插入元素
        int j = i - 1;
        // 将大于key的元素后移
        while (j >= 0 && arr[j] > key) {
            arr[j+1] = arr[j];
            j--;
        }
        arr[j+1] = key; // 插入到正确位置
    }
}

插入排序调用示例(直观展示)

  int arr[] = {12, 11, 13, 5, 6};
    int n = sizeof(arr)/sizeof(arr[0]);
    
    printf("原始数组: ");
    for (int i = 0; i < n; i++) printf("%d ", arr[i]);
    printf("\n\n");
    
    insertionSort(arr, n);
    
    printf("\n最终结果: ");
    for (int i = 0; i < n; i++) printf("%d ", arr[i]);

//流程
原始数组: 12 11 13 5 6 

第1轮插入: |11| 12 13 5 6  // 11插入到12前
第2轮插入: 11 12 |13| 5 6  // 13保持位置
第3轮插入: |5| 11 12 13 6  // 5插入到最前
第4轮插入: 5 |6| 11 12 13  // 6插入到5和11之间

最终结果: 5 6 11 12 13

进阶排序

• 归并排序

重点：分治法，先分后合
使用场景：需要稳定排序且不关心额外空间时
时间复杂度：O(nlogn)

// 合并两个有序数组
void merge(int arr[], int l, int m, int r) {
    int n1 = m - l + 1;
    int n2 = r - m;
    
    // 创建临时数组
    int L[n1], R[n2];
    
    // 拷贝数据到临时数组
    for (int i = 0; i < n1; i++)
        L[i] = arr[l + i];
    for (int j = 0; j < n2; j++)
        R[j] = arr[m + 1 + j];
    
    // 合并临时数组
    int i = 0, j = 0, k = l;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }
    
    // 拷贝剩余元素
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }
    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}

void mergeSort(int arr[], int l, int r) {
    if (l < r) {
        int m = l + (r - l) / 2; // 防止溢出
        mergeSort(arr, l, m);     // 排序左半部分
        mergeSort(arr, m+1, r);   // 排序右半部分
        merge(arr, l, m, r);      // 合并
    }
}

归并排序调用示例(直观展示)

int arr[] = {38, 27, 43, 3, 9, 82, 10};
int n = sizeof(arr)/sizeof(arr[0]);

printf("原始数组: ");
printArray(arr, n); // 输出: 38 27 43 3 9 82 10

mergeSort(arr, 0, n-1);

printf("排序后数组: ");
printArray(arr, n); // 输出: 3 9 10 27 38 43 82

//合并过程
分割到最小单元: [38] [27] → 合并为[27,38]
[43] [3] → 合并为[3,43]
[27,38]和[3,43] → 合并为[3,27,38,43]

• 快速排序

重点：分治法，选取基准值分区
使用场景：大规模数据排序，性能要求高
时间复杂度：O(nlogn)（平均），O(n²)（最坏）

// 分区函数
int partition(int arr[], int low, int high) {
    int pivot = arr[high]; // 选取最后一个元素作为基准
    int i = (low - 1);     // 小于基准的元素的索引
    
    for (int j = low; j <= high-1; j++) {
        if (arr[j] < pivot) { // 当前元素小于基准
            i++;
            // 交换arr[i]和arr[j]
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    // 将基准放到正确位置
    int temp = arr[i+1];
    arr[i+1] = arr[high];
    arr[high] = temp;
    return (i + 1);
}

void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high); // 分区索引
        quickSort(arr, low, pi - 1);  // 排序左子数组
        quickSort(arr, pi + 1, high); // 排序右子数组
    }
}

快速排序调用示例(直观展示)

int arr[] = {10, 7, 8, 9, 1, 5};
int n = sizeof(arr)/sizeof(arr[0]);

printf("原始数组: ");
printArray(arr, n); // 输出: 10 7 8 9 1 5

quickSort(arr, 0, n-1);

printf("排序后数组: ");
printArray(arr, n); // 输出: 1 5 7 8 9 10

//分区过程
基准选择5: [1] 5 [10,7,8,9]  // 第一次分区结果
左子数组[10,7,8,9]选基准9: [7,8] 9 [10]  
继续处理[7,8]...

• 希尔排序

重点：改进的插入排序，按增量分组
使用场景：中等规模数据，需要比O(n²)更好的性能
时间复杂度：O(n^(3/2))（取决于增量序列

void shellSort(int arr[], int n) {
    // 初始增量gap为数组长度的一半，逐步缩小
    for (int gap = n/2; gap > 0; gap /= 2) {
        // 对每个子数组进行插入排序
        for (int i = gap; i < n; i++) {
            int temp = arr[i];
            int j;
            for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {
                arr[j] = arr[j - gap];
            }
            arr[j] = temp;
        }
    }
}

 希尔排序调用示例(直观展示)

int arr[] = {35, 33, 42, 10, 14, 19, 27, 44};
    int n = sizeof(arr)/sizeof(arr[0]);
    
    printf("原始数组: ");
    for (int i = 0; i < n; i++) printf("%d ", arr[i]);
    printf("\n\n");
    
    shellSort(arr, n);
    
    printf("\n最终结果: ");
    for (int i = 0; i < n; i++) printf("%d ", arr[i]);

//流程
原始数组: 35 33 42 10 14 19 27 44 

增量gap=4时: 14 19 27 10 35 33 42 44  // 分组[35,14], [33,19], [42,27], [10,44]排序
增量gap=2时: 14 10 27 19 35 33 42 44  // 分组[14,27,35,42], [10,19,33,44]排序
增量gap=1时: 10 14 19 27 33 35 42 44  // 标准插入排序

最终结果: 10 14 19 27 33 35 42 44

非比较排序

• 基数排序

重点：按位数从低到高分别排序
使用场景：整数或字符串排序，位数不多
时间复杂度：O(nk)（k是最大数字的位数）

// 获取数组中最大数的位数
int getMaxDigits(int arr[], int n) {
    int max = arr[0];
    for (int i = 1; i < n; i++) {
        if (arr[i] > max) {
            max = arr[i];
        }
    }
    int digits = 0;
    while (max != 0) {
        digits++;
        max /= 10;
    }
    return digits;
}

// 基数排序
void radixSort(int arr[], int n) {
    int max_digits = getMaxDigits(arr, n);
    int exp = 1; // 当前位数（1表示个位，10表示十位...）
    
    for (int d = 0; d < max_digits; d++) {
        // 10个桶（0-9）
        int buckets[10][n];
        int bucket_sizes[10] = {0};
        
        // 分配到桶中
        for (int i = 0; i < n; i++) {
            int digit = (arr[i] / exp) % 10;
            buckets[digit][bucket_sizes[digit]++] = arr[i];
        }
        
        // 从桶中收集回数组
        int index = 0;
        for (int i = 0; i < 10; i++) {
            for (int j = 0; j < bucket_sizes[i]; j++) {
                arr[index++] = buckets[i][j];
            }
        }
        
        exp *= 10; // 处理下一位
    }
}

基数排序 调用示例(直观展示)

int arr[] = {170, 45, 75, 90, 802, 24, 2, 66};
int n = sizeof(arr)/sizeof(arr[0]);

printf("原始数组: ");
printArray(arr, n); 

radixSort(arr, n);

printf("排序后数组: ");
printArray(arr, n); // 输出: 2 24 45 66 75 90 170 802

//流程
个位排序: 170 90 802 2 24 45 75 66
十位排序: 802 2 24 45 66 170 75 90
百位排序: 2 24 45 66 75 90 170 802

计数排序

 重点：统计元素出现次数
使用场景：数据范围不大的非负整数
时间复杂度：O(n+k)（k是数据范围）

void countingSort(int arr[], int n) {
    // 找出数组中的最大值
    int max = arr[0];
    for (int i = 1; i < n; i++) {
        if (arr[i] > max) {
            max = arr[i];
        }
    }
    
    // 创建计数数组并初始化
    int count[max+1];
    for (int i = 0; i <= max; i++) {
        count[i] = 0;
    }
    
    // 统计每个元素出现次数
    for (int i = 0; i < n; i++) {
        count[arr[i]]++;
    }
    
    // 根据计数数组重构原数组
    int index = 0;
    for (int i = 0; i <= max; i++) {
        while (count[i] > 0) {
            arr[index++] = i;
            count[i]--;
        }
    }
}

计数排序调用示例(直观展示)

 

int arr[] = {4, 2, 2, 8, 3, 3, 1};
int n = sizeof(arr)/sizeof(arr[0]);

printf("原始数组: ");
printArray(arr, n); // 输出: 4 2 2 8 3 3 1

countingSort(arr, n);

printf("排序后数组: ");
printArray(arr, n); // 输出: 1 2 2 3 3 4 8

//流程
count数组: [0,1,2,2,1,0,0,0,1] 
(表示1出现1次，2出现2次...8出现1次)

• 桶排序

重点：将数据分到有限数量的桶中，每个桶单独排序
使用场景：数据均匀分布在一定范围内
时间复杂度：O(n+k)（k是桶的数量）

// 简单桶排序实现（假设输入数据在[0,100)范围内）
void bucketSort(int arr[], int n) {
    // 创建10个桶（每个桶负责10个数的范围）
    const int bucket_num = 10;
    int buckets[bucket_num][n]; // 每个桶最多可能存储n个元素
    int bucket_sizes[bucket_num] = {0}; // 记录每个桶当前大小
    
    // 将元素分配到桶中
    for (int i = 0; i < n; i++) {
        int bucket_idx = arr[i] / 10; // 确定桶索引
        buckets[bucket_idx][bucket_sizes[bucket_idx]++] = arr[i];
    }
    
    // 对每个桶进行排序（这里使用插入排序）
    for (int i = 0; i < bucket_num; i++) {
        insertionSort(buckets[i], bucket_sizes[i]);
    }
    
    // 将排序后的桶合并回原数组
    int index = 0;
    for (int i = 0; i < bucket_num; i++) {
        for (int j = 0; j < bucket_sizes[i]; j++) {
            arr[index++] = buckets[i][j];
        }
    }
}

桶排序调用示例(直观展示)

 int arr[] = {29, 25, 3, 49, 9, 37, 21, 43};
    int n = sizeof(arr)/sizeof(arr[0]);
    int bucketSize = 5; // 桶数量
    
    printf("原始数组: ");
    for (int i = 0; i < n; i++) printf("%d ", arr[i]);
    printf("\n\n");
    
    bucketSort(arr, n, bucketSize);
    
    printf("\n最终结果: ");
    for (int i = 0; i < n; i++) printf("%d ", arr[i]);
    
//流程
原始数组: 29 25 3 49 9 37 21 43 

分桶结果:
桶0: 3 9      // 0-9.8
桶1: 25 21    // 9.8-19.6
桶2: 29       // 19.6-29.4
桶3: 37       // 29.4-39.2
桶4: 49 43    // 39.2-49

最终结果: 3 9 21 25 29 37 43 49

• 堆排序

重点：利用堆数据结构进行选择排序
使用场景：需要原地排序且O(nlogn)时间复杂度
时间复杂度：O(nlogn)

// 调整堆（大顶堆）
void heapify(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) {
        // 交换
        int temp = arr[i];
        arr[i] = arr[largest];
        arr[largest] = temp;
        
        // 递归调整受影响的子堆
        heapify(arr, n, largest);
    }
}

void heapSort(int arr[], int n) {
    // 构建堆（从最后一个非叶子节点开始）
    for (int i = n/2 - 1; i >= 0; i--) {
        heapify(arr, n, i);
    }
    
    // 一个个从堆顶取出元素
    for (int i = n-1; i > 0; i--) {
        // 将当前根（最大值）移动到数组末尾
        int temp = arr[0];
        arr[0] = arr[i];
        arr[i] = temp;
        
        // 调整剩余元素的堆
        heapify(arr, i, 0);
    }
}

 堆排序调用示例(直观展示)

int arr[] = {12, 11, 13, 5, 6, 7};
int n = sizeof(arr)/sizeof(arr[0]);

printf("原始数组: ");
printArray(arr, n); // 输出: 12 11 13 5 6 7

heapSort(arr, n);

printf("排序后数组: ");
printArray(arr, n); // 输出: 5 6 7 11 12 13

//建堆过程
初始: 12(0)
     /    \
   11(1)  13(2)
   / \  
 5(3)6(4)

调整后堆顶: 13
交换13和末尾元素7...

使用场景选择