devbox
AllinToyou
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

C语言实现几种常见排序方法_c语言排序输出方法

作者：AllinToyou | 2024-03-21 03:53:52

赞

踩

c语言排序输出方法

目录

一、冒泡排序法

二、选择排序法

三、插入排序法

四、希尔排序法

五、快速排序法

六、归并排序法

七、堆排序法

八、基数排序法

九、桶排序法

一、冒泡排序法

        冒泡排序法的核心思想是比较相邻的元素，如果第一个比第二个大，就交换它们两个。对每一对相邻元素进行比较，将最大或最小的元素移动到数组末尾，直到没有任何一对数字需要比较。

  1. #include <stdio.h>
  2.  
  3. void bubble_sort(int arr[], int len) {
  4.     int i, j, temp;
  5.     for (i = 0; i < len - 1; i++) {
  6.         for (j = 0; j < len - 1 - i; j++) {
  7.             if (arr[j] > arr[j+1]) {
  8.                 temp = arr[j];
  9.                 arr[j] = arr[j+1];
  10.                 arr[j+1] = temp;
  11.             }
  12.         }
  13.     }
  14. }
  15.  
  16. int main() {
  17.     int arr[] = {5, 2, 8, 3, 1};
  18.     int len = sizeof(arr) / sizeof(int);
  19.     int i;
  20.  
  21.     printf("排序前数组元素为：");
  22.     for (i = 0; i < len; i++) {
  23.         printf("%d ", arr[i]);
  24.     }
  25.     printf("\n");
  26.  
  27.     bubble_sort(arr, len);
  28.  
  29.     printf("排序后数组元素为：");
  30.     for (i = 0; i < len; i++) {
  31.         printf("%d ", arr[i]);
  32.     }
  33.     printf("\n");
  34.  
  35.     return 0;
  36. }

        使用了一个名为 bubble_sort 的函数，该函数接受一个整型数组 arr 和数组长度 len 作为参数，对数组进行冒泡排序并修改原数组。主函数中定义了一个整型数组 arr，在使用 sizeof 获取数组长度后，调用 bubble_sort 函数对数组进行排序，最后输出排序结果。

二、选择排序法

        选择排序法的核心思想是记录未排序数组的最小值或最大值，将其与无序部分的第一个元素交换位置，直到数组完全有序。其中，一次排序会确定当前无序区内的最小值或最大值，并将该值放置在正确的有序区位置上。

  1. #include <stdio.h>
  2.  
  3. void selection_sort(int arr[], int len) {
  4.     int i, j, temp;
  5.     int min_index;
  6.     for (i = 0; i < len - 1; i++) {
  7.         min_index = i;
  8.         for (j = i + 1; j < len; j++) {
  9.             if (arr[min_index] > arr[j]) {
  10.                 min_index = j;
  11.             }
  12.         }
  13.         if (min_index != i) {
  14.             temp = arr[i];
  15.             arr[i] = arr[min_index];
  16.             arr[min_index] = temp;
  17.         }
  18.     }
  19. }
  20.  
  21. int main() {
  22.     int arr[] = {5, 2, 8, 3, 1};
  23.     int len = sizeof(arr) / sizeof(int);
  24.     int i;
  25.  
  26.     printf("排序前数组元素为：");
  27.     for (i = 0; i < len; i++) {
  28.         printf("%d ", arr[i]);
  29.     }
  30.     printf("\n");
  31.  
  32.     selection_sort(arr, len);
  33.  
  34.     printf("排序后数组元素为：");
  35.     for (i = 0; i < len; i++) {
  36.         printf("%d ", arr[i]);
  37.     }
  38.     printf("\n");
  39.  
  40.     return 0;
  41. }

        使用了一个名为 selection_sort 的函数，该函数接受一个整型数组 arr 和数组长度 len 作为参数，对数组进行选择排序并修改原数组。主函数中定义了一个整型数组 arr，在使用 sizeof 获取数组长度后，调用 selection_sort 函数对数组进行排序，最后输出排序结果。

