首页 > 编程语言 >【排序算法(二)】——冒泡排序、快速排序和归并排序—>深层解析

【排序算法(二)】——冒泡排序、快速排序和归并排序—>深层解析

时间:2024-07-30 20:53:19浏览次数:19  
标签:归并 right 基准值 int arr 冒泡排序 排序 left

前言:

        接上篇,排序算法除了选择排序(希尔排序)和插入排序(堆排序)之外,还用交换排序(冒泡排序、快速排序)和归并排序已经非比较排序,本篇来深层解析这些排序算法

一、交换排序

        1.1、冒泡排序

        冒泡排序,这个再熟悉不过了,学校中老师讲的第一个排序就是冒泡排序;直接看代码

代码如下:

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

        时间复杂度:O(n^2);空间复杂度O(1)。

        1.2、快速排序

        快速排序,是hoare于1962年提出的一种二叉树结构的交换排序算法,其基本思想为:任意取待排序元素序列中的某元素作为基准值,按照该排序码将待排序集合分割成两个子序列,左子序列中所有元素均小于基准值,右子序列所有元素均大于基准值然后左右子序列重复此过程,直到所有元素都排列在相应位置上。

实现快速排序主要框架如下:

//快速排序
void QuickSort(int* a, int left, int right)
{
	if (left >= right) {
		return;
	}
	//_QuickSort⽤于按照基准值将区间[left,right)中的元素进⾏划分
	int meet = _QuickSort(a, left, right);
	QuickSort(a, left, meet - 1);
	QuickSort(a, meet + 1, right);
}

下面的不同方法指的是找基准值的方法不同而已。

1.2.1、hoare版本

思路:

        1.  创建左右指针,却基准值

        2.  从左到右找出比基准值大的数据,从右到左找出比基准值小的数据,左右指针数据交换,进入下一次循环

这里可能有一些问题,

        1.跳出循环后,right位置的值一定不大于key?

        当left > right时,即right走到了left的左侧,而left走过的位置值都不大于key,因此right此时指向的数据一定不大于key

        2.为什么left或者right指定的数据与key值相等也要交换?

        这里如果,数组中大量的数据都相等,不进行交换的话,就无法进行有效的分割数组。

代码实现:

//快速排序
int _QuickSort1(int* arr, int left, int right)
{
	int key = arr[left];
	int mid = left;
	left++;
	while (left <= right)
	{
		//左边找大
		while (left<=right && arr[left] < key)
		{
			left++;
		}
		//右边找小
		while (left <= right && arr[right] > key)
		{
			right--;
		}
		if (left <= right)
		{
			Swap(&arr[left], &arr[right]);
			left++;
			right--;
		}
	}
	Swap(&arr[mid], &arr[right]);
	return right;
}

1.2.2、挖坑法

思路:

        创建左右指针;首先从右向左找出比基准值小的数据,找到后立即放入左边 "坑" 中,当前位置变为新的 "坑",然后从左往右找出比基准值大的数据,找到后立即放入右边坑中,当前位置变为新的 "坑",结束循环后将最开始存储的分界值放入当前的 "坑"中,返回当前"坑"下标。

代码实现如下:

int _QuickSort2(int* arr, int left, int right)
{
	int tmp = arr[left];
	int hole = left;
	left++;
	while (left < right)
	{
		//从右边开始找
		while (left < right && arr[right] > tmp)
		{
			right--;
		}
		arr[hole] = arr[right];
		hole = right;
		while (left < right && arr[left] < tmp)
		{
			left++;
		}
		arr[hole] = arr[left];
		hole = left;
	}
	arr[hole] = tmp;
	return hole;
}

1.2.3、lomuto指针法

思路:

        创建前后指针,从左往右找比基准值小的进行交换,使得小的都排在基准值的左边。

代码实现:

int _QuickSort(int* arr, int left, int right)
{
	int prev = left, pcur = left + 1;
	int key = left;
	while (pcur <= right)
	{
		if (arr[pcur] < arr[key] && ++prev != pcur)
		{
			Swap(&arr[prev], &arr[pcur]);
		}
		pcur++;
	}
	Swap(&arr[key], &arr[prev]);
	return prev;
}

二、归并排序

思路:

        归并排序,是建立在归并操作上的一种有效的排序算法,该算法是采用分治法的一个典型的应用。将已有序的子序列合并,得到完全有序的序列;即先让每一个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路合并。

代码实现:

//归并排序
void _MergeSort(int* arr, int left, int right,int* tmp)
{
	if (left >= right)
	{
		return;
	}

	int mid = (left + right) / 2;
	_MergeSort(arr, left, mid, tmp);
	_MergeSort(arr, mid+1, right, tmp);


	//合并数组
	int begin1 = left, end1 = mid;
	int begin2 = mid + 1, end2 = right;
	int index = left;
	while (begin1 <= end1 && begin2 <= end2)
	{
		if (arr[begin1] < arr[begin2])
		{
			tmp[index++] = arr[begin1++];
		}
		else {
			tmp[index++] = arr[begin2++];
		}
	}
	while (begin1 <= end1)
	{
		tmp[index++] = arr[begin1++];
	}
	while (begin2 <= end2)
	{
		tmp[index++] = arr[begin2++];
	}
	//将tmp数据拷贝回arr中
	for (int i = left; i <= right; i++)
	{
		arr[i] = tmp[i];
	}
}
void MergeSort(int* arr, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);

	_MergeSort(arr, 0, n - 1, tmp);

	free(tmp);
}

