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

常见排序算法（C/C++）--- 动画演示

作者：羊村懒王 | 2024-03-12 12:06:42

赞

踩

常见排序算法（C/C++）--- 动画演示

        本篇将介绍一些常见的排序算法，如插入排序：直接插入排序、希尔排序；选择排序：选择排序、堆排序；交换排序：快速排序、冒泡排序；以及最后的归并排序。

        对于以上的排序算法，我们总结了每种排序算法的特性，接着对直接插入排序进行了优化；然后实现了归并排序和快速排序的非递归形式；并且实现了快速排序的三种类型：Hoare、前后指针、 挖坑法，以及如何优化快速排序。 最后，我们还通过生成大量的随机数据，来测试每种排序算法消耗的时间。      

        还给出了每种算法的动画演示，便于读者理解。若想对应的排序算法，可以直接通过以下目录进行查看：

目录

 1. 插入排序

 1.1 直接插入排序

1.2 希尔排序

 2. 选择排序

2.1 直接选择排序

2.2 堆排序

3. 归并排序

3.1 归并排序递归实现

3.2 归并排序非递归实现 

4. 交换排序

4.1 冒泡排序

4.2 快速排序--Hoare快排、挖坑法快排、前后指针快排（递归）

 4.3 快排的优化

 4.4 快速排序的非递归实现

5. 各排序算法运行时间测试评估

 1. 插入排序

        插入排序的基本思想：把待排序的记录按照其关键码值的大小逐个插入到一个已经排好序的序列中，直到所有的记录插入完为止，得到一个新的有序序列。其实我们也可以叫插入排序为扑克牌排序，因为在玩扑克牌时就用了排序的思想。

​

 1.1 直接插入排序

        直接插入排序思想：当插入第 i 个元素时，前面的a[0]，a[1]，a[2]……，a[i-1]已经排好序了，此时用a[i]的排序码与a[i-1]，a[i-2]，.......的排序码顺序进行比较，找到插入位置即将a[i]插入，原来位置的元素顺序后移。动画演示如下：

​

        直接插入排序的特性总结：

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

        2. 时间复杂度O(n^2)，空间复杂度O(1);

        3. 稳定性：稳定。

        可以发现在比较第 i 个元素的同时，就已经在移动前面的数据了，对于以上思想的具体实现如下：

  1. //直接插入排序
  2. void InsertSort(int* a, int length) {
  3. 	for (int i = 0; i < length - 1; ++i) {
  4. 		int end = i;
  5. 		//保存第i+1个数据
  6. 		int tmp = a[end + 1];
  7. 		while (end >= 0) {
  8. 			//若第i+1个位置的元素小于前一个元素，交换位置
  9. 			if (tmp < a[end]) {
  10. 				a[end + 1] = a[end];
  11. 				--end;
  12. 			}
  13. 			//若没有交换位置，说明已经有序，跳出循环
  14. 			else {
  15. 				break;
  16. 			}
  17. 		}
  18. 		//将end移动到的当前位置赋值为最初的第i+1个数据
  19. 		a[end + 1] = tmp;
  20. 	}
  21. }

1.2 希尔排序

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

        对于以上总结来说，就是在整体数据中将间隔为gap的分为一组，然后对每组进行直接插入排序，每组排完之后，将gap更新变小。这个过程叫做预排序，可以将数据呈现为趋于有序。当gap==1时，其实就为直接插入排序，不过此时数据已经区域有序，所以直接插入排序也要不了几次排序就可以完成。动画演示如下：