三、插入排序法

        插入排序法的核心思想是将待排序的数组分成两部分：已排序部分和未排序部分。从未排序部分取出第一个元素，与已排序部分从后向前比较，找到其应该插入的位置并插入。重复这个过程，直到未排序部分没有元素。其中，每次排序会将新的元素插入到已排序部分合适的位置，使得已排序部分保持有序。

  1. #include <stdio.h>
  2.  
  3. void insertion_sort(int arr[], int len) {
  4.     int i, j, temp;
  5.     for (i = 1; i < len; i++) {
  6.         temp = arr[i];
  7.         j = i - 1;
  8.         while (j >= 0 && arr[j] > temp) {
  9.             arr[j+1] = arr[j];
  10.             j--;
  11.         }
  12.         arr[j+1] = temp;
  13.     }
  14. }
  15.  
  16. int main() {
  17.     int arr[] = {5, 2, 8, 3, 1};
  18.     int len = sizeof(arr) / sizeof(int);
  19.     int i;
  20.  
  21.     printf("排序前数组元素为：");
  22.     for (i = 0; i < len; i++) {
  23.         printf("%d ", arr[i]);
  24.     }
  25.     printf("\n");
  26.  
  27.     insertion_sort(arr, len);
  28.  
  29.     printf("排序后数组元素为：");
  30.     for (i = 0; i < len; i++) {
  31.         printf("%d ", arr[i]);
  32.     }
  33.     printf("\n");
  34.  
  35.     return 0;
  36. }

        使用了一个名为 insertion_sort 的函数，该函数接受一个整型数组 arr 和数组长度 len 作为参数，对数组进行插入排序并修改原数组。主函数中定义了一个整型数组 arr，在使用 sizeof 获取数组长度后，调用 insertion_sort 函数对数组进行排序，最后输出排序结果。

四、希尔排序法

        希尔排序法是插入排序法的改进版本，其核心思想是将数组分割为若干个子序列，分别进行插入排序。通过逐步减小子序列的长度，并不断对整个数组进行插入排序，使得整个数组变得有序。希尔排序法中的增量序列可以设定很多种，如 Shell 增量、Hibbard 增量、Knuth 增量等，通常采用 Shell 增量。

  1. #include <stdio.h>
  2.  
  3. void shell_sort(int arr[], int len) {
  4.     int i, j, gap;
  5.     int temp;
  6.     for (gap = len / 2; gap > 0; gap /= 2) {
  7.         for (i = gap; i < len; i++) {
  8.             temp = arr[i];
  9.             for (j = i - gap; j >= 0 && arr[j] > temp; j -= gap) {
  10.                 arr[j+gap] = arr[j];
  11.             }
  12.             arr[j+gap] = temp;
  13.         }
  14.     }
  15. }
  16.  
  17. int main() {
  18.     int arr[] = {5, 2, 8, 3, 1};
  19.     int len = sizeof(arr) / sizeof(int);
  20.     int i;
  21.  
  22.     printf("排序前数组元素为：");
  23.     for (i = 0; i < len; i++) {
  24.         printf("%d ", arr[i]);
  25.     }
  26.     printf("\n");
  27.  
  28.     shell_sort(arr, len);
  29.  
  30.     printf("排序后数组元素为：");
  31.     for (i = 0; i < len; i++) {
  32.         printf("%d ", arr[i]);
  33.     }
  34.     printf("\n");
  35.  
  36.     return 0;
  37. }

        使用了一个名为 shell_sort 的函数，该函数接受一个整型数组 arr 和数组长度 len 作为参数，对数组进行希尔排序并修改原数组。主函数中定义了一个整型数组 arr，在使用 sizeof 获取数组长度后，调用 shell_sort 函数对数组进行排序，最后输出排序结果。

