各种排序算法的比较和c语言代码实现

排序算法是计算机科学中处理数据的一种基础操作，常见的有多种，每种都有其优缺点以及适用场景。这里简要概述几种常见的排序算法，并提供一些基本的C语言代码示例：

1. **冒泡排序（Bubble Sort）**：
- 简单易懂，但效率低，时间复杂度为O(n^2)。
- C语言代码：

     void bubble_sort(int arr[], int n) {
       for (int i = 0; i < n - 1; i++) {
         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;
           }
         }
       }
     }

2. **选择排序（Selection Sort）**：
- 比较次数较少，但交换次数多，同样为O(n^2)。
- C代码：

     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;
         }
         int temp = arr[i];
         arr[i] = arr[min_idx];
         arr[min_idx] = temp;
       }
     }

3. **插入排序（Insertion Sort）**：
- 对于部分有序的数据，效率较高，平均/最好情况为O(n)，最差为O(n^2)。
- C代码：

     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;
       }
     }

4. **快速排序（Quick Sort）**：
- 平均性能好，平均O(n log n)，但最坏情况下O(n^2)，通过分治法实现。
- C代码简化版：

     void quick_sort(int arr[], int low, int high) {
       if (low < high) {
         int pivot = partition(arr, low, high);
         quick_sort(arr, low, pivot - 1);
         quick_sort(arr, pivot + 1, high);
       }
     }
     int partition(int arr[], int low, int high) {
       // 代码省略...
     }

5. **归并排序（Merge Sort）**：
- 性能稳定，时间复杂度始终为O(n log n)，但需要额外空间。
- C代码：

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