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

排序算法详细讲解（超酷）

作者：花生_TL007 | 2024-02-29 06:02:23

赞

踩

排序算法

目录

前言

一、插入类排序

1.直接插入排序

2.折半插入排序

3.希尔排序

二、交换类排序

1.冒泡排序（相邻比序法）

2.快速排序

三、选择类排序

1.简单选择排序

2.树形选择排序

3.堆排序

四、归并排序

五、分配类排序

1.多关键字排序

2.链式基数排序

3.计数排序

总结

排序算法作为数据结构中重要的部分，是必须要掌握的知识之一。

前言

         在进行数据处理时，经常需要对数据进行查找，为了查的更快，通常要求数据有序排列。根据排序时数据所占用存储器的不同，可将排序分为俩类。一类是整个排序过程完全在内存中进行，成为内部排序；另一类是由于待排序记录数据量太大，内存无法容纳全部数据，排序需要借助外部存储设备才能完成，称为外部排序。

        下面将介绍各种排序算法，其中重点讲述内部排序。为了方便观察各种排序之间的相同与不同，我统一按照升序来进行介绍。

文中对排序算法的讲解主要从4方面出发：（部分不经常使用的方法只介绍算法思想） 

 1. 算法思想
 2. 代码实现
 3. 时间复杂度与空间复杂度
 4. 稳定性
 
注：假设在待排序的序列中存在多个具有相同关键字的记录。若在排序前的序列中R1领先于R2，经过排序后得到的序列中R1仍然领先于R2，则称所使用的排序方法是稳定的；反之，如果经过排序后得到的序列中R2领先于R1，则称所使用的排序方法是不稳定的。

一、插入类排序

1.直接插入排序

  •  算法思想：

直接插入排序是一种最基本的插入排序方法，基本操作是将第i个记录插入到前面i-1个已经排好序的记录中。假如待排序的序列为48,62,35,77,55,14,35,98。观察这组记录，我们发现记录的数据中存在相同的数字35，这俩个35在下图中使用一个特殊标识作于区分，方便在排好序后观察直接插入排序的稳定性。

将数据分为俩队，一队是已经排好序的数据，另外一队为还没有进行排序的数据。一开始假设只有第一个数字是有序的，则只有第一个数字即48在已经排好序的队列里。接下来取数据中的第二个数字62，因为62大于48，所以应该排在48后面，与原先相同故不需要进行交换。此时48,62在已经排好序的队列中，且数据在队列中按升序排好。再取第三个数据35,35大于48，需要排在48前面，故将48,62,向后移动一位空出第一位让35插入。.....一直这样直至将所有的数据排好。