五、快速排序法

        快速排序法是基于交换的排序算法，它采用了分治的思想。具体来说，每次选择一个基准值，将序列分为两个部分，左边部分都小于等于基准值，右边部分都大于等于基准值。然后递归地分别对左右两边部分进行排序，直到整个序列有序。通常采用双指针法，从左右两边同时向中间扫描找到需要交换的元素，然后进行交换。基准值的选取可以采用多种方式，如取第一个元素、取中间元素、取随机元素等，具体选取方式影响算法的效率。

  1. #include <stdio.h>
  2.  
  3. void quick_sort(int arr[], int left, int right) {
  4.     if (left >= right) {
  5.         return;
  6.     }
  7.  
  8.     int i = left, j = right;
  9.     int pivot = arr[left];
  10.     while (i < j) {
  11.         while (i < j && arr[j] >= pivot) {
  12.             j--;
  13.         }
  14.         arr[i] = arr[j];
  15.         while (i < j && arr[i] <= pivot) {
  16.             i++;
  17.         }
  18.         arr[j] = arr[i];
  19.     }
  20.     arr[i] = pivot;
  21.  
  22.     quick_sort(arr, left, i-1);
  23.     quick_sort(arr, i+1, right);
  24. }
  25.  
  26. int main() {
  27.     int arr[] = {5, 2, 8, 3, 1};
  28.     int len = sizeof(arr) / sizeof(int);
  29.     int i;
  30.  
  31.     printf("排序前数组元素为：");
  32.     for (i = 0; i < len; i++) {
  33.         printf("%d ", arr[i]);
  34.     }
  35.     printf("\n");
  36.  
  37.     quick_sort(arr, 0, len-1);
  38.  
  39.     printf("排序后数组元素为：");
  40.     for (i = 0; i < len; i++) {
  41.         printf("%d ", arr[i]);
  42.     }
  43.     printf("\n");
  44.  
  45.     return 0;
  46. }

        使用了一个名为 quick_sort 的函数，该函数接受一个整型数组 arr、左边界 left 和右边界 right 作为参数，对数组进行快速排序并修改原数组。主函数中定义了一个整型数组 arr，在使用 sizeof 获取数组长度后，调用 quick_sort 函数对数组进行排序，最后输出排序结果。

六、归并排序法

        归并排序法是基于比较的稳定排序算法，采用了分治的思想。具体来说，将待排序序列逐层划分为若干个子序列，每个子序列都是有序的，然后将相邻两个子序列进行合并，直到整个序列有序。合并过程中需要用到一个额外的数组来存储归并后的结果，最后将排序好的结果赋值给原数组。原始序列被均分成两个长度相等的子序列，直到子序列长度为1，然后将相邻两个子序列进行合并。

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. void merge(int arr[], int left, int mid, int right) {
  5.     int i = left, j = mid+1, k = 0;
  6.     int* temp = (int*) malloc(sizeof(int) * (right-left+1));
  7.     while (i <= mid && j <= right) {
  8.         if (arr[i] <= arr[j]) {
  9.             temp[k++] = arr[i++];
  10.         } else {
  11.             temp[k++] = arr[j++];
  12.         }
  13.     }
  14.     while (i <= mid) {
  15.         temp[k++] = arr[i++];
  16.     }
  17.     while (j <= right) {
  18.         temp[k++] = arr[j++];
  19.     }
  20.     for (i = left, k = 0; i <= right; i++, k++) {
  21.         arr[i] = temp[k];
  22.     }
  23.     free(temp);
  24. }
  25.  
  26. void merge_sort(int arr[], int left, int right) {
  27.     if (left >= right) {
  28.         return;
  29.     }
  30.     int mid = left + (right - left) / 2;
  31.     merge_sort(arr, left, mid);
  32.     merge_sort(arr, mid+1, right);
  33.     merge(arr, left, mid, right);
  34. }
  35.  
  36. int main() {
  37.     int arr[] = {5, 2, 8, 3, 1};
  38.     int len = sizeof(arr) / sizeof(int);
  39.     int i;
  40.  
  41.     printf("排序前数组元素为：");
  42.     for (i = 0; i < len; i++) {
  43.         printf("%d ", arr[i]);
  44.     }
  45.     printf("\n");
  46.  
  47.     merge_sort(arr, 0, len-1);
  48.  
  49.     printf("排序后数组元素为：");
  50.     for (i = 0; i < len; i++) {
  51.         printf("%d ", arr[i]);
  52.     }
  53.     printf("\n");
  54.  
  55.     return 0;
  56. }

        该程序使用了一个名为 merge 的函数，该函数接受一个整型数组 arr、左边界 left、中间位置 mid 和右边界 right 作为参数，对数组的左半部分和右半部分进行归并排序并修改原数组。在归并排序过程中，需要用到一个额外的数组来存储排序过程中产生的临时结果。主函数中定义了一个整型数组 arr，在使用 sizeof 获取数组长度后，调用 merge_sort 函数对数组进行排序，最后输出排序结果。