三、非比较排序

非比较排序,就是不进行比较数据来进行排序。

        计数排序

1>  统计相同元素出现次数

2>  根据统计的结果将序列回收到原来的序列中

这里又会存在一些问题,比如如果数据是负数,那该怎样开辟空间?

        这里,我们开辟空间大小为数组数据最大值和最小值之差。

然后在将统计结果返回到原来数组当中时,让数组下标加上原数组最小值即可。

//计数排序
void CountSort(int* arr, int n)
{
	int max = arr[0];
	int min = arr[0];
	for (int i = 0; i < n; i++)
	{
		if (arr[i] > max)
		{
			max = arr[i];
		}
		if (arr[i] < min)
		{
			min = arr[i];
		}
	}

	//开辟空间
	int range = max - min + 1;
	int* tmp = (int*)calloc(sizeof(int),range);
	if (tmp == NULL)
	{
		perror("calloc fail");
		return;
	}

	for (int i = 0; i < n; i++)
	{
		tmp[arr[i] - min]++;
	}
	int j = 0;
	for (int i = 0; i < range; i++)
	{
		while (tmp[i]--)
		{
			arr[j++] = i + min;
		}
	}
}

各种排序算法的算法复杂度和稳定性分析

到这里,排序算法就结束了,希望你能有所收获

感谢各位大佬支持并指出问题,

                        如果本篇内容对你有帮助,可以一键三连支持以下,感谢支持!!!

标签:归并,right,基准值,int,arr,冒泡排序,排序,left
From: https://blog.csdn.net/LH__1314/article/details/140799886

相关文章

  • 排序 floyd 拓扑排序
    //排序.cpp:此文件包含"main"函数。程序执行将在此处开始并结束。///**https://www.acwing.com/problem/content/345/给定n个变量和m个不等式。其中n小于等于26,变量分别用前n的大写英文字母表示。不等式之间具有传递性,即若A>B且B>C,则A>C。请从前往后遍......
  • 归并排序详解
    归并排序简介什么是排序算法排序算法是算法的基石,许多算法都基于排序算法,比如二分搜索、离散化等。这篇文章将要详细介绍将要介绍排序算法之一——归并排序。归并排序的性能归并排序的时间复杂度稳定在\(\mathcal{O}(n\log(n))\),是一种具有稳定性(即相同元素相对位置不变)的排......
  • RuntimeError:permute(sparse_coo):张量输入中的维度数与所需维度排序的长度不匹配
    因此,我使用这个剪辑模型来执行一些标记任务。但是当我使用剪辑模型的文本编码器时,它会出现以下错误:<ipython-input-117-4c513cc2d787>inforward(self,batch)34print(y.size())35print(y.dim())--->36y=self.text_encoder(y)37......
  • 排序 - 题解
    排序时间限制:C/C++1000MS,其他语言2000MS内存限制:C/C++64MB,其他语言128MB描述给定你一个长度为\(n\)的整数数列。请你使用任意排序对这个数列按照从小到大进行排序。并将排好序的数列按顺序输出。数据范围\(1≤n≤100000\)禁止使用sort函数输入描述输入共两......
  • 两种常见排序(冒泡排序和选择排序)详解
    一、冒泡排序1.1、冒泡排序的原理讲解。例如有以下7个数的无序数列储存在数组arr[7]中,现在需要用冒泡排序法来对以下序列进行排序冒泡排序是比较相邻的两个数,如果第一个数比第二个数大,这两个数就要交换两个数的位置,如果第一个数小于第二个数则不用变换位置,例如第一个数3比......
  • 【数据结构】排序
    1.排序的概念及其运用1.1排序的概念排序:指的是将一组数据(通常是一个列表、数组或任何有限集合)按照某种特定的顺序重新排列的过程。这个特定的顺序可以是升序(从小到大)、降序(从大到小)或者根据自定义的规则进行排序。稳定性:假定在待排序的记录序列中,存在多个具有相同的关键字的......
  • Python自定义排序
    Python封装了成熟的排序函数,我们只需要调用内部的sort函数,就可以完成排序。但是实际场景当中,排序的应用往往比较复杂,比如对象类型,当中有多个字段,我们希望按照指定字段排序,或者是希望按照多关键字排序,这个时候就不能简单的函数调用来解决了。1.字典排序我们先来看下最常见的字典......
  • 如何使用 group by 对 pandas 数据框进行排序
    我正在处理类似于下面示例的数据框:importpandasaspdimportnumpyasnpnp.random.seed(0)np.random.seed(0)df=pd.DataFrame({'date':np.tile(['2024-05-01','2024-06-01'],4),'State':np.repeat(['fl&#......
  • 拓扑排序
    一,概念1.DAG图:一个有向图中不存在环,则称为有向无环图,简称DAG图2.拓扑排序:在DAG图中,所有活动可排列成一个线性序列,使得每个活动的所有前驱活动都排在该活动的前面,我们把此序列叫做拓扑序列,由DAG图构造拓扑序列的过程叫做拓扑排序。二,实现过程First:从DAG图中选择一个没有前驱的......
  • 【数据结构】排序算法
    目录排序冒泡排序选择排序直接插入排序希尔排序堆排序归并排序快速排序排序排序的概念:假设含有n个记录的序列为{R1,R2,R3,···,Rn},其相应的关键字分别为{K1,K2,K3,···Kn},需确定1,2,3,···,n的一种排列P1,P2,···,Pn,使其相应的关键字满足Kp1<=Kp2<=K......