C语言实现的常见排序算法

排序是计算机科学中非常重要的基础算法之一。无论是在数据分析、数据库查询还是图形界面中，我们都可能会遇到排序问题。本文将介绍几种常见的排序算法，并提供其C语言实现代码。排序算法的效率和应用场景有很大关系，不同的算法有不同的时间复杂度和空间复杂度。 1. 冒泡排序（Bubble Sort）

冒泡排序是最简单的排序算法之一。它通过重复交换相邻的元素，将最大或最小的元素逐渐“冒泡”到序列的一端。虽然实现简单，但其时间复杂度较高，通常不适用于大规模数据的排序。

实现逻辑：

冒泡排序的核心思想是通过不断交换相邻的元素，将较大的元素逐步“冒泡”到数组的一端。每一轮排序，都会将一个最大（或最小）元素放到正确的位置。具体步骤如下：

从数组的第一个元素开始，依次比较相邻的元素。如果前一个元素比后一个元素大，就交换它们的位置。这样，经过第一轮比较后，最大的元素被移动到数组的最后一个位置。在下一轮比较时，忽略已经排序好的部分（即已排好序的元素），只比较剩余部分，依此类推。当某一轮排序中没有发生任何交换时，说明数组已经有序，可以提前结束排序。 1.1 冒泡排序的C语言实现 #include <stdio.h> // 冒泡排序函数 void bubbleSort(int arr[], int n) { int i, j, temp; // 外层循环控制比较的轮次 for (i = 0; i < n-1; i++) { // 内层循环进行相邻元素的比较与交换 for (j = 0; j < n-i-1; j++) { // 如果当前元素大于下一个元素，则交换它们 if (arr[j] > arr[j+1]) { temp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = temp; } } } } // 打印数组的函数 void printArray(int arr[], int size) { int i; for (i = 0; i < size; i++) { printf("%d ", arr[i]); } printf("\n"); } int main() { int arr[] = {64, 34, 25, 12, 22, 11, 90}; int n = sizeof(arr)/sizeof(arr[0]); // 获取数组长度 printf("原始数组: \n"); printArray(arr, n); bubbleSort(arr, n); // 调用冒泡排序 printf("排序后的数组: \n"); printArray(arr, n); // 打印排序后的数组 return 0; } 1.2 时间复杂度： 最坏时间复杂度：O(n^2)最好时间复杂度：O(n)（当数组已经有序时） 2. 选择排序（Selection Sort）

实现逻辑：

选择排序的核心思想是每一次从未排序部分中选择一个最小（或最大）元素，并将其放到已排序部分的末尾。具体步骤如下：

从数组的第一个元素开始，假设它是最小的元素，遍历剩余部分，找到真正的最小元素。将最小元素与当前元素交换位置。继续从下一个元素开始，重复上述操作，直到整个数组有序。

与冒泡排序不同，选择排序每次只进行一次交换，即使找到最小值，也不会像冒泡排序那样进行多次交换。

2.1 选择排序的C语言实现 #include <stdio.h> // 选择排序函数 void selectionSort(int arr[], int n) { int i, j, minIndex, temp; // 外层循环每次选择一个最小值 for (i = 0; i < n-1; i++) { minIndex = i; // 假设当前元素是最小的 // 内层循环找出未排序部分中的最小元素 for (j = i+1; j < n; j++) { if (arr[j] < arr[minIndex]) { minIndex = j; // 更新最小值的索引 } } // 交换当前元素和最小元素 temp = arr[i]; arr[i] = arr[minIndex]; arr[minIndex] = temp; } } // 打印数组的函数 void printArray(int arr[], int size) { int i; for (i = 0; i < size; i++) { printf("%d ", arr[i]); } printf("\n"); } int main() { int arr[] = {64, 25, 12, 22, 11}; int n = sizeof(arr)/sizeof(arr[0]); // 获取数组长度 printf("原始数组: \n"); printArray(arr, n); selectionSort(arr, n); // 调用选择排序 printf("排序后的数组: \n"); printArray(arr, n); // 打印排序后的数组 return 0; } 2.2 时间复杂度： 最坏时间复杂度：O(n^2)最好时间复杂度：O(n^2) 3. 插入排序（Insertion Sort）

插入排序将数组分为已排序部分和未排序部分，每次取未排序部分的第一个元素，将其插入到已排序部分的合适位置，直到整个数组有序。

实现逻辑：

插入排序的核心思想是将数组分为已排序和未排序两部分，依次将未排序部分的元素插入到已排序部分的合适位置。具体步骤如下：