七、堆排序法

        堆排序法是基于比较的不稳定排序算法，采用了大根堆（或小根堆）的数据结构来实现。首先将待排序序列建立成大根堆（或小根堆），然后将根节点与最后一个节点交换位置，这时候最后一个节点已经是有序的了，再对剩余部分的序列进行堆化，得到新的根节点，再将根节点与倒数第二个节点交换位置，以此类推，不断缩小排序范围，直到整个序列有序。堆排序需要额外的空间来存储堆结构，且常数因子较大。

  1. #include <stdio.h>
  2.  
  3. void heapify(int arr[], int n, int i) {
  4.     int largest = i;
  5.     int l = 2*i+1, r = 2*i+2;
  6.     if (l < n && arr[l] > arr[largest]) {
  7.         largest = l;
  8.     }
  9.     if (r < n && arr[r] > arr[largest]) {
  10.         largest = r;
  11.     }
  12.     if (largest != i) {
  13.         int temp = arr[i];
  14.         arr[i] = arr[largest];
  15.         arr[largest] = temp;
  16.         heapify(arr, n, largest);
  17.     }
  18. }
  19.  
  20. void heap_sort(int arr[], int n) {
  21.     int i;
  22.     for (i = n/2-1; i >= 0; i--) {
  23.         heapify(arr, n, i);
  24.     }
  25.     for (i = n-1; i >= 0; i--) {
  26.         int temp = arr[0];
  27.         arr[0] = arr[i];
  28.         arr[i] = temp;
  29.         heapify(arr, i, 0);
  30.     }
  31. }
  32.  
  33. int main() {
  34.     int arr[] = {5, 2, 8, 3, 1};
  35.     int len = sizeof(arr) / sizeof(int);
  36.     int i;
  37.  
  38.     printf("排序前数组元素为：");
  39.     for (i = 0; i < len; i++) {
  40.         printf("%d ", arr[i]);
  41.     }
  42.     printf("\n");
  43.  
  44.     heap_sort(arr, len);
  45.  
  46.     printf("排序后数组元素为：");
  47.     for (i = 0; i < len; i++) {
  48.         printf("%d ", arr[i]);
  49.     }
  50.     printf("\n");
  51.  
  52.     return 0;
  53. }

        使用了一个名为 heapify 的函数和一个名为 heap_sort 的函数，分别对整型数组进行堆化和堆排序。在堆化过程中，需要通过递归地调用该函数来维护大根堆的性质；在堆排序过程中，需要先将整个数组堆化，然后逐步将最大值交换到数组末尾，并重新堆化剩余部分的数组。主函数中定义了一个整型数组 arr，在使用 sizeof 获取数组长度后，调用 heap_sort 函数对数组进行排序，最后输出排序结果。

八、基数排序法

        基数排序是一种非比较排序算法，采用了将数据按照位来比较的策略，由低位到高位依次对数据进行排序。它需要使用到计数排序或桶排序等线性时间复杂度的辅助排序算法，而且需要数据具有一定的范围限制和可比性。

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. int get_digit(int num, int radix) {
  5.     int digit = 1;
  6.     while ((num /= radix) > 0) {
  7.         digit++;
  8.     }
  9.     return digit;
  10. }
  11.  
  12. int get_num_at_digit(int num, int digit, int radix) {
  13.     int i;
  14.     for (i = 1; i < digit; i++) {
  15.         num /= radix;
  16.     }
  17.     return num % radix;
  18. }
  19.  
  20. void radix_sort(int arr[], int n, int radix) {
  21.     int i, j, k, digit, max_digit = 0;
  22.     int* count = (int*) malloc(sizeof(int) * radix);
  23.     int* bucket = (int*) malloc(sizeof(int) * n);
  24.  
  25.     for (i = 0; i < n; i++) {
  26.         digit = get_digit(arr[i], radix);
  27.         if (digit > max_digit) {
  28.             max_digit = digit;
  29.         }
  30.     }
  31.  
  32.     for (k = 1; k <= max_digit; k++) {
  33.         for (i = 0; i < radix; i++) {
  34.             count[i] = 0;
  35.         }
  36.         for (i = 0; i < n; i++) {
  37.             digit = get_num_at_digit(arr[i], k, radix);
  38.             count[digit]++;
  39.         }
  40.         for (i = 1; i < radix; i++) {
  41.             count[i] += count[i-1];
  42.         }
  43.         for (i = n-1; i >= 0; i--) {
  44.             digit = get_num_at_digit(arr[i], k, radix);
  45.             bucket[--count[digit]] = arr[i];
  46.         }
  47.         for (i = 0; i < n; i++) {
  48.             arr[i] = bucket[i];
  49.         }
  50.     }
  51.     free(count);
  52.     free(bucket);
  53. }
  54.  
  55. int main() {
  56.     int arr[] = {35, 28, 98, 45, 67, 23, 10};
  57.     int len = sizeof(arr) / sizeof(int);
  58.     int i;
  59.  
  60.     printf("排序前数组元素为：");
  61.     for (i = 0; i < len; i++) {
  62.         printf("%d ", arr[i]);
  63.     }
  64.     printf("\n");
  65.  
  66.     radix_sort(arr, len, 10);
  67.  
  68.     printf("排序后数组元素为：");
  69.     for (i = 0; i < len; i++) {
  70.         printf("%d ", arr[i]);
  71.     }
  72.     printf("\n");
  73.  
  74.     return 0;
  75. }

        该程序使用了一个名为 get_digit 的函数和一个名为 get_num_at_digit 的函数，分别用于获取一个整数的位数及某一位的数字；还使用了一个名为 radix_sort 的函数，基于计数排序的思想实现基数排序。在基数排序过程中，需要将待排序序列按照位数从低到高依次进行排序，每次排序需要使用计数排序对相应位上的数字进行排序。主函数中定义了一个整型数组 arr，在使用 sizeof 获取数组长度后，调用 radix_sort 函数对数组进行排序，最后输出排序结果。

