当前位置:   article > 正文

常见排序算法及其C语言实现

常见排序算法及其C语言实现

排序算法在计算机科学中是一个非常重要的主题。本文将详细介绍几种常见的排序算法,包括快速排序、归并排序、堆排序、冒泡排序、选择排序、插入排序、桶排序和二分查找插入排序,并提供每种算法的C语言实现代码。

1. 快速排序(Quick Sort)

概述: 快速排序是一种基于分治法的高效排序算法。它通过选择一个“枢轴”(pivot)元素,将数组分成两部分,一部分比枢轴小,另一部分比枢轴大,然后递归地对这两部分进行排序。

时间复杂度

  • 最优情况:O(nlog⁡n)O(n \log n)O(nlogn)
  • 平均情况:O(nlog⁡n)O(n \log n)O(nlogn)
  • 最坏情况:O(n2)O(n^2)O(n2)(当每次选到的枢轴都是最小或最大的元素时)

C语言实现

  1. #include <stdio.h>
  2. void swap(int *a, int *b) {
  3. int temp = *a;
  4. *a = *b;
  5. *b = temp;
  6. }
  7. int partition(int arr[], int low, int high) {
  8. int pivot = arr[high];
  9. int i = (low - 1);
  10. for (int j = low; j <= high - 1; j++) {
  11. if (arr[j] < pivot) {
  12. i++;
  13. swap(&arr[i], &arr[j]);
  14. }
  15. }
  16. swap(&arr[i + 1], &arr[high]);
  17. return (i + 1);
  18. }
  19. void quickSort(int arr[], int low, int high) {
  20. if (low < high) {
  21. int pi = partition(arr, low, high);
  22. quickSort(arr, low, pi - 1);
  23. quickSort(arr, pi + 1, high);
  24. }
  25. }
  26. int main() {
  27. int arr[] = {10, 7, 8, 9, 1, 5};
  28. int n = sizeof(arr) / sizeof(arr[0]);
  29. quickSort(arr, 0, n - 1);
  30. printf("Sorted array: ");
  31. for (int i = 0; i < n; i++)
  32. printf("%d ", arr[i]);
  33. printf("\n");
  34. return 0;
  35. }

2. 归并排序(Merge Sort)

概述: 归并排序也是一种基于分治法的排序算法。它将数组分成两个子数组,分别排序后再合并成一个有序的数组。

时间复杂度

  • 最优情况、平均情况、最坏情况:O(nlog⁡n)O(n \log n)O(nlogn)

C语言实现

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. void merge(int arr[], int l, int m, int r) {
  4. int n1 = m - l + 1;
  5. int n2 = r - m;
  6. int L[n1], R[n2];
  7. for (int i = 0; i < n1; i++)
  8. L[i] = arr[l + i];
  9. for (int j = 0; j < n2; j++)
  10. R[j] = arr[m + 1 + j];
  11. int i = 0, j = 0, k = l;
  12. while (i < n1 && j < n2) {
  13. if (L[i] <= R[j]) {
  14. arr[k] = L[i];
  15. i++;
  16. } else {
  17. arr[k] = R[j];
  18. j++;
  19. }
  20. k++;
  21. }
  22. while (i < n1) {
  23. arr[k] = L[i];
  24. i++;
  25. k++;
  26. }
  27. while (j < n2) {
  28. arr[k] = R[j];
  29. j++;
  30. k++;
  31. }
  32. }
  33. void mergeSort(int arr[], int l, int r) {
  34. if (l < r) {
  35. int m = l + (r - l) / 2;
  36. mergeSort(arr, l, m);
  37. mergeSort(arr, m + 1, r);
  38. merge(arr, l, m, r);
  39. }
  40. }
  41. int main() {
  42. int arr[] = {12, 11, 13, 5, 6, 7};
  43. int arr_size = sizeof(arr) / sizeof(arr[0]);
  44. mergeSort(arr, 0, arr_size - 1);
  45. printf("Sorted array: ");
  46. for (int i = 0; i < arr_size; i++)
  47. printf("%d ", arr[i]);
  48. printf("\n");
  49. return 0;
  50. }

3. 堆排序(Heap Sort)

概述: 堆排序利用堆这种数据结构来实现排序。堆是一种完全二叉树,分为最大堆和最小堆。最大堆的性质是每个节点的值都不小于其子节点的值。

时间复杂度

  • 最优情况、平均情况、最坏情况:O(nlog⁡n)O(n \log n)O(nlogn)

