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

【数据结构】——常见排序算法（演示图+代码+算法分析）_数据结构排序算法程序

作者：繁依Fanyi0 | 2024-04-22 04:34:10

赞

踩

数据结构排序算法程序

目录

1.  常见排序算法

1.2 稳定性

2.  常见排序算法的实现

2.1 插入排序

2.1.1基本思想

2.1.2代码

2.1.4算法分析

 2.2 希尔排序

2.2.1基本思想

2.2.2代码

2.2.3演示图

 2.2.4算法分析

2.3 选择排序

2.3.1基本思想

2.3.2代码

2.3.3演示图

2.3.4算法分析

2.4 堆排序

2.4.1基本思想

 2.4.2代码

2.4.3演示图

2.4.4算法分析 

 2.5 冒泡排序

2.5.1基本思想

2.5.2代码 

2.5.3演示图

 2.5.4算法分析

 2.6 快速排序

 2.6.1基本思想

2.6.2代码(递归实现)

2.6.3 演示图

2.6.4算法分析 

2.6.5三数取中

2.6.6挖坑法

2.6.7前后指针法 

2.6.8快排的非递归实现

 3.  完整代码：

 Sort.h

Stack.h 

Sort.c 

Stack.c 

 test.c

运行结果截图

1.  常见排序算法

1.2 稳定性

稳定性指的是在排序过程中，相等元素的相对顺序是否会改变。如果排序算法是稳定的，则相等元素的相对位置在排序后会保持不变；如果排序算法是不稳定的，则相等元素的相对位置有可能会改变。

2.  常见排序算法的实现

2.1 插入排序

2.1.1基本思想

插入排序：把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列 。它的思想是将数据分为已排序区和未排序区。例如，实际中玩扑克牌的时候，就用到了直接插入排序。

2.1.2代码

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

2.1.3演示图

首先，我们把第一个数据看作已排序区，剩余的数据看作未排序区。

然后，我们逐个地将未排序区的数据插入到已排序区的合适位置。插入的过程就像是打扑克牌时，我们将新抓到的牌插入到手中已排序好的牌中的正确位置。

具体来说，我们从第二个数据开始，将它与已排序区的最后一个数据比较。如果这个数据比最后一个数据小（或者大，具体情况由你决定），就把它插入到已排序区的合适位置，并将已排序区中的其他数据向后移动一个位置。

然后，我们继续取下一个未排序区的数据，再次与已排序区的数据进行比较并插入到合适位置。我们不断重复这个过程，直到所有的数据都被插入到已排序区。

通过这种方式，每个数据在插入过程中都会找到自己的位置，最终形成一个完整的有序序列。

总结起来，插入排序就是逐个将未排序的数据插入到已排序的合适位置，直到所有数据都被插入完成。

插入排序的优点是简单易懂，适用于小型数据集或已经部分有序的数据集。但对于大型乱序的数据集来说，插入排序的效率可能不如其他更高级的排序算法。

2.1.4算法分析

1. 元素集合越接近有序，直接插入排序算法的时间效率越高

2. 时间复杂度：O(N^2)

3. 空间复杂度：O(1)，它是一种稳定的排序算法

4. 稳定性：稳定

 2.2 希尔排序

2.2.1基本思想

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

2.2.2代码

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

2.2.3演示图

  • 预排序时：
  • gap越大，大的数可以更快得到后面，小的可以更快得到前面，越不接近有序；
  • gap越小，数据跳动越慢，越接近有序。 

 2.2.4算法分析

  1. 希尔排序是对直接插入排序的优化。
  2. 当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就 会很快。这样整体而言，可以达到优化的效果。
  3. 时间复杂度O(N^1.3)
  4. 稳定性：不稳定

2.3 选择排序

2.3.1基本思想

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

2.3.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. 			{
  11. 				mini = i;
  12. 			}
  13. 			if (a[i] > a[maxi])
  14. 			{
  15. 				maxi = i;
  16. 			}
  17.  
  18. 		}
  19. 		Swap(&a[begin], &a[mini]);
  20. 		if (maxi == begin)
  21. 		{
  22. 			maxi = mini;
  23. 		}
  24. 		Swap(&a[end], &a[maxi]);
  25. 		--end;
  26. 		++begin;
  27. 	}
  28. }

由于最小的元素下标begin可能会与最大的元素下标重合，那么在执行Swap(&a[begin], &a[mini]);语句之后，begin的值就会变成mini的值，如果接下来直接执行Swap(&a[end], &a[maxi]);那么排序就会出现错误，所以在它们之间加入了一个判断语句。

2.3.3演示图

（小的数据往前放）

  1. 把第1个数据当作最小元素
  2. 遍历数组中在这个最小元素之后的数据，找出比这个元素还要小的元素
  3. 交换
  4. 重复上述过程 

