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

常见的八种基本排序的代码_排序代码

作者：寸_铁 | 2024-06-26 16:17:19

赞

踩

排序代码

目录

1.直接插入排序

2.希尔排序

3.选择排序

4.堆排序

5.冒泡排序

6.快速排序

7.归并排序

8.计数排序

1.直接插入排序

直接插入排序实际上就是从数组的第一位开始，每次增加一位，进行比较

第一次：下标0和下标1比较

第二次：下标0、1和下标2比较

第三次：下标0、1、2和下标3比较

依次类推，所以很明显时间复杂度就是O(N^2)

其次直接插入排序元素集合越接近有序时，效率就越高

  1. //直接插入排序
  2. void InsertSort(int* a, int n)
  3. {
  4. 	for (int i = 0; i < n - 1; ++i)
  5. 	{
  6. 		int end = i;//定义每一次的个数
  7. 		int Insert = a[end + 1];//插入的数就是end的下一位数
  8. 		while (end >= 0)
  9. 		{
  10. 			if (a[end] > Insert)
  11. 			{
  12. 				a[end + 1] = a[end];
  13. 				--end;//每比较一次end就减一次
  14. 			}
  15. 			else
  16. 			{
  17. 				break;
  18. 			}
  19. 		}
  20. 		a[end + 1] = Insert;
  21. 	}
  22. }

2.希尔排序

希尔排序法又称缩小增量法。希尔排序法的基本思想是：先选定一个整数，把待排序文件中所有记录分成个 组，所有距离为的记录分在同一组内，并对每一组内的记录进行排序。然后，取，重复上述分组和排序的工 作。当到达=1时，所有记录在统一组内排好序。

1.希尔排序就是对直接插入排序的优化

2.当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就 会很快。这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的对比。

3.希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，因此在好些树中给出的 希尔排序的时间复杂度都不固定

关于我的gap是根据Knuth提出的算法进行取值的，所以时间复杂度就暂定为

O(N^1.25) ~O(1.6 * N^1.25)

  1. void ShellSort(int* a, int n)
  2. {
  3. 	int gap = n;
  4. 	while (gap > 1)
  5. 	{
  6. 		gap = gap / 3 + 1;
  7. 		for (int i = 0; i < n - gap; ++i)
  8. 		{
  9. 			int end = i;
  10. 			int tmp = a[end + gap];
  11. 			while (end >= 0)
  12. 			{
  13. 				if (a[end] > tmp)
  14. 				{
  15. 					a[end + gap] = a[end];
  16. 					end -= gap;
  17. 				}
  18. 				else
  19. 				{
  20. 					break;
  21. 				}
  22. 			}
  23. 			a[end + gap] = tmp;
  24. 		}
  25. 	}
  26. }

3.选择排序

        每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的 数据元素排完 。

实际中很少用，仅做了解即可。

时间复杂度O(N^2)

  1. void SelectSort(int* a, int n)
  2. {
  3. 	int begin = 0, end = n - 1;
  4. 	while (begin < end)
  5. 	{
  6. 		int mini = begin, maxi = begin;
  7. 		for (int i = begin + 1; i <= end; ++i)
  8. 		{
  9. 			if (a[i] < a[mini])
  10. 				mini = i;
  11. 			if (a[i] > a[maxi])
  12. 				maxi = i;
  13. 		}
  14. 		Swap(&a[begin], &a[mini]);
  15.  
  16. 		if (begin == maxi)
  17. 			maxi = mini;
  18.  
  19. 		Swap(&a[end], &a[maxi]);
  20. 		++begin;
  21. 		--end;
  22. 	}
  23. }

4.堆排序

堆排序我们应该在学习二叉树的时候就了解过了，需要注意的点就是，排升序建大堆，排降序建小堆即可

我这里是按照升序来排的。

