【数据结构】排序之交换排序(冒泡 | 快排)

这篇具有很好参考价值的文章主要介绍了【数据结构】排序之交换排序(冒泡 | 快排)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

1. 前言

在之前的博客中介绍了插入排序,有需要的可以点这个链接: link,这次来介绍交换排序,包括冒泡和快排。
话不多说,正文开始。

2. 交换排序

基本思想:所谓交换,就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置。

交换排序的特点是:将键值较大的记录向序列的尾部移动,键值较小的记录向序列的前部移动。

交换排序这里介绍冒泡排序和快速排序,来一起看看。

3. 冒泡排序

【数据结构】排序之交换排序(冒泡 | 快排),数据结构,数据结构,算法,排序算法
动图形象的展示了冒泡排序的过程。

冒泡排序的特性总结:

  1. 冒泡排序是一种非常容易理解的排序
  2. 时间复杂度:O(N^2)
  3. 空间复杂度:O(1)
  4. 稳定性:稳定

3.1 分析

交换排序肯定离不开交换,就先写一个Swap。

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

同样的方法,先实现单趟排序,如果前一个大于后一个就交换,把最大的放在了最后。
得注意把控区间的位置,如果if中的代码是a[i+1]>a[i],那么上面循环的区间就是从0到n-1。
【数据结构】排序之交换排序(冒泡 | 快排),数据结构,数据结构,算法,排序算法
第一趟的位置在n-1,那么第j趟就是n-j。
所以对于总的来排,就在外面套一个循环,也就是:
【数据结构】排序之交换排序(冒泡 | 快排),数据结构,数据结构,算法,排序算法
来看看使用结果
【数据结构】排序之交换排序(冒泡 | 快排),数据结构,数据结构,算法,排序算法
如果说没有给定的数据已经排好序了,就不用经行交换了,就加一个标志bool exchange = false,如果交换了就变为true。
【数据结构】排序之交换排序(冒泡 | 快排),数据结构,数据结构,算法,排序算法

3.2 代码实现

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

void BubbleSort(int* a, int n)
{
	for (int j = 0; j < n; j++)
	{
		bool exchange = false;
		for (int i = 1; i < n - j; i++)
		{
			if (a[i - 1] > a[i])
			{
				Swap(&a[i - 1], &a[i]);
				exchange = true;
			}
		}

		if (exchange == false)
			break;
	}

}

4. 快速排序

快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法。

其基本思想为:任取待排序元素序列中的某元素作为基准值,按照该排序码将待排序集合分割成两子序列,左子序列中所有元素均小于基准值,右子序列中所有元素均大于基准值,然后最左右子序列重复该过程,直到所有元素都排列在相应位置上为止。

快速排序有三种实现方法,下面来介绍。

4.1 hoare版本

hoare版本是怎么实现的?
来看看动图:
【数据结构】排序之交换排序(冒泡 | 快排),数据结构,数据结构,算法,排序算法
可以看到这里,先选取了一个关键的值key,
【数据结构】排序之交换排序(冒泡 | 快排),数据结构,数据结构,算法,排序算法

然后右边边开始走,可以发现,当右边找到第一个比key小的值,就停下来。然后走左边,左边找到第一个比key大的值,然后左右两边交换;交换完,又继续。
【数据结构】排序之交换排序(冒泡 | 快排),数据结构,数据结构,算法,排序算法
当左右两边相遇就结束,然后将key与这个位置交换。
【数据结构】排序之交换排序(冒泡 | 快排),数据结构,数据结构,算法,排序算法
为什么要相遇位置比key的值小?
因为是从右边先走,相遇就有两种情况:

  1. R遇到L,R没有找到比key小的值,就一直走,直到遇见L,相遇位置是L,比key小。
  2. L遇到R,R先走,找到小于key的值就停下,L找大,一直找,没有找到,但是遇见R就停下来,相遇位置就是R找到小的位置,也比key要小。

4.1.1 分析

用keyi来记录交换值的下标。