2.3.4算法分析

  1. 直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用
  2.  时间复杂度：O(N^2)
  3.  空间复杂度：O(1)
  4.  稳定性：不稳定

2.4 堆排序

2.4.1基本思想

  1. 构建最大堆（或最小堆）：将待排序的数组看作一个完全二叉树，根据堆的定义，可以通过从最后一个非叶子节点开始，逐层向上进行调整，使得每个父节点的值大于（或小于）其子节点的值。这个过程称为构建最大堆（或最小堆）。

  2. 排序：将构建好的最大堆（或最小堆）中的根节点与数组的最后一个元素交换位置，即将最大值（或最小值）放到数组的末尾。然后，将剩下的 n-1 个元素重新构建成一个最大堆（或最小堆），再次将堆顶元素与当前的末尾元素交换位置。重复这个过程，直到所有的元素都排好序。 

  3. 升序，建大堆；降序，建小堆。

 2.4.2代码

  1. void Swap(int* p1, int* p2)
  2. {
  3. 	int tmp = *p1;
  4. 	*p1 = *p2;
  5. 	*p2 = tmp;
  6. }
  7.  
  8. void AdjustDown(int* a, int n, int parent)
  9. {
  10. 	int child = parent * 2 + 1;
  11. 	while (child<n)
  12. 	{
  13. 		//确认child指向大的那个孩子
  14. 		if (child + 1 < n && a[child + 1] > a[child])
  15. 		{
  16. 			++child;
  17. 		}
  18. 		//孩子大于父亲，交换，继续向下调整
  19. 		//孩子小于父亲，则调整结束
  20. 		if (a[child] > a[parent])
  21. 		{
  22. 			Swap(&a[child], &a[parent]);
  23. 			parent = child;
  24. 			child = parent * 2 + 1;
  25. 		}
  26. 		else
  27. 		{
  28. 			break;
  29. 		}
  30. 	}
  31. }
  32.  
  33. void HeapSort(int* a, int n)
  34. {
  35. 	//向下调整--O(N)
  36. 	//升序，建大堆
  37. 	for (int i = (n - 1 - 1) / 2; i >= 0; --i)
  38. 	{
  39. 		AdjustDown(a, n, i);
  40. 	}
  41.  
  42. 	//O(N*logN)
  43. 	int end = n - 1;
  44. 	while (end > 0)
  45. 	{
  46. 		Swap(&a[0], &a[end]);
  47. 		AdjustDown(a, end, 0);
  48. 		--end;
  49. 	}
  50. }
  51.  
  52. int main()
  53. {
  54.     int a[] = { 9,8,7,6,5,4,3,2,1,5,3,1,0,4,-1,-2,-1 };
  55. 	HeapSort(a, sizeof(a) / sizeof(int));
  56.     //打印数组数据
  57.     return 0;
  58. }

2.4.3演示图

在这里我就不演示了，在之前写的博客中有：【数据结构】二叉树——堆_@简单就好的博客-CSDN博客

以最大堆为例，首先建立一个大根堆

在排序过程中，每次将堆顶元素与当前堆的最后一个元素进行交换后，最后一个元素不看做堆里面的元素，再通过对n-1个元素向下调整操作来维护堆的性质。
这样，每次交换之后，最大的元素就被放置在了数组的末尾位置。随着排序的进行，每次交换都会将当前堆中的最大值移动到数组的末尾，
所以最后每次的最后一个数是最大的。经过多次迭代，整个数组就会按照从小到大的顺序排序完成

2.4.4算法分析 

  1. 堆排序使用堆来选数，效率就高了很多。
  2.  时间复杂度：O(N*logN)
  3.  空间复杂度：O(1)
  4.  稳定性：不稳定 

 2.5 冒泡排序

2.5.1基本思想

通过相邻元素之间的比较和交换，逐渐将最大（或最小）的元素“冒泡”到正确的位置上。

2.5.2代码 

  1. void Swap(int* p1, int* p2)
  2. {
  3. 	int tmp = *p1;
  4. 	*p1 = *p2;
  5. 	*p2 = tmp;
  6. }
  7.  
  8. void BubbleSort(int* a, int n)
  9. {
  10. 	for (int j = 0; j < n; ++j)
  11. 	{
  12. 		int exchange = 0;
  13. 		for (int i = 1; i < n - j; ++i)
  14. 		{
  15. 			if (a[i - 1] > a[i])
  16. 			{
  17. 				Swap(&a[i - 1], &a[i]);
  18. 				exchange = 1;
  19. 			}
  20. 		}
  21. 		//一趟冒泡过程中，如果没有发生交换，说明已经有序
  22. 		if (exchange == 0)
  23. 		{
  24. 			break;
  25. 		}
  26. 	}
  27.  
  28. }
  29.  
  30. int main()
  31. {
  32.     int a[] = { 9,5,4,0,2,1,3,7,6,8};
  33. 	BubbleSort(a, sizeof(a) / sizeof(int));
  34.     //打印数组数据
  35.     return 0;
  36. }

