【数据结构】排序(2)—冒泡排序 & 快速排序

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

   

                             

目录

一. 冒泡排序

基本思想

代码实现

时间和空间复杂度

稳定性

二. 快速排序

基本思想

代码实现

hoare法

挖坑法

前后指针法

时间和空间复杂度

稳定性


一. 冒泡排序

       基本思想

           冒泡排序是一种交换排序。两两比较数组元素,如果是逆序(即排列顺序与排序后的顺序相     反)就交换,直到所有元素都有序为止。

      方法步骤:                   

          ① 比较相邻的元素。如果第一个比第二个大,就交换他们两个。

          ② 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。这步做完后,最后                  的元素会是最大的数

          ③ 针对所有的元素重复以上的步骤,除了最后一个。

          ④ 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较

        图示

        【数据结构】排序(2)—冒泡排序 & 快速排序,数据结构,排序算法,算法

代码实现

  

//冒泡排序
void BubbleSort(int* a, int n)
{
	for (int i = 0; i < n - 1; i++)
	{
		int flag = 0; //作为判断是否交换的标志
		for (int j = 1; j < n - i; j++)
		{
			if (a[j-1] > a[j])
			{
				flag = 1;
				int tmp = a[j-1]; //交换
				a[j-1] = a[j];
				a[j] = tmp;
			}
		}
		if (flag == 0)
			break;
	}
}

时间和空间复杂度

     若初始序列为正序序列,则只需进行一趟排序,在排序过程中进行n-1次比较不移动元素;若初始序列为逆序序列,则需进行n-1趟排序n(n-1) / 2次比较,每次比较都需要移动 3 次,移动次数为  3n(n-1) / 2.

    时间复杂度:O(n^2)

    空间复杂度:O(1)

稳定性

     冒泡排序:稳定排序

二. 快速排序

      基本思想

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

     方法步骤:       

  1. 从数列中挑出一个元素,称为 "基准"(pivot);

  2. 重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分区退出之后,该基准就处于数列的中间位置。这个称为分区(partition)操作;

  3. 递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序;

     图示

【数据结构】排序(2)—冒泡排序 & 快速排序,数据结构,排序算法,算法

代码实现

   

 hoare法

        思想方法:

           定义两个指针 left 和 right,分别指向左边和右边,左指针从左向右找大( 大于pivotkey),右      指针从右向左找小(小于pivotkey),左大右小就交换,相遇时与基准值交换

         图解:

               【数据结构】排序(2)—冒泡排序 & 快速排序,数据结构,排序算法,算法

        

 

int PartSort(int* a, int left, int right) //给数组分区,返回枢轴元素下标
{
	int pivotkey = left;
	while (left < right)
	{
		//右边找比pivotkey小的
		while (left < right && a[right] >= a[pivotkey])
			right--;
		//左边找比pivotkey大的
		while (left < right && a[left] <= a[pivotkey])
			left++;
		Swap(&a[left], &a[right]);
	}
	Swap(&a[left], &a[pivotkey]); //把记录的枢轴元素,交换到枢轴位置
	return left;   //返回枢轴所在的位置下标
}

   

 挖坑法

      思想方法

              定义两个指针 left 和 right,分别指向左边和右边,先将第一个数据元素放在临时变量 pivotkey 中,形成一个坑位右指针先走,当指向的值小于 pivotkey 就停下,形成新的坑位;让左指针走,当指向的值大于 pivotkey 就停下,使其形成此次的新坑位,直到两指针相遇,把pivotkey的值放入坑中。

 

        图解:

         【数据结构】排序(2)—冒泡排序 & 快速排序,数据结构,排序算法,算法

           


int PartSort(int* a, int left, int right) //给数组分区,返回枢轴元素下标
{
	int pivotkey = a[left]; //保存第一个数据元素的值
	while (left < right)
	{
		while (left < right && a[right] >= pivotkey) //找小
		{
			right--;
		}
		a[left] = a[right]; //右边形成新的坑
		while (left < right && a[left] <= pivotkey) //找大
		{
			left++;
		}
		a[right] = a[left]; //左边形成新的坑
	}
	a[left] = pivotkey;
	return left;
}


  前后指针法

      思想方法:

        定义两个指针 prev 和 cur ,初始时,prev指针指向序列开头,cur指针指向prev指针的后一个位置;cur的值与pivotkey的值比较,cur的值小,prev先后移一步,cur再后移;当cur的值大时,就prev的值与cur的值交换;直到cur为空时,prev的值与pivotkey的值交换。

       图解:

            【数据结构】排序(2)—冒泡排序 & 快速排序,数据结构,排序算法,算法  

       