同样先看单趟排序,在上面已经分析了。
首先右边先走,找小,那么它的代码是
【数据结构】排序之交换排序(冒泡 | 快排),数据结构,数据结构,算法,排序算法
左边找大。
【数据结构】排序之交换排序(冒泡 | 快排),数据结构,数据结构,算法,排序算法
但是走到结尾会发生错误,可能会错位,出现right<left的情况,所以在循环里面多加一个判断。
【数据结构】排序之交换排序(冒泡 | 快排),数据结构,数据结构,算法,排序算法
循环出来后就交换。
要让keyi到它最终的位置,就得用while ( left < right)来走,当走完后,交换key和left。任何继续排下一个数。
这里的keyi将区间分为三部分:[begin,keyi-1],keyi,[keyi+1,end]。
如果左边有序,右边有序,那么整体就有序。
【数据结构】排序之交换排序(冒泡 | 快排),数据结构,数据结构,算法,排序算法
用递归实现,当这个区间只有一个值或者没有值时候,结束。否则就调用左区间和右区间。
【数据结构】排序之交换排序(冒泡 | 快排),数据结构,数据结构,算法,排序算法

实现结果:【数据结构】排序之交换排序(冒泡 | 快排),数据结构,数据结构,算法,排序算法

4.1.2 hoare版本代码

void QuickSort(int* a, int begin, int end)
{
	if (begin >= end)
		return;
		int left = begin, right = end;
		int keyi = begin;
		while ( left < right)
		{
			// 右边找小
			while (left < right && a[right] >= a[keyi])
			{
				--right;
			}

			// 左边找大
			while (left < right && a[left] <= a[keyi])
			{
				++left;
			}
			
			Swap(&a[left], &a[right]);
		}

		Swap(&a[left], &a[keyi]);
		keyi = left;

		// [begin, keyi-1] keyi [keyi+1, end]
		QuickSort(a, begin, keyi - 1);
		QuickSort(a, keyi + 1, end);
	
}

4.2 挖坑法

看动图展示一下:
【数据结构】排序之交换排序(冒泡 | 快排),数据结构,数据结构,算法,排序算法
把左边位置的值先挖出来,用key先保存起来。形成了第一个坑位。
【数据结构】排序之交换排序(冒泡 | 快排),数据结构,数据结构,算法,排序算法
然后右边先走,找到比key要小的值,然后就把这个值,取出来放到这个坑中。【数据结构】排序之交换排序(冒泡 | 快排),数据结构,数据结构,算法,排序算法
然后形成了新的坑。
【数据结构】排序之交换排序(冒泡 | 快排),数据结构,数据结构,算法,排序算法
然后左边找大,找到大以后,将它扔到坑中。
【数据结构】排序之交换排序(冒泡 | 快排),数据结构,数据结构,算法,排序算法
直到它们两个相遇就终止了,然后把key填上。
【数据结构】排序之交换排序(冒泡 | 快排),数据结构,数据结构,算法,排序算法

4.2.1 分析

挖坑法没有hoare版的复杂,先找到右边找到小放在坑里,左边找到大的放坑里,在相遇时候把key放进去就行。
为了方便递归,重新写递归部分在,将坑位置的值传进去就行。
【数据结构】排序之交换排序(冒泡 | 快排),数据结构,数据结构,算法,排序算法
举个例子实现一下:
【数据结构】排序之交换排序(冒泡 | 快排),数据结构,数据结构,算法,排序算法

4.2.2 挖坑法代码实现

int PartSort2(int* a, int begin, int end)
{
	
	int key = a[begin];
	int hole = begin;
	while (begin < end)
	{
		// 右边找小,填到左边的坑
		while (begin < end && a[end] >= key)
		{
			--end;
		}

		a[hole] = a[end];
		hole = end;

		// 左边找大,填到右边的坑
		while (begin < end && a[begin] <= key)
		{
			++begin;
		}

		a[hole] = a[begin];
		hole = begin;
	}

	a[hole] = key;
	return hole;	
}

void QuickSort(int* a, int begin, int end)
{
	if (begin >= end)
		return;

	int keyi = PartSort2(a, begin, end);
	QuickSort(a, begin, keyi - 1);
	QuickSort(a, keyi + 1, end);
}