冒泡排序代码中，内循环表示一趟排序，即进行一趟冒泡排序；i < n - j 表示前n-j个元素进行冒泡排序；exchange表示如果在一趟排序后exhange=0,即没有对数据进行新的顺序改动，则有序。

2.5.3演示图

 

 2.5.4算法分析

  1. 冒泡排序是一种非常容易理解的排序
  2. 时间复杂度：O(N^2)
  3. 空间复杂度：O(1)
  4. 稳定性：稳定

 2.6 快速排序

 2.6.1基本思想

任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

2.6.2代码(递归实现)

  1. //Hoare
  2. int PartSort1(int* a, int begin, int end)
  3. {
  4. 	int left = begin, right = end;
  5. 	int keyi = left;
  6. 	while (left < right)
  7. 	{
  8. 		//右边先走，找小
  9. 		while (left < right && a[right] >= a[keyi])
  10. 		{
  11. 			--right;
  12. 		}
  13.  
  14. 		while (left < right && a[left] <= a[keyi])
  15. 		{
  16. 			++left;
  17. 		}
  18. 		Swap(&a[left], &a[right]);
  19. 	}
  20. 	Swap(&a[left], &a[keyi]);
  21. 	
  22. 	keyi = left;            
  23. 	return keyi;
  24. }
  25.  
  26. void QuickSort(int* a, int begin, int end)
  27. {
  28. 	if (begin >= end)
  29. 	{
  30. 		return;
  31. 	}
  32.  
  33. 		int keyi = PartSort1(a, begin, end);
  34. 		//[begin,keyi-1] keyi[keyi+1,end]
  35. 		QuickSort(a, begin, keyi - 1);
  36. 		QuickSort(a, keyi + 1, end);
  37. }
  38.  
  39. int main()
  40. {
  41.     int a[] = { 6,1,2,7,9,3,4,5,8,10};
  42. 	QuickSort(a, 0, sizeof(a) / sizeof(int)-1);//sizeof(a) / sizeof(int) - 1 是为了获取数组 a 的元素个数，并将其减1作为快速排序的结束索引。
  43. 	
  44.     return 0;
  45. }

第一趟快排排好了key的位置，并且key将数组分为左右两个区间，接下来就和二叉树的递归差不多了。 

2.6.3 演示图

  1.  选取最左边的为key值，
  2. 右边先走，找到比key值小的值，停下；
  3. 左边走，找到比key值大的值，停下
  4. 交换left和right位置的数值，重复2，3，4过程，直到相遇
  5. 相遇时，相遇位置的值与key位置的值交换，重复上述过程

 

2.6.4算法分析 

  1. 快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序
  2. 时间复杂度：O(N*logN)
  3. 空间复杂度：O(logN)
  4. 稳定性：不稳定 

 此外,key值的位置尤为关键，如果面对的是一个有序的数据，key值仍然取的是最最左边的值的话，此时的时间复杂度会达到O(N^2).

所以就有了，key值的三数取中 ：

2.6.5三数取中

为什么要使用三数取中法呢？这是因为快速排序的性能高度依赖于关键值的选择。如果每次都选择最大或最小的元素作为关键值，会导致分区极不平衡，使得快速排序的效率大大降低，时间复杂度接近O(n^2)。而通过选择较为中间的元素作为关键值，可以有效避免最坏情况的发生，减少排序的比较和交换次数，提高快速排序的效率。

三数取中后，快排瞬间从最坏变成最好，快排几乎不会出现最坏的情况。快排的时间复杂度可以认为时O(N*logN)

  1. //三数取中
  2. //begin  mid  end
  3. int GetMidIndex(int* a, int begin, int end)
  4. {
  5. 	int mid = (end - begin) / 2;
  6. 	if (a[begin] < a[mid])
  7. 	{
  8. 		if (a[begin] > a[end])
  9. 		{
  10. 			return begin;
  11. 		}
  12. 		else if (a[mid] < a[end])
  13. 		{
  14. 			return mid;
  15. 		}
  16. 		else
  17. 		{
  18. 			return end;
  19. 		}
  20. 	}
  21. 	else//a[begin]>a[mid]
  22. 	{
  23. 		if (a[mid] > a[end])
  24. 		{
  25. 			return mid;
  26. 		}
  27. 		else if (a[begin] < a[end])
  28. 		{
  29. 			return begin;
  30. 		}
  31. 		else
  32. 		{
  33. 			return end;
  34. 		}
  35. 	}
  36. }

2.6.6挖坑法