​

        希尔排序的特性总结：

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

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

        3. 希尔排序的时间复杂度不好计算，因为gap的取值方法很多，但一般的希尔排序都基于O(nlogn)~O(n^1.5)之中。

        4. 稳定性：不稳定。
        对于希尔排序的具体实现代码如下：

  1. //希尔排序
  2. void ShellSort(int* a, int length) {
  3. 	int gap = length;
  4. 	while (gap > 1) {
  5. 		//gap的更新方法，gap的更新存在很多种，不过需要判断最后gap能否等于1
  6. 		gap = gap / 3 + 1;
  7. 		//对gap组进行直接插入排序
  8. 		for (int j = 0; j < gap; j++) {
  9. 			//对每一组中的数据元素进行直接插入排序
  10. 			for (int i = j; i < length - gap; i += gap) {
  11. 				int end = i;
  12. 				int tmp = a[end + gap];
  13. 				while (end >= 0) {
  14. 					if (tmp < a[end]) {
  15. 						a[end + gap] = a[end];
  16. 						end -= gap;
  17. 					}
  18. 					else {
  19. 						break;
  20. 					}
  21. 				}
  22. 				a[end + gap] = tmp;
  23. 			}
  24. 		}
  25. 	}
  26. }

        以上的代码虽然便于理解，但是循环有点过于冗余，以下为简化后的代码：

  1. //希尔排序
  2. void ShellSort(int* a, int length) {
  3. 	int gap = length;
  4. 	while (gap > 1) {
  5. 		gap = gap / 3 + 1;
  6. 		//依次对gap组中的元素进行直接插入排序
  7. 		for (int i = 0; i < length - gap; ++i) {
  8. 			int end = i;
  9. 			int tmp = a[end + gap];
  10. 			while (end >= 0) {
  11. 				if (tmp < a[end]) {
  12. 					a[end + gap] = a[end];
  13. 					end -= gap;
  14. 				}
  15. 				else {
  16. 					break;
  17. 				}
  18. 			}
  19. 			a[end + gap] = tmp;
  20. 		}
  21. 		
  22. 	}
  23. }

 2. 选择排序

        选择排序的基本思想，每次从待排序的数据元素中选出最小的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。

        本篇中将该算法思想稍微的优化了一下下，一次性选出最大的和最小的，放在原数据的右边和左边，

2.1 直接选择排序

        直接选择排序的思想：

        1.在元素集合array[i]--array[n-1]中选择关键码最大(小)的数据元素；
        2.若它不是这组元素中的最后一个(第一个)元素，则将它与这组元素中的最后一个（第一个）元素交换；
        在剩余的array[i]--array[n-2]（array[i+1]--array[n-1]）集合中，重复上述步骤，直到集合剩余1个元素。

      关于以上思想的动画演示如下：

​

        直接选择排序的特性总结：

        1.直接选择排序思想非常好理解，但效率不是很高。实际中很少使用；

        2.时间复杂度：O(n^2)、空间复杂度：O(1)；

        3.稳定性：不稳定。

        对于以上的思想，具体实现代码如下：

  1. //直接选择排序
  2. void SelectSort(int* a, int length) {
  3. 	int left = 0, right = length - 1;
  4. 	while (left <= right) {
  5. 		int mini = left;
  6. 		//遍历查找最小的数
  7. 		for (int i = left + 1; i <= right; ++i) {
  8. 			//找到更小的数，mini记录下标
  9. 			if (a[i] < a[mini])
  10. 				mini = i;
  11. 		}
  12. 		Swap(&a[mini], &a[left]);
  13. 		++left;
  14. 	}
  15. }

        对于以上的代码，我们还可以对其进行优化，一次性找到最大和最小的数，然后分别将其放在最左边和最右边未排序的位置。但是其中有一点需要注意：当先交换最右边（最左边）时，最右边（最左边）刚好是最小（大）位置的交换地方，那么很可能导致排序错误，所以我们需要加一个判断，然后及时改正。具体实现的代码如下：

  1. //选择排序
  2. void SelectSort(int* a, int length) {
  3. 	int left = 0, right = length - 1;
  4. 	while (left < right) {
  5. 		int maxi = right, mini = left;
  6. 		for (int i = left + 1; i <= right; ++i) {
  7. 			if (a[i] < a[mini])
  8. 				mini = i;
  9. 			if (a[i] > a[maxi])
  10. 				maxi = i;
  11. 		}
  12. 		Swap(&a[maxi], &a[right]);
  13. 		//当最小位置和最右边重合，那么需要将最小位置修改，因为最右边已经被替换为最大值
  14. 		if (mini == right) {
  15. 			mini=maxi;
  16. 		}
  17. 		Swap(&a[mini], &a[left]);
  18. 		++left;
  19. 		--right;
  20. 	}
  21. }

2.2 堆排序

        堆排序是指利用堆积树这种数据结构所设计的一种排序算法，属于选择排序中的一种，通过 堆来进行选择数据。需要注意的一点是：排升序需要建大堆、降序需要建小堆。

        对于建堆以及堆的一些其他知识可以看这篇blog：堆/堆排序（C/C++）-CSDN博客

        堆排序的动画演示如下：

