详解C语言快速排序三种方法的单趟实现

目录
  • 交换排序的思想
    • 冒泡排序的思想
  • 快速排序的整体框架
  • 快速排序单趟实现逻辑
    • 1. hoare版本单趟实现(左右指针法)
    • 2.挖坑法单趟排序实现
    • 3.前后指针法

交换排序的思想

基本思想:所谓交换,就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置,交换排 序的特点是:将键值较大的记录向序列的尾部移动,键值较小的记录向序列的前部移动。

冒泡排序的思想

冒泡排序比较简单,我们之前使用也很多,简单讲解,就是比较两个数,如果比他大就交换,没有他大就接着向后比,一直到数组结束,这是单趟排序,多趟就是控制好下标,进行循环即可。

冒泡代码实现

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

void BubbleSort(int* a, int n)
{
	assert(a);

	for (int j = 0; j < n - 1; ++j)
	{
		int exchange = 0;//定义变量,用于判断是否交换过
		for (int i = 1; i < n - j; ++i)
		{
			if (a[i - 1] > a[i])
			{
				Swap(&a[i - 1], &a[i]);
				exchange = 1;
			}
		}

		if (exchange == 0)//没有交换过表示有序,直接跳出
		{
			break;
		}
	}
}

冒泡排序的特性

1. 冒泡排序是一种非常容易理解的排序

2. 时间复杂度:O(N^2)

3. 空间复杂度:O(1)

4. 稳定性:稳定

快速排序的整体框架

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

// 假设按照升序对array数组中[left, right)区间中的元素进行排序
void QuickSort(int array[], int left, int right)
{
 if(right - left <= 1)
 return;

 // 按照基准值对array数组的 [left, right)区间中的元素进行划分
 int div = partion(array, left, right);

 // 划分成功后以div为边界形成了左右两部分 [left, div) 和 [div+1, right)
 // 递归排[left, div)
 QuickSort(array, left, div);

 // 递归排[div+1, right)
 QuickSort(array, div+1, right);
}

述为快速排序递归实现的主框架,发现与二叉树前序遍历规则非常像,同学们在写递归框架时可想想二叉 树前序遍历规则即可快速写出来,后序只需分析如何按照基准值来对区间中数据进行划分的方式即可。

简单理解:

我们先选出一个数,然后把所有数据分为三部分,第一部分是大于这个数的部分,第二个部分是这个数,第三个部分是大于这个数的。

然后,进行递归求解,对于小于的部分,选一个数,分为三部分。对于大于的部分,选一个数,分为三部分进行求解。

递归返回条件:首先是区间不存在返回,区间只有一个数返回。

快速排序单趟实现逻辑

1. hoare版本单趟实现(左右指针法)

首先我们先学习下最经典的左右指针法:

首先我们一般都会这两个疑问?(后续挖坑法和前后指针法同理)

1.为什么要选左边的数作为初识位置比较位置。

2.为什么要让右边先走?

我们之所以选取左边,只是因为方便,容易控制,你也可以选择右边,或者任意位置,都可以,只不过在代码逻辑上稍微复杂点,不容易控制。

我们让右边先走,是因为最后我们要把 key位置的数据移动到相遇位置,也就是key位置数据的正确位置,所以我们应该保证让左边来遇到右边,就是让右边的位置先到等着左边。因为我们选取的是左边的key,所以左边的下标就是少了 1 ,我们让右边先走就可以刚好弥补过来。反之,如果我们选取左边为key,还让左边先走,那么我们最后就会发现,这个位置的下标就错了,不能保证左边都是大于key的数了。

综上:我们如果选择了左边为key,那么就让右边先走,选择右边为key,就让左边先走。

我们看着示意图实现下单趟排序代码:

//前后指针法单趟排序
int PartSort(int *a,int left,int right)
{
	int keyi = left;//先保存最左侧下标,作为keyi

	while (left < right)
	{
		//先让右走,找小,并且不能越界
		while (left < right && a[right] >= a[keyi])
		{
			--right;
		}

		//再让左走,找大,不越界。
		while (left < right && a[left] <= a[keyi])
		{
			++left;
		}

		//交换左边大的,和右边小的
		Swap(&a[left], &a[right]);
	}

	//循环完成,我们在最后交换下,相遇位置的和原来keyi位置的值
	Swap(&a[keyi], &a[left]);

	//返回相遇位置的下标是为进行下一步递归。
	return left;
}