九、桶排序法

        桶排序是一种常用的排序算法，它需要根据数据的特点构建若干个桶，将数据分配到相应的桶中并对每个桶中的数据进行排序，最后按照桶的顺序依次输出所有数据。桶排序具有线性时间复杂度，但需要额外的存储空间来存放桶。

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. void bucket_sort(int arr[], int n, int bucketSize) {
  5.     int i, j, k;
  6.     int* bucket;
  7.  
  8.     if (bucketSize <= 0) {
  9.         return;
  10.     }
  11.  
  12.     int min_value = arr[0], max_value = arr[0];
  13.     for (i = 1; i < n; i++) {
  14.         if (arr[i] < min_value) {
  15.             min_value = arr[i];
  16.         } else if (arr[i] > max_value) {
  17.             max_value = arr[i];
  18.         }
  19.     }
  20.  
  21.     int bucket_count = (max_value - min_value) / bucketSize + 1;
  22.     bucket = (int*) malloc(sizeof(int) * bucket_count);
  23.  
  24.     for (i = 0; i < bucket_count; i++) {
  25.         bucket[i] = 0;
  26.     }
  27.  
  28.     for (i = 0; i < n; i++) {
  29.         bucket[(arr[i] - min_value) / bucketSize]++;
  30.     }
  31.  
  32.     for (i = 1; i < bucket_count; i++) {
  33.         bucket[i] += bucket[i-1];
  34.     }
  35.  
  36.     int* results = (int*) malloc(sizeof(int) * n);
  37.     for (i = n-1; i >= 0; i--) {
  38.         j = (arr[i] - min_value) / bucketSize;
  39.         results[--bucket[j]] = arr[i];
  40.     }
  41.  
  42.     for (i = 0; i < n; i++) {
  43.         arr[i] = results[i];
  44.     }
  45.  
  46.     free(bucket);
  47.     free(results);
  48. }
  49.  
  50. int main() {
  51.     int arr[] = {35, 28, 98, 45, 67, 23, 10};
  52.     int len = sizeof(arr) / sizeof(int);
  53.     int i;
  54.  
  55.     printf("排序前数组元素为：");
  56.     for (i = 0; i < len; i++) {
  57.         printf("%d ", arr[i]);
  58.     }
  59.     printf("\n");
  60.  
  61.     bucket_sort(arr, len, 10);
  62.  
  63.     printf("排序后数组元素为：");
  64.     for (i = 0; i < len; i++) {
  65.         printf("%d ", arr[i]);
  66.     }
  67.     printf("\n");
  68.  
  69.     return 0;
  70. }

        使用了一个名为 bucket_sort 的函数来实现桶排序。在桶排序过程中，需要将待排序序列分配到若干个桶中，然后对每个桶中的数据进行排序，最后按照桶的顺序依次输出所有数据。主函数中定义了一个整型数组 arr，在使用 sizeof 获取数组长度后，调用 bucket_sort 函数对数组进行排序，最后输出排序结果。

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/AllinToyou/article/detail/278229
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号