4.3 前后指针版本

【数据结构】排序之交换排序(冒泡 | 快排),数据结构,数据结构,算法,排序算法
cur遇到比key大的值,就++cur;
cur遇到比key小的值,就++prev,交换prev和cur位置的值
【数据结构】排序之交换排序(冒泡 | 快排),数据结构,数据结构,算法,排序算法
cur先走

【数据结构】排序之交换排序(冒泡 | 快排),数据结构,数据结构,算法,排序算法
当cur遇到比key小的值,【数据结构】排序之交换排序(冒泡 | 快排),数据结构,数据结构,算法,排序算法
先加加prev,再与cur交换。
【数据结构】排序之交换排序(冒泡 | 快排),数据结构,数据结构,算法,排序算法
然后cur继续往后走,又遇见比key小的
【数据结构】排序之交换排序(冒泡 | 快排),数据结构,数据结构,算法,排序算法
然后先加加prev,再与cur交换。
【数据结构】排序之交换排序(冒泡 | 快排),数据结构,数据结构,算法,排序算法
cur继续往后找小
【数据结构】排序之交换排序(冒泡 | 快排),数据结构,数据结构,算法,排序算法
cur比end大,就结束,然后将key与prev交换。
【数据结构】排序之交换排序(冒泡 | 快排),数据结构,数据结构,算法,排序算法

4.3.1 分析

先定义一下cur和prev,让int cur = prev + 1int prev = begin
当cur比key的值小时就继续走,否则就++prev,然后prev与cur交换。
就直接写一个循环就行,将加加放在条件里面。
【数据结构】排序之交换排序(冒泡 | 快排),数据结构,数据结构,算法,排序算法
当cur出去后,再将key与prev交换。

这里也是先写好单趟,然后调用就行。
【数据结构】排序之交换排序(冒泡 | 快排),数据结构,数据结构,算法,排序算法

举个例子看看:
【数据结构】排序之交换排序(冒泡 | 快排),数据结构,数据结构,算法,排序算法

4.3.2 前后指针版本代码实现

int PartSort3(int* a, int begin, int end)
{
	int keyi = begin;

	int prev = begin;
	int cur = prev + 1;
	while (cur <= end)
	{
		if (a[cur] < a[keyi] && ++prev != cur)
			Swap(&a[prev], &a[cur]);

		++cur;
	}

	Swap(&a[prev], &a[keyi]);
	keyi = prev;
	return keyi;
}