先将第一个数据存放在临时变量key中，形成一个坑位；右边找比key小的值，找到后把该位置的值赋值到坑位中，自身的位置形成新的坑位；左边找比key大的值，找到后把该位置的值赋值到坑位中，自身的位置新的坑位；当相遇时将key的值放到相遇的位置；重复上述过程。

代码

  1. //挖坑法
  2. int PartSort2(int* a, int begin, int end)
  3. {
  4. 	int mid = GetMidIndex(a, begin, end);
  5. 	Swap(&a[begin], &a[mid]);
  6.  
  7. 	int left = begin, right = end;
  8. 	int keyi = a[left];
  9. 	int hole = left;
  10. 	while (left < right)
  11. 	{
  12. 		while (left < right && a[right] >= keyi)
  13. 		{
  14. 			--right;
  15. 		}
  16. 		a[hole] = a[right];
  17. 		hole = right;
  18. 		while (left < right && a[left] <= keyi)
  19. 		{
  20. 			++left;
  21. 		}
  22. 		a[hole] = a[left];
  23. 		hole = left;
  24. 	}
  25. 	a[hole] = keyi;
  26. 	return hole;
  27. }
  28.  
  29. void QuickSort(int* a, int begin, int end)
  30. {
  31. 	if (begin >= end)
  32. 	{
  33. 		return;
  34. 	}
  35. 	if ((end - begin + 1) < 15)
  36. 	{
  37. 		//小区间用直接插入代替，减少递归调用次数
  38. 		InsertSort(a + begin, end-begin+1);
  39. 	}
  40. 	else
  41. 	{
  42. 		int keyi = PartSort2(a, begin, end);
  43. 		//[begin,keyi-1] keyi[keyi+1,end]
  44. 		QuickSort(a, begin, keyi - 1);
  45. 		QuickSort(a, keyi + 1, end);
  46. 	}
  47. }
  48.  
  49. int main()
  50. {
  51.     int a[] = { 6,1,2,7,9,3,4,5,8,10};
  52. 	QuickSort(a, 0, sizeof(a) / sizeof(int)-1);
  53.     //打印
  54.     return 0;
  55. }

演示图

2.6.7前后指针法 

代码

  1. int PartSort3(int *a,int begin,int end)
  2. {
  3. 	int mid = GetMidIndex(a, begin, end);
  4. 	Swap(&a[begin], &a[mid]);
  5.  
  6. 	int keyi = begin;
  7. 	int prev = begin, cur = begin + 1;
  8. 	while (cur <= end)
  9. 	{
  10. 		if (a[cur] < a[keyi] && ++prev != cur)
  11. 		{
  12. 			Swap(&a[prev], &a[cur]);
  13. 		}
  14. 		++cur;
  15. 	}
  16. 	Swap(&a[prev], &a[keyi]);
  17. 	keyi = prev;
  18. 	return keyi;
  19. }
  20.  
  21. void QuickSort(int* a, int begin, int end)
  22. {
  23. 	if (begin >= end)
  24. 	{
  25. 		return;
  26. 	}
  27. 	if ((end - begin + 1) < 15)
  28. 	{
  29. 		//小区间用直接插入代替，减少递归调用次数
  30. 		InsertSort(a + begin, end-begin+1);
  31. 	}
  32. 	else
  33. 	{
  34. 		int keyi = PartSort3(a, begin, end);
  35. 		//[begin,keyi-1] keyi[keyi+1,end]
  36. 		QuickSort(a, begin, keyi - 1);
  37. 		QuickSort(a, keyi + 1, end);
  38. 	}
  39. }
  40.  
  41. int main()
  42. {
  43.     int a[] = { 6,1,2,7,9,3,4,5,8,10};
  44. 	QuickSort(a, 0, sizeof(a) / sizeof(int)-1);
  45.     //打印
  46.     return 0;
  47. }

 演示图

1、cur找比key值小，找到后停下来

2、++prev,交换cur位置的值和prev位置的值

3、cur越界后，交换key位置的值和 prev位置的值

2.6.8快排的非递归实现

由于快速排序的递归实现每次递归都要开辟栈帧，当数据量大到一定程度可能会造成栈溢出，所以可以有快排的非递归实现。

可以用栈结构或者队列对数据进行存储和释放，此处用栈。