​

        堆排序的特性总结：

        1. 堆排序使用堆来选数，效率高很多；

        2. 时间复杂度O(n*logn)、空间复杂度O(1)；

        3. 稳定性：不稳定。

        对于堆排序的排序原则为，降序排序为建大堆，升序排序为建小堆。以降序排序为例：当我们建立出小顶堆时，可以得出整列数据中最小的值，然后将最小值移至顺序表的最后位置，接着对前面的数据建堆，然后置换位置，以此迭代。若使用建大堆进行降序排列呢？每一次可以得到一个最大的值，然后将其放在第一个位置，对2 ~ n个位置的元素进行建堆。理论上可以，但是真正实行起来，对于第一个位置后的元素进行建堆这个步骤就会很麻烦，所以我们使用小堆进行降序排序。

        升序排序思路和上面基本一致，只有建小堆和大堆的区别。具体代码如下：

  1. //向下调整算法,大堆的向下调整算法
  2. void AdjustDown(int* a, int size, int parent) {
  3.     //左孩子结点与双亲结点的关系
  4. 	int child = parent * 2 + 1;
  5. 	if (child + 1 < size && a[child] < a[child + 1]) {
  6. 		++child;
  7. 	}
  8.     //当child>=size时表示已经到达叶子结点跳出循环
  9. 	while (child < size) {
  10. 		if (a[parent] < a[child]) {
  11. 			Swap(&a[parent], &a[child]);
  12. 			parent = child;
  13. 			child = parent * 2 + 1;
  14. 			if (child + 1 < size && a[child] < a[child + 1]) {
  15. 				++child;
  16. 			}
  17. 		}
  18.         //若双亲结点不在大于孩子结点，说明已经迭代结束，不在需要继续进行迭代
  19. 		else {
  20. 			break;
  21. 		}
  22. 	}
  23. }
  24.  
  25. void HeapSort(int* a, int length) {
  26. 	//建大堆
  27. 	//从最后一个结点的父亲结点开始使用向下调整算法建堆。整体效率比向上调整算法好很多。
  28. 	for (int i = (length - 1 - 1) / 2; i >= 0; --i) {
  29. 		AdjustDown(a, length, i);
  30. 	}
  31. 	//进行排序
  32. 	int right = length - 1;
  33. 	while (right > 0) {
  34. 		Swap(&a[0], &a[right]);
  35. 		//每一次交换数据之后都要重新进行建堆。
  36. 		AdjustDown(a, right, 0);
  37. 		right--;
  38. 	}
  39. }

3. 归并排序

        归并排序是一种建立在归并操作的一种 有效的排序算法，该算法采用分治法的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；及先使每个子序列有序，再使子序列段有序。若将两个有序表合并成一个有序表，称为二路归并。具体思路如下：

​

        动画演示如下：

​

        归并排序的特性总结：

        1.归并的缺点在于需要O(n)的空间复杂度，归并排序的思想更多的是解决在磁盘中的外排序的问题。

        2.时间复杂度：O(n*logn)、空间复杂度：O(n)

        3.稳定性：稳定。

3.1 归并排序递归实现

        递归排序的递归实现：递归的主要思路和以上的思路基本一致，先对数据进行分解，等到分解成只剩下一个元素时，我们就开始对其进行合并。但是在合并时，得到的有序数据，我们不能直接将其放回原数组中，而是需要另一个数组将其储存。等到此次归并结束时，才将其拷贝到原数组中。其余一些细节在代码注释中给出。

        具体实现的代码如下：

  1. //创建一个子函数，用于递归
  2. void SubMerge(int* a, int begin, int end, int* tmp) {
  3. 	if (begin >= end)
  4. 		return;
  5. 	int mid = (begin + end) / 2;
  6. 	//先分解，后合并，所以需要先递归然后归并
  7. 	//将其划分归并区间：[begin mid] [mid+1 end]
  8. 	SubMerge(a, begin, mid, tmp);
  9. 	SubMerge(a, mid + 1, end, tmp);
  10. 	//归并
  11. 	int begin1 = begin, end1 = mid;
  12. 	int begin2 = mid + 1, end2 = end;
  13. 	int i = begin;
  14. 	//将数据进行合并
  15. 	while (begin1 <= end1 && begin2 <= end2) {
  16. 		if (a[begin1] < a[begin2])
  17. 			tmp[i++] = a[begin1++];
  18. 		else
  19. 			tmp[i++] = a[begin2++];
  20. 	}
  21. 	//将剩余的数据合并
  22. 	while(begin1 <= end1)
  23. 		tmp[i++] = a[begin1++];
  24. 	while(begin2 <= end2)
  25. 		tmp[i++] = a[begin2++];
  26. 	//拷贝回原数组
  27. 	memcpy(a + begin, tmp + begin, sizeof(int) * (end - begin + 1));
  28. }
  29.  
  30. void MergeSort(int* a, int length) {
  31. 	//创建一个数组用于暂时存储归并后的数据
  32. 	int* tmp = (int*)malloc(sizeof(int) * length);
  33. 	if (tmp == NULL) {
  34. 		perror("MergeSort malloc failed:");
  35. 		exit(1);
  36. 	}
  37. 	SubMerge(a, 0, length - 1, tmp);
  38. 	free(tmp);
  39. }

