C/C++实现快速排序(两种方式)图文详解

目录
  • 介绍
  • 实现
    • 方式一
    • 方式二
  • 总结

介绍

快速排序是对冒泡排序算法的一种改进，快速排序算法通过多次比较和交换来实现排序。

流程如下：

实现

以下有两种实现方式，说是两种，其实就是在交换元素时具体细节上有点不同罢了。

方式一

int Partition(int A[],int low,int high){
	int pivot=A[low];//第一个元素作为基准
	while(low<high){
		while(low<high && A[high]>=pivot) high--;
		A[low]=A[high];
		while(low<high && A[low]<=pivot) low++;
		A[high]=A[low];
	}
	A[low]=pivot;

	return low;
}

void QuickSort(int A[],int low,int high){
	if(low<high){
		int pivotpos=Partition(A,low,high);
		QuickSort(A,low,pivotpos-1);
		QuickSort(A,pivotpos+1,high);
	}
}

该方式，先把基准元素保存起来

如下图数组，把49看作基准元素，先移动high指针，当指向27时退出while循环，把27放到low位置

这时候，high位置就空出来一个，那么让low移动，移动到下图所示时，65>49，退出while循环，再将65放到high位置

这样low这个位置又空出来了，再移动high，如此反复。

最后得到如下图的情况：

这样我们就按照“49”，把数组分为了左右两部分。

对左右两部分分别进行上述操作即可。

方式二

void Quick_sort(int left,int right,int arr[]){
	if(left>=right)return;
	int i,j,base,temp;
	i=left,j=right;
	base=arr[left];
	while(i<j){
		while(arr[j]>=base && i<j)j--;
		while(arr[i]<=base && i<j)i++;
		if(i<j){
			temp=arr[i];
			arr[i]=arr[j];
			arr[j]=temp;
		}
	}
	arr[left]=arr[i];
	arr[i]=base;
	Quick_sort(left,i-1,arr);
	Quick_sort(i+1,right,arr);
}

对于第二种方式，看下图即可很好理解。

高低指针不是轮流替换空余位置，而是同时找到不符合的元素，然后交换二者。

最后，高低指针相遇，再把基准元素与相遇位置上的元素交换即可。

总结

本篇文章就到这里了，希望能给你带来帮助，也希望您能够多多关注我们的更多内容！

赞 (0)