C语言实现

  1. #include <stdio.h>
  2. void swap(int *a, int *b) {
  3. int temp = *a;
  4. *a = *b;
  5. *b = temp;
  6. }
  7. void heapify(int arr[], int n, int i) {
  8. int largest = i;
  9. int left = 2 * i + 1;
  10. int right = 2 * i + 2;
  11. if (left < n && arr[left] > arr[largest])
  12. largest = left;
  13. if (right < n && arr[right] > arr[largest])
  14. largest = right;
  15. if (largest != i) {
  16. swap(&arr[i], &arr[largest]);
  17. heapify(arr, n, largest);
  18. }
  19. }
  20. void heapSort(int arr[], int n) {
  21. for (int i = n / 2 - 1; i >= 0; i--)
  22. heapify(arr, n, i);
  23. for (int i = n - 1; i > 0; i--) {
  24. swap(&arr[0], &arr[i]);
  25. heapify(arr, i, 0);
  26. }
  27. }
  28. int main() {
  29. int arr[] = {12, 11, 13, 5, 6, 7};
  30. int n = sizeof(arr) / sizeof(arr[0]);
  31. heapSort(arr, n);
  32. printf("Sorted array: ");
  33. for (int i = 0; i < n; i++)
  34. printf("%d ", arr[i]);
  35. printf("\n");
  36. return 0;
  37. }

4. 冒泡排序(Bubble Sort)

概述: 冒泡排序通过重复地遍历待排序的数组,一次比较相邻的元素并交换它们的位置,如果它们的顺序错误的话。遍历数组的工作是重复进行直到没有再需要交换,也就是说该数组已经排序完成。

时间复杂度

  • 最优情况:O(n)O(n)O(n)(当数组已经有序)
  • 平均情况:O(n2)O(n^2)O(n2)
  • 最坏情况:O(n2)O(n^2)O(n2)

C语言实现

  1. #include <stdio.h>
  2. void bubbleSort(int arr[], int n) {
  3. for (int i = 0; i < n - 1; i++) {
  4. for (int j = 0; j < n - i - 1; j++) {
  5. if (arr[j] > arr[j + 1]) {
  6. int temp = arr[j];
  7. arr[j] = arr[j + 1];
  8. arr[j + 1] = temp;
  9. }
  10. }
  11. }
  12. }
  13. int main() {
  14. int arr[] = {64, 34, 25, 12, 22, 11, 90};
  15. int n = sizeof(arr) / sizeof(arr[0]);
  16. bubbleSort(arr, n);
  17. printf("Sorted array: ");
  18. for (int i = 0; i < n; i++)
  19. printf("%d ", arr[i]);
  20. printf("\n");
  21. return 0;
  22. }

5. 选择排序(Selection Sort)

概述: 选择排序的工作原理是每一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,直到全部待排序的数据元素排完。

时间复杂度

  • 最优情况、平均情况、最坏情况:O(n2)O(n^2)O(n2)

C语言实现

  1. #include <stdio.h>
  2. void selectionSort(int arr[], int n) {
  3. for (int i = 0; i < n - 1; i++) {
  4. int min_idx = i;
  5. for (int j = i + 1; j < n; j++) {
  6. if (arr[j] < arr[min_idx])
  7. min_idx = j;
  8. }
  9. int temp = arr[min_idx];
  10. arr[min_idx] = arr[i];
  11. arr[i] = temp;
  12. }
  13. }
  14. int main() {
  15. int arr[] = {64, 25, 12, 22, 11};
  16. int n = sizeof(arr) / sizeof(arr[0]);
  17. selectionSort(arr, n);
  18. printf("Sorted array: ");
  19. for (int i = 0; i < n; i++)
  20. printf("%d ", arr[i]);
  21. printf("\n");
  22. return 0;
  23. }

6. 插入排序(Insertion Sort)

概述: 插入排序通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。

时间复杂度

  • 最优情况:O(n)O(n)O(n)(当数组已经有序)
  • 平均情况、最坏情况:O(n2)O(n^2)O(n2)

C语言实现

  1. #include <stdio.h>
  2. void insertionSort(int arr[], int n) {
  3. for (int i = 1; i < n; i++) {
  4. int key = arr[i];
  5. int j = i - 1;
  6. while (j >= 0 && arr[j] > key) {
  7. arr[j + 1] = arr[j];
  8. j = j - 1;
  9. }
  10. arr[j + 1] = key;
  11. }
  12. }
  13. int main() {
  14. int arr[] = {12, 11, 13, 5, 6};
  15. int n = sizeof(arr) / sizeof(arr[0]);
  16. insertionSort(arr, n);
  17. printf("Sorted array: ");
  18. for (int i = 0; i < n; i++)
  19. printf("%d ", arr[i]);
  20. printf("\n");
  21. return 0;
  22. }