从第二个元素开始，将其与前面的元素进行比较，找到它应该插入的位置。将插入位置之后的元素依次右移，直到找到合适的位置。将当前元素插入到合适位置。重复上述操作，直到数组全部有序。 3.1 插入排序的C语言实现 #include <stdio.h> // 插入排序函数 void insertionSort(int arr[], int n) { int i, key, j; // 从第二个元素开始，每次将一个元素插入到已排序部分 for (i = 1; i < n; i++) { key = arr[i]; // 保存当前要插入的元素 j = i - 1; // 将已排序部分大于 key 的元素向右移动 while (j >= 0 && arr[j] > key) { arr[j+1] = arr[j]; j = j - 1; } // 将 key 插入到正确的位置 arr[j+1] = key; } } // 打印数组的函数 void printArray(int arr[], int size) { int i; for (i = 0; i < size; i++) { printf("%d ", arr[i]); } printf("\n"); } int main() { int arr[] = {12, 11, 13, 5, 6}; int n = sizeof(arr)/sizeof(arr[0]); // 获取数组长度 printf("原始数组: \n"); printArray(arr, n); insertionSort(arr, n); // 调用插入排序 printf("排序后的数组: \n"); printArray(arr, n); // 打印排序后的数组 return 0; } 3.2 时间复杂度： 最坏时间复杂度：O(n^2)最好时间复杂度：O(n)（当数组已经有序时） 4. 快速排序（Quick Sort）

快速排序是一种分治法排序算法，它通过一个基准元素将数组分为两个子数组，然后递归地排序这两个子数组。由于其平均时间复杂度较低，快速排序在实际应用中非常高效。

实现逻辑：

快速排序是一种分治算法，其核心思想是通过一个基准元素将数组分为两部分：一部分比基准元素小，另一部分比基准元素大。然后递归地对这两部分进行排序，直到整个数组有序。具体步骤如下：

选择一个基准元素（通常选择数组的第一个元素、最后一个元素或随机选择一个元素）。将数组重新排列，使得所有比基准元素小的元素都在基准元素的左边，所有比基准元素大的元素都在右边。基准元素就位后，将左子数组和右子数组递归地进行快速排序。递归的终止条件是子数组的大小为1或0。

快速排序通过分治策略来将大问题分解为小问题，因此具有较高的效率。

4.1 快速排序的C语言实现 #include <stdio.h> // 分区操作：将数组分为两个子数组 int partition(int arr[], int low, int high) { int pivot = arr[high]; // 选择最右侧元素作为基准 int i = low - 1; // i 是已排序部分的边界 // 遍历数组，将小于基准的元素放到左边，大于基准的放到右边 for (int j = low; j < high; 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); } } // 打印数组的函数 void printArray(int arr[], int size) { int i; for (i = 0; i < size; i++) { printf("%d ", arr[i]); } printf("\n"); } int main() { int arr[] = {10, 7, 8, 9, 1, 5}; int n = sizeof(arr)/sizeof(arr[0]); // 获取数组长度 printf("原始数组: \n"); printArray(arr, n); quickSort(arr, 0, n-1); // 调用快速排序 printf("排序后的数组: \n"); printArray(arr, n); // 打印排序后的数组 return 0; } 4.2 时间复杂度： 最坏时间复杂度：O(n^2)最好时间复杂度：O(n log n)平均时间复杂度：O(n log n) 5. 归并排序（Merge Sort）

归并排序也是一种分治法排序算法，它将数组分为两个子数组，分别对它们排序后再合并。归并排序是一个稳定的排序算法，适用于大规模数据。

实现逻辑：

归并排序也是一种分治算法，核心思想是将数组分成两个子数组，分别对其进行排序，然后将两个已排序的子数组合并成一个大的有序数组。具体步骤如下：

将数组递归地分割成两半，直到每个子数组只包含一个元素。然后将这些小的有序子数组逐步合并成更大的有序子数组。在合并时，始终保持两个子数组之间的有序性。

归并排序的关键操作是合并两个已排序的子数组，合并过程是线性时间复杂度。

5.1 归并排序的C语言实现 #include <stdio.h> // 合并两个已排序的子数组 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); // 合并两个已排序的子数组 } } // 打印数组的函数 void printArray(int arr[], int size) { int i; for (i = 0; i < size; i++) { printf("%d ", arr[i]); } printf("\n"); } int main() { int arr[] = {12, 11, 13, 5, 6, 7}; int n = sizeof(arr)/sizeof(arr[0]); // 获取数组长度 printf("原始数组: \n"); printArray(arr, n); mergeSort(arr, 0, n-1); // 调用归并排序 printf("排序后的数组: \n"); printArray(arr, n); // 打印排序后的数组 return 0; } 5.2 时间复杂度： 最坏时间复杂度：O(n log n)最好时间复杂度：O(n log n)平均时间复杂度：O(n log n)

---

总结

本文介绍了几种经典的排序算法，包括冒泡排序、选择排序、插入排序、快速排序和归并排序。每种排序算法都有其特定的优缺点，适用于不同的应用场景。在选择排序算法时，需要根据数据的规模、要求的时间复杂度以及是否需要稳定排序来做出决策。通过理解这些排序算法的实现和性能特点，您可以在实际开发中更加高效地选择合适的排序算法。

版权声明：本文为原创文章，转载请注明出处。