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

数据结构与算法—排序算法篇_数据结构与算法排序算法

作者：很楠不爱3 | 2024-04-30 04:25:59

赞

踩

数据结构与算法排序算法

目录

1、选择排序

1.1、算法思想

1.2、步骤

1.3、算法实现

1.4、算法分析

2、 冒泡排序

2.1、算法思想

2.2、算法实现

2.3、算法分析

2.4、改进冒泡排序

3、插入排序

3.1、算法思想

3.2、算法实现

3.3、算法分析

4、希尔排序

4.1、算法思想

4.2、增长量选定规则

4.3、算法实现

4.4、算法分析

5、归并排序

5.1、算法思想

5.2、算法实现

5.3、算法分析

6、快速排序

6.1、算法思想

6.2、算法实现

6.3、算法分析

7、基数排序（桶排序）

7.1、算法思想

7.2、算法步骤

7.3、算法实现

7.4、算法分析

8、堆积树排序

8.1、算法思想

1、选择排序

1.1、算法思想

每趟从待排序的数据元素中，选出最小（或最大）的一个元素，顺序放在待排序的数列最前面，直到全部待排序的数据元素排完。

1.2、步骤

1、查找此数列中的最小元素，将其与第一个交换

2、从第二个值开始找，查找到最小元素，将其与第二个交换

3、以此类推，直到遍历结束

1.3、算法实现

  1. //选择排序
  2. void Select_Sort(int a[],int n) {	//第一个参数是数组，第二个参数是 元素个数
  3. 	for (int i = 0; i < n;i++) {
  4. 		for (int j = i + 1; j < n;j++) {
  5. 			if (a[i] > a[j]) {	//a[i] > a[j] 就是升序 ，< 为降序
  6. 				int temp;
  7. 				temp = a[i];
  8. 				a[i] = a[j];
  9. 				a[j] = temp;
  10. 			}
  11. 		}
  12. 	}
  13.  
  14. }

1.4、算法分析

1、时间复杂度：O(n2)

2、空间复杂度：O(1)

3、会改变数据排列顺序，是不稳定排序

4、适用于数据量小，或有部分数据已经排序的情况

2、 冒泡排序

2.1、算法思想

1、比较相邻的元素，如果前一个元素比后一个元素大，就交换两个元素的位置。

2、对每一对相邻元素作相同的工作，从开第一对元素到结尾最后一对元素，最终最后位置的元素就是最大值。

2.2、算法实现

  1. //冒泡排序
  2. void bubble_sort(int a[], int n) {
  3. 	for (int i = 0; i < n; i++) {
  4. 		for (int j = 1; j < n - i;j++) {
  5. 			if (a[j-1] > a[j]) {	//  > 升序， < 降序
  6. 				int temp;
  7. 				temp = a[j-1];
  8. 				a[j-1] = a[j];
  9. 				a[j] = temp;
  10. 			}
  11. 		}
  12. 		
  13. 	}
  14. }

2.3、算法分析

1、时间复杂度：O(n2)

2、冒泡在比较两个相邻元素后，再决定是否互换位置，不会改变原来排列的顺序，因此是稳定排序算法。

3、空间复杂度：O(1)

4、冒泡排序法适合数据量小，或有部分数据已经排过序的情况。

2.4、改进冒泡排序

缺点：无论数据是否已排序完成都固定会执行n(n-1)/2次数据比较。

改进方法：加入一个判断条件来判断何时可以提前结束循环。

  1. //改进冒泡排序
  2. void bubble_sort1(int a[], int n) {
  3. 	for (int i = 0; i < n; i++) {
  4. 		/*
  5. 		引入一个标志，如果为0 则说明以下未发生交换，
  6. 		即，后面的数据已经有序。
  7. 		如果不等于 0 ，说明后面暂时无序，还需要比较
  8. 		*/
  9. 		int flag = 0;	
  10. 		for (int j = 1; j < n - i; j++) {
  11. 			if (a[j - 1] > a[j]) {	//  > 升序， < 降序
  12. 				int temp;
  13. 				temp = a[j - 1];
  14. 				a[j - 1] = a[j];
  15. 				a[j] = temp;
  16. 				flag++;
  17. 			}
  18. 		}
  19. 		if (flag == 0) {	/为 0 ，结束排序
  20. 			break;
  21. 		}
  22.  
  23. 	}
  24. }