7. 桶排序(Bucket Sort)

概述: 桶排序是计数排序的扩展,适用于均匀分布的数据。桶排序将元素分配到有限数量的桶中,对每个桶分别排序,然后依次合并所有桶中的元素。

时间复杂度

  • 最优情况、平均情况:O(n+k)O(n + k)O(n+k)
  • 最坏情况:O(n2)O(n^2)O(n2)(当所有元素被分配到同一个桶中)

C语言实现

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. // 插入排序,用于桶排序中的桶内排序
  4. void insertionSort(int arr[], int n) {
  5. for (int i = 1; i < n; i++) {
  6. int key = arr[i];
  7. int j = i - 1;
  8. while (j >= 0 && arr[j] > key) {
  9. arr[j + 1] = arr[j];
  10. j = j - 1;
  11. }
  12. arr[j + 1] = key;
  13. }
  14. }
  15. void bucketSort(float arr[], int n) {
  16. // 创建 n 个桶
  17. struct Bucket {
  18. int count;
  19. float* values;
  20. };
  21. struct Bucket* buckets = malloc(n * sizeof(struct Bucket));
  22. for (int i = 0; i < n; i++) {
  23. buckets[i].count = 0;
  24. buckets[i].values = malloc(n * sizeof(float));
  25. }
  26. // 将元素分配到各个桶中
  27. for (int i = 0; i < n; i++) {
  28. int bucketIndex = n * arr[i];
  29. buckets[bucketIndex].values[buckets[bucketIndex].count++] = arr[i];
  30. }
  31. // 对每个桶中的元素进行排序
  32. for (int i = 0; i < n; i++) {
  33. insertionSort(buckets[i].values, buckets[i].count);
  34. }
  35. // 合并所有桶中的元素
  36. int index = 0;
  37. for (int i = 0; i < n; i++) {
  38. for (int j = 0; j < buckets[i].count; j++) {
  39. arr[index++] = buckets[i].values[j];
  40. }
  41. }
  42. // 释放内存
  43. for (int i = 0; i < n; i++) {
  44. free(buckets[i].values);
  45. }
  46. free(buckets);
  47. }
  48. int main() {
  49. float arr[] = {0.897, 0.565, 0.656, 0.1234, 0.665, 0.3434};
  50. int n = sizeof(arr) / sizeof(arr[0]);
  51. bucketSort(arr, n);
  52. printf("Sorted array: ");
  53. for (int i = 0; i < n; i++)
  54. printf("%f ", arr[i]);
  55. printf("\n");
  56. return 0;
  57. }

8. 二分查找插入排序(Binary Insertion Sort)

概述: 二分查找插入排序是插入排序的优化版,它使用二分查找来找到插入位置,从而减少比较次数。

时间复杂度

  • 最优情况:O(n)O(n)O(n)
  • 平均情况、最坏情况:O(n2)O(n^2)O(n2)

C语言实现

  1. #include <stdio.h>
  2. // 二分查找用于找到插入位置
  3. int binarySearch(int arr[], int item, int low, int high) {
  4. if (high <= low)
  5. return (item > arr[low]) ? (low + 1) : low;
  6. int mid = (low + high) / 2;
  7. if (item == arr[mid])
  8. return mid + 1;
  9. if (item > arr[mid])
  10. return binarySearch(arr, item, mid + 1, high);
  11. return binarySearch(arr, item, low, mid - 1);
  12. }
  13. // 二分查找插入排序
  14. void binaryInsertionSort(int arr[], int n) {
  15. for (int i = 1; i < n; i++) {
  16. int j = i - 1;
  17. int selected = arr[i];
  18. int loc = binarySearch(arr, selected, 0, j);
  19. while (j >= loc) {
  20. arr[j + 1] = arr[j];
  21. j--;
  22. }
  23. arr[j + 1] = selected;
  24. }
  25. }
  26. int main() {
  27. int arr[] = {37, 23, 0, 17, 12, 72, 31, 46, 100, 88, 54};
  28. int n = sizeof(arr) / sizeof(arr[0]);
  29. binaryInsertionSort(arr, n);
  30. printf("Sorted array: ");
  31. for (int i = 0; i < n; i++)
  32. printf("%d ", arr[i]);
  33. printf("\n");
  34. return 0;
  35. }

结论

通过本文,我们介绍了多种常见的排序算法,并提供了每种算法的C语言实现。每种算法有其独特的特点和适用场景,选择合适的排序算法可以根据具体需求来决定。

本文内容由网友自发贡献,转载请注明出处:【wpsshop博客】
推荐阅读
相关标签
  

闽ICP备14008679号