int PartSort(int* a, int left, int right) //给数组分区,返回枢轴元素下标
{
	int prev = left;
	int cur = left + 1;
	int pivotkey = left;
	while (cur <= right)
	{
		if (a[cur] < a[pivotkey] && ++prev != cur)
			Swap(&a[cur], &a[prev]);
		cur++;
	}
	Swap(&a[pivotkey], &a[prev]);
	return prev;
}

时间和空间复杂度

         在最优情况下,partition每次都划的很均匀,此时时间复杂度为O(nlogn);平均情况下,其时   间复杂度也为O(nlogn)。在最坏的情况下,待排序的序列为正序或逆序时,递归树是一棵斜树,   此时,快速排序会堕落为冒泡排序,其时间复杂度为O(n^2),不过可以通过优化,使其提升为O(nlogn),总的来说还是O(nlogn)。

        空间复杂度,主要是递归造成的栈空间的使用,最好情况及平均情况下,树的递归深度为logn,空间复杂度均为O(logn);最坏情况,空间复杂度为O(n).

       时间复杂度:O(nlogn)

       空间复杂度:O(logn)

  稳定性

      由于元素的比较和交换是跳跃进行的,因此

      快速排序:不稳定排序文章来源地址https://www.toymoban.com/news/detail-719133.html

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

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

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

相关文章

  • 【数据结构初阶】八大排序(二)——快速排序&&冒泡排序

    大家好我是沐曦希💕 书接【数据结构初阶】八大排序(一)——希尔排序堆排序直接插入排序直接选择排序 基本思想:所谓交换,就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置,交换排序的特点是: 将键值较大的记录向序列的尾部移动,键值较小

    2024年02月21日
    浏览(117)
  • 【数据结构】 七大排序详解(贰)——冒泡排序、快速排序、归并排序

    ==冒泡排序(Bubble Sort)==也是一种简单直观的排序算法。它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会

    2024年02月09日
    浏览(123)
  • 数据结构——六大排序 (插入,选择,希尔,冒泡,堆,快速排序)

    1.1基本思路 把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中,直到所有的记录插入完为止,得到一个新的有序序列  我们熟知的斗地主就是一个插入排序 我们这里将一个无序数组变成有序数组 插入排序时间复杂度分析 最优情况:待排序的数组是

    2024年02月17日
    浏览(95)
  • 【数据结构】冒泡,快速,直接插入,归并,选择排序

    🎊专栏【数据结构】 🍔喜欢的诗句:更喜岷山千里雪 三军过后尽开颜。 🎆音乐分享【Dream It Possible】 大一同学小吉,欢迎并且感谢大家指出我的问题🥰 目录   🎁冒泡排序 🏳️‍🌈图解 🏳️‍🌈实现过程 🏳️‍🌈代码 🎁快速排序 🏳️‍🌈图解 🏳️‍🌈实现过

    2024年02月06日
    浏览(83)
  • 数据结构排序:插入排序、希尔排序、选择排序、冒泡排序、堆排序、快速排序

    基本思想: 直接插入排序是一种简单的插入排序法,其基本思想是: 把待排序的值按其关键码值的大小逐个插入到一个已经排好序的有序序列中,直到所有的记录插入完为止,得到一个新的有序序列 。 直接插入排序: 当插入第i(i=1)个元素时,前面的array[0],array[1],…,array[

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

    目录 一、冒泡排序 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【快速排序】

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

    2024年02月16日
    浏览(70)
  • 【数据结构】一文带你全面了解排序(下)——冒泡排序、快速排序、归并排序、计数排序

      目录 一、常见排序算法的实现   1.1 交换排序 1.1.1 基本思想 1.1.2 冒泡排序  1.1.3 快速排序 1.2 归并排序 1.3 非比较排序 二、排序算法复杂度及稳定性分析  人总得为过去的懒惰而付出点代价! 1.1.1 基本思想 基本思想:所谓交换,就是根据序列中两个记录键值的比较结

    2024年02月16日
    浏览(51)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包