3、插入排序

3.1、算法思想

1、把所有的元素分为两组，已经排序的和未排序的

2、找到未排序的组中的第一个元素，向已排序的组中进行插入；

3、倒序遍历已排序的元素，依次和待插入的元素进行比较，如果某个元素小于待插入元素，则交换两者位置。

3.2、算法实现

  1. //插入排序
  2. void insert_sort(int a[],int n) {
  3. 	for (int i = 1; i < n;i++) {
  4. 		int index = i;	//引入一个变量，记录当前待插入的元素索引
  5. 		for (int j = i-1; j >= 0;j--) {
  6. 			if (a[j] > a[index]) {	// > 升序   <降序
  7. 				int temp;
  8. 				temp = a[j];
  9. 				a[j] = a[index];
  10. 				a[index] = temp;
  11. 				index = j;	//交换后，需要更换索引的值，才能进行下一步比较
  12. 			}
  13. 		}
  14. 	}
  15.  
  16. }

3.3、算法分析

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

2、插入排序是稳定的排序

3、空间复杂度：O(1)

4、适用于大部分数据已经排序的情况，或者往已排序的数据库中添加新的元素，然后再次排序的情况。

5、插入排序会造成大量的数据迁移，建议在链表上使用。

4、希尔排序

4.1、算法思想

1、选定一个增长量h，按照增长量h作为数据分组的一句，对数据进行分组。

2、对分好组的每一组数据进行插入排序。

3、减小增长量，最小减为1，重复第二步操作。

4.2、增长量选定规则

对于初始增长量，没有固定的规则，很多论文研究了各种不同的递增序列，但都无法增量那个序列是最好的，这里简单介绍两种：
1、

  1. int h = 1;
  2. while(h < 数组长度 / 2){
  3.     h = 2*h -1;
  4. }

2、​​ h = 数组长度 / 2;​​

每次减少量：​​ h = h /2;​​

4.3、算法实现

  1. //希尔排序
  2. void shell_sort(int a[],int n) {	//1、数组首地址  2、数组长度
  3. 	//计算步长
  4. 	int jmp = 1;
  5. 	while (jmp < n >>1) {	 // jmp < n / 2   >>1 一定程度上等价于 /2
  6. 		jmp = jmp * 2 + 1;
  7. 	}
  8.  
  9. 	//插入排序
  10. 	int tmp;	//记录当前待插入元素
  11. 	int j;		//定位比较的元素
  12. 	while (jmp != 0) {
  13. 		for (int i = jmp; i < n; i++) {
  14. 			tmp = a[i];
  15. 			j = i - jmp;
  16. 			while (j >= 0 && tmp < a[j]) {
  17. 				a[j + jmp] = a[j];
  18. 				j = j - jmp;
  19. 			}
  20. 			a[j + jmp] = tmp;
  21. 		}
  22. 		jmp = jmp / 2;
  23. 	}
  24. }

4.4、算法分析

1、当初始步长 ​​h = 数组长度 / 2 ​​时 ，时间复杂度为O(n3/2)

2、稳定的排序算法

3、空间复杂度：O(1)

4、适用于大部分数据已经排序的情况

5、归并排序

5.1、算法思想

1、尽可能的将一组数据才分成两个等分的子组，并对每个子组进行拆分，直到每个子组的元素个数为1为止

2、将相邻的两个子组进行合并成一个有序的大组

3、重复步骤2，直到最终只有一个组为止。