堆排序的时间复杂度O(NlogN)

  1. void AdjustDown(int* a, int n, int parent)
  2. {
  3. 	int child = parent * 2;
  4. 	while (child < n)
  5. 	{
  6. 		if (child + 1 < n && a[child + 1] > a[child])
  7. 			++child;
  8. 		if (a[parent] < a[child])
  9. 		{
  10. 			Swap(&a[child], &a[parent]);
  11. 			parent = child;
  12. 			child = parent * 2;
  13. 		}
  14. 		else
  15. 		{
  16. 			break;
  17. 		}
  18. 	}
  19. }
  20.  
  21. //排升序，建大堆 大堆就是从大到小建立的
  22. //排降序，建小堆 小堆就是从小到大建立的
  23. void HeapSort(int* a, int n)
  24. {
  25. 	for (int i = (n - 1 - 1) / 2; i >= 0; --i)
  26. 	{
  27. 		AdjustDown(a, n, i);
  28. 	}
  29. 	int end = n - 1;
  30. 	while (end > 0)
  31. 	{
  32. 		Swap(&a[0], &a[end]);
  33. 		AdjustDown(a, end, 0);
  34. 		--end;
  35. 	}
  36. }

5.冒泡排序

冒泡排序我们应该很熟悉，在前期c语言的学习中，我想我们接触较早的就是冒泡了

时间复杂度0(N^2)

  1. void BubbleSort(int* a, int n)
  2. {
  3. 	for (int i = 0; i < n; ++i)
  4. 	{
  5. 		for (int j = 1; j < n - i; ++j)
  6. 		{
  7. 			if (a[j] < a[j - 1])
  8. 				Swap(&a[j], &a[j - 1]);
  9. 		}
  10. 	}
  11. }

6.快速排序

快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中 的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右 子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

快排是Hoare创建的的，所以就先介绍Hoare的版本

Hoare的方法就是定义一个left，right以及一个keyi

右边的 right找比key小的值，找到之后，左边的left再开始找比key大的值，再二者都找到后，left和right进行交换，然后进行递归依次进行

挖坑法

        就是在Hoare的基础上增加一个piti位，还是right先找小的，不同于Hoare版就是，找到小的后直接和piti位进行交换，然后让right位成为坑位，然后左边找大的，找到后和piti位进行交换，然后让left位成为坑位，在循环完后，一定是left和right相遇，此时把left或right的值和key进行交换

 前后指针法

 定义两个指针，一个prev一个cur，让cur初始化比prev前一位，让cur找比key小的值，找到后和prev惊醒交换，需要注意的就是不管cur每次有没有找到比key小的值，他都是要++的

  1. //Hoare版本
  2. int PartSort1(int* a, int begin, int end)
  3. {
  4. 	int left = begin, right = end;
  5. 	int keyi = begin;
  6. 	while (left < right)
  7. 	{
  8. 		while (left < right && a[right] >= a[keyi])
  9. 			--right;
  10. 		while (left < right && a[left] <= a[keyi])
  11. 			++left;
  12. 		Swap(&a[right], &a[left]);
  13. 	}
  14. 	Swap(&a[left], &a[keyi]);
  15. 	keyi = left;
  16. 	return keyi;
  17. }
  18.  
  19. // 挖坑法
  20. int PartSort2(int* a, int begin, int end)
  21. {
  22. 	int key = a[begin];
  23. 	int piti = begin;
  24. 	while (begin < end)
  25. 	{
  26. 		// 右边找小，填到左边的坑里面去。这个位置形成新的坑
  27. 		while (begin < end && a[end] >= key)
  28. 			--end;
  29.  
  30. 		a[piti] = a[end];
  31. 		piti = end;
  32.  
  33. 		// 左边找大，填到右边的坑里面去。这个位置形成新的坑
  34. 		while (begin < end && a[begin] <= key)
  35. 			++begin;
  36.  
  37. 		a[piti] = a[begin];
  38. 		piti = begin;
  39. 	}
  40.  
  41. 	a[piti] = key;
  42. 	return piti;
  43. }
  44.  
  45.  
  46. int PartSort3(int* a, int begin, int end)
  47. {
  48. 	int prev = begin, cur = begin + 1;
  49. 	int keyi = begin;
  50. 	while (cur <= end)
  51. 	{
  52. 		if (a[cur] < a[keyi] && ++prev != cur)
  53. 			Swap(&a[prev], &a[cur]);
  54. 		++cur;
  55. 	}
  56. 	Swap(&a[prev], &a[keyi]);
  57. 	keyi = prev;
  58. 	return keyi;
  59. }
  60.  
  61. void QuickSort(int* a, int begin, int end)
  62. {
  63. 	if (begin >= end)
  64. 		return;
  65.  
  66. //N为1，2，3
  67. 	int keyi = PartSortN(a, begin, end);
  68. 	QuickSort(a, begin, keyi - 1);
  69. 	QuickSort(a, keyi + 1, end);
  70.  
  71. }

