八大排序详解（二）：冒泡排序和（超详细 ）

一.冒泡排序 1.什么是冒泡排序？

冒泡排序（Bubble Sort),是最基础的排序，之所以叫做冒泡排序，因为每一个元素都可以像小气泡一样，根据自身大小一点一点向数组的一侧移动。也可以成为沉石排序。冒泡排序是稳定的（不存在跳跃交换）

2.冒泡排序方法

每一趟排序从左向右两两比较，如果左边值大于右边值，则进行交换（从小到大排列  确定每一趟排序最大值在末尾）

初始：12 3 24 31 21 31

第一趟排序：3 12 24 21 31 31

第二趟排序：3 12 21 24 31 31

第三趟排序：3 12 21 24 31 31

第四趟排序：3 12 21 24 31 31

第五趟排序：3 12 21 24 31 31

第六趟排序：不需要

发现：len个值  需要len-1趟排序   但在上面排序中，我们发现在第三趟的时候，冒泡排序就已经将数据完全有序了，那么后面就不需要在排序了，所以这就有了优化。我们这里可以下一个标记flag.

3.冒泡排序代码实现

void Bubble_Sort(int* arr, int len) {
	for (int i = 0; i < len - 1; i++) //控制趟数
    
  {
		bool flag = true;//下标记
		printf("第%d趟\n", i+1);
		for (int j = 0; j < len - 1 - i; j++) {
			if (arr[j] > arr[j + 1]) {
				
				flag = false;//存在交换 将flag变为false
				int tmp = arr[j + 1];
				arr[j + 1] = arr[j];
				arr[j] =tmp;
			}
		}
		if (flag) {
			break;
		}
	}
}

4.时间复杂度 冒泡排序时间复杂度是o（n^2),空间复杂度是o(1) 二.归并排序 1.归并排序：归并排序（Merge sort）是建立在归并 *** 作上的一种有效的排序算法，归并排序对序列的元素进行逐层折半分组，然后从最小分组开始比较排序，合并成一个大的分组，逐层进行，最终所有的元素都是有序的 2.归并排序规则：（1）先将所有数据一个一个的分组（如果一个组内只有一个数据 则认为其已经有序） （2）两两合并（两个组合并）

 

3.归并排序代码实现：

//单次两个组合并  //gap  代表两个组合并的每一个组多少个值
void Merge(int *arr, int len, int gap) //
{
	int *brr = (int *)malloc(len * sizeof(int));//额外辅助空间brr
	int low1 = 0;
	int high1 = low1+gap-1;
	int low2 = high1+1;
	int high2 = low2+gap-1 < len ? low2+gap-1 : len-1;

	int k = 0;//代表辅助空间brr的下标
	
	while(low2 < len)//判断左右手都抓到数据组
	{
		
		while(low1<=high1 && low2<=high2)//确定两个组，都还有值
		{
			if(arr[low1] <= arr[low2])
			{
				brr[k++] = arr[low1++];
			}
			else
			{
				brr[k++] = arr[low2++];
			}
		}

		//此时，上面while循环退出，代表肯定有一个组空了，另一个组没空
		//此时需要将不空的组，剩余数据一次挪动到brr中
		while(low1 <= high1)//如果左边组不空
		{
			brr[k++] = arr[low1++];
		}
		while(low2 <= high2)//如果右边组不空
		{
			brr[k++] = arr[low2++];
		}

		low1 = high2+1;
		high1 = low1+gap-1;
		low2 = high1+1;
		high2 = low2+gap-1 < len ? low2+gap-1 : len-1;
	}

	//此时，整体退出，代表着最终抓的两个组中的，左边这个组还有数据没有处理掉
	while(low1 < len)//如果左边组不空
	{
		brr[k++] = arr[low1++];
	}

	//最后，将处理结束后brr中数据，重新拷贝回arr
	for(int i=0; i

4.总结：

归并排序时间复杂度：O(nlogn)  空间复杂度：O(n)  稳定性：稳定

欢迎分享，转载请注明来源：内存溢出

原文地址:https://54852.com/langs/924430.html