5.2、算法实现

  1. //归并排序
  2. //2、归并 vector
  3. void Merge(int a[], int left, int mid, int right) {
  4. 	vector<int> vt;		//定义一个临时动态数组
  5. 	vt.resize(right-left+1);	//指定vector尺寸
  6. 	int k = 0;
  7. 	int pl = left;
  8. 	int pr = mid + 1;
  9.  
  10. 	//同时成立时，两个索引的值进行比较
  11. 	while (pl <= mid && pr <= right) {
  12. 		if (a[pl] < a[pr]) {
  13. 			vt[k++] = a[pl++];
  14.  
  15. 		}
  16. 		else {
  17. 			vt[k++] = a[pr++];
  18.  
  19. 		}
  20.  
  21. 	}
  22.  
  23. 	//如果是因为 pr 不满足条件，则将剩下的pl索引元素放入
  24. 	while (pl <= mid) {
  25. 		vt[k++] = a[pl++];
  26. 	}
  27.  
  28. 	//如果是因为 pl 不满足条件，则将剩下的pr索引元素放入
  29. 	while (pr <= right) {
  30. 		vt[k++] = a[pr++];
  31. 	}
  32.  
  33. 	//拷贝 临时 -> 目标
  34. 	for (int i = left, j = 0; i <= right; i++, j++) {
  35. 		a[i] = vt[j];
  36. 	}
  37.  
  38. }
  39.  
  40.  
  41. //1、排序
  42. void Merge_sort(int a[],int left,int right) {	//1、数组首地址，2、组的左边界，3、组的右边界
  43. 	//递归到子组只有一个元素时，退出
  44. 	if (left == right) {
  45. 		return;
  46. 	}
  47.  
  48. 	//折半，划分子组
  49. 	int mid = (left + right) / 2;
  50. 	//左子组归并排序
  51. 	Merge_sort(a,left,mid);
  52. 	//右子组归并排序
  53. 	Merge_sort(a, mid+1,right);
  54. 	//排序后，进行归并
  55. 	Merge(a,left,mid,right);
  56.  
  57. }

5.3、算法分析

1、时间复杂度：O(nlog2n)

2、缺点：需要申请数组空间，导致空间浪费，是典型的空间换时间操作

3、归并排序是稳定排序法

6、快速排序

6.1、算法思想

1、在数据中找一个虚拟的中间件（一般就是第一个元素）

2、按照中间值，将小于中间值的数据放在中间值的左边，大于中间值的数据放在右边

3、再以同样的方式分别处理左右两边的数据，直到排完序为止。

6.2、算法实现

1、递归

  1. //快速排序——递归
  2. void quick_sort(int a[],int size, int left, int right) { //1、数组首地址 2、左边界 3、右边界	
  3.  
  4. 	if (left >= right) {
  5. 		return;
  6. 	}
  7. 	//以a[left] 为基准
  8. 	int le = left+1;
  9. 	int ri = right;
  10.  
  11. 	while(true){
  12.  
  13. 		cout << "第" << ret++ << "次：";
  14. 		for (int i = 0; i < size; i++) {
  15. 			cout << a[i] << " ";
  16. 		}
  17. 		cout << endl;
  18.  
  19.  
  20. 		//从左->右，取大于
  21. 		while (le <= right) {
  22. 			if (a[le] >= a[left]) {
  23. 				break;
  24. 			}
  25. 			le++;
  26. 		}
  27.  
  28. 		//从右->左，取小于
  29. 		while (ri >= left+1) {
  30. 			if (a[ri] <= a[left]) {
  31. 				break;
  32. 			}
  33. 			ri--;
  34. 		}
  35.  
  36. 		//如果 左边索引 < 右边索引 ，交换le 和 ri索引的值
  37. 		if (le < ri) {
  38. 			int temp1;
  39. 			temp1 = a[le];
  40. 			a[le] = a[ri];
  41. 			a[ri] = temp1;
  42. 		}
  43. 		else {
  44. 			break;
  45. 		}
  46. 	}
  47. 	//当左边索引 >= 右边索引 ，将ri位置的元素和base 交换
  48. 	if (le >= ri) {
  49. 		int temp;
  50. 		temp = a[left];
  51. 		a[left] = a[ri];
  52. 		a[ri] = temp;
  53.  
  54.  
  55. 		quick_sort(a,size,left,ri-1);
  56. 		quick_sort(a,size,ri+1,right);
  57. 	}
  58. }