7.归并排序

归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有 序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。 

归并排序的分治过程类似于二叉树中的后序遍历，并且归并排序是一定要建立一个新的数组来进行存放，最后再拷贝到原数组中。

  1. //对于分治需要注意的就是先分治，在归并
  2. //分治类似于后序遍历。
  3. void _MergeSort(int* a, int begin, int end, int* tmp)
  4. {
  5. 	if (begin >= end)
  6. 		return;
  7. 	//分治
  8. 	int mid = (begin + end) / 2;
  9. 	_MergeSort(a, begin, mid, tmp);
  10. 	_MergeSort(a, mid + 1, end, tmp);
  11. 	//归并
  12. 	int begin1 = begin, end1 = mid;
  13. 	int begin2 = mid + 1, end2 = end;
  14. 	int i = begin1;
  15. 	while (begin1 <= end1 && begin2 <= end2)
  16. 	{
  17. 		if (a[begin1] < a[begin2])
  18. 		{
  19. 			tmp[i++] = a[begin1++];
  20. 		}
  21. 		else
  22. 		{
  23. 			tmp[i++] = a[begin2++];
  24. 		}
  25. 	}
  26. 	while (begin1 <= end1)
  27. 		tmp[i++] = a[begin1++];
  28. 	while (begin2 <= end2)
  29. 		tmp[i++] = a[begin2++];
  30. 	memcpy(a + begin, tmp + begin, (end - begin + 1) * sizeof(int));
  31. }
  32.  
  33. void MergeSort(int* a, int n)
  34. {
  35. 	int* tmp = (int*)malloc(sizeof(int) * n);
  36. 	if (tmp == NULL)
  37. 	{
  38. 		printf("malloc fail\n");
  39. 		exit(-1);
  40. 	}
  41. 	_MergeSort(a, 0, n-1, tmp);
  42. 	free(tmp);
  43. 	tmp = NULL;
  44. }

8.计数排序

计数排序的基本属于非比较排序的一类，就是不通过比较大小来进行排序的

计数排序顾名思义就是记录数组中每一种数组出现的次数，然后进行排序

1.统计每个数字出现的次数

2.按照出现次数写回原数组

开辟一个6位数的空间，为什么开辟6位数呢，因为原数组中最小的数是0，最大的数是5，期间一共是6个数，所以开辟6位空间

 

 最后写回原数组

  1. void CountSort(int* a, int n)
  2. {
  3. 	int min = a[0], max = a[0];
  4. 	for (int i = 1; i < n; ++i)
  5. 	{
  6. 		if (a[i] > max)
  7. 		{
  8. 			max = a[i];
  9. 		}
  10. 		if (a[i] < min)
  11. 		{
  12. 			min = a[i];
  13. 		}
  14. 	}
  15. 	//计算数据中最大最小数的差值
  16. 	int num = max - min + 1;
  17. 	//创建插值个数的数组
  18. 	int* tmp = (int*)malloc(sizeof(int) * num);
  19. 	if (tmp == NULL)
  20. 	{
  21. 		printf("malloc fail\n");
  22. 		exit(-1);
  23. 	}
  24. 	memset(tmp, 0,sizeof(int) * num);
  25. 	//统计次数
  26. 	for (int i = 0; i < n; ++i)
  27. 	{
  28. 		tmp[a[i] - min]++;
  29. 	}
  30. 	//回写-排序
  31. 	int j = 0;
  32. 	for (int i = 0; i < num; ++i)
  33. 	{
  34. 		while (tmp[i]--)
  35. 		{
  36. 			a[j++] = i + min;
  37. 		}
  38. 	}
  39. }

 但要知道非比较排序的局限性

1.适用于整数形式，若是浮点型，字符串就显得不太合适

2.如果数据范围很大（最大最小值的差值很大）空间复杂度就会很大，不太合适

例如本数组中最大的是1009，最小的是2，差值位1008，但发现有很多的位置就没有值，这就造成了很大空间的浪费

再例如 

虽说这样可以减少空间浪费，但还是会发现其局限性

本章节只是简单的介绍了下这八种排序，主要是说明其主要的代码. 

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

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

  

闽ICP备14008679号