六种排序算法C语言实现源代码

在IT领域，排序算法是计算机科学中的基础概念，尤其对于编程初学者来说，理解并掌握各种排序算法至关重要。本文将详细解析标题所提及的六种排序算法的C语言实现，并探讨其工作原理、效率和适用场景。 1. 冒泡排序（Bubble Sort） 冒泡排序是一种简单的交换排序方法。它通过不断比较相邻元素并交换位置，使得最大或最小的元素逐渐“冒”到序列的末尾。C语言实现如下： ```c void bubbleSort(int arr[], int n) { for (int i = 0; i < n - 1; i++) { for (int j = 0; j < n - 1 - i; j++) { if (arr[j] > arr[j + 1]) { int temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } } } } ``` 2. 插入排序（Insertion Sort） 插入排序通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。C语言实现如下： ```c void insertionSort(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; } } ``` 3. 归并排序（Merge Sort） 归并排序是分治策略的典型应用，将大问题分解为小问题解决。它将数组分为两半，分别排序，再合并。C语言实现如下： ```c 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); } } 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++; } } ``` 4. 快速排序（Quick Sort） 快速排序采用分治策略，选取一个基准值，将数组分为小于和大于基准值的两部分，再对这两部分进行快速排序。C语言实现如下： ```c int partition(int arr[], int l, int r) { int pivot = arr[r]; int i = l - 1; for (int j = l; j < r; j++) { if (arr[j] < pivot) { i++; int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } } int temp = arr[i + 1]; arr[i + 1] = arr[r]; arr[r] = temp; return i + 1; } void quickSort(int arr[], int l, int r) { if (l < r) { int pi = partition(arr, l, r); quickSort(arr, l, pi - 1); quickSort(arr, pi + 1, r); } } ``` 5. 希尔排序（Shell Sort） 希尔排序是对插入排序的一种优化，通过设定间隔序列，使得原本无序的序列变得局部有序，从而提高排序效率。C语言实现如下： ```c void shellSort(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; } } } ``` 6. 选择排序（Selection Sort） 选择排序每次从未排序的部分找出最小（或最大）元素，放到已排序部分的末尾。C语言实现如下： ```c 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[min_idx]; arr[min_idx] = arr[i]; arr[i] = temp; } } ``` 这六种排序算法各有特点，冒泡排序和插入排序简单直观，但效率较低；归并排序和快速排序具有较高的时间复杂度，适用于大规模数据排序；希尔排序在处理部分有序数据时效果较好；选择排序虽然简单，但不适用于大数据量。了解和掌握这些排序算法有助于提升编程能力，更好地解决实际问题。