相关推荐

  • C/C++实现快速排序算法的思路及原理解析

    C/C++实现快速排序算法的思路及原理解析

    快速排序 1. 算法思想 快速排序的基本思想:通过一趟排序将待排记录分隔成独立的两部分,其中一部分记录的关键字均比另一部分的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序. 2. 实现原理 2.1.设置两个变量 low.high,排序开始时:low=0,high=size-1. 2.2.整个数组找基准正确位置,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面 默认数组的第一个数为基准数据,赋值给key,即key=array[low]. 因为默认数组的第一个

  • C/C++实现快速排序算法的两种方式实例

    C/C++实现快速排序算法的两种方式实例

    目录 介绍 流程如下 实现 方式一 方式二 总结 介绍 快速排序是对冒泡排序算法的一种改进,快速排序算法通过多次比较和交换来实现排序. 流程如下 (图片来自百度) 实现 以下有两种实现方式,说是两种,其实就是在交换元素时具体细节上有点不同罢了. 方式一 int Partition(int A[],int low,int high){ int pivot=A[low];//第一个元素作为基准 while(low<high){ while(low<high && A[high]&g

  • C/C++实现双路快速排序算法原理

    看了刘宇波的视频,讲双路快速排序的,原理讲的很直观,程序讲解也一看就懂.这里写一下自己的理解过程,也加深一下自己的理解. 首先说一下为什么需要双路排序,在有些带有许多重复数据的数组里,使用随机快速排序或者最简单的快速排序算法时,由于重复的数据会放在原来的索引位置不动,就回导致划分数组时划分的某一部分太长,起不到分段排序的效果,这样就导致算法退化成O(n^2)的复杂度.就像下图: 为了解决这个问题,双路快速排序采用的方法是对等于v的数也进行交换,原理如下所述: 首先选择一个数作为标志,放在数组的最

  • C++归并法+快速排序实现链表排序的方法

    C++归并法+快速排序实现链表排序的方法

    本文主要介绍了C++归并法+快速排序实现链表排序的方法,分享给大家,具体如下: 我们可以试用归并排序解决: 对链表归并排序的过程如下. 找到链表的中点,以中点为分界,将链表拆分成两个子链表.寻找链表的中点可以使用快慢指针的做法,快指针每次移动 2 步,慢指针每次移动 1步,当快指针到达链表末尾时,慢指针指向的链表节点即为链表的中点. 对两个子链表分别排序. 将两个排序后的子链表合并,得到完整的排序后的链表 上述过程可以通过递归实现.递归的终止条件是链表的节点个数小于或等于 1,即当链表为空或者链

  • C++实现快速排序(Quicksort)算法

    本文实例为大家分享了C++快速排序算法,供大家参考,具体内容如下 一.基本思想是: 通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列. 二.方法1实现程序:左右两个方向扫描 // 快速排序:选第一个对象作为基准,按照该对象的排序码大小,将整个对象 // 序列划分为左右两个字序列: // 左侧子序列中所有对象的排序码都小于或等于基准对象的排序码: /

  • C/C++实现快速排序(两种方式)图文详解

    C/C++实现快速排序(两种方式)图文详解

    目录 介绍 实现 方式一 方式二 总结 介绍 快速排序是对冒泡排序算法的一种改进,快速排序算法通过多次比较和交换来实现排序. 流程如下: 实现 以下有两种实现方式,说是两种,其实就是在交换元素时具体细节上有点不同罢了. 方式一 int Partition(int A[],int low,int high){ int pivot=A[low];//第一个元素作为基准 while(low<high){ while(low<high && A[high]>=pivot) hig

  • Windows10安装linux子系统的两种方式(图文详解)

    Windows10支持Linux子系统了,告别繁琐的双系统.虚拟机安装,原生安装方便快捷. windows subsystem for linux简称WSL. 这里介绍2种安装方式,总有一款适合你. 图形化安装 启用开发者模式 按下 Windows 键,打开设置 设置-->更新和安全-->开发者选项-->开发人员模式 开启适用于Linux的Windows子系统按下 Windows jian键,输入控制面板 打开控制面板 打开 应用或关闭Windows功能 ,勾选 适用于Linux的Win

  • ubuntu 16.04安装redis的两种方式教程详解(apt和编译方式）

    ubuntu 16.04安装redis的两种方式教程如下所示: 方式一 :apt安装 在 Ubuntu 系统安装 Redi 可以使用以下命令: $sudo apt-get update $sudo apt-get install redis-server 启动 Redis $ redis-server 查看 redis 是否启动? $ redis-cli 以上命令将打开以下终端: redis 127.0.0.1:6379> 127.0.0.1 是本机 IP ,6379 是 redis 服务端口.

  • Spring加载properties文件的两种方式实例详解

    Spring加载properties文件的两种方式实例详解

    在项目中如果有些参数经常需要修改,或者后期可能需要修改,那我们最好把这些参数放到properties文件中,源代码中读取properties里面的配置,这样后期只需要改动properties文件即可,不需要修改源代码,这样更加方便.在Spring中也可以这么做,而且Spring有两种加载properties文件的方式:基于xml方式和基于注解方式.下面分别讨论下这两种方式. 1. 通过xml方式加载properties文件 我们以Spring实例化dataSource为例,我们一般会在beans

  • java 实现websocket的两种方式实例详解

    一.介绍 1.两种方式,一种使用tomcat的websocket实现,一种使用spring的websocket 2.tomcat的方式需要tomcat 7.x,JEE7的支持. 3.spring与websocket整合需要spring 4.x,并且使用了socketjs,对不支持websocket的浏览器可以模拟websocket使用 二.方式一:tomcat 使用这种方式无需别的任何配置,只需服务端一个处理类, 服务器端代码 package com.Socket; import java.io

  • QT实现多线程两种方式案例详解

    Qt线程 Qt4.7之前版本处理步骤 1.自定义一个类,继承于QThread. class MyThread:public QThread{ public: vid run(); //虚函数 线程处理函数(和主线程不在同一个线程) signals: void isDone(); //信号 线程执行完发送 } void MyThread::run() { // 实现 -- 复杂的处理过程 emit isDome; // 发送线程 }; 2.定义线程 MyThread thread; 3.开启线程

  • Android实现旋转动画的两种方式案例详解

    Android实现旋转动画的两种方式案例详解

    目录 练习案例 效果展示 前期准备 自定义 View java代码编写 方法一 方法二 易错点总结: 练习案例 视差动画 - 雅虎新闻摘要加载 效果展示 前期准备 第一步:准备好颜色数组 res => values => colors.xml <color name="orange">#FF9600</color> <color name="aqua">#02D1AC</color> <color n

  • 国产化中的 .NET Core 操作达梦数据库DM8的两种方式(操作详解)

    国产化中的 .NET Core 操作达梦数据库DM8的两种方式(操作详解)

    目录 背景 环境 SDK 操作数据库 DbHelperSQL方式 Dapper方式 背景 某个项目需要实现基础软件全部国产化,其中操作系统指定银河麒麟,数据库使用达梦V8,CPU平台的范围包括x64.龙芯.飞腾.鲲鹏等.考虑到这些基础产品对.NET的支持,最终选择了.NET Core 3.1. 环境 CPU平台:x86-64 / Arm64 操作系统:银河麒麟 v4 数据库:DM8 .NET:.NET Core 3.1 SDK 达梦自己提供了.NET操作其数据库的SDK,可以通过NuGet安装,

  • Go实现线程池(工作池)的两种方式实例详解

    Go实现线程池(工作池)的两种方式实例详解

    worker pool简介 worker pool其实就是线程池thread pool.对于go来说,直接使用的是goroutine而非线程,不过这里仍然以线程来解释线程池. 在线程池模型中,有2个队列一个池子:任务队列.已完成任务队列和线程池.其中已完成任务队列可能存在也可能不存在,依据实际需求而定. 只要有任务进来,就会放进任务队列中.只要线程执行完了一个任务,就将任务放进已完成任务队列,有时候还会将任务的处理结果也放进已完成队列中. worker pool中包含了一堆的线程(worker,

  • JS实现Tab栏切换的两种方式案例详解

    面向过程的写法 <!DOCTYPE html> <html lang="en"> <head> <meta charset="UTF-8"> <meta http-equiv="X-UA-Compatible" content="IE=edge"> <meta name="viewport" content="width=devic

随机推荐