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

C语言最常用的八种排序方式_c语言排序

作者：羊村懒王 | 2024-03-21 03:48:23

赞

踩

c语言排序

目录

一、 排序的概念

二、常见的排序算法

 三、用代码来实现排序算法

1.直接插入排序

 2.希尔排序

3.选择排序

4.堆排序

5.冒泡排序 

6. 快速排序

 7.归并排序

8.计数排序

 四、如何选择合适的排序算法

一、 排序的概念

        排序：排序是指一串记录，按照其中的某个或某些关键字的大小，使他们递增或递减的进行排列起来的操作。（将无序变成有序）

        内部排序：数据元素全部放在内存中的排序。

        外部排序：数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序。

二、常见的排序算法

 三、用代码来实现排序算法

1.直接插入排序

        原理：最简单的排序，将元素逐个插入到已经排好序的有序列表中，从而得到一个新的、容量增1的有序表。

        图示讲解：

实现代码：

  1. #define _CRT_SECURE_NO_WARNINGS 1
  2. #include<stdio.h>
  3.  
  4. void Print(int arr[], int n)//结果打印函数
  5. {
  6. 		int i = 0;
  7. 		for (i = 0; i < n; i++)
  8. 		{
  9. 			printf("%d ", arr[i]);  
  10. 		}
  11. 		printf("\n");
  12. }
  13. void Sort_arr(int arr[], int n)
  14. {
  15. 	int tmp = 0;
  16. 	int i = 0;
  17. 	int j = 0;
  18. 	for (i = 1; i < n; i++)
  19. 	{
  20. 		tmp = arr[i];
  21. 		for (j = i - 1; j >= 0; j--)
  22. 		{
  23. 			if (tmp > arr[j])
  24. 			{
  25. 				break;
  26. 			}
  27. 			else
  28. 			{
  29. 				arr[j + 1] = arr[j];
  30. 			}
  31. 		}
  32. 		arr[j + 1] = tmp;
  33. 		Print(arr, 10);  //打印排序过程
  34. 	}
  35.  
  36. }
  37. int main()
  38. {
  39. 	int a[10] = { 12,18,2,6,8,9,34,51,-2,7 };
  40. 	Sort_arr(a, 10);
  41. 	Print(a, 10);
  42.  
  43. 	return 0;
  44. }

 运行结果：

 优点：直接插入排序在数组量较小，数组较为整齐时较快

 缺点：不稳定，要是出现较小的数字在数组的后边，则会使排序变复杂

 2.希尔排序

        原理：希尔排序是对插入排序的优化，基本思路是先选定一个整数作为增量，把待排序文件中的所有数据分组，以每个距离的等差数列为一组，对每一组进行排序，然后将增量缩小，继续分组排序，重复上述排序，直到增量为1时，排序完正好有序。整体原理是每一对分组进行排序后，整个数据就会更接近有序，当增量缩小为1 时就是插入排序，但是现在的数组非常的接近有序，移动的数据少，因此效率高，因此希尔排序又叫缩小增量排序。

        图示讲解：

                                        根据数组长度7，进行求找增量（gap）值

                                        计算出第二轮增量为1，进行直接排序

  （会进行多次预排序，只要gap>1就是预排序，当gap==1时就是直接插入排序）

                                         排出：1、2、3、5、6、8、8

实现代码：

  1. //希尔排序
  2. #define _CRT_SECURE_NO_WARNINGS 1
  3. #include<stdio.h>
  4.  
  5. void ShellSort(int* arr, int sz)
  6. {
  7. 	int count = 0;//为了看希尔排序和直接插入排序的性能比较
  8. 	int gap = sz ;//设置排序的间隔
  9. 	while (gap > 1)
  10. 	{
  11. 		//一定要保证gap最后进来循环后为1，所以对此加1
  12. 		gap = gap / 3 + 1;//gap大于1为预排序，gap==1，为直接插入排序
  13. 		for (int i = 0; i < sz - gap; i++)//这里不是一次性把一组排完，而是挨个往后，一组一个轮流排
  14. 		{
  15. 			int end = i;
  16. 			int tmp = arr[end + gap];
  17. 			while (end >= 0)
  18. 			{
  19. 				if (tmp < arr[end])
  20. 				{
  21. 					arr[end + gap] = arr[end];
  22. 					end -= gap;
  23. 					count++;
  24. 				}
  25. 				else {
  26. 					break;
  27. 				}
  28. 			}arr[end + gap] = tmp;
  29. 		}
  30.  
  31.  
  32. 	}
  33. 	printf("希尔插入排序后移次数count=%d", count);
  34. }
  35. void Print(int* arr,int sz)
  36. {
  37. 	for (int i = 0; i < sz; i++)
  38. 	{
  39. 		printf("%d ", arr[i]);
  40. 	}
  41. }
  42.  
  43. void test()
  44. {
  45. 	int arr[] = { 9,8,7,6,5,4,3,2,1,0 };
  46. 	int sz = sizeof(arr) / sizeof(arr[1]);
  47. 	ShellSort(arr, sz);
  48. 	printf("\n");
  49. 	Print(arr, sz);
  50. }
  51. int main()
  52. {
  53. 	test();
  54. 	return 0;
  55. }

