排序(一)----冒泡排序,插入排序

 前言

今天讲一些简单的排序,冒泡排序和插入排序,但是这两个排序时间复杂度较大,只是起到一定的学习作用,只需要了解并会使用就行,本文章是以升序为例子来介绍的

一冒泡排序

思路

冒泡排序是一种简单的排序算法，它重复地遍历要排序的序列，每次比较相邻的两个元素，如果顺序错误则交换它们。这样每一轮遍历过后，序列中最大的元素就会被移动到最后的位置上，直至整个序列有序。

具体步骤如下：
1. 从序列的第一个元素开始，比较相邻的两个元素，如果顺序错误则交换它们；
2. 继续遍历序列，每次比较相邻的两个元素并交换，直至遍历完整个序列；
3. 重复以上步骤，除去已排序的元素，直至整个序列有序

屏幕录制 2024-05-14 213653-CSDN直播

具体实现

这里建议排序可以写一次的运动在推测总体的代码,下面第一次写代码,下面的n 是数组具体个数,但是第一个代码和第二个代码是一样的情况,都可以实现这个排序

为什么会不一样呢?

• 因为下面的索引  i  的不同,第一个是i和i+1,那么假设有4个数的话,从0下标开始比较3次,i<n-1  满足了条件三次循环的条件,并从下标0开始比较
• 因为下面的索引  i  的不同,第二个是i和i-1,那么假设有4个数的话,从0下标开始比较3次,i<n 满足了条件三次循环的条件,并从下标1开始比较

 
		for (int i = 0; i < n-1; i++) {
			if (a[i] > a[i + 1]) {
				Swap(&a[i], &a[i + 1]);
			}
		}
 
		for (int i = 1; i < n ; i++) {
			if (a[i - 1] > a[i]) {
				Swap(&a[i], &a[i-1]);
			}
		}

实现了一次的代码之后就可以套用整个代码的逻辑去完善代码,总共n个数,那么比较n-1次就行了

为什么?因为每一次比较两个数,例如比较3个数,那么就是

• 第一个和第二个数
• 第二个数和第三个数比较

void BubbleSort(int* a, int n) {
	for (int j = 0; j < n; j++) {//运行n-1次
		for (int i = 0; i < n-j-1; i++) {
			if (a[i] > a[i + 1]) {
				Swap(&a[i], &a[i + 1]);
			}
		}
	}
}

然后下面是结果,是这上面的动态图片是一致的,可以和上面的图片一起配合理解

总结

冒泡排序的时间复杂度为O(n^2)，其中n为序列的长度。虽然它比较简单，但由于其效率较低，在实际应用中往往不被推荐使用。

二插入排序

思路

插入排序是一种简单直观的排序算法。它的基本思想是将待排序的元素依次插入已排好序的序列中，直到全部元素都插入完成。

具体操作如下：
1. 将待排序的元素分成已排序和未排序的两部分。初始时已排序部分只包含第一个元素，未排序部分包含剩下的元素。
2. 从未排序部分取出第一个元素，与已排序部分的元素逐个比较。如果当前元素小于已排序部分的某个元素，则将该元素插入到该位置，同时将该位置之后的元素都后移一位。
3. 重复步骤2，直到未排序部分为空，即所有元素都已插入到已排序部分。

屏幕录制 2024-05-14 223809-CSDN直播

具体实现

还是和刚才一样,先实现一次代码的运行来完善整个代码,具体的思路是先插入数字,每一次插入数字要前最后一个数字比较

• 如果比他大的话符合题目条件,就跳出循环
• 如果更小的话,就将和插入数字比较的数字往后移动来留出空位最后给他插入,

比如1,2插入一个0的话,与2比较2往后移,是一次循环,接着end--进入下一循环,比一小就将1往后移,插入数字就移动到1的前面,变成0,1,2

int end = i;
int tem = a[end + 1];
while (end >= 0)
{
	if (tem < a[end]) {
		a[end + 1] = a[end];//往后移动,留出空位
		end--;
	}
	else
		break;
}
a[end+1] = tem;//把前面的空位填满

那么就把它补充一下变成完整的代码,由一趟看出是不断插入的,每一次比较两个数0比较1 0  

i=1比较1 2,所以只要到n-1就行,如果i<n的话end+1溢出,所以下面是n-1

void InsertSort(int*a, int n) {
	//0 end
	for (int i = 0; i < n-1; i++) 
		int end = i;
		int tem = a[end + 1];
		while (end >= 0)
		{
			if (tem < a[end]) {
				a[end + 1] = a[end];//留出空位
				end--;
			}
			else
				break;
		}
		a[end+1] = tem;//把前面的空位填满
	}
	
 
}

总结

插入排序的时间复杂度为O(n^2)，其中n为待排序元素的个数。最好情况下，如果待排序的序列已经是有序的，插入排序的时间复杂度为O(n)。插入排序是一种稳定的排序算法，它不会改变相等元素的相对顺序。

学习思考

学习了冒泡排序和选择排序虽然他们的时间复杂度是o^2,但是选择排序更优一点,具体的可以通过

下面是用了一个函数clock的它的作用是记录时间,单位是毫秒,可以计算相同情况下这个代码运行的时间差异,来比较代码的优劣

	int begin7 = clock(); 
	BubbleSort(a7, N);
	int end7 = clock(); 
	int begin1 = clock();
	InsertSort(a1, N);
	int end1 = clock();

因为冒泡排序只是全是有序的才会只执行一次内层循环

选择排序只要插入数字比中间数字小的话,就会跳出循环,与之相比跳出循环的可能性更高

所以代码光看时间复杂度是不行的要结合具体情况分析!!