代码

  1. //快排非递归实现
  2. void QuickSortR(int* a, int begin, int end)
  3. {
  4. 	ST st;
  5. 	StackInit(&st);
  6. 	StackPush(&st, begin);
  7. 	StackPush(&st, end);
  8.  
  9. 	while (!StackEmpty(&st))
  10. 	{
  11. 		int right = StackTop(&st);
  12. 		StackPop(&st);
  13. 		int left = StackTop(&st);
  14. 		StackPop(&st);
  15.  
  16. 		int keyi = PartSort3(a, left, right);
  17. 		if (keyi + 1 < right)                 //处理前面的数据时，后面的数据先进栈
  18. 		{
  19. 			StackPush(&st, keyi + 1);
  20. 			StackPush(&st, end);
  21. 		}
  22. 		if (left < keyi - 1)
  23. 		{
  24. 			StackPush(&st, left);
  25. 			StackPush(&st, keyi - 1);
  26. 		}
  27. 	}
  28. 	StackDestroy(&st);
  29. }
  30.  
  31. int main()
  32. {
  33.     int a[] = { 6,1,2,7,9,3,4,5,8,10,8 };
  34. 	QuickSortR(a, 0, sizeof(a) / sizeof(int) - 1);
  35. 	//打印数组元素
  36.     return 0;
  37. }

实现的思想和递归的思想一样，用栈记录数组对应的下标：首先数组第一个元素下标和最后一个元素下标入栈，进入while循环，出栈，然后执行第一趟快排并返回keyi的下标；

此时key值把数组分为左边小和右边大的两个区间；

然后由于栈是先进后出的结构，我们先处理左区间的值，所以先入右区间的第一个数的下标(keyi+1)和右区间最后一个数的下标end，再入左区间的left和keyi-1，这样出栈的时候就可以先出左区间的值的下标了。

演示图

 例如上图中，数组有10个值，数组第一个元素下标0和最后一个元素9先入栈，然后出栈，调用快速排序函数并返回keyi的下标；然后右区间第一个元素的下标6和最后一个元素下标9入栈，左区间第一个元素下标0和最后一个元素下标4入栈，然后出栈，对左区间进行快速排序......

 3.  完整代码：

 Sort.h

  1. #pragma once
  2. #include<stdio.h>
  3. #include<stdlib.h>
  4. #include<time.h>
  5.  
  6. void PrintArray(int* a, int n);//打印
  7. void InsertSort(int* a, int n);//插入排序
  8. void ShellSort(int* a, int n);
  9. void HeapSort(int* a, int n);
  10. void SelectSort(int* a, int n);
  11. void BublbleSort(int* a, int n);
  12. void QuickSort(int* a, int begin, int end);
  13. void QuickSortNonR(int* a, int begin, int end);

Stack.h 

  1. #pragma once
  2. #include<stdio.h>
  3. #include<assert.h>
  4. #include<stdbool.h>
  5. #include<stdlib.h>
  6.  
  7. typedef int STDatetype;
  8. typedef struct Stack
  9. {
  10. 	STDatetype* a;
  11. 	int capacity;
  12. 	int top;                 //初始化为0,表示栈顶位置下一个位置的下标
  13. }ST;
  14.  
  15. void StackInit(ST* ps);
  16. void StackDestroy(ST* ps);
  17. void StackPush(ST* ps,STDatetype x);
  18. void StackPop(ST* ps);
  19.  
  20. STDatetype StackTop(ST* ps);
  21.  
  22. bool StackEmpty(ST* ps);
  23. int StackSize(ST* ps);
  24.