运行结果：

优点：在对几乎已经排好序的数据进行操作中效率较高，可以达到线性排序的效率

缺点：希尔排序一般情况下是低效的，因为插入排序每次只能将数据移动一位

3.选择排序

        原理： 在一组需要排序的数组中，对俩俩数据之间顺序与对应顺序相反时，交换数据。基本思想是从i=0位置到 i=n-1每次通过内循环找出i位置到n-1位置的最大（小）值

        图示讲解：        

实现代码： 

   

  1. #define _CRT_SECURE_NO_WARNINGS 1
  2. #include <stdio.h>
  3.  
  4. void Print(int* arr, int n)
  5. {
  6. 	int i = 0;
  7. 	for (i = 0; i < n - 1; i++)       //打印结果
  8. 	{
  9. 		printf("%d ", arr[i]);
  10. 	}
  11. 	printf("\n");
  12. }
  13.  
  14. void Sort_arr(int* arr, int n)
  15. {
  16. 	int i = 0;
  17. 	int j = 0;
  18. 	int min = 0;
  19. 	for (i = 0; i < n - 1; i++)
  20. 	{
  21. 		min = i;
  22. 		for (j = i + 1; j < n; j++)
  23. 		{
  24. 			if (arr[j] < arr[min])     //这里是找最小的那个数，然后记下该下标
  25. 			{
  26. 				min = j;
  27. 			}
  28. 		}
  29.  
  30. 		if (i != min)         //这里如果i==min时，就不需要交换
  31. 		{
  32. 			int tmp = arr[i];
  33. 			arr[i] = arr[min];
  34. 			arr[min] = tmp;
  35. 		}
  36. 		Print(arr, 10);      //打印排序过程
  37. 	}
  38. }
  39.  
  40. int main()
  41. {
  42.  
  43. 	int arr[10] = { 2,6,1,-2,-4,9,19,37,-15,0 };
  44. 	Sort_arr(arr, 10);                              //实现排序的函数
  45. 	printf("排序后的数组:\n");
  46.  
  47. 	Print(arr, 10);            //实现打印的函数
  48.  
  49. 	return 0;
  50. }

运行结果：

4.堆排序

        原理：堆排序其实是一种树状排序，以二叉堆为例是一颗完全二叉树，（除最后一层外每一层都有俩个子节点，且非满的二叉数子节点也在左边）二叉树满足每个节点都大于等于他的子节点（大顶堆）或每个节点都小于等于他的子节点（小顶堆），根据堆的定义可以得到堆满足顶点一定是整个序列的最大值（大顶堆）或者最小值（小顶堆）。

        图解：

                                                 排升序建大堆，排降序建小堆

索引值下标：i

双亲结点的下标：parent =(i-1)/2

左孩子结点的下标 child1 = 2*i+2

右孩子结点的下标：child2 = 2*i+2