3.2 归并排序非递归实现 

        归并排序的非递归思想其实是仿照递归的思想，先分解后合并，但是在非递归的实现中，我们会发现分解的步骤并不好实现，但是对于合并反而可以直接实现。所以我们在实现归并排序的非递归时，我们可以直接按照以下思想，将其合并：

​

         所以，我们对于非递归的实现，我们可以直接进行合并这一步骤。我们需要精确的控制每一步的合并，先是两个两个的合并，然后四个四个的合并，八个八个的合并……，直到合并完为止。但是在合并的过程中，我们也需要主要到其中的一些细节，具体的细节将在代码的注释中给出，代码如下：

  1. void MergeSortNonR(int* a, int length) {
  2. 	int* tmp = (int*)malloc(sizeof(int) * length);
  3. 	if (tmp == NULL) {
  4. 		perror("MergeSortNonR malloc failed:");
  5. 		exit(1);
  6. 	}
  7. 	//gap从1开始
  8. 	int gap = 1;
  9. 	while (gap < length) {
  10. 		for (int i = 0; i < length; i += 2 * gap) {
  11. 			//以下分区间的方法和递归时使用的方法基本一致
  12. 			int begin1 = i, end1 = i + gap - 1;
  13. 			int begin2 = i + gap, end2 = i + 2 * gap - 1;
  14. 			//若第一个区间已经越界或者第二期区间开始处越界，那么直接跳出循环，此次已经不能在合并
  15. 			if (end1 >= length || begin2 >= length)
  16. 				break;
  17. 			//第二个区间的begin没有问题，但是第二个区间的右边越界，直接将其赋值为数组的长度
  18. 			if (end2 >= length)
  19. 				end2 = length - 1;
  20.  
  21. 			//[begin1 end1] [begin2 end2]
  22. 			int j = begin1;
  23. 			while (begin1 <= end1 && begin2 <= end2) {
  24. 				if (a[begin1] < a[begin2])
  25. 					tmp[j++] = a[begin1++];
  26. 				else
  27. 					tmp[j++] = a[begin2++];
  28. 			}
  29. 			while (begin1 <= end1)
  30. 				tmp[j++] = a[begin1++];
  31. 			while (begin2 <= end2)
  32. 				tmp[j++] = a[begin2++];
  33. 			//对对应为止进行拷贝
  34. 			memcpy(a + i, tmp + i, sizeof(int) * (end2 - i + 1));
  35. 		}
  36. 		//gap需要迭代
  37. 		gap *= 2;
  38. 	}
  39. 	free(tmp);
  40. }

4. 交换排序

         交换排序的基本思想：根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置。交换排序的特点：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。

4.1 冒泡排序

        冒泡排序的基本思想：重复地走访要排序的数据，一次比较两个数据，若后一个数据小于前一个数据，则交换位置。走访数据的工作是重复地进行，直到没有再需要交换。其中，每次冒泡排序的走访都会排序好一个数。动画演示如下：

​

        冒泡排序的特性总结：

        1.冒泡排序是一种非常容易理解的排序；

        2.时间复杂度O(n^2)，空间复杂度O(1);

        3.稳定性：稳定。

        算法的具体细节放在代码注释中，代码实现如下：

  1. //冒泡排序
  2. void BubbleSort(int* a, int length) {
  3. 	for (int i = 0; i < length - 1; ++i) {
  4. 		//判断在下面的整个数据走访中，是否存在数据交换
  5. 		bool exchange = false;
  6. 		for (int j = 0; j < length - 1 - i; ++j) {
  7. 			//存在后一个数据小于前一个数据，说明要交换
  8. 			if (a[j] > a[j + 1]) {
  9. 				Swap(&a[j], &a[j + 1]);
  10. 				//数据存在交换，将exchange值改为true
  11. 				exchange = true;
  12. 			}
  13. 		}
  14. 		//若以上序列不在出现数据交换，则跳出循环
  15. 		if (exchange == false)
  16. 			break;
  17. 	}
  18. }