2、非递归—利用栈，代替递归

  1. // 子组排序算法
  2. int get_key(int a[],int left, int right) {
  3.  
  4. 	//取基准为 a[left]
  5. 	int lf1 = left+1;
  6. 	int rg1 = right;
  7.  
  8. 	while (true) {	//控制比较躺数
  9. 		//左 -> 右  
  10. 		while (lf1 <= right) {
  11. 			if (a[lf1] > a[left]) {
  12. 				break;
  13. 			}
  14. 			lf1++;
  15. 		}
  16.  
  17. 		//右 -> 左  
  18. 		while (rg1 >= left + 1) {
  19. 			if (a[rg1] < a[left]) {
  20. 				break;
  21. 			}
  22. 			rg1--;
  23. 		}
  24.  
  25. 		if (lf1 < rg1) {
  26. 			int temp = a[lf1];
  27. 			a[lf1] = a[rg1];
  28. 			a[rg1] = temp;
  29. 		}
  30. 		else {
  31. 			break;
  32. 		}
  33. 	}
  34. 	if (lf1 >= rg1) {
  35. 		int tmp = a[left];
  36. 		a[left] = a[rg1];
  37. 		a[rg1] = tmp;
  38. 	}
  39.  
  40. 	return rg1;
  41.  
  42. }
  43.  
  44. //快速排序——非递归 栈
  45. void quick_sort_no(int a[],int size, int left, int right) {
  46. 	if (left>=right) {
  47. 		return;
  48. 	}
  49.  
  50. 	stack<int> s;
  51. 	s.push(left);
  52. 	s.push(right);
  53.  
  54. 	while (!s.empty()) {
  55. 		int rg = s.top();
  56. 		s.pop();
  57. 		int lf = s.top();
  58. 		s.pop();
  59.  
  60. 		int key = get_key(a,lf, rg);
  61.  
  62. 		cout << "第" << ret++ << "次：";
  63. 		for (int i = 0; i < size; i++) {
  64. 			cout << a[i] << " ";
  65. 		}
  66. 		cout << endl;
  67.  
  68. 		if (key-1 > lf ) {
  69. 			s.push(lf);
  70. 			s.push(key-1);
  71. 		}
  72. 		if (key+1 < rg) {
  73. 			s.push(key+1);
  74. 			s.push(rg);
  75. 		}
  76. 	}
  77. }

3、非递归—利用队列，代替递归

  1. // 子组排序算法
  2. int get_key(int a[],int left, int right) {
  3.  
  4. 	//取基准为 a[left]
  5. 	int lf1 = left+1;
  6. 	int rg1 = right;
  7.  
  8. 	while (true) {	//控制比较躺数
  9. 		//左 -> 右  
  10. 		while (lf1 <= right) {
  11. 			if (a[lf1] > a[left]) {
  12. 				break;
  13. 			}
  14. 			lf1++;
  15. 		}
  16. 		  
  17. 		//右 -> 左  
  18. 		while (rg1 >= left + 1) {
  19. 			if (a[rg1] < a[left]) {
  20. 				break;
  21. 			}
  22. 			rg1--;
  23. 		}
  24.  
  25. 		if (lf1 < rg1) {
  26. 			int temp = a[lf1];
  27. 			a[lf1] = a[rg1];
  28. 			a[rg1] = temp;
  29. 		}
  30. 		else {
  31. 			break;
  32. 		}
  33. 	}
  34. 	if (lf1 >= rg1) {
  35. 		int tmp = a[left];
  36. 		a[left] = a[rg1];
  37. 		a[rg1] = tmp;
  38. 	}
  39.  
  40. 	return rg1;
  41.  
  42. }
  43.  
  44. //快速排序——非递归 队列
  45. void quick_sort_no01(int a[], int size, int left, int right) {
  46. 	if (left >= right) {
  47. 		return;
  48. 	}
  49.  
  50. 	queue<int> q;
  51. 	q.push(left);
  52. 	q.push(right);
  53.  
  54. 	while (!q.empty()) {
  55. 		int lf = q.front();
  56. 		q.pop();
  57. 		int rg = q.front();
  58. 		q.pop();
  59.  
  60. 		int key = get_key(a, lf, rg);
  61.  
  62. 		cout << "第" << ret++ << "次：";
  63. 		for (int i = 0; i < size; i++) {
  64. 			cout << a[i] << " ";
  65. 		}
  66. 		cout << endl;
  67.  
  68. 		if (key - 1 > lf) {
  69. 			q.push(lf);
  70. 			q.push(key - 1);
  71. 		}
  72. 		if (key + 1 < rg) {
  73. 			q.push(key + 1);
  74. 			q.push(rg);
  75. 		}
  76.  
  77.  
  78. 	}
  79. }