2.挖坑法单趟排序实现

我们看下有点意思的挖坑法。

我们观察发现,还是先选取一个位置作为我们比较的数同时也是坑位,然后还是先让右边走,然后把数据放到坑中,形成一个新的坑,接着左边走,再把数据放入坑中,形成新坑,最后,把我们选取位置的数据放到最后一个坑位上,就满了。

其实在我们调试发现,"挖坑" 只不过是形象描述了,其实乜有坑位,只是数据重复,然后替换掉了。

图示比较简单,我们尝试实现下单趟排序:

 //挖坑法
int PartSort2(int* a, int left, int right)
{
	int key = a[left];//保存最左边初始位置的值

	while (left < right)
	{
		while (left < right && a[right] >= key)
		{
			--right;
		}

		a[left] = a[right];//产生一个坑位

		while (left < right && a[left] <= key)
		{
			++left;
		}

		a[right] = a[left];//上一个坑位填上,产生新的坑位
	}

	a[left] = key;//把最后的坑位填上了。

	return left;//返回最后相遇的下标,以便后序递归
}

3.前后指针法

前后指针法和左右指针类似但是不完全一样哦。

前后指针法,其实就是定义两个指针,一个是prev为初始位置,一个是cur为初始位置+1,cur是遇见大于初始位置的值停下,交换(prev+1)下标的值,直到 cur 指针走到结尾,此时就交换prev指针和初始位置即可。

简单理解:

前后指针,就是不停的把大于初始位置的数据向后移动,最后一个指针走到末尾了,另一个指针此时的指向,刚好就是我们初始位置在整个数据中要排的位置。

需要注意的是:我们每次交换的都是prev+1的下标值,如果 prev = cur 时,此时我们不用交换,prev也不用++,只需要 cur++ 即可。

前后指针的单趟代码实现:

//前后指针法
int PartSort3(int *a, int left, int right)
{
	int prev = left;//后指针
	int cur = left + 1;//前指针
	int keyi = left;//初始位置

	while(cur <= right)//当cur小于等于最右边时进入循环
	{
		//当cur找到比初始位置大的数,如果此时cur不等于prev,
		//那么就交换cur和++prev,一定是前置++。
		if (a[cur] < a[keyi] && prev != cur)
		{
			Swap(&a[cur], &a[++prev]);
		}
		cur++;
	}
	Swap(&a[prev], &a[keyi]);//最后交换prev和初始位置即可

	return prev;//返回prev为了后续递归做铺垫
}

以上就是详解C语言快速排序三种方法的单趟实现的详细内容,更多关于C语言快速排序单趟实现的资料请关注我们其它相关文章!

(0)