4.2 快速排序--Hoare快排、挖坑法快排、前后指针快排（递归）

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

        对于快速排序的实现方法一共存在三种：hoare版本、挖坑法、前后指针法。

        先对快速排序的特性进行总结：

        1. 快速排序整体的综合性能和使用的场景都是比较好的，所以被称为快速排序。

        2. 时间复杂度：O(n*logn)，空间复杂度：O(logn)；

        3. 稳定性：稳定。

        Hoare版本快排：动画演示如下：

​

        通过以上动图所演示，我们可以得出Hoare版本中的一趟排序的主要思想为：将第一个元素作为基准，然后从右边开始找小于等于基准的值，从左边开始找大于等于基准的值，都找到之后，交换此处的值，以此循环，当左右两个指针相遇时，将基准的值于指针的值交换。

        对于此方法，为什么当左右指针相遇点一定比基准值要小：

        1. L遇到R：R先走的，找到小的停下来，L找大，没有找到，遇到R停下来了，相遇位置为R，比基准值要小；

        2. R遇到L：R没有找到比基准值要小的值，直到遇到L，相遇位置是L，比基准值要小。（若难以理解，可找一个特殊的序列，使用第一趟就直接进行模拟）

        对于此版本的快排具体代码如下，其中的细节处在注释中给出：

  1. // 某一趟的快速排序
  2. int PartSort1(int* a, int begin, int end) {
  3. 	int keyi = begin;
  4. 	int left = begin, right = end;
  5. 	//下面注释的两行代码是快排的优化算法，将在下文中给出解释
  6. 	//int midi = GetMidi(a, begin, end);
  7. 	//Swap(&a[keyi], &a[midi]);
  8.  
  9. 	while (left < right) {
  10. 		//右边找小，其中注意左右指针移动时，不要越界
  11. 		while (left < right && a[right] >= a[keyi])
  12. 			--right;
  13. 		//左边找大，其中注意左右指针移动时，不要越界
  14. 		while (left < right && a[left] <= a[keyi])
  15. 			++left;
  16. 		//找到之后交换值
  17. 		Swap(&a[left], &a[right]);
  18. 	}
  19.  
  20. 	//完成一趟，现在前面部分都小于大于a[keyi]，后面部分都大于a[right]
  21. 	//交换keyi与left的位置
  22. 	Swap(&a[keyi], &a[left]);
  23. 	keyi = left;
  24. 	return keyi;
  25. }
  26.  
  27. // hoare版本快排
  28. //对于传入的参数begin和end都是闭区间，所以传入的值分别为0 和 length-1
  29. void QuickSort1(int* a, int begin, int end) {
  30. 	//当begin>=end时，说明此时传入的元素只有一个或者是空区间，没有元素，停止递归
  31. 	if (begin >= end)
  32. 		return;
  33. 	int keyi = PartSort1(a, begin, end);
  34. 	//[begin keyi-1] keyi [keyi+1 end]
  35. 	QuickSort1(a, begin, keyi - 1);
  36. 	QuickSort1(a, keyi + 1, end);
  37. }

        快慢指针快排：动画演示如下：

