惊叹数据结构之美，品味排序算法之妙：对四大排序的详细介绍

文章惊叹数据结构之美，品味排序算法之妙：对四大排序的详细介绍分享给大家，欢迎收藏Java资料网，专注分享技术知识

大家好，这里是小编的博客频道
小编的博客：就爱学编程

很高兴在CSDN这个大家庭与大家相识，希望能在这里与大家共同进步，共同收获更好的自己！！！

---

---

那接下来就让我们开始遨游在知识的海洋！

正文

---

一、冒泡排序（Bubble Sort）

1. 原理：通过重复遍历要排序的序列，每次比较相邻的两个元素并交换它们的位置，如果它们的顺序错误（即前一个元素大于后一个元素）。这样，每一轮遍历都会将当前未排序部分中的最大元素移动到末尾。这个过程就像气泡一样逐渐把较大的元素“冒”到数组的顶端，因此得名冒泡排序。

1. 过程：

• 第一次遍历时，比较第一个和第二个元素，如果前者大于后者则交换；然后比较第二个和第三个元素，依此类推。这样一轮下来，最大的元素就被移动到了数组的最后一个位置。

• 接着进行第二轮遍历，这次不再考虑已经排好序的最大元素，继续对剩余的元素进行比较和交换。

• 重复上述步骤，直到整个数组有序为止。

代码实现：

void Swap(int* p1, int* p2) {
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}

//冒泡排序
void BubbleSort(int* a, int n) {
	for (int i = 0; i < n; i++) {
		int change = 0;
		for (int j = 0; j < n - i - 1; j++) {
			if (a[j] > a[j + 1]) {
				change = 1;
				Swap(&a[j], &a[j + 1]);
			}
		}
		if (change == 0) break;
	}
}

1. 时间复杂度：平均和最坏情况下为O(n^2)，最好情况为O(n)（当序列已经有序时）。

1. 稳定性：稳定排序算法，即相等元素的相对位置在排序前后不会改变。

1. 适用场景：适用于数据量较小且对效率要求不高的场景，如小型程序中对学生成绩的快速排序。

---

二、选择排序（Selection Sort）

1. 原理：从未排序的部分找到最小（或最大）的元素，将其放到已排序部分的末尾（或开头）。

1. 过程：

• 从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置。

• 在剩余的集合中重复上述步骤，直到所有元素都排列完毕。

代码实现：

void Swap(int* p1, int* p2) {
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}

//选择排序
void SelectSort(int* a, int n) {
	int left = 0, right = n - 1;
	while (left < right) {
		int mini = left, maxi = right;
		for (int i = left; i <= right; i++) {
			if (a[i] <= a[mini]) {
				mini = i;
			}
			if (a[i] > a[maxi]) {
				maxi = i;
			}
		}
		Swap(&a[mini], &a[left]);
		Swap(&a[maxi], &a[right]);

		++left;
		--right;
	}

1. 时间复杂度：无论数据规模如何，其时间复杂度都是O(n^2)。

1. 稳定性：不稳定排序算法，因为相同关键字的记录可能会因为最后一步的赋值而更改相对次序。

1. 适用场景：适用于数据量较小且对稳定性无要求的场景，如小型库存管理系统中对库存物品价格的排序。

---

三、插入排序（Insertion Sort）

1. 原理：构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

1. 过程：

• 将第一个元素视为已排序部分。

• 取下一个元素，与已排序部分的元素从后往前逐一比较，找到合适的位置插入。

• 重复上述步骤，直到所有元素都插入到已排序部分中。

代码实现：

//插入排序-------O(N ^ 2)
void InsertSort(int* a, int n) {
	for (int i = 1; i < n; i++) {
		int end = i - 1;					//对应有序数字最后一个元素的下标
		int temp = a[end + 1];					//end的后一个，也就是要插入的元素
		while (end >= 0) {
			if (temp < a[end])
			{
				a[end + 1] = a[end];
				--end;
			}
			else {
				break;
			}
		}
		a[end + 1] = temp;
	}
}

1. 时间复杂度：平均和最坏情况下均为O(n^2)，但在数据基本有序的情况下，其性能可以接近O(n)。

1. 空间复杂度：O(1)，因为它是一种原地排序算法，不需要额外的存储空间。

1. 稳定性：稳定排序算法。

1. 适用场景：适用于数据量较小且基本有序的数据排序场景，如实时数据处理系统中对新数据的快速排序。

---

四、希尔排序（Shell Sort）

1. 原理：是插入排序的一种改进版，也称为缩小增量排序。它先选定一个整数gap作为增量，将待排序文件中的所有记录分成若干组，每组内的记录相距gap个位置。然后对每组内的记录进行直接插入排序。随着排序的进行，逐步减小gap的值，直到gap为1时，对整个序列进行一次最后的插入排序。

1. 过程：

• 选择初始增量gap，通常取数组长度的一半。

• 根据当前的gap值，将数组分成若干子序列，对每个子序列进行插入排序。

• 逐步减小gap的值，并重复上述步骤，直到gap为1时进行一次完整的插入排序。

代码实现：

//希尔排序-------O(N ^ 1.3)
void ShellSort(int* a, int n) {
	int gap = n;
	while (gap > 1) {
		gap /= 2;
		/*for (int i = 0; i < gap; i++) {
			for (int j = i; j < n - gap; j += gap) {
				int end = j;
				int tmp = a[end + gap];
				while (end >= 0) {
					if (tmp < a[end]) {
						a[end + gap] = a[end];
						end -= gap;
					}
					else {
						break;
					}
				}
				a[end + gap] = tmp;
			}
		}*/

		for (int i = 0; i < n - gap; i++) {
			int end = i;
			int tmp = a[end + gap];
			while (end >= 0) {
				if (tmp < a[end]) {
					a[end + gap] = a[end];
					end -= gap;
				}
				else {
					break;
				}
			}
			a[end + gap] = tmp;
		}
		PrintArray(a, n);
		printf("\n");
	}
}

1. 时间复杂度：平均时间复杂度约为O(n^1.3)至O(n2)之间，具体取决于增量的选择和数据的分布情况。但通过优化增量序列，可以显著提高排序效率。

1. 空间复杂度：O(1)，同样是一种原地排序算法。

1. 稳定性：不稳定排序算法。

1. 适用场景：适用于中等规模的数据排序，当希望获得比简单排序算法更好的效率时。

综上所述：

• 这四种排序算法各有优缺点和适用场景。在实际应用中，应根据具体需求和数据特点选择合适的排序算法以提高程序执行效率和用户体验。

---

快乐的时光总是短暂，咱们下篇博文再见啦！！！不要忘了，给小编点点赞和收藏支持一下，在此非常感谢！！！

文章来源:https://blog.csdn.net/z15879084549/article/details/145091531
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若内容造成侵权/违法违规/事实不符，请联系邮箱：jacktools123@163.com进行投诉反馈，一经查实，立即删除！