假如待排序的序列为48,62,35,77,55,14,35,98。下面为示例图：

  • 实现代码：（C语言）
  1. //数组a为待排序的数据，n为数据的个数
  2. void InsertSort(int* a, int n) {
  3. 	for (int i = 1; i < n ; i++) {
  4. 		int temp=a[i];
  5. 		for (int j = i-1; j >=0; j--) {
  6. 			if (a[j] > temp) {
  7. 				a[j + 1] = a[j];
  8. 				a[j] = temp;
  9. 			}
  10. 			else {
  11. 				break;
  12. 			}
  13. 		}
  14. 	}
  15. 	//打印数组
  16. 	for (int i = 0; i < n; i++) {
  17. 		printf("%d ", a[i]);
  18. 	}
  19. 	printf("\n");
  20. }
  • 时间复杂度：O(n^2）
  • 空间复杂度：O(1)
  • 稳定性：稳定

在待排序的关键字序列基本有序且关键字个数n较少时，其算法的性能最佳。

2.折半插入排序

它是对直接插入排序的一种优化算法。

  • 算法思想：

对有序表进行查找时，折半查找（二分法）的性能优于顺序查找。所以对直接插入排序可以使用折半查找的思想进行优化，这样的排序法被称为折半插入排序法。采用折半插入排序法，可以减少关键字的比较次数。

  • 实现代码：
  1. //折半插入排序
  2. void BinSort(int* a, int n) {
  3. 	for (int i = 1; i < n - 1; i++) {
  4. 		int temp = a[i];
  5. 		int begin = 0, end = i - 1;
  6. 		while (begin<=end) {
  7. 			int mid = (begin + end) / 2;
  8. 			if (temp < a[mid]) {
  9. 				end = mid - 1;
  10. 			}
  11. 			else {
  12. 				begin = mid + 1;
  13. 			}
  14. 		}
  15. 		for (int j = i - 1; j >= begin; j--)
  16. 			a[j + 1] = a[j];
  17. 		a[begin] = temp;
  18. 	}
  19. 	for (int i = 0; i < n; i++) {
  20. 		printf("%d ", a[i]);
  21. 	}
  22. 	printf("\n");
  23. }
  • 时间复杂度：O(n^2)

注：虽然折半插入排序法与直接插入排序相比，改善了算法中比较次数的数量级，达到了O(nlogn),但是并未改变交换元素的时间耗费，所以折半插入排序的总时间复杂度仍然是O(n^2)。此方法不经常使用，相同适用场景下一般使用直接排序算法也可以解决问题。

  • 空间复杂度：O(1)
  • 稳定性：稳定

3.希尔排序

它也是对直接插入排序的一种优化算法。

  • 算法思想：

将待排序的元素分为若干个较小的子序列，对子序列进行插入排序，使整个待排序序列排好序。那么问题就是我们应该怎样去分子序列？平均分为俩组或者多组?如果你这样做结果会发现子序列是有序了，但是整个序列并没有接近有序。所以希尔（Shell）提出在分子序列时应该“跳着选（间隔选）”，而不是“连着选”，“跳着选（间隔选）”后子序列中排好序后，我们发现整个序列中小的元素更靠前，大的元素更靠后，这样就比之前接近有序了。

接下来我们发现子序列是应该“跳着选（间隔选）”的，但是每次应该“跳几步（间隔几个）”呢？将每次“跳的步数（间隔）”记为gap，关于gap的取法有很多种，希尔（Shell）提出取gap=n/2,再gap=gap/2，直至gap=1为止，Knuth提出gap=gap/3+1。除此之外还有其他的取法，感兴趣的小伙伴可以去了解一下。此次我选取希尔（Shell）提出的gap取法进行下面的内容。

假如待排序的序列为48,62,35,77,55,14,35,98。下面为示例图：

  • 实现代码：（C语言）
  1. // 希尔排序
  2. void ShellSort(int* a, int n) {
  3. 	for (int gap = n / 2; gap >= 1;) {
  4. 		for (int i = gap; i < n ; i++) {
  5. 			int temp = a[i];
  6. 			for (int j = i-gap; j>=0; j-=gap) {
  7. 				if (a[j] > temp) {
  8. 					a[j + gap] = a[j];
  9. 					a[j] = temp;
  10. 				}
  11. 				else {
  12. 					break;
  13. 				}
  14. 			}
  15. 		}
  16. 		gap = gap / 2;
  17. 	}
  18. 	for (int i = 0; i < n; i++) {
  19. 		printf("%d ", a[i]);
  20. 	}
  21. 	printf("\n");
  22. }
  • 时间复杂度：O(n^1.5) 

注：gap的取值不同，它所对应的时间复杂度也不同。Knuth提出gap=gap/3+1的时间复杂度为O(n^1.25)~1.6O(n^1.25)。

  • 空间复杂度：O(1)
  • 稳定性：不稳定

注：从我举的例子来看，貌似希尔算法是稳定的，但是判断算法是否稳定往往无法通过一个例子来说明，这个例子带有偶然性。排序算法的稳定性必须通过算法本身加以证明。但证明排序方法不是稳定的，只需要给出一个反例说明。在平时我们分析排序算法是否稳定时还是经常通过举例子来判断，这样判断的正确性有不确定性。如果一定要举例分析的话建议使用较多的例子，减小不确定性。希尔排序是不稳定的，反例：{2,4,1,2}；

二、交换类排序

1.冒泡排序（相邻比序法）

冒泡排序是一种较为简单的排序方法，它是通过对相邻的数据元素进行比较交换，逐步将待排序序列变成有序序列的过程。

  • 算法思想：

反复扫描待排序记录序列，在扫描过程中顺次比较相邻俩个元素的大小，若逆序就交换。假如待排序的序列为48,62,35,77,55,14,35,98。下面为示例图：

第一趟冒泡排序： 

注：观察发现第一趟冒泡排序完成后，最后一个元素是序列中最大的元素。那么下一次冒泡排序时只需要排前n-1个元素就够了（序列中一共有n个元素）。

每一趟冒泡排序： 

  • 实现代码：（C语言）
  1. void BubbleSort(int* a, int n){
  2.      for (int i = 0; i < n - 1; i++) {
  3. 		for (int j = 0; j < n - i - 1; j++) {
  4. 			if (a[j] > a[j + 1]) {
  5. 				int temp = a[j+1];
  6. 				a[j + 1] = a[j];
  7. 				a[j] = temp;
  8. 			}
  9. 		}
  10. 	}
  11. 	for (int i = 0; i < n; i++) {
  12. 		printf("%d ", a[i]);
  13. 	}
  14. }
  • 时间复杂度：O(n^2) 
  • 空间复杂度：O(1)
  • 稳定性：稳定

冒泡排序第一次找出最大的值，第二次找出次大的值，第三次找出第三大的值......这样一次可以将一个值排好序。

但事实上一趟不止能找出这些较大的值，还可以找出较小的值（第一次找出最大的值和最小的值，第二次找出次大的值和次小的值......），这样一趟就可以把俩个元素排好。

2.快速排序

快速排序是冒泡排序的改进方法。冒泡排序一次只能消除一个逆序，快速排序中的一次交换可能消除多个逆序。

  • 算法思想：

从待排序的数据中选取一个元素为基准值，然后将小于基准值的元素放到基准值的前面，将大于等于基准值的元素放到基准值的后面。这样就将待排序的数据分为俩个子表，将这个过程称为一趟快速排序。对分割后的子表继续按照上面的方法进行操作，直至所有子表的表长不超过1为止，此时待排序数据序列就变成了一个有序表。

那么现在就得思考如何取基准值？大家都希望基准值是数据序列中值为中间的元素，可是现在序列还是一个无序表，又怎么找呢？因此基准值的三种较为常用的取法中，三数取中法是更为合适的。

基准值较常使用的取法共有三种：

  1. 最左侧的元素
  2. 最右侧的元素
  3. 三数取中法：最左侧的元素、最右侧的元素和中间的元素进行比较，选择值不大不小的元素作为基准值。

将区间按照基准值划分为左右两半部分的常见方式有：

      1.hoare法

假如待排序的序列为48,62,35,77,55,14,35,98。

此次实例的基准值为最左侧元素48。先让指针end从后向前找比基准值小的元素，找到了就停止。再让指针begin从前向后找比基准值大的元素，找到了就停止；如果指针begin和end没有相遇，则将begin和end指向的元素进行交换。交换之后，再次重复上方法直至指针begin和end相遇，最后将基准值和指针begin/end指向的元素（指针begin和end相遇，俩个指针指向的元素是同一个）进行交换。

下面为示例图：

 以下为示意代码：

  1. // 快速排序hoare版本 左侧元素作为基准值
  2. int PartSort1(int* a, int left, int right) {
  3. 	int begin = left;
  4. 	int end = right-1;
  5. 	int key = a[left];//关键字的取值为a[dir]即a[begin]，最左侧的元素
  6. 	while (begin < end) {
  7. 		while (begin<end&&a[end] >= key) {
  8. 			end--;
  9. 		}
  10. 		while (begin<end&&a[begin] <=key) {
  11. 			begin++;
  12. 		}
  13. 		if (begin != end) {
  14. 			int temp = a[begin];
  15. 			a[begin] = a[end];
  16. 			a[end] = temp;
  17. 		}
  18. 	}
  19. 	int tem = a[begin];
  20. 	a[begin] = a[left];
  21. 	a[left]= tem;
  22. 	return begin;//返回关键字的下标
  23. }

注：当基准值取值方法为三数取中法时指针的移动与基准值为最左侧元素是相同的。但是如果基准值取为最右侧元素，指针移动是与基准值为最左侧元素的顺序是正好相反的。让指针begin指向最左侧元素，end指向最右侧元素，让指针begin从前向后找比基准值大的元素；让指针end从后向前找比基准值小的元素。

 以下为示意代码：

  1. //快速排序hoare版本，基准值为最右侧元素
  2. int PartSort1(vector<int>& nums, int left, int right) {
  3. 	int begin = left, end = right - 1;
  4. 	int key = nums[end];
  5. 	while (begin < end) {
  6. 		while (begin<end && nums[begin]<=key) {
  7. 			begin++;
  8. 		}
  9. 		while (begin < end && nums[end] >= key) {
  10. 			end--;
  11. 		}
  12. 		if (begin != end) swap(nums[begin], nums[end]);
  13. 	}
  14. 	swap(nums[begin], nums[right-1]);
  15. 	return begin;
  16. }

     2.挖坑法

假如待排序的序列为48,62,35,77,55,14,35,98。

此次实例的基准值为最左侧元素48。把48拿出后原来它所在的位置上就留下了一个“坑”，先让指针end从后向前找比基准值小的元素，找到了就“填坑”，但是有又“挖下了新的坑”。再让指针begin从前向后找比基准值大的元素，找到了“填指针end指向位置的坑”；之后再次重复上方法直至指针begin和end相遇，把“最后一个坑”放入基准值。

下面为示例图：

  1. // 快速排序挖坑法
  2. int PartSort2(int* a, int left, int right) {
  3. 	int begin = left;
  4. 	int end = right-1;
  5. 	int key = a[left];
  6. 	while (begin < end) {
  7. 		while (begin < end && a[end] >= key) {
  8. 			end--;
  9. 		}
  10. 		if (begin < end) {
  11. 			a[begin] = a[end];
  12. 			begin++;
  13. 		}
  14. 		while (begin < end && a[begin] <= key)
  15. 			begin++;
  16. 		if (begin < end) {
  17. 			a[end] = a[begin];
  18. 			end--;
  19. 		}
  20. 	}
  21. 	a[begin] = key;
  22. 	return begin;
  23. }

 注：当基准值取值方法为三数取中法时指针的移动与基准值为最左侧元素是相同的。但是如果基准值取为最右侧元素，指针移动是与基准值为最左侧元素的顺序是正好相反的。让指针begin指向最左侧元素，end指向最右侧元素，让指针begin从前向后找比基准值大的元素；让指针end从后向前找比基准值小的元素。

  1. //挖坑法 基准值为最右侧元素
  2. int PartSort2(vector<int>& nums, int left, int right) {
  3. 	int begin = left, end = right - 1;
  4. 	int key = nums[end];
  5. 	while (begin < end) {
  6. 		while (begin < end && nums[begin] <= key) {
  7. 			begin++;
  8. 		}
  9. 		nums[end] = nums[begin];
  10. 		while (begin < end && nums[end] >= key) {
  11. 			end--;
  12. 		}
  13. 		nums[begin] = nums[end];
  14. 	}
  15. 	nums[begin] = key;
  16. 	return begin;
  17. }

    3.前后指针法

这是一个大佬想出来的办法，仅仅用语言和图片描述不足以体现这个方法的神奇。大家多多品味代码。此次实例的基准值为最右侧元素。

在代码中除了cur==0之外，如果cur==prev，表示它们当前所指向的值为序列中从左到右第一个小于基准值key的元素，并且这个元素前面没有大于基准值key的元素；如果cur！=prev，表示cur指向序列中从左到右第一个小于基准值key的元素，prev指向从左到右第一个大于基准值key的元素。那么cur！=prev时，prev>cur &&nums[prev]>key>nums[cur]，交换nums[prev]和nums[cur]就可以让序列更加有序。

注：当基准值取值方法为三数取中法时指针的移动与基准值为最左侧元素是相同的。但是如果基准值取为最右侧元素，指针移动是与基准值为最左侧元素的顺序是正好相反的。让指针begin指向最左侧元素，end指向最右侧元素，让指针begin从前向后找比基准值大的元素；让指针end从后向前找比基准值小的元素。

示意代码：

  1. // 快速排序前后指针法,基准值取值为最右侧元素
  2. int PartSort3(int* a, int left, int right) {
  3. 	int cur = left;
  4. 	int prev = cur - 1;
  5. 	int key = a[right-1];
  6. 	while (cur < right) {
  7. 		if (a[cur] < key && ++prev != cur) {
  8. 			int temp = a[cur];
  9. 			a[cur] = a[prev];
  10. 			a[prev] = temp;
  11. 		}
  12. 		cur++;
  13. 	}
  14. 	if (++prev != right - 1) {
  15. 		int temp = a[prev];
  16. 		a[prev] = a[right-1];
  17. 		a[right-1] = temp;
  18. 	}
  19. 	return prev;
  20. }
  1. //前后指针法 基准值为最左侧元素
  2. int PartSort3(vector<int>& nums, int left, int right) {
  3. 	int cur = right-1;
  4. 	int prev = right;
  5. 	int key = nums[left];
  6. 	while (cur>=left) {
  7. 		if (nums[cur] > key && --prev != cur) {//nums[cur] < key为降序排列
  8. 			swap(nums[cur], nums[prev]);
  9. 		}
  10. 		cur--;
  11. 	}
  12. 	if (--prev != left) {
  13. 		swap(nums[prev], nums[left]);
  14. 	}
  15. 	return prev;
  16. }

  • 实现代码：（C语言）
  1. // 快速排序递归实现
  2. // 快速排序hoare版本
  3. int PartSort1(int* a, int left, int right) {
  4. 	int begin = left;
  5. 	int end = right-1;
  6. 	int key = a[left];//关键字的取值为a[dir]即a[begin]，最左侧的元素
  7. 	while (begin < end) {
  8. 		while (begin<end&&a[end] >= key) {
  9. 			end--;
  10. 		}
  11. 		while (begin<end&&a[begin] <=key) {
  12. 			begin++;
  13. 		}
  14. 		if (begin != end) {
  15. 			int temp = a[begin];
  16. 			a[begin] = a[end];
  17. 			a[end] = temp;
  18. 		}
  19. 	}
  20. 	int tem = a[begin];
  21. 	a[begin] = a[left];
  22. 	a[left]= tem;
  23. 	return begin;//返回关键字的下标
  24. }
  25. // 快速排序挖坑法
  26. int PartSort2(int* a, int left, int right) {
  27. 	int begin = left;
  28. 	int end = right-1;
  29. 	int key = a[left];
  30. 	while (begin < end) {
  31. 		while (begin < end && a[end] >= key) {
  32. 			end--;
  33. 		}
  34. 		if (begin < end) {
  35. 			a[begin] = a[end];
  36. 			begin++;
  37. 		}
  38. 		while (begin < end && a[begin] <= key)
  39. 			begin++;
  40. 		if (begin < end) {
  41. 			a[end] = a[begin];
  42. 			end--;
  43. 		}
  44. 	}
  45. 	a[begin] = key;
  46. 	return begin;
  47. }
  48. // 快速排序前后指针法,基准值取值为最右侧元素
  49. int PartSort3(int* a, int left, int right) {
  50. 	int cur = left;
  51. 	int prev = cur - 1;
  52. 	int key = a[right-1];
  53. 	while (cur < right) {
  54. 		if (a[cur] < key && ++prev != cur) {
  55. 			int temp = a[cur];
  56. 			a[cur] = a[prev];
  57. 			a[prev] = temp;
  58. 		}
  59. 		cur++;
  60. 	}
  61. 	if (++prev != right - 1) {
  62. 		int temp = a[prev];
  63. 		a[prev] = a[right-1];
  64. 		a[right-1] = temp;
  65. 	}
  66. 	return prev;
  67. }
  68.  
  69. void QuickSort(int* a, int left, int right) {
  70. 	if (left >= right) {
  71. 		return;
  72. 	}
  73. 	int div = PartSort1(a, left, right);
  74. 	QuickSort(a, left, div);
  75. 	QuickSort(a, div + 1, right);
  76. 	
  77. }

注1：除了使用递归的方法之外，还有使用非递归的方法，是通过栈实现的。

  • 时间复杂度：O(nlogn)
  • 空间复杂度：O(logn)
  • 稳定性：不稳定 反例：{3,3,2}

快速排序整体的综合性能和使用场景都是比较好的。因此它往往也是面试考察的重点。

三、选择类排序

1.简单选择排序

每一趟选出较大或较小的值，将它与排好序后位于位置的值进行交换。每一趟在n-i+1个元素中选取关键字最小（最大）的元素作为有序序列中第i个记录。（一共有n个元素）

  • 算法思想：

第一趟简单选择排序时，从第一个元素开始，通过n-1次关键字的比较，从n个元素中选出最小的元素，并与第一个元素交换。

第二趟简单选择排序时，从第二个元素开始，通过n-2次关键字的比较，从n-1个元素中选出最小的元素，并与第二个元素交换。

第三趟简单选择排序时，从第三个元素开始，通过n-3次关键字的比较，从n-2个元素中选出最小的元素，并与第三个元素交换。

......

第i趟简单选择排序时，从第i个元素开始，通过n-i次关键字的比较，从n-i+1个元素中选出最小的元素，并与第i个元素交换。

假如待排序的序列为48,62,35,77,55,14,35,98。下面为示例图：

如此反复，经过n-1趟简单选择排序，将n-1个元素排好，剩下一个元素直接在最后，所以共需进行n-1趟简单选择排序。

  • 实现代码：（C语言）
  1. // 选择排序(升序)
  2. void SelectSort(int* a, int n) {
  3. 	for (int i = 0; i < n-1; i++) {
  4. 		int min = i;
  5. 		for (int j = i+1; j < n; j++) {
  6. 			if (a[min] > a[j]) {
  7. 				min = j;
  8. 			}
  9. 		}
  10. 		int temp = a[min];
  11. 		a[min] = a[i];
  12. 		a[i] = temp;
  13. 	}
  14. 	for (int i = 0; i < n; i++) {
  15. 		printf("%d ", a[i]);
  16. 	}
  17. 	printf("\n");
  18. }
  • 时间复杂度：O(n^2) 
  • 空间复杂度：O(1)
  • 稳定性：不稳定  

注：从实例图中观察，选择排序看似是稳定的但其实不是。反例：{3,3,2}

2.树形选择排序

树形选择排序也称作锦标赛排序，树形选择排序时简单选择排序的改进算法。在简单选择排序中，首先从n个元素中选择关键字最小的元素需要n-1次比较，在n-1个元素中选择关键字最小的元素需要n-2次比较，......，每次都没有利用上次比较结果，所以比较操作的时间复杂度为O(n^2)，想要降低比较的次数，则需要把比较过程中的大小关系保存下来。

  • 算法思想：

先把待排序的n个元素俩俩进行比较，取出较小者，然后再n/2个较小者中采取同样的方法进行比较，选出较小者，如此反复，直至选出最小的元素为止。这个过程可以使用一颗满二叉树来表示，不满时用无穷大的数补充，选出的最小元素就是这棵树的根结点。将根结点输出后，叶子结点为最小值的变为无穷大的数，然后从该叶子结点和其兄弟结点的关键字比较，修改该叶子结点到根结点路径上各结点的值，则根结点的值为次小的元素。

  • 时间复杂度：O(nlogn) 
  • 空间复杂度：O(n)
  • 稳定性：稳定

这个算法思想听起来好复杂的样子啊。虽然描述算法思想使用了很多文字，但是如果理解了就会发现树形选择排序思想并不难理解。如果还是没有明白，大可先把它放在一边。因为实际上使用它的次数并不多，也不是排序算法中考察的重点。

3.堆排序

堆排序是树形选择排序的改进算法，弥补树形选择排序占用太多空间的缺陷。采用堆排序，只需要一个记录大小的辅助空间。

  • 算法思想：

把待排序的元素放在堆中，每个结点表示一个元素。建立初堆后将根结点与堆的最后一个结点交换，之后重建堆的对象为n-1个，再把次大的结点与倒数第二个结点交换，之后重建堆的对象为n-2个，......，以此类推，直至重建堆的对象为0。此时将堆输出即可得到排好序的序列。

堆排序的过程主要解决俩个问题：一是按堆定义建立初堆，二是去掉最大元素之后重建堆。这俩个问题都需要向下调整法来解决。

向下调整法：当完全二叉树不是大堆但左右子树都为大堆时，需要调整满二叉树的根节点使其成为大堆。大堆每一个结点的值都大于等于它左右孩子的值。此时根节点并不符合这定义，所以我们需要将根节点换为所有结点中的最大值，那我们怎么找最大值呢？让根节点的左右孩子进行比较选出较大值，它们之间的较大值就是整个树的最大值（因为左右子树都为大堆）。将较大值所在的结点与根节点进行交换，此时根节点已经符合但是并不能确定原根节点现在位于的子树是否是大堆，仍然需要判断，如果不是大堆则需要接着调整，直至符合定义。

建立初堆：一开始接收到的数据并不是已经成为大堆了，需要对它进行调整使其成为大堆。此时的堆是无序的，需要从最后的子树开始向下调整。

注：1.为什么一定需要从最后的子树开始向下调整呢？从根节点开始不行吗？

答：不行，向下调整法使用的前提是堆根节点左右子树都是大堆。而一开始我们并不能确定这一定。

2.那我要怎么找最后的子树呢？

答: 最小子树根结点的下一个结点没有左右子树，而它前面的结点都有左右子树。我们可以给堆中的结点进行标号，一共有n个结点，如果号码从1开始那么最后子树的根节点为n/2，如果号码从0开始那么最后子树的根节点为（n-2）/2。

重建堆：当根结点移出后，它原来的位置就有了新的结点。新结点最为根结点可能不满足大堆的条件，需要堆根结点进行向下调整。

  • 实现代码：（C语言）
  1. // 堆排序（大堆：升序）
  2. void AdjustDwon(int* a, int n, int root) {
  3. 	int parent = root;
  4. 	int child = parent*2+1;
  5. 	while (child<n) {
  6. 		if (child + 1 < n && a[child + 1] > a[child]) {
  7. 			child += 1;
  8. 		}
  9. 		if (a[child] > a[parent]) {
  10. 			int temp = a[parent];
  11. 			a[parent] = a[child];
  12. 			a[child] = temp;
  13.  
  14. 			parent=child;
  15. 			child = parent * 2 + 1;
  16. 		}
  17. 		else {
  18. 			break;
  19. 		}
  20. 	}
  21. }
  22.  
  23. void HeapSort(int* a, int n) {
  24. 	if (a == NULL)
  25. 		return;
  26. 	for (int i = (n - 2) / 2; i >= 0; i--) {
  27. 		AdjustDwon(a, n, i);
  28. 	}
  29. 	for (int i = 0; i < n - 1; i++) {
  30. 		int temp = a[n - i-1];
  31. 		a[n - i-1] = a[0];
  32. 		a[0] = temp;
  33. 		AdjustDwon(a, n - i-1, 0);
  34. 	}
  35. 	for (int i = 0; i < n; i++) {
  36. 		printf("%d ", a[i]);
  37. 	}
  38. 	printf("\n");
  39. }

注：升序建立大堆，降序建立小堆。

  • 时间复杂度：O(nlogn) 
  • 空间复杂度：O(1)
  • 稳定性：不稳定       反例：{5,5,3}

堆排序的思想还可以被用来解决TOPK问题。TOPK问题最为经典题目经常出现在面试或实际生活中，希望大家可以掌握。（这里就不多介绍了，想偷懒(p . q)。下面是我找的大神的讲解，感兴趣的同学去看看）

Top K 问题的解决方案_HerofH_的博客-CSDN博客_topk问题

四、归并排序

算法思想：将俩个或俩个以上的有序序列合并成一个。

2-路归并：假设初始序列有n个元素，首先将这n个元素看成n个子序列，俩俩归并为有序的序列,此时序列的长度为2，再俩俩归并为有序的序列，此时序列的长度为4，......，一直归并直至得到一个长为n的序列。

假如待排序的序列为48,62,35,77,55,14,35,98。下面为示例图：

  • 实现代码：（C语言）

使用递归：

  1. // 归并排序递归实现
  2. //合并，需要借助辅助空间temp
  3. void MergeDate(int *a,int left,int mid,int right,int *temp) {
  4. 	int begin1 = left;
  5. 	int begin2 = mid;
  6. 	int end1 = mid;
  7. 	int end2 = right;
  8. 	int index = left;
  9. 	while (begin1 < end1 && begin2 < end2) {
  10. 		if (a[begin1] < a[begin2]) {
  11. 			temp[index++] = a[begin1++];
  12. 		}
  13. 		else {
  14. 			temp[index++] = a[begin2++];
  15. 		}
  16. 	}
  17. 	while (begin1 < end1) {
  18. 		temp[index++] = a[begin1++];
  19. 	}
  20. 	while (begin2 < end2) {
  21. 		temp[index++] = a[begin2++];
  22. 	}
  23. }
  24. void _MergeSort(int *a, int left, int right, int* temp) {
  25. 	if (right - left <= 1) {
  26. 		return;
  27. 	}
  28. 	int mid = left + ((right - left) >> 1);
  29. 	_MergeSort(a, left, mid,temp);
  30. 	_MergeSort(a, mid, right,temp);
  31. 	MergeDate(a, left, mid, right, temp);
  32. 	memcpy(a+left, temp+left, (right - left) * sizeof(a[0]));
  33. }
  34. void MergeSort(int* a, int n) {
  35. 	int* temp = (int *)malloc(sizeof(a[0]) * n);
  36. 	if (NULL == temp) {
  37. 		assert(0);
  38. 		return;
  39. 	}
  40. 	_MergeSort(a, 0, n, temp);
  41. 	for (int i = 0; i < n; i++) {
  42. 		printf("%d ", a[i]);
  43. 	}
  44. 	printf("\n"); 
  45. 	free(temp);
  46. }

非递归：

  1. // 归并排序非递归实现
  2. void MergeSortNonR(int* a, int n) {
  3. 	int* temp = (int*)malloc(sizeof(a[0]) * n);
  4. 	if (NULL == temp) {
  5. 		assert(0);
  6. 		return;
  7. 	}
  8. 	int gap = 1;
  9. 	while ( gap<n) {
  10. 		for (int i = 0; i < n; i+=2*gap) {
  11. 			int left = i;
  12. 			int mid = left + gap;
  13. 			int right = mid + gap;
  14. 			if (mid >= n)
  15. 				mid = n;
  16. 			if (right >= n)
  17. 				right = n;
  18. 			//前面递归中也使用了此函数，已给出
  19. 			MergeDate(a, left, mid, right, temp);
  20. 		}
  21. 		memcpy(a, temp, n * sizeof(a[0]));
  22. 		gap *= 2;
  23. 	}
  24. 	free(temp);
  25. 	for (int i = 0; i < n; i++) {
  26. 		printf("%d ", a[i]);
  27. 	}
  28. 	printf("\n");
  29. }
  • 时间复杂度：O(nlogn) 
  • 空间复杂度：O(n)
  • 稳定性：稳定

归并排序还常常原来做外部排序，感兴趣的同学可以去了解一下。

当数据过大时，计算机无法一次性将所有数据加载到内存中，这时我们可以建立俩个存储空间通过归并排序的思想来排序。挠挠头，好像说的很奇怪。但因为篇幅问题这里只能这样简单介绍一下。如果之后我有时间，另外开一篇博客来讲解。

五、分配类排序

前面所介绍的各种排序方法使用的基本操作是比较与交换，而分配类排序则是利用分配和收集俩种基本操作实现排序。

1.多关键字排序

  • 算法思想：

先按第一个关键字K1进行排序,将记录序列分成若干个子序列,每个子序列有相同的K1值;然后分别对每个子序列按第二个关键字K2进行排序,每个子序列又被分成若干个更小的子序列;如此重复,直到按最后一个关键字Kd进行排序。 最后,将所有的子序列依次联接成一个有序的记录序列,该方法称为“高位优先”排序法(Most Significant Digit first)。

2.链式基数排序

  • 算法思想：

基数排序属于上述“低位优先”排序法，通过反复进行分配与收集操作完成排序。排序时先按最低位的值对元素进行初步排序，在此基础上再按次低位的值进一步排序。

假如待排序的序列为48,62,35,77,55,14,35,98。下面为示例图：

  • 稳定性：稳定

基数排序适用于元素个数多但元素的位数较小的序列。

3.计数排序

  • 算法思想：

对于给定的输入序列中的每一个元素，统计该序列中元素的出现的次数，将元素出现次数存放起来，再从序列的最小值元素开始输出（如果出现次数为0则不输出，出现次数为2则输出2次）。

  • 实现代码：（C语言）
  1. void CountSort(int* a, int n) {
  2. 	//统计数据出现的次数
  3. 	int count[10] = {0};//数据集中在9个元素，根据实际情况的不同需要更改
  4. 	for (int i = 0; i < n; i++) {
  5. 		count[a[i]]++;
  6. 	}
  7. 	//排序
  8. 	int index = 0;
  9. 	for (int i = 0; i < 10; i++) {
  10. 		while (count[i] > 0) {
  11. 			a[index++] = i;
  12. 			count[i]--;
  13. 		}
  14. 	}
  15. 	for (int i = 0; i < n; i++) {
  16. 		printf("%d ", a[i]);
  17. 	}
  18. 	printf("\n");
  19. }
  20.  
  21. void main() {
  22. 	int a[10] = {5,6,4,3,7,2,8,1,9,1};
  23.  
  24. 	int n = sizeof(a) / sizeof(a[0]);
  25. 	//SelectSort(a, n);
  26. 	//HeapSort(a, n);
  27. 	//InsertSort(a, n);
  28. 	//BinSort(a, n);
  29. 	//ShellSort(a, n);
  30. 	//BubbleSort(a, n);
  31. 	//MergeSort(a, n);
  32. 	//MergeSortNonR(a, n);
  33. 	CountSort(a, n);
  34. }
  • 稳定性：稳定

计数排序适应与所有元素的值密集集中在一定范围中的数据。

注：分配类排序除此之外还有桶排序，有兴趣的同学之后可以去了解一下。

总结

以上就是今天要讲的内容，本文仅仅简单介绍了一些较常用的排序算法，但是还有很多优秀又神奇的排序算法。对此感兴趣的同学可以多多去了解。事实上我们实际应用中很少单一的使用某一种算法而是结合起来使用。

有时候自己写出来的算法代码稳定性与其算法本来的稳定性存在差异，这时就要认真观察自己的代码在边界的处理上是否有更好的选择。有时候将"<="写为"<"或者把"<"写为"<="，代码也同样能得出正确结果但是却会影响稳定性。

对于初学者，往往知道了算法思想也不能敲出正确的代码，这是学习的必经之路，不必太过担忧。坚持练习一段时间就能有较大改善。学习重在坚持！！！希望我的文章可以帮助到大家。愿与各位共勉，共同进步。

mu'mu的碎碎念：这篇博客花了我好长时间呀，希望各位看官一键三连。我好想取一个神仙标题，可惜自己是个取名废，大家帮我想想发在评论区，我遇到喜欢的会采纳。感谢!感谢!感谢!

如果有错误请指出。

参考文献：耿国华.数据结构（用C语言描述）

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

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

  

闽ICP备14008679号