​

        通过以上动图，我们可以得出前后指针快排的基本思想为：使用两个指针对整个数据进行遍历，起初，这两个指针一个指向第一个元素prev，一个指针cur指向prev的前一个元素，若cur指向的当前元素大于基准值，则将cur向前走，prev不动；若cur指向的当前元素小于基准值并且此时cur不等于prev，那么我们将prev加一，然后交换cur和prev指向的值，最后cur在向前走一步，直到cur越界时，交换prev指向的值和基准值，此处循环结束。

        对于以上加粗的部分是前后指针法的关键：由上图中也可以发现，当cur指向的当前元素小于基准值且cur不等于prev时，prev向前走一步一定大于基准值，所以可以交换。

        对于此版本的快排具体代码如下，其中的细节处在注释中给出：

  1. int PartSort2(int* a, int begin, int end) {
  2. 	int keyi = begin;
  3. 	//以下两行注释的代码为对快排的优化，将在下文给出
  4. 	//int midi = GetMidi(a, begin, end);
  5. 	//Swap(&a[keyi], &a[midi]);
  6. 	int prev = begin, cur = prev + 1;
  7. 	while (cur <= end) {
  8. 		//以下注释的代码，为此次循环中代码的缩减版
  9. 		//if (a[cur] < a[key] && (++prev) != cur)
  10. 		//	Swap(&a[cur], &a[prev]);
  11. 		//++cur;
  12. 		
  13. 		//当cur指向的值小于基准值时并且cur！=prev时，++prev之后交换cur和prev指向的值
  14. 		if (a[cur] < a[keyi] && prev != cur) {
  15. 			++prev;
  16. 			Swap(&a[cur], &a[prev]);
  17. 			//交换后cur需要加一
  18. 			++cur;
  19. 		}
  20. 		else {
  21. 			++cur;
  22. 		}
  23. 	}
  24. 	Swap(&a[keyi], &a[prev]);
  25. 	keyi = prev;
  26. 	return keyi;
  27. }
  28.  
  29. // 前后指针快排
  30. // 对于传入的参数begin和end都是闭区间，所以传入的值分别为0 和 length-1
  31. void QuickSort2(int* a, int begin, int end) {
  32. 	if (begin >= end)
  33. 		return;
  34. 	int keyi = PartSort2(a, begin, end);
  35. 	//[begin key-1] key [key+1 end]
  36. 	QuickSort2(a, begin, keyi - 1);
  37. 	QuickSort2(a, keyi + 1, end);
  38. }

        挖坑法快排：动画演示如下：

​

        由以上动画可知，挖坑法快排的基本思想为：先将基准值用某一变量保存下来，将第一个基准值的位置先设置为坑位，从右边开始找小于基准值的值，若找到，将该值放入坑位，然后当前位置变成坑位，然后从左边找大于基准值的值，若找到，将该值放入坑位，然后当前位置变成坑位，以此循环，直到左右指针相遇时，此时一定是坑位，将提前保存好的基准值放入坑位中。

        对于此版本的快排具体代码如下，其中的细节处在注释中给出：

  1. int PartSort3(int* a, int begin, int end) {
  2. 	//初始将hole放在基准值的位置
  3. 	int hole = begin;
  4. 	//用一个变量将基准值暂时存储起来
  5. 	int keyi = a[begin];
  6. 	int left = begin, right = end;
  7. 	while (left < right) {
  8. 		//右边找小，注意左右指针不要越界
  9. 		while (left < right && a[right] >= keyi)
  10. 			--right;
  11. 		//找到小之后将坑位的值更新，然后更新坑位的位置
  12. 		a[hole] = a[right];
  13. 		hole = right;
  14. 		//左边找大
  15. 		while (left < right && a[left] < keyi)
  16. 			++left;
  17. 		//找到大之后，将坑位的值更新，然后更新坑位的位置
  18. 		a[hole] = a[left];
  19. 		hole = left;
  20. 	}
  21. 	//将坑位的值赋值为基准值
  22. 	a[hole] = keyi;
  23. 	keyi = hole;
  24. 	return keyi;
  25. }
  26.  
  27. // 挖坑法
  28. // 对于传入的参数begin和end都是闭区间，所以传入的值分别为0 和 length-1
  29. void QuickSort3(int* a, int begin, int end) {
  30. 	if (begin >= end)
  31. 		return;
  32. 	int keyi = PartSort3(a, begin, end);
  33. 	//[begin keyi-1] keyi [keyi+1 end]
  34. 	QuickSort3(a, begin, keyi - 1);
  35. 	QuickSort3(a, keyi + 1, end);
  36. }

 4.3 快排的优化

        对于快速排序的优化方法一共有两种，第一种：三数取中法，第二种：递归到小区间时，使用插入排序。

        三数取中法：

        对于快速排序算法，若遇到要排序的数据已经有序，比如：要排序升序，但数据为降序；要排序降序，但数据为升序时，这时快排的时间复杂度就退化为O(n^2)了，以排序升序，但数据为降序为例：基准值为第一个数据，此时基准值为最大值，从右边开始找小于基准值的值，最右边的值就刚好小于基准值，此时从左边向右寻找大于基准值，直到左指针和右指针相等时，都还没找到大于基准值的值，所以此时交换基准值和最后一个元素的位置，此时被分开的区间为：[0，n-1]  key(基准值)  [空]，以此循环，每一次都排序一个数，所以效率将为O(n^2)。

        为了解决整个问题，我们可以使用三数取中法，也就是从第一个位置，最后一个位置，中间位置中，选出中间值，然后将其与基准值进行替换，将基准值替换为这个中间值之后在进行快排，三数取中算法如下：

  1. int GetMidi(int* a, int begin, int end) {
  2. 	int midi = (begin + end) / 2;
  3. 	if (a[begin] > a[midi]) {
  4. 		if (a[midi] > a[end])
  5. 			return midi;
  6. 		else if (a[begin] < a[end])
  7. 			return begin;
  8. 		else
  9. 			return end;
  10. 	}
  11. 	else {
  12. 		if (a[begin] > a[end])
  13. 			return end;
  14. 		else if (a[end] > a[midi])
  15. 			return midi;
  16. 		else
  17. 			return begin;
  18. 	}
  19. }

        递归到小区间时，使用插入排序：

        当我们越往后递归，递归出来的小区间会越来越多，刚好此时的数据已经趋于有序了，所以此时，我们可以使用插入排序对数据进行排序，直接结束，可以提高这后半部分的效率。