void QuickSort(int* a, int begin, int end)
{
	if (begin >= end)
		return;

	int keyi = PartSort3(a, begin, end);
	QuickSort(a, begin, keyi - 1);
	QuickSort(a, keyi + 1, end);

有问题请指出,大家一起进步吧!文章来源地址https://www.toymoban.com/news/detail-776463.html

到了这里,关于【数据结构】排序之交换排序(冒泡 | 快排)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构常见七大排序(三)上】—交换排序篇【冒泡排序】And【快速排序】

    目录 前言 1.冒泡排序 1.1冒泡排序动图 1.2冒泡排序源代码 1.3冒泡排序的特性总结 2.快速排序👑 2.1hoare版本实现思想 排序前 排序中 排序后 2.2hoare版本快排源代码 2.3分析先走 情况1🥇 情况2🥈 交换类排序两个常见的排序算法【冒泡排序】、【快速排序】 交换排序基本思想:

    2024年02月16日
    浏览(70)
  • 数据结构进阶篇 之 【交换排序】(冒泡排序,快速排序递归、非递归实现)详细讲解

    当你觉的自己不行时,你就走到斑马线上,这样你就会成为一个行人 1.1 基本思想 1.2 实现原理 1.3 代码实现 1.4 冒泡排序的特性总结 2.1 基本思想 2.2 递归实现 2.2.1 hoare版 2.2.2 前后指针版本 2.3 快速排序优化 2.3.1 随机数选key 2.3.2 三数取中选key 2.3.3 递归到小的子区间使用插入排

    2024年04月10日
    浏览(68)
  • 【数据结构与算法】排序算法:冒泡排序,冒泡排序优化,选择排序、选择排序优化

    目录 一、冒泡排序 1、冒泡排序思想 2、冒泡排序算法的性能分析 代码实现: 二、选择排序 1、选择排序思想 2、选择排序算法的性能分析  代码实现: 1、冒泡排序思想 冒泡排序的基本思想是通过相邻元素之间的比较和交换来逐步将最大(或最小)的元素移到右边(或左边

    2024年01月19日
    浏览(50)
  • 【数据结构与算法】十大经典排序算法-冒泡排序

    🌟 个人博客: www.hellocode.top 🏰 Java知识导航: Java-Navigate 🔥 CSDN: HelloCode. 🌴 掘金 :HelloCode 🌞 知乎 :HelloCode ⚡如有问题,欢迎指正,一起学习~~ 冒泡排序(Bubble Sort)是一种简单的排序算法,它通过重复地交换相邻元素的位置来将最大(或最小)的元素逐步“冒泡”到

    2024年02月14日
    浏览(75)
  • 数据结构算法练习 插入排序 冒泡排序

    插入排序 代码如下  package main import \\\"fmt\\\" func main() {     a := []int{4, 5, 6, 1, 3, 2}         b := insert(a)     for i := 0; i len(b); i++ {         fmt.Println(b[i])     } } func insert(a []int) []int {     if len(a) = 1 {                   如果数组长度小于等于1 不用排序直接返回          retur

    2024年02月08日
    浏览(58)
  • 数据结构:排序- 插入排序(插入排序and希尔排序) , 选择排序(选择排序and堆排序) , 交换排序(冒泡排序and快速排序) , 归并排序

    目录 前言 复杂度总结 预备代码 插入排序 1.直接插入排序: 时间复杂度O(N^2) 空间复杂度O(1) 复杂度(空间/时间): 2.希尔排序: 时间复杂度 O(N^1.3~ N^2) 空间复杂度为O(1) 复杂度(空间/时间): 选择排序 1.直接选择排序 时间复杂度O(N^2)/空间复杂度O(1) 复杂度(空间/时间)

    2024年02月07日
    浏览(57)
  • 数据结构算法--2 冒泡排序,选择排序,插入排序

    思想就是将相邻元素两两比较,当一个元素大于右侧相邻元素时,交换他们的位置,小于右侧元素时,位置不变,最终序列中的最大元素,像气泡一样,到了最右侧。 这时冒泡排序第一轮结束,数列最右侧元素9的位置可认为是一个有序区,有序区目前有一个元素. 第二轮排序

    2024年02月13日
    浏览(64)
  • 【数据结构与算法】排序算法(选择排序,冒泡排序,插入排序,希尔排序)

    基本概念这了就不浪费时间解释了,这四种都是很简单的排序方式,本专栏后续文章会出归并排序,计数排序,快速排序,堆排序,桶排序等排序算法,今天这篇文章中给出选择排序,冒泡排序,插入排序和希尔排序的实现; 如果发现文章中有错误,还请大家指出来,我会非

    2024年02月15日
    浏览(86)
  • 【数据结构与算法】冒泡排序算法(BubbleSort)

    目录 1、缘起 2、BubbleSort 算法描述 3、用图示描述 BubbleSort 算法 4、C 语言描述 5、Python 语言描述  6、Java 语言描述  7、总结         冒泡排序算法 是一个非常经典的算法,它是各大网络编程平台上的座上宾,面试官口中的最爱。这个算法就是因其中数字从列表的开始向顶

    2024年02月03日
    浏览(43)
  • 【数据结构】排序算法(二)—>冒泡排序、快速排序、归并排序、计数排序

    👀 樊梓慕: 个人主页  🎥 个人专栏: 《C语言》《数据结构》《蓝桥杯试题》《LeetCode刷题笔记》《实训项目》 🌝 每一个不曾起舞的日子,都是对生命的辜负 目录 前言 1.冒泡排序 2.快速排序 2.1Hoare版 2.2占坑版 2.3前后指针版 2.4三数取中对快速排序的优化 2.5非递归版 3.归

    2024年02月08日
    浏览(54)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包