代码实现：

  1. #include <stdio.h>
  2. /*
  3.     parent(i) = (i-1)/2
  4.     left child  (i) = 2*i + 1
  5.     right child (i) = 2*i + 2
  6. */
  7.  
  8. void swap(int *a, int *b)
  9. {
  10.     int tmp;
  11.     tmp = *a;
  12.     *a = *b;
  13.     *b = tmp;
  14.     return;
  15. }
  16.  
  17. void shiftUp(int arr[], int n, int k)
  18. {
  19.     while ((k - 1) / 2 >= 0 && arr[k] > arr[(k - 1) / 2])
  20.     {
  21.         swap(&arr[k], &arr[(k - 1) / 2]);
  22.         k = (k - 1) / 2;
  23.     }
  24.     return;
  25. }
  26.  
  27. void shiftDown(int arr[], int n, int k)
  28. {
  29.     int j = 0;
  30.     while (2 * k + 1 < n)
  31.     {
  32.         j = 2 * k + 1;
  33.         if (j + 1 < n && arr[j] < arr[j + 1])
  34.         {
  35.             j++;
  36.         }
  37.         if (arr[k] < arr[j])
  38.         {
  39.             swap(&arr[k], &arr[j]);
  40.             k = j;
  41.         }
  42.         else
  43.         {
  44.             break;
  45.         }
  46.     }
  47.     return;
  48. }
  49.  
  50. void heapSort(int arr[], int n)
  51. {
  52.     int i = 0;
  53.     for (i = (n - 1 - 1) / 2; i >= 0; i--)
  54.     {
  55.         shiftDown(arr, n, i);
  56.     }
  57.     for (i = n - 1; i > 0; i--)
  58.     {
  59.         swap(&arr[0], &arr[i]);
  60.         shiftDown(arr, i, 0);
  61.     }
  62.     return;
  63. }
  64.  
  65. void printArray(int arr[], int n)
  66. {
  67.     int i;
  68.     for (i = 0; i < n; i++)
  69.     {
  70.         printf("%d ", arr[i]);
  71.     }
  72.     printf("\n");
  73.     return;
  74. }
  75. void main()
  76. {
  77.     int arr[10] = {1, 5, 9, 8, 7, 6, 3, 4, 0, 2};
  78.  
  79.     printArray(arr, 10);
  80.     heapSort(arr, 10);
  81.     printArray(arr, 10);
  82. }

 运行结果：

5.冒泡排序 

        原理：冒泡排序是最简单的排序算法，思路简单容易理解，是一种简单的交换排序，基本思想是俩俩比较相邻的关键字，如果反序则交换直到没有反序的记录为止。 

 图解：

代码实现： 

  1. #define _CRT_SECURE_NO_WARNINGS 1
  2. #include <stdio.h>
  3.  
  4. #define ARR_LEN 255 /*数组长度上限*/
  5.  
  6. void bubble_Sort(int* arr, int len)
  7. {
  8.     int i, flag, temp;
  9.     do
  10.     {
  11.         flag = 0;
  12.         for (i = 0; i < len - 1; i++)
  13.         {
  14.             if (arr[i] > arr[i + 1])
  15.             {
  16.                 temp = arr[i];
  17.                 arr[i] = arr[i + 1];
  18.                 arr[i + 1] = temp;
  19.                 flag = i + 1;
  20.             }
  21.         }
  22.         len = flag;
  23.  
  24.     } while (flag);
  25. }
  26.  
  27. int main()
  28. {
  29.  
  30.     int len = 0;
  31.     int arr[ARR_LEN] = { 0 };
  32.  
  33.     printf("please input arr len:");
  34.     scanf("%d", &len);
  35.  
  36.     printf("please input arr member......\n");
  37.     for (int j = 0; j < len; j++)
  38.     {
  39.         scanf("%d", &arr[j]);
  40.     }
  41.     puts("");
  42.  
  43.     printf("sort after is ......\n");
  44.     bubble_Sort(arr, len);
  45.     for (int j = 0; j < len; j++)
  46.     {
  47.         printf("%d  ", arr[j]);
  48.     }
  49.     putchar('\n');
  50.  
  51.     return 0;
  52. }

运行结果：

6. 快速排序

原理：基本思想是通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