相关推荐

  • C语言实现单链表的快速排序算法

    目录 背景 设计思路 算法主要步骤 快速排序算法实现 整个程序源代码 测试案例 总结 背景 传统QuickSort算法最大不足之处在于,由于其基于可索引存储结构设计(一般为数组或索引表),因而无法用于链式存储结构,而链式存储结构的实际应用非常广泛,例如动态存储管理.动态优先级调度等等,故本文针对于单向链表,以QuickSort的分治策略为基础,提出一种可用于单向链表的快速排序算法. 设计思路 将单向链表的首节点作为枢轴节点,然后从单向链表首部的第二个节点开始,逐一遍历所有后续节点,并将这些已遍历

  • C语言实现快速排序算法实例

    首先我们要对一组数据进行排序: 在数组中选一个基准数(通常为数组第一个,黄圈圈标记了): 将数组中小于基准数的数据移到基准数左边,大于基准数的移到右边,怎么移动,后面说: 对于基准数左.右两边的数组,不断重复以上两个过程,直到每个子集只有一个元素,即为全部有序. 好了,咱们开始吧! 快速排序需要两个哨兵,i 和 j,分别指向数组的头和尾.接下来就要进行移动. 我们通常选择第一个元素作为基准数,去移动数组元素,使其达到这个基准数的左边都是小于它的,右边都是大于它的.开始移动 i 和 j , i 和

  • C语言简明讲解快速排序的应用

    目录 快速排序 1.1快速排序引入 1.2快速排序的基本思想 1.3快速排序的排序流程 1.4实例说明 1.5代码实现 1.6性能分析 快速排序 快速排序,说白了就是给基准数据找其正确索引位置的过程 1.1快速排序引入 希尔排序相当于直接插入排序的升级,他们属于插入排序类:堆排序相当于简单选择排序的升级,他们同属于选择排序类:而对于交换排序类的冒泡排序升级版本就是快速排序. 1.2快速排序的基本思想 通过一趟排序将待排记录分割成独立的两部分,其中一部分记录的关键字比另一部分记录的关键字小,则可分

  • c语言快速排序算法示例代码分享

    步骤为:1.从数列中挑出一个元素,称为 "基准"(pivot);2.重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边).在这个分区退出之后,该基准就处于数列的中间位置.这个称为分区(partition)操作.3.递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序.递归的最底部情形,是数列的大小是零或一,也就是永远都已经被排序好了.虽然一直递归下去,但是这个算法总会退出,因为在每次的迭代(iterat

  • C语言实现快速排序

    快速排序算法是一种分治排序算法.它将数组划分为两个部分,然后分别对两个部分进行排序.我们将看到,划分的准确位置取决于输入数组中元素的初始位置.关键在于划分过程,它重排数组,使得以下三个条件成立:(i)对于某个i,a[i]在最终位置上 (ii)a[left],...,a[i-1]中的元素都比a[i]小 (iii)a[i+1],...a[right]中的元素都比a[i]大.我们通过划分来完成排序,然后递归地应用该方法处理子数组. 我们使用一般策略来实现划分.首先,我们任选一个a[right]作为划分

  • C语言实现快速排序算法

    一.快速排序算法(Quicksort) 1. 定义 快速排序由C. A. R. Hoare在1962年提出.快速排序是对冒泡排序的一种改进,采用了一种分治的策略. 2. 基本思想 通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列. 3. 步骤 a. 先从数列中取出一个数作为基准数. b. 分区过程,将比这个数大的数全放到它的右边,小于或等于它的数全

  • 详解C语言快速排序三种方法的单趟实现

    目录 交换排序的思想 冒泡排序的思想 快速排序的整体框架 快速排序单趟实现逻辑 1. hoare版本单趟实现(左右指针法) 2.挖坑法单趟排序实现 3.前后指针法 交换排序的思想 基本思想:所谓交换,就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置,交换排 序的特点是:将键值较大的记录向序列的尾部移动,键值较小的记录向序列的前部移动. 冒泡排序的思想 冒泡排序比较简单,我们之前使用也很多,简单讲解,就是比较两个数,如果比他大就交换,没有他大就接着向后比,一直到数组结束,这是单趟

  • 详解python中的三种命令行模块(sys.argv,argparse,click)

    Python作为一门脚本语言,经常作为脚本接受命令行传入参数,Python接受命令行参数大概有三种方式.因为在日常工作场景会经常使用到,这里对这几种方式进行总结. 命令行参数模块 这里命令行参数模块平时工作中用到最多就是这三种模块:sys.argv,argparse,click.sys.argv和argparse都是内置模块,click则是第三方模块. sys.argv模块(内置模块) 先看一个简单的示例: #!/usr/bin/python import sys def hello(name,

  • 详解C++ 中的三种继承方式

    public 方式继承 基类成员对派生类的可见性对派生类来说,基类的公有成员和保护成员可见,基类的公有成员和保护成员作为派生类的成员时,它们都保持原有的状态;基类的私有成员不可见,基类的私有成员仍然是私有的,派生类不可访问基类中的私有成员. 基类成员对派生类对象的可见性对派生类对象来说,基类的公有成员是可见的,其他成员是不可见的. 所以,在公有继承时,派生类的对象可以访问基类中的公有成员,派生类的成员函数可以访问基类中的公有成员和保护成员. 简单来说,派生类能访问基类的public, prote

  • Java语言通过三种方法实现队列的示例代码

    目录 队列 图解 数组模拟队列 队列优化—循环队列 代码 使用java内部队列 代码 队列 队列是一种特殊的线性表,只允许在表的前端进行删除操作,在表的后端进行插入操作. 队列是一个有序列表,可以用数组或是链表来实现. 遵循先入先出的原则.即:先存入队列的数据,要先取出.后存入的要后取出. 就相当于我们日常生活中的排队,先来先服务,后来的只能在后面进行排队等待. 图解 数组模拟队列 通过对定义的了解,发现队列很像我们的数组,那我们是不是可以通过数组来模拟队列,下面我们来实践一下. 首先先分析一下

  • 详解Java中的三种流程控制语句

    目录 顺序语句 选择语句 if else的嵌套 switch case default 循环语句 for for in while do while break continue 顺序语句 顺序顾名思义就是程序自上而下执行 public class User { public static void main(String[] args) { String name = "hacker"; int age = 18; String happy = "学习Java";

  • C语言通过三种方法实现属于你的通讯录

    目录 一.基础版本 1.1 通讯录的个人信息(结构体来实现) 1.2通讯录名单 1.3人员初始化 1.4菜单 1.5主函数 二.功能的实现 2.1.增加人数 2.2.删除人数 2.3.查找 2.4.展示 2.5.排序(这里我是通过名字) 三.通讯录进阶(设置动态存储) 3.1通讯录从静态改为动态 3.2通讯录的初始化 3.3通讯录的增加需要判断是否满了 四.文件的形式存储通讯录 4.1人员信息的保存 4.2人员信息的流入 一.基础版本 前提准备: 1.通讯录里面的人的个人信息(姓名.性别.年龄.

  • 详解js 创建对象的几种方法

    在js中创建对象的方法可分为6种,分别是:基本模式.工厂模式.构造函数模式.原型模式.组合模式.动态原型模式,接下来分别看下这几种模式的写法吧 一.基本模式 var person = new Object(); person.name = "孙悟空"; person.weapon = "棒子"; person.run = function () { return this.name + "武器是" + person.weapon; } 二.工厂模

  • 详解js创建对象的几种方法及继承

    创建对象 通过Object构造函数或对象字面量创建单个对象 这些方式有明显的缺点:使用同一个接口创建很多对象,会产生大量的重复代码.为了解决这个问题,出现了工厂模式. 工厂模式 考虑在ES中无法创建类(ES6前),开发人员发明了一种函数,用函数来封装以特定接口创建对象的细节.(实现起来是在一个函数内创建好对象,然后把对象返回). function createPerson(name,age,job){ var o=new Object(); o.name=name; o.age=age; o.j

  • Ubuntu系统安装Ruby语言的三种方法

    Ruby是一个开源的动态编程语言,它有优美的语法,可用于构建可伸缩的Web应用程序.ruby gems可以很好地增强Ruby开发者的开发效率. 要在Ubuntu系统上安装Ruby,有几种方法,每种方法都只需几步就能搞定. 方法一:使用apt-get安装 可以直接使用两个命令完成Ruby的安装. 复制代码 代码如下: # sudo apt-get update # sudo apt-get install ruby 或者 复制代码 代码如下: # sudo apt-get install ruby

  • 详解Java 中的三种代理模式

    代理模式 代理(Proxy)是一种设计模式,提供了对目标对象另外的访问方式;即通过代理对象访问目标对象.这样做的好处是:可以在目标对象实现的基础上,增强额外的功能操作,即扩展目标对象的功能. 这里使用到编程中的一个思想:不要随意去修改别人已经写好的代码或者方法,如果需改修改,可以通过代理的方式来扩展该方法. 举个例子来说明代理的作用:假设我们想邀请一位明星,那么并不是直接连接明星,而是联系明星的经纪人,来达到同样的目的.明星就是一个目标对象,他只要负责活动中的节目,而其他琐碎的事情就交给他的代理

随机推荐