Sort.c 

  1. #define  _CRT_SECURE_NO_WARNINGS
  2. #include"Sort.h"
  3. #include"Stack.h"
  4.  
  5. void PrintArray(int* a, int n)
  6. {
  7. 	for (int i = 0; i < n; ++i)
  8. 	{
  9. 		printf("%d ", a[i]);
  10. 	}
  11. 	printf("\n");
  12. }
  13.  
  14. void InsertSort(int* a, int n)
  15. {
  16. 	for (int i = 0; i < n-1; ++i)
  17. 	{
  18. 		int end = i;
  19. 		int tmp = a[end + 1];
  20. 		while (end>=0)
  21. 		{
  22. 			if (tmp<a[end])
  23. 			{
  24. 				a[end + 1] = a[end];
  25. 				--end;
  26. 			}
  27. 			else
  28. 			{
  29. 				break;
  30. 			}
  31. 		}
  32. 		a[end + 1] = tmp;
  33. 	}
  34. }
  35.  
  36. //O(N^1.3)
  37. void ShellSort(int* a, int n)
  38. {
  39. 	int gap = n;
  40. 	while (gap > 1)
  41. 	{
  42. 		gap = gap / 3 + 1;
  43.  
  44. 		for (int i = 0; i < n - gap; ++i)
  45. 		{
  46. 			int end = i;
  47. 			int tmp = a[end + gap];
  48. 			while (end >= 0)
  49. 			{
  50. 				if (tmp < a[end])
  51. 				{
  52. 					a[end + gap] = a[end];
  53. 					end -= gap;
  54. 				}
  55. 				else
  56. 				{
  57. 					break;
  58. 				}
  59. 			}
  60. 			a[end + gap] = tmp;
  61. 		}
  62. 	}
  63.  
  64. }
  65.  
  66. void Swap(int* p1, int* p2)
  67. {
  68. 	int tmp = *p1;
  69. 	*p1 = *p2;
  70. 	*p2 = tmp;
  71. }
  72.  
  73. void AdjustDown(int* a, int n, int parent)
  74. {
  75. 	int child = parent * 2 + 1;
  76. 	while (child<n)
  77. 	{
  78. 		//确认child指向大的那个孩子
  79. 		if (child + 1 < n && a[child + 1] > a[child])
  80. 		{
  81. 			++child;
  82. 		}
  83. 		//孩子大于父亲，交换，继续向下调整
  84. 		//孩子小于父亲，则调整结束
  85. 		if (a[child] > a[parent])
  86. 		{
  87. 			Swap(&a[child], &a[parent]);
  88. 			parent = child;
  89. 			child = parent * 2 + 1;
  90. 		}
  91. 		else
  92. 		{
  93. 			break;
  94. 		}
  95. 	}
  96. }
  97.  
  98. //O(N*logN)
  99. //在排序过程中，每次将堆顶元素与当前堆的最后一个元素进行交换后，再通过向下调整操作来维护堆的性质。
  100. //这样，每次交换之后，最大的元素就被放置在了数组的末尾位置。随着排序的进行，每次交换都会将当前堆中的最大值移动到数组的末尾，
  101. //所以最后每次的最后一个数是最大的。经过多次迭代，整个数组就会按照从小到大的顺序排序完成
  102. void HeapSort(int* a, int n)
  103. {
  104. 	//向下调整--O(N)
  105. 	//升序，建大堆
  106. 	for (int i = (n - 1 - 1) / 2; i >= 0; --i)
  107. 	{
  108. 		AdjustDown(a, n, i);
  109. 	}
  110.  
  111. 	//O(N*logN)
  112. 	int end = n - 1;
  113. 	while (end > 0)
  114. 	{
  115. 		Swap(&a[0], &a[end]);
  116. 		AdjustDown(a, end, 0);
  117. 		--end;
  118. 	}
  119. }
  120.  
  121. //O(N^2)
  122. //根插入排序比较，谁更好——插入
  123. //插入适应性很强，对于有序，局部有序，都能效率提升
  124.  
  125. //任何情况下都是O(N^2)包括有序或者接近有序
  126. void SelectSort(int* a, int n)
  127. {
  128. 	int begin = 0, end = n-1;
  129. 	while (begin < end)
  130. 	{
  131. 		int mini = begin, maxi = begin;
  132. 		for (int i = begin + 1; i <= end; ++i)
  133. 		{
  134. 			if (a[i] < a[mini])
  135. 			{
  136. 				mini = i;
  137. 			}
  138. 			if (a[i] > a[maxi])
  139. 			{
  140. 				maxi = i;
  141. 			}
  142.  
  143. 		}
  144. 		Swap(&a[begin], &a[mini]);
  145. 		if (maxi == begin)
  146. 		{
  147. 			maxi = mini;
  148. 		}
  149. 		Swap(&a[end], &a[maxi]);
  150. 		--end;
  151. 		++begin;
  152. 	}
  153. }
  154. //最大的数往下沉
  155. void BubbleSort(int* a, int n)
  156. {
  157. 	for (int j = 0; j < n; ++j)
  158. 	{
  159. 		int exchange = 0;
  160. 		for (int i = 1; i < n - j; ++i)
  161. 		{
  162. 			if (a[i - 1] > a[i])
  163. 			{
  164. 				Swap(&a[i - 1], &a[i]);
  165. 				exchange = 1;
  166. 			}
  167. 		}
  168. 		//一趟冒泡过程中，如果没有发生交换，说明已经有序
  169. 		if (exchange == 0)
  170. 		{
  171. 			break;
  172. 		}
  173. 	}
  174.  
  175. }
  176.  
  177. //三数取中
  178. //begin  mid  end
  179. int GetMidIndex(int* a, int begin, int end)
  180. {
  181. 	int mid = (end - begin) / 2;
  182. 	if (a[begin] < a[mid])
  183. 	{
  184. 		if (a[begin] > a[end])
  185. 		{
  186. 			return begin;
  187. 		}
  188. 		else if (a[mid] < a[end])
  189. 		{
  190. 			return mid;
  191. 		}
  192. 		else
  193. 		{
  194. 			return end;
  195. 		}
  196. 	}
  197. 	else//a[begin]>a[mid]
  198. 	{
  199. 		if (a[mid] > a[end])
  200. 		{
  201. 			return mid;
  202. 		}
  203. 		else if (a[begin] < a[end])
  204. 		{
  205. 			return begin;
  206. 		}
  207. 		else
  208. 		{
  209. 			return end;
  210. 		}
  211. 	}
  212. }
  213.  
  214. //Hoare
  215. int PartSort1(int* a, int begin, int end)
  216. {
  217. 	int mid = GetMidIndex(a, begin, end);
  218. 	Swap(&a[begin], &a[mid]);
  219.  
  220. 	int left = begin, right = end;
  221. 	int keyi = left;
  222. 	while (left < right)
  223. 	{
  224. 		//右边先走，找小
  225. 		while (left < right && a[right] >= a[keyi])
  226. 		{
  227. 			--right;
  228. 		}
  229.  
  230. 		while (left < right && a[left] <= a[keyi])
  231. 		{
  232. 			++left;
  233. 		}
  234. 		Swap(&a[left], &a[right]);
  235. 	}
  236. 	Swap(&a[left], &a[keyi]);
  237. 	
  238. 	keyi = left;            
  239. 	return keyi;
  240. }
  241.  
  242. //挖坑法
  243. int PartSort2(int* a, int begin, int end)
  244. {
  245. 	int mid = GetMidIndex(a, begin, end);
  246. 	Swap(&a[begin], &a[mid]);
  247.  
  248. 	int left = begin, right = end;
  249. 	int keyi = a[left];
  250. 	int hole = left;
  251. 	while (left < right)
  252. 	{
  253. 		while (left < right && a[right] >= keyi)
  254. 		{
  255. 			--right;
  256. 		}
  257. 		a[hole] = a[right];
  258. 		hole = right;
  259. 		while (left < right && a[left] <= keyi)
  260. 		{
  261. 			++left;
  262. 		}
  263. 		a[hole] = a[left];
  264. 		hole = left;
  265. 	}
  266. 	a[hole] = keyi;
  267. 	return hole;
  268. }
  269.  
  270. //双指针法
  271. int PartSort3(int *a,int begin,int end)
  272. {
  273. 	int mid = GetMidIndex(a, begin, end);
  274. 	Swap(&a[begin], &a[mid]);
  275.  
  276. 	int keyi = begin;
  277. 	int prev = begin, cur = begin + 1;
  278. 	while (cur <= end)
  279. 	{
  280. 		if (a[cur] < a[keyi] && ++prev != cur)
  281. 		{
  282. 			Swap(&a[prev], &a[cur]);
  283. 		}
  284. 		++cur;
  285. 	}
  286. 	Swap(&a[prev], &a[keyi]);
  287. 	keyi = prev;
  288. 	return keyi;
  289. }
  290.  
  291. void QuickSort(int* a, int begin, int end)
  292. {
  293. 	if (begin >= end)
  294. 	{
  295. 		return;
  296. 	}
  297. 	if ((end - begin + 1) < 15)
  298. 	{
  299. 		//小区间用直接插入代替，减少递归调用次数
  300. 		InsertSort(a + begin, end-begin+1);
  301. 	}
  302. 	else
  303. 	{
  304. 		int keyi = PartSort3(a, begin, end);
  305. 		//[begin,keyi-1] keyi[keyi+1,end]
  306. 		QuickSort(a, begin, keyi - 1);
  307. 		QuickSort(a, keyi + 1, end);
  308. 	}
  309. }
  310.  
  311. //快排非递归实现
  312. void QuickSortR(int* a, int begin, int end)
  313. {
  314. 	ST st;
  315. 	StackInit(&st);
  316. 	StackPush(&st, begin);
  317. 	StackPush(&st, end);
  318.  
  319. 	while (!StackEmpty(&st))
  320. 	{
  321. 		int right = StackTop(&st);
  322. 		StackPop(&st);
  323. 		int left = StackTop(&st);
  324. 		StackPop(&st);
  325.  
  326. 		int keyi = PartSort3(a, left, right);
  327. 		if (keyi + 1 < right)                 //处理前面的数据时，后面的数据先进栈
  328. 		{
  329. 			StackPush(&st, keyi + 1);
  330. 			StackPush(&st, end);
  331. 		}
  332. 		if (left < keyi - 1)
  333. 		{
  334. 			StackPush(&st, left);
  335. 			StackPush(&st, keyi - 1);
  336. 		}
  337. 	}
  338. 	StackDestroy(&st);
  339. }