图解：

 代码实现：

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. #define  N  10
  5.  
  6. //快速排序法
  7. int quick_sort(int *a, int low, int high)
  8. {
  9. 	int i = low;	//第一位
  10. 	int j = high;	//最后一位
  11. 	int key = a[i]; //将第一个数作为基准值-- 先找到一个基准值
  12.  
  13. 	//进行排序---> 最终结果就是 左面的 都比基准值小 ，右面的都比 基准值大，所以这是所有循环的结束条件
  14. 	while (i < j)
  15. 	{
  16. 		//下面的循环执行的条件是 如果右面的比基准值大，就赋一下值，否则继续向前移动
  17.                 //---如果直接把循环写成下面这样---
  18. 		//while(a[j] >= key) //如果下面的不写这个i<j,这个就出错、越界，并且排序不准--理由：
  19. 		//如果i<j,并且： 右面的值 大于 基准值 时，j往前移动一个
  20. 					//i 跟 j 的可能情况 只有 i<j i==j
  21. 		while(i < j && a[j] >= key)//i<j 是 当前while循环的结束条件，如果没有这个，i会大于j，出现越界，错误 
  22. 		{
  23. 			j--;//继续走
  24. 		}//如果不成立，也就是 a[j] <= key;右面的比key小了，那就换个位置
  25. 		//把a[j]的数据给a[i]	
  26. 		a[i] = a[j];	
  27.  
  28. 		//将事先保存好的基准值与左边的值进行比较，如果基准值大，保持不变，i往前
  29. 		//然后 判断一下这个新的a[i]，也就是之前的a[j]跟key值的关系---> 一定是 a[i]<key
  30. 		//所以把i向前移动一下，i++
  31. 		while(i < j && a[i] <= key)
  32. 		{
  33. 			i++;
  34. 		}
  35. 		//移动完以后，把新的位置的a[i]的数值 给刚才的 a[j],然后开始下一次循环
  36. 		a[j] = a[i];
  37. 	}
  38.  
  39. 	//跳出循环，将基准值放入数据a[i]中
  40. 	a[i] = key;
  41. 	//对基准值左边 的所有数据 再次进行快速查找（递归）
  42. 	if (i-1 > low) 
  43. 	{
  44. 		quick_sort(a, low, i-1);
  45. 	}
  46.  
  47. 	//对基准值右边的所有数据再次进行快速查找（递归）
  48. 	if (i+1 < high)
  49. 	{
  50. 		quick_sort(a, i+1, high);
  51. 	}
  52.  
  53. 	return 0;
  54. } 
  55.  
  56. int main(int argc, const char *argv[])
  57. {
  58. 	int a[N] = {1, 3, 5, 7, 9, 2, 4, 6, 8, 0};//先整了个数组，初始化了一堆数	
  59.  
  60. 	int i = 0;
  61. 	printf("排序前:\n");
  62. 	for(i = 0; i < N; i++)
  63. 	{
  64. 		printf("%d ", a[i]);
  65. 	}
  66. 	putchar(10);
  67.  
  68. 	//调用-快排
  69. 	quick_sort(a, 0, N-1);//数组，0 ，9
  70. 														
  71. 	printf("排序后:\n");
  72. 	for(i = 0; i < N; i++)
  73. 	{
  74. 		printf("%d ", a[i]);
  75. 	}
  76. 	putchar(10);
  77. 	
  78. 	return 0;
  79. }

 运行结果：

 7.归并排序

原理：归并排序是基于归并操作的一种排序算法，归并操作的原理就是将一组有序的子序列合并成一个完整的有序序列，即首先需要把一个序列分成多个有序的子序列，通过分解到每个子序列只有一个元素时，每个子序列都是有序的，在通过归并各个子序列得到一个完整的序列。

图解：

代码：

  1. #include <stdio.h>
  2. //实现分割操作的函数
  3. void merge_sort(int* arr, int p, int q);
  4. //实现归并操作的函数
  5. void merge(int* arr, int p, int mid, int q);
  6.  
  7. int main() {
  8.     int i = 0;
  9.     int arr[8] = { 7,5,2,4,1,6,3,0 };
  10.     //对 arr 数组中第 1 至 8 个元素进行归并排序
  11.     merge_sort(arr, 1, 8);
  12.     while (i < 8)
  13.     {
  14.         printf("%d ", arr[i]);
  15.         i++;
  16.     }
  17.     return 0;
  18. }
  19. //实现分割操作的函数，[p,q] 用于指定归并排序的区域范围，
  20. void merge_sort(int* arr, int p, int q) {
  21.     int mid;
  22.     if (arr == NULL || p > q || p == q) {
  23.         return ;
  24.     }
  25.     mid = (p + q) / 2;
  26.     //将 [p,q] 分为[p,mid] 和 [mid+1,q] 区域
  27.     merge_sort(arr, p, mid);
  28.     merge_sort(arr, mid + 1, q);
  29.     //对分好的 [p,mid] 和 [mid,q] 进行归并操作
  30.     merge(arr, p, mid, q);
  31. }
  32. //实现归并操作的函数，归并的 2 个区域分别为 [p,mid] 和 [mid+1,q]
  33. void merge(int* arr, int p, int mid, int q) {
  34.     int i,j,k;
  35.     int leftarr[100], rightarr[100];
  36.     int numL = mid - p + 1;
  37.     int numR = q - mid;
  38.     //将 arr 数组中 [p,mid] 区域内的元素逐一拷贝到 leftarr 数组中
  39.     for (i = 0; i < numL; i++) {
  40.         leftarr[i] = arr[p - 1 + i];
  41.     }
  42.     //将 arr 数组中 [mid+1,q] 区域内的元素逐一拷贝到 rightarr 数组中
  43.     leftarr[i] = 2147483647;
  44.     for (i = 0; i < numR; i++) {
  45.         rightarr[i] = arr[mid + i];
  46.     }
  47.     rightarr[i] = 2147483647;
  48.     i = 0;
  49.     j = 0;
  50.     //逐一比较 leftarr 和 rightarr 中的元素，每次将较小的元素拷贝到 arr 数组中的 [p,q] 区域内
  51.     for (k = p; k <= q; k++) {
  52.         if (leftarr[i] <= rightarr[j]) {
  53.             arr[k - 1] = leftarr[i];
  54.             i++;
  55.         }
  56.         else {
  57.             arr[k - 1] = rightarr[j];
  58.             j++;
  59.         }
  60.     }
  61. }

