• 数据结构入门——排序（代码实现）（上）

    sort.h

    1. #pragma once
    2. #include
    3.  
    4. void PrintArray(int* a, int n);
    5.  
    6. void InsertSort(int* a, int n);
    7. void ShellSort(int* a, int n);
    8. void BubbleSort(int* a, int n);
    9. void HeapSort(int* a, int n);
    10. void SelectSort(int* a, int n);

    sort.c

    准备工作

    1. #include"Sort.h"
    2.  
    3. void PrintArray(int* a, int n)
    4. {
    5. 	for (int i = 0; i < n; i++)
    6. 	{
    7. 		printf("%d ", a[i]);
    8. 	}
    9. 	printf("\n");
    10. }
    11.  
    12. void Swap(int* x, int* y)
    13. {
    14. 	int tmp = *x;
    15. 	*x = *y;
    16. 	*y = tmp;
    17. }
    18.  
    19.  
    1. void InsertSort(int* a, int n)
    2. {
    3. 	// [0,end]有序，把end+1位置的插入到前序序列
    4. 	// 控制[0,end+1]有序
    5. 	for (size_t i = 0; i < n - 1; i++)
    6. 	{
    7. 		int end = i;
    8. 		int tmp = a[end + 1];
    9. 		while (end >= 0)
    10. 		{
    11. 			if (tmp < a[end])
    12. 			{
    13. 				a[end + 1] = a[end];
    14. 			}
    15. 			else
    16. 			{
    17. 				break;
    18. 			}
    19.  
    20. 			--end;
    21. 		}
    22.  
    23. 		a[end + 1] = tmp;
    24. 	}
    25. }

    1. 插入排序

    2. void InsertSort(int* a, int n)：这是一个名为InsertSort的函数，它接受一个整型数组指针a和一个整数n作为参数，表示要排序的数组和数组的长度。

    3. for (size_t i = 0; i < n - 1; i++)：使用for循环遍历数组，从第一个元素开始直到倒数第二个元素。

    4. int end = i;：在每次循环开始时，将end初始化为当前循环的索引i。

    5. int tmp = a[end + 1];：将下一个位置的元素保存在tmp变量中，用于后续的插入操作。

    6. while (end >= 0)：进入一个while循环，该循环会从当前位置向前遍历，直到找到合适的位置插入tmp。

    7. if (tmp < a[end])：如果tmp比当前位置的元素小，则将当前位置的元素后移一位。

    8. else：否则，跳出循环，表示找到了tmp应该插入的位置。

    9. a[end + 1] = tmp;：将tmp插入到找到的位置后面，完成一次插入操作。

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

    1. 希尔排序

    2. void ShellSort(int* a, int n)：这是一个名为ShellSort的函数，接受一个整型数组指针a和一个整数n作为参数，表示要排序的数组和数组的长度。

    3. int gap = n;：初始化间隔gap为数组的长度n。

    4. while (gap > 1)：进入一个while循环，当间隔大于1时执行排序算法。

    5. gap = gap / 3 + 1;：根据希尔排序的间隔序列选择规则，更新间隔gap。通常选择gap = gap / 3 + 1。

    6. for (int i = 0; i < n - gap; ++i)：使用for循环遍历数组，每次以间隔gap对数组进行分组。

    7. int end = i;：在每次循环开始时，将end初始化为当前循环的索引i。

    8. int tmp = a[end + gap];：将当前位置往后间隔gap的元素保存在tmp变量中，用于后续的插入操作。

    9. while (end >= 0)：进入一个while循环，该循环会从当前位置向前遍历，直到找到合适的位置插入tmp。

    10. if (tmp < a[end])：如果tmp比当前位置的元素小，则将当前位置的元素后移一个间隔gap。

    11. else：否则，跳出循环，表示找到了tmp应该插入的位置。

    12. a[end + gap] = tmp;：将tmp插入到找到的位置后面，完成一次插入操作。

    13. 循环结束后，缩小间隔gap，继续进行下一轮的排序操作，直到间隔为1时完成整个排序过程。

                                                                                  希尔

    1. void BubbleSort(int* a, int n)
    2. {
    3. 	for (size_t j = 0; j < n; j++)
    4. 	{
    5. 		int exchange = 0;
    6. 		for (size_t i = 1; i < n-j; i++)
    7. 		{
    8. 			if (a[i - 1] > a[i])
    9. 			{
    10. 				Swap(&a[i - 1], &a[i]);
    11. 				exchange = 1;
    12. 			}
    13. 		}
    14.  
    15. 		if (exchange == 0)
    16. 		{
    17. 			break;
    18. 		}
    19. 	}
    20. }

    1. 冒泡排序

    2. void BubbleSort(int* a, int n)：这是一个名为BubbleSort的函数，接受一个整型数组指针a和一个整数n作为参数，表示要排序的数组和数组的长度。

    3. for (size_t j = 0; j < n; j++)：外层循环，控制需要进行多少轮冒泡排序，每轮将一个最大的元素移动到正确的位置。

    4. int exchange = 0;：用于标记在当前轮冒泡排序中是否发生过元素交换，若没有发生交换则表示数组已经有序，可以提前结束排序。

    5. for (size_t i = 1; i < n-j; i++)：内层循环，从第一个元素开始向后比较相邻的元素并进行交换。

    6. if (a[i - 1] > a[i])：如果前一个元素大于后一个元素，则交换它们的位置。

    7. Swap(&a[i - 1], &a[i]);：调用Swap函数来交换两个元素的位置。

    8. exchange = 1;：标记发生了元素交换。

    9. if (exchange == 0)：如果在一轮冒泡排序中没有发生任何交换，说明数组已经有序，可以提前结束排序。

    10. break;：跳出外层循环，提前结束排序。

    1. void AdjustDown(int* a, int n, int parent)
    2. {
    3. 	int child = parent * 2 + 1;
    4. 	while (child < n)
    5. 	{
    6. 		// 找出小的那个孩子
    7. 		if (child + 1 < n && a[child + 1] > a[child])
    8. 		{
    9. 			++child;
    10. 		}
    11.  
    12. 		if (a[child] > a[parent])
    13. 		{
    14. 			Swap(&a[child], &a[parent]);
    15. 			// 继续往下调整
    16. 			parent = child;
    17. 			child = parent * 2 + 1;
    18. 		}
    19. 		else
    20. 		{
    21. 			break;
    22. 		}
    23. 	}
    24. }
    25.  
    26. void HeapSort(int* a, int n)
    27. {
    28. 	// 向下调整建堆
    29. 	// O(N)
    30. 	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
    31. 	{
    32. 		AdjustDown(a, n, i);
    33. 	}
    34.  
    35. 	// O(N*logN)
    36. 	int end = n - 1;
    37. 	while (end > 0)
    38. 	{
    39. 		Swap(&a[0], &a[end]);
    40. 		AdjustDown(a, end, 0);
    41. 		--end;
    42. 	}
    43. }

    1. 堆排序

    2. void AdjustDown(int* a, int n, int parent)：这是一个名为AdjustDown的函数，用于向下调整堆。接受一个整型数组指针a，数组长度n和父节点索引parent作为参数。

    3. int child = parent * 2 + 1;：计算父节点parent的左孩子节点索引。

    4. while (child < n)：进入一个while循环，循环条件是孩子节点索引小于数组长度。

    5. if (child + 1 < n && a[child + 1] > a[child])：如果右孩子存在且比左孩子大，则选择右孩子作为较小的孩子。

    6. if (a[child] > a[parent])：如果较小的孩子比父节点大，则交换父节点和孩子节点的值，并继续向下调整。

    7. Swap(&a[child], &a[parent]);：调用Swap函数来交换父节点和孩子节点的值。

    8. parent = child;：更新父节点为当前孩子节点。

    9. child = parent * 2 + 1;：更新孩子节点为新的父节点的左孩子。

    10. else：如果孩子节点比父节点小或相等，则跳出循环，调整结束。

    11. void HeapSort(int* a, int n)：这是一个名为HeapSort的函数，用于实现堆排序算法。接受一个整型数组指针a和数组长度n作为参数。

    12. for (int i = (n - 1 - 1) / 2; i >= 0; i--)：建立初始堆，从最后一个非叶子节点开始，向上逐个调整节点，保证每个节点都满足堆的性质。

    13. AdjustDown(a, n, i);：调用AdjustDown函数进行向下调整。

    14. int end = n - 1;：初始化堆的末尾位置。

    15. while (end > 0)：进入一个while循环，直到堆中只剩一个元素。

    16. Swap(&a[0], &a[end]);：将堆顶元素（最大值）与当前末尾元素交换。

    17. AdjustDown(a, end, 0);：调整交换后的堆顶元素，重新使堆满足堆的性质。

    18. --end;：缩小堆的范围，继续下一轮排序。

    1. void SelectSort(int* a, int n)
    2. {
    3. 	int begin = 0, end = n - 1;
    4.  
    5. 	while (begin < end)
    6. 	{
    7. 		// [begin, end]
    8. 		int mini = begin, maxi = begin;
    9. 		for (int i = begin+1; i <= end; i++)
    10. 		{
    11. 			if (a[i] > a[maxi])
    12. 			{
    13. 				maxi = i;
    14. 			}
    15.  
    16. 			if (a[i] < a[mini])
    17. 			{
    18. 				mini = i;
    19. 			}
    20. 		}
    21.  
    22. 		Swap(&a[begin], &a[mini]);
    23. 		// max如果被换走了，修正一下
    24. 		if (maxi == begin)
    25. 		{
    26. 			maxi = mini;
    27. 		}
    28.  
    29. 		Swap(&a[end], &a[maxi]);
    30.  
    31. 		++begin;
    32. 		--end;
    33. 	}
    34. }

    1. 选择排序

    2. void SelectSort(int* a, int n)：这是一个名为SelectSort的函数，接受一个整型数组指针a和一个整数n作为参数，表示要排序的数组和数组的长度。

    3. int begin = 0, end = n - 1;：初始化begin为0，end为数组长度减1，表示当前待排序部分的起始和结束位置。

    4. while (begin < end)：进入一个while循环，循环条件是begin小于end，表示还有未排序的元素。

    5. int mini = begin, maxi = begin;：初始化最小值索引mini和最大值索引maxi为begin，用于记录待排序部分中的最小值和最大值。

    6. for (int i = begin+1; i <= end; i++)：遍历待排序部分，查找最小值和最大值的索引。

    7. if (a[i] > a[maxi])：如果当前元素大于最大值元素，则更新最大值索引maxi为当前元素索引i。

    8. if (a[i] < a[mini])：如果当前元素小于最小值元素，则更新最小值索引mini为当前元素索引i。

    9. Swap(&a[begin], &a[mini]);：交换最小值元素和当前待排序部分的第一个元素。

    10. if (maxi == begin)：如果最大值索引maxi等于begin，说明最大值元素已经被换到最小值的位置，需要更新maxi为最小值索引mini。

    11. Swap(&a[end], &a[maxi]);：交换最大值元素和当前待排序部分的最后一个元素。

    12. ++begin;：增加begin指向下一个待排序元素。

    13. --end;：减少end指向下一个待排序元素，同时缩小待排序部分的范围。

  • 相关阅读:
    TypeScript核心篇——类(class)-可选参数-存取器-构造函数-静态属性方法-抽象类
    【Unity编辑器扩展】| SceneView面板扩展
    AIGC时代 浪潮信息积极推动存储产品创新
    Linux 中的权限
    SpringCloud04 --- Nacos集群搭建
    ListUtil java
    刷完三个Java教程后不再犹豫
    地狱挖掘者系列#1
    蓝牙资讯|三星推迟发布智能戒指Galaxy Ring，智能穿戴小型化是大趋势
    A-Level经济例题解析及练习Analysis of Tax
  • 原文地址：https://blog.csdn.net/Lucas_Micheal/article/details/137789394