6.3、算法分析

1、最好和平均情况下，时间复杂度O(nlog2n),最坏，O(n^2)

2、快速排序不是稳定的排序算法

3、最好情况下，空间复杂度O(log2n)，最坏情况下，O(n)

4、快速排序算法是平均速度最快的算法。

7、基数排序（桶排序）

7.1、算法思想

从数据的低位（LSD）或者高位 (MSD) 开始，按照这一位数字的值(0~9)放到对应的编号为 0~9 的桶中。我们按照这一位数字进行完了排序，再按照次低位(下一位)数字进行上述的操作。重复这样的操作一直到最高位，直到最后每一位数字都进行完排序，整个基数排序完成。

7.2、算法步骤

1、建立一个桶，存放每个位数上出现元素的个数

2、最低位开始，将数列按照该位的数值放入到桶中，

3、将桶中的存放的数据按 a[i+1] = a[i],依次相加，计算出当前数字的位置。

4、把数列按照在当前桶中的顺序依次存放到临时数组中

5、将临时数组的值，拷贝到原数组中

6、依次循环，直到最高位比较结束，排序完成。

7.3、算法实现

  1. //基数排序（桶排序）
  2. void radix_sort(int* a,int size) {
  3.  
  4. 	//找出数组中的最大值(顺序查找)
  5. 	int max = a[0];
  6. 	for (int i = 1; i < size;i++) {
  7. 		if (a[i] > max) {
  8. 			max = a[i];
  9. 		}
  10. 	}
  11. 	
  12. 		//定义一个桶，存放每个位数，出现的元素次数
  13. 	int base = 1;
  14. 	int* tmp = (int*)malloc(sizeof(int) * size);	//开辟一块连续的地址，作为临时数组
  15. 	if (tmp) {
  16. 		while (max / base > 0) {
  17. 			int data[10] = { 0 };
  18. 			//记录元素在每个位数上，出现的次数
  19. 			for (int i = 0; i < size; i++) {
  20. 				data[(a[i] / base) % 10]++;
  21. 			}
  22.  
  23. 			//将桶中的数据，变为需要存放在临时数组的位置
  24. 			for (int i = 1; i < 10; i++) {
  25. 				data[i] += data[i - 1];
  26. 			}
  27.  
  28. 			for (int i = size - 1; i >= 0; i--) {
  29. 				tmp[data[(a[i] / base) % 10] - 1] = a[i];
  30. 				data[(a[i] / base) % 10]--;
  31. 			}
  32. 			for (int i = 0; i < size; i++) {
  33. 				a[i] = tmp[i];
  34. 			}
  35.  
  36. 			base = base * 10;
  37. 		}
  38. 	}
  39. 	free(tmp);	
  40. }

7.4、算法分析

1、时间复杂度：O(nlog​​p​​k)

2、基数排序是稳定排序法

3、空间复杂度：O(n*p),n是原始数据个数，p是数据字符数

4、如果n很大，p固定或者很小，此排序效率很高。

8、堆积树排序

8.1、算法思想

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

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

  

闽ICP备14008679号