运行结果：

8.计数排序

原理：计数排序又称为鸽巢原理，是对哈希直接定制法变形应用，是一种稳定的算法，它的优势在于在对一定范围内的整数排序时，它的复杂度为Ο(n+k)（其中k是整数的范围），快于任何比较排序算法，当然这是一种牺牲空间换取时间的做法，而且当O(k)>O(n*log(n))的时候其效率反而不如基于比较的排序（基于比较的排序的时间复杂度在理论上的下限是O(n*log(n))，如归并排序，堆排序）

图解：

 代码：

  1. #include<stdio.h>
  2. #include<assert.h>
  3. #include<stdlib.h>
  4. //计数排序
  5. void CountSort(int* a, int len)
  6. {
  7. 	assert(a);
  8. 	//通过max和min计算出临时数组所需要开辟的空间大小
  9. 	int max = a[0], min = a[0];
  10. 	for (int i = 0; i < len; i++) {
  11. 		if (a[i] > max)
  12. 			max = a[i];
  13. 		if (a[i] < min)
  14. 			min = a[i];
  15. 	}
  16. 	//使用calloc将数组都初始化为0
  17. 	int range = max - min + 1;
  18. 	int* b = (int*)calloc(range, sizeof(int));
  19. 	//使用临时数组记录原始数组中每个数的个数
  20. 	for (int i = 0; i < len; i++) {
  21. 		//注意：这里在存储上要在原始数组数值上减去min才不会出现越界问题
  22. 		b[a[i] - min] += 1;
  23. 	}
  24. 	int j = 0;
  25. 	//根据统计结果，重新对元素进行回收
  26. 	for (int i = 0; i < range; i++) {
  27. 		while (b[i]--) {
  28. 			//注意：要将i的值加上min才能还原到原始数据
  29. 			a[j++] = i + min;
  30. 		}
  31. 	}
  32. 	//释放临时数组
  33. 	free(b);
  34. 	b = NULL;
  35. }
  36. //打印数组
  37. void PrintArray(int* a, int len)
  38. {
  39. 	for (int i = 0; i < len; i++) {
  40. 		printf("%d ", a[i]);
  41. 	}
  42. 	printf("\n");
  43. }
  44. int main()
  45. {
  46. 	int a[] = { 3, 4, 3, 2, 1, 2, 6, 5, 4, 7 };
  47. 	printf("排序前：");
  48. 	PrintArray(a, sizeof(a) / sizeof(int));
  49. 	CountSort(a, sizeof(a) / sizeof(int));
  50. 	printf("排序后：");
  51. 	PrintArray(a, sizeof(a) / sizeof(int));
  52. 	system("pause");
  53. 	return 0;
  54. }

运行结果：

 

 四、如何选择合适的排序算法

        在实际应用中，选择合适的排序算法可以根据数据规模和特点来进行判断。以下是一些常见的选择排序算法的方法：

  1. 对于小规模的数据集，可以选择简单的排序算法，如插入排序、选择排序或冒泡排序。这些算法的时间复杂度较低，适用于小规模数据的排序。

  2. 对于大规模的数据集，可以选择更高效的排序算法，如归并排序、快速排序或堆排序。这些算法的时间复杂度较低，适用于大规模数据的排序。

  3. 如果数据集中存在大量重复元素，可以考虑使用计数排序或桶排序。这些算法可以通过统计元素出现的次数或将元素分配到不同的桶中来实现排序。

  4. 如果数据集中的元素是整数，并且范围较小，可以考虑使用基数排序。基数排序按照元素的位数进行排序，可以在一定程度上提高排序的效率。

  5. 在实际应用中，还可以根据具体的需求和场景选择合适的排序算法。例如，如果需要稳定的排序结果，可以选择归并排序或计数排序。

总之，选择合适的排序算法需要考虑数据规模、特点和排序需求等因素。根据不同的情况选择合适的排序算法可以提高排序的效率和准确性。

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

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

  

闽ICP备14008679号