​

        对于递归到多少区间开始使用插入排序，给出的一般为 begin - end <= 10 的时候开始使用插入排序对数据进行排序。以Hoare版本的数据为例：

  1. // 某一趟的快速排序
  2. int PartSort1(int* a, int begin, int end) {
  3. 	int keyi = begin;
  4. 	int left = begin, right = end;
  5. 	//下面注释的两行代码是快排的优化算法，将在下文中给出解释
  6. 	//int midi = GetMidi(a, begin, end);
  7. 	//Swap(&a[keyi], &a[midi]);
  8.  
  9. 	while (left < right) {
  10. 		//右边找小，其中注意左右指针移动时，不要越界
  11. 		while (left < right && a[right] >= a[keyi])
  12. 			--right;
  13. 		//左边找大，其中注意左右指针移动时，不要越界
  14. 		while (left < right && a[left] <= a[keyi])
  15. 			++left;
  16. 		//找到之后交换值
  17. 		Swap(&a[left], &a[right]);
  18. 	}
  19.  
  20. 	//完成一趟，现在前面部分都小于大于a[keyi]，后面部分都大于a[right]
  21. 	//交换keyi与left的位置
  22. 	Swap(&a[keyi], &a[left]);
  23. 	keyi = left;
  24. 	return keyi;
  25. }
  26.  
  27. // hoare版本快排
  28. // 对于传入的参数begin和end都是闭区间，所以传入的值分别为0 和 length-1
  29. void QuickSort1(int* a, int begin, int end) {
  30. 	//当begin>=end时，说明此时传入的元素只有一个或者是空区间，没有元素，停止递归
  31. 	if (begin >= end)
  32. 		return;
  33. 	//使用插入排序提高效率
  34. 	if (end - begin <= 10) {
  35. 		InsertSort(a + begin, end - begin + 1);
  36. 		return;
  37. 	}
  38. 	int keyi = PartSort1(a, begin, end);
  39. 	//[begin keyi-1] keyi [keyi+1 end]
  40. 	QuickSort1(a, begin, keyi - 1);
  41. 	QuickSort1(a, keyi + 1, end);
  42. }

 4.4 快速排序的非递归实现

        对于快速排序，我们也可以对齐进行非递归模拟。进行非递归模拟，那么我们需要模拟出，每一次只进行区间部分的快排。所以，我们需要某一个数据结构能够存储这些区间。答案是，可以使用栈来存储这些区间，先将 0 和 length - 1 存入栈中，然后分别取出 length - 1 和 0，取出之后记得将其弹出栈，进行使用PartSort函数进行取 keyi ，然后在依次进行取区间：[begin keyi-1] keyi [keyi+1 end] 若这些区间都是合法值，即：begin < end，我们都将其压栈，注：此时入栈的顺序要和最初入栈的顺序相同。以此循环，直到栈空即代表以及排序完成。

        具体实现如下：

        注：对于其中关于栈的实现，源自这篇文章：栈和队列&循环队列（C/C++）_栈和循环队列-CSDN博客

  1. //非递归快排
  2. void QuickSortNonR(int* a, int begin, int end) {
  3. 	int keyi = begin;
  4. 	int left = begin, right = end;
  5. 	Stack st;
  6. 	STInit(&st);
  7. 	//将右边界压入栈，然后将左边界压入栈
  8. 	STPush(&st, end);
  9. 	STPush(&st, begin);
  10. 	while (!STEmpty(&st)) {
  11. 		//分别将左边界和有边界取出
  12. 		int begin1 = STTop(&st);
  13. 		STPop(&st);
  14. 		int end1 = STTop(&st);
  15. 		STPop(&st);
  16. 		//取keyi
  17. 		int keyi = PartSort2(a, begin1, end1);
  18. 		//[begin1 keyi-1] keyi [keyi+1 end1]
  19. 		//若两办区间内的元素大于等于2（begin<end）则将这两个区间压入栈
  20. 		//压入栈时，需要注意其顺序，与压入第一个区间时要保存一致
  21. 		if (keyi + 1 < end1) {
  22. 			STPush(&st, end1);
  23. 			STPush(&st, keyi + 1);
  24. 		}
  25. 		if (begin1 < keyi - 1) {
  26. 			STPush(&st, keyi - 1);
  27. 			STPush(&st, begin1);
  28. 		}
  29. 	}
  30. 	STDestroy(&st);
  31. }