Stack.c 

  1. #define  _CRT_SECURE_NO_WARNINGS
  2. #include"Stack.h"
  3.  
  4.  
  5. void StackInit(ST* ps)
  6. {
  7. 	assert(ps);
  8. 	ps->a = (STDatetype*)malloc(sizeof(STDatetype) * 4);
  9. 	if (ps->a == NULL)
  10. 	{
  11. 		perror("malloc fail");
  12. 		exit(-1);
  13. 	}
  14. 	ps->top = 0;
  15. 	ps->capacity = 4;
  16. }
  17.  
  18.  
  19. void StackDestroy(ST* ps)
  20. {
  21. 	assert(ps);
  22. 	free(ps->a);
  23. 	ps->a = NULL;
  24. 	ps->top = ps->capacity = 0;
  25. }
  26.  
  27. void StackPush(ST* ps,STDatetype x)
  28. {
  29. 	assert(ps);                  //防止是一个没有初始化的空栈
  30. 	if (ps->top == ps->capacity)
  31. 	{
  32. 		STDatetype* tmp = (STDatetype*)realloc(ps->a, ps->capacity * 2);
  33. 		if (tmp == NULL)
  34. 		{
  35. 			perror("realloc fail");
  36. 			exit(-1);
  37. 		}
  38. 		ps->a = tmp;
  39. 		ps->capacity *= 2;
  40. 	}
  41. 	ps->a[ps->top] = x;                //因为top初始化为0,所以先入栈再++;
  42. 	ps->top++;
  43. }
  44.  
  45.  
  46. bool StackEmpty(ST* ps)
  47. {
  48. 	assert(ps);
  49. 	return ps->top == 0;
  50. }
  51.  
  52. void StackPop(ST* ps)
  53. {
  54. 	assert(ps);
  55. 	assert(!StackEmpty(ps));
  56. 	ps->top--;
  57. }
  58.  
  59. int StackSize(ST* ps)
  60. {
  61. 	assert(ps);
  62. 	return ps->top;
  63. }
  64.  
  65. STDatetype StackTop(ST* ps)              //输出栈顶元素
  66. {
  67. 	assert(ps);
  68. 	assert(!StackEmpty(ps));
  69. 	return ps->a[ps->top-1];
  70. }

 test.c

  1. #define  _CRT_SECURE_NO_WARNINGS
  2. #include"Sort.h"
  3.  
  4. void TestInsertSort()
  5. {
  6. 	int a[] = { 9,1,2,5,7,4,8,6,3,5 };
  7. 	InsertSort(a, sizeof(a) / sizeof(int));
  8. 	printf("InsertSort:\n");
  9. 	PrintArray(a, sizeof(a) / sizeof(int));
  10. }
  11.  
  12. void TestShellSort()
  13. {
  14. 	int a[] = { 9,8,7,6,5,4,3,2,1,5,3,1,0,4,-1,-2,-1 };
  15. 	ShellSort(a, sizeof(a) / sizeof(int));
  16. 	printf("ShellSort:\n");
  17. 	PrintArray(a, sizeof(a) / sizeof(int));
  18. }
  19.  
  20.  
  21. void TestHeapSort()
  22. {
  23. 	int a[] = { 9,8,7,6,5,4,3,2,1,5,3,1,0,4,-1,-2,-1 };
  24. 	HeapSort(a, sizeof(a) / sizeof(int));
  25. 	printf("HeapSort:\n");
  26. 	PrintArray(a, sizeof(a) / sizeof(int));
  27. }
  28.  
  29. void TestSelectSort()
  30. {
  31. 	int a[] = { 9,1,2,5,7,4,8,6,3,5 };
  32. 	SelectSort(a, sizeof(a) / sizeof(int));
  33. 	printf("SelectSort\n");
  34. 	PrintArray(a, sizeof(a) / sizeof(int));
  35. }
  36.  
  37. void TestBubbleSort()
  38. {
  39. 	int a[] = { 9,1,2,5,7,4,8,6,3,5,-2,-1 };
  40. 	BubbleSort(a, sizeof(a) / sizeof(int));
  41. 	printf("BubbleSort\n");
  42. 	PrintArray(a, sizeof(a) / sizeof(int));
  43. }
  44.  
  45. void TestQuickSort()
  46. {
  47. 	int a[] = { 6,1,2,7,9,3,4,5,8,10,8 };
  48. 	//QuickSort(a, 0, sizeof(a) / sizeof(int)-1);//sizeof(a) / sizeof(int) - 1 是为了获取数组 a 的元素个数，并将其减1作为快速排序的结束索引。
  49. 	QuickSortR(a, 0, sizeof(a) / sizeof(int) - 1);
  50. 	printf("QuickSort:\n");
  51. 	PrintArray(a, sizeof(a) / sizeof(int));
  52. }
  53.  
  54.  
  55. int main()
  56. {
  57. 	//TestInsertSort();
  58. 	//TestShellSort();
  59. 	//TestHeapSort();
  60. 	//TestSelectSort();
  61. 	//TestBubbleSort();
  62. 	TestInsertSort();
  63. 	TestShellSort();
  64. 	TestHeapSort();
  65. 	TestBubbleSort();
  66. 	TestSelectSort();
  67. 	TestQuickSort();
  68. 	return 0;
  69. }

运行结果截图

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

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

  

闽ICP备14008679号