八大经典排序算法

八大经典排序算法

目录

1. 算法概览
2. 算法详解
   • 冒泡排序
   • 选择排序
   • 插入排序
   • 希尔排序
   • 归并排序
   • 快速排序
   • 堆排序
   • 计数排序
3. 性能对比

1. 算法概览

2. 算法详解

2.1 冒泡排序

基本思想：通过相邻元素比较交换，使最大元素"浮"到末尾
动图演示：气泡从水底逐渐上浮的过程

void bubble_sort(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]) {
                swap(&arr[j], &arr[j+1]);
                swapped = 1;
            }
        }
        if (!swapped) break; // 提前终止优化
    }
}

2.2 选择排序

基本思想：每次选择最小元素放到已排序序列末尾

void selection_sort(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;
        }
        swap(&arr[i], &arr[min_idx]);
    }
}

2.3 插入排序

基本思想：将未排序元素插入已排序序列合适位置

void insertion_sort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i-1;
        while (j >= 0 && arr[j] > key) {
            arr[j+1] = arr[j];
            j--;
        }
        arr[j+1] = key;
    }
}

2.4 希尔排序

基本思想：分组插入排序，逐步缩小间隔

void shell_sort(int arr[], int n) {
    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;
        }
    }
}

2.5 归并排序

基本思想：分治法，先拆分再合并有序子序列

void merge(int arr[], int l, int m, int r) {
    // 合并操作实现
}

void merge_sort(int arr[], int l, int r) {
    if (l < r) {
        int m = l + (r - l)/2;
        merge_sort(arr, l, m);
        merge_sort(arr, m+1, r);
        merge(arr, l, m, r);
    }
}

2.6 快速排序

基本思想：选取基准值进行分区排序

int partition(int arr[], int low, int high) {
    int pivot = arr[high];
    int i = low - 1;
    for (int j = low; j < high; j++) {
        if (arr[j] < pivot) {
            i++;
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i+1], &arr[high]);
    return i+1;
}

void quick_sort(int arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quick_sort(arr, low, pi-1);
        quick_sort(arr, pi+1, high);
    }
}

2.7 堆排序

基本思想：利用堆结构进行选择排序

void heapify(int arr[], int n, int i) {
    // 堆调整实现
}

void heap_sort(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--) {
        swap(&arr[0], &arr[i]);
        heapify(arr, i, 0);
    }
}

2.8 计数排序

适用场景：整数排序，数据范围较小

void counting_sort(int arr[], int n) {
    int max = arr[0], min = arr[0];
    for (int i = 1; i < n; i++) {
        if (arr[i] > max) max = arr[i];
        if (arr[i] < min) min = arr[i];
    }
    
    int range = max - min + 1;
    int *count = calloc(range, sizeof(int));
    
    for (int i = 0; i < n; i++)
        count[arr[i] - min]++;
    
    int idx = 0;
    for (int i = 0; i < range; i++) {
        while (count[i]--) 
            arr[idx++] = i + min;
    }
    free(count);
}

3. 性能对比

选择建议：

• 小规模数据：插入排序
• 通用场景：快速排序
• 稳定性要求：归并排序
• 内存敏感：堆排序
• 特殊场景：计数排序（数据范围小）

完整代码实现建议在本地IDE中测试运行，理解算法原理后尝试手写实现