5. 各排序算法运行时间测试评估

        对以上算法，我们可以进行时间复杂度评估，这里的评估不是只用数学运算进行理论评估，而是使用生成的几组相同的随机数，对齐进行排序时间的计算，查看每个排序算法运行的排序时间，具体实现的代码如下：

        注：运行时最好将版本调整为Release版本，Debug版本运行的时间比较长。

  1. void TestOp() {
  2. 	//通过当前时间给随机数发生器 rand() 设置一个种子，以确保每次运行程序时生成的随机数序列都不同。
  3. 	srand(time(0));
  4. 	const int N = 100000;
  5. 	int* a1 = (int*)malloc(sizeof(int) * N);
  6. 	int* a2 = (int*)malloc(sizeof(int) * N);
  7. 	int* a3 = (int*)malloc(sizeof(int) * N);
  8. 	int* a4 = (int*)malloc(sizeof(int) * N);
  9. 	int* a5 = (int*)malloc(sizeof(int) * N);
  10. 	int* a6 = (int*)malloc(sizeof(int) * N);
  11. 	int* a7 = (int*)malloc(sizeof(int) * N);
  12. 	for (int i = 0; i < N; i++) {
  13. 		//rand()函数其实只能产生2~3万个不同的数据，这里要产生100000个数据
  14. 		//会出现很多重复的数据，对排序有影响，所以使用rand()+i
  15. 		a1[i] = rand() + i;
  16. 		a2[i] = a1[i];
  17. 		a3[i] = a1[i];
  18. 		a4[i] = a1[i];
  19. 		a5[i] = a1[i];
  20. 		a6[i] = a1[i];
  21. 		a7[i] = a1[i];
  22. 	}
  23. 	int begin1 = clock();
  24. 	InsertSort(a1, N);
  25. 	int end1 = clock();
  26.  
  27. 	int begin2 = clock();
  28. 	ShellSort(a2, N);
  29. 	int end2 = clock();
  30.  
  31. 	int begin3 = clock();
  32. 	SelectSort(a3, N);
  33. 	int end3 = clock();
  34.  
  35. 	int begin4 = clock();
  36. 	HeapSort(a4, N);
  37. 	int end4 = clock();
  38.  
  39. 	int begin5 = clock();
  40. 	QuickSort1(a5, 0, N - 1);
  41. 	int end5 = clock();
  42.  
  43. 	int begin6 = clock();
  44. 	MergeSort(a6, N);
  45. 	int end6 = clock();
  46.  
  47. 	int begin7 = clock();
  48. 	BubbleSort(a7, N);
  49. 	int end7 = clock();
  50.  
  51. 	printf("InsertSort:%d\n", end1 - begin1);
  52. 	printf("ShellSort:%d\n", end2 - begin2);
  53. 	printf("SelectSort:%d\n", end3 - begin3);
  54. 	printf("HeapSort:%d\n", end4 - begin4);
  55. 	printf("QuickSort:%d\n", end5 - begin5);
  56. 	printf("MergeSort:%d\n", end6 - begin6);
  57. 	printf("BubbleSort:%d\n", end7 - begin7);
  58.  
  59. 	free(a1);
  60. 	free(a2);
  61. 	free(a3);
  62. 	free(a4);
  63. 	free(a5);
  64. 	free(a6);
  65. 	free(a7);
  66. }

        测试结果：

​

        由上图所示，尽管插入排序的理论时间复杂度为O(n^2)，和冒泡、选择排序属于一个量级，但是插入排序的消耗的时间要小得多。

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

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

  

闽ICP备14008679号