【数据结构】-排序-快速排序

~快速排序在平均情况下是效果最好的排序算法~

每趟子表的排序都是从两头向中间交替逼近,接下来举一个例子

 

类别

排序方法

最好时间

最坏时间

平均时间

空间复杂度

稳定性

序列特征

适用于

插入排序

直接插入排序

n(顺序)

n2(逆序)

n2

1

稳定

有序序列+待排序元素+无序序列

基本有序/n很小

 

折半插入排序

 

 

 

 

稳定

有序序列+待排序元素+无序序列

 

 

希尔排序

与d相关

n2

n1.3

1

不稳定

缩小增量,组内直接插入排序

顺序存储

交换排序

冒泡排序

n(顺序)

n2逆序

n2

1

稳定

无序序列+最大值/最小值+无序序列

 

 

快速排序

无序

有序n2

逆序

nlogn

平均:Logn

最坏:n

不稳定

较小无序序列+基准值+较大有序序列

非自然排序

越乱越好

编程注意事项:

1.为了处理快排的输出,采用引用传值,直接在原来的数组上移动,不拷贝

2.注意大于等于/小于等于

 

int partition(vector<int> &a, int low, int high) {
	int pivot = a[low];//其实可以不用pivot,直接用a[0]就好了,但是为了理解“基准”的意思,还是用pivot
	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(vector<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);
	}

}

void Sort() {
	int n;
	cout << "请输入元素个数:";
	cin >> n;
	vector<int> num(n+1);
	for (int i = 1; i < n + 1; i++)cin >> num[i];

	quickSort(num,1,num.size()-1);
	for (int i = 1; i < num.size(); i++)cout << num[i] << " ";
}

int main()
{
	Sort();
}

热门文章

暂无图片
编程学习 ·

c++数制2~16数进制的转换

通项公式: while(n!=0){ a[i]=n%d; n=(n/d); i++; } 其中n为要转换的十进制的数。d为要转换的数制,如二进制为2. #include<iostream> using namespace std;int main() {int i,n,d,a[100];//n 为要转换的十进制数,d为要转为的数制 while(cin>>n>>d){i=0;wh…
暂无图片
编程学习 ·

OpenCV笔记三--直方图

直方图定义:直方图均衡化-提高对比度-cv::equalizeHistvoid equalizeHist( InputArray src, OutputArray dst ); //输入为八位灰度图像从图片建立直方图-split,calcHistapi:void split(const Mat& src, Mat* mvbegin);//三Mat图像转化为三个图像 void calcHist( const Mat…
暂无图片
编程学习 ·

718. 最长重复子数组

给两个整数数组 A 和 B ,返回两个数组中公共的、长度最长的子数组的长度。目录1、题目分析2、解题分析3、代码示例 1:输入: A: [1,2,3,2,1] B: [3,2,1,4,7] 输出: 3 解释: 长度最长的公共子数组是 [3, 2, 1]。1、题目分析求两个数组公共的子数组的长度,那么可以用较短的那个…
暂无图片
编程学习 ·

线程

1.线程 1.什么叫做线程,跟进程之间的关系 进程:独立的cup空间运行 线程:进程中的一个执行流程,一个进程中可以包含多个线程,这些线程共享该进程提供的资源 2.创建线程(两种方式) 让这类继承Thread类 class XXX extends Thread{ public void run() Thread xx = new Threa…
暂无图片
编程学习 ·

单词学习2020

1. mindset: 心态;观念模式,思维倾向(1)This old mindset has not changed这个旧的思想意识还未转变(2)Enhancing leadership commitment and proactive mindset.增强领导力承诺和积极进取的心态(3)He faces all challenges by aggressive mindset他以积极的心态面对所…
暂无图片
编程学习 ·

Linux上远程命令

远程Linux: ssh -l root 192.168.0.1 -l 用户 远程成功了在输密码 远程Windows: rdesktop - u tedu -p tedu 192.168.0.10:3389 -u 用户 -p 密码
暂无图片
编程学习 ·

分享 github 上JavaArticle 知识库

我喜欢那些闪光的东西,比如冬日的雪花,天上的星星,还有你发光的眼睛。 以前都是被别人授之以鱼,尝到了鱼肉的鲜美,我学习了捕鱼之术,以后希望不仅能授之以鱼,同时也能授之以渔。 面试学会龙叔这套面试秘诀,一套大招带走面试官 当你面试“自我介绍”还在我是XXX时,看到…
暂无图片
编程学习 ·

springboot 整合xcf 发布 webservice

Spring Boot集成webService在pom添加依赖<!--WerbService CXF依赖 start--> <dependency><groupId>org.apache.cxf</groupId><artifactId>cxf-rt-frontend-jaxws</artifactId> </dependency> <dependency><groupId>org.…
暂无图片
编程学习 ·

Java new关键词的作用

文章目录new关键词的作用成员变量"字符串" new关键词的作用Person person = new Person();右边的new Person: 是以Person类为模板在堆中实例化一个对象。 右边的(): 意味着在对象实例化后,调用Person的构造器,对其初始化。 左边的Person person: 创建一个Person类…
暂无图片
编程学习 ·

rem移动端布局

rem移动端布局: 1、rem是CSS3新增的相对长度单位,是指相对于根元素html的font-size计算值的大小。简单可理解为屏幕宽度的百分比。 2、什么是dpr? dpr是屏幕像素密码比 计算:dpr=液晶屏幕px尺寸 / 物理尺寸(量多少就是多少) 常用的dpr有:dpr = 2,dpr=3 window.devicePi…
暂无图片
编程学习 ·

导入spring源码到idea的完整步骤

导入spring源码到idea的完整步骤1.到github上找到spring-framework代码,然后将代码fork到码云上,步骤地址如下: https://cloud.tencent.com/developer/article/1589675 2.下载gradle,安装gradle(注意idea和gradle对应的版本,楼主使用的是2019.2版本的idea和5.2.1版本的gr…
暂无图片
编程学习 ·

数据结构的基本概念和常用术语

下面是对android数据结构的基本概念和常用术语的一些理解,大家可以了解学习一下。我收集了一些学习用的资料,其中包含了很多学习,面试,中高进阶fluuter资料,还有很多视频详解,如果有同学想进一步了解,详情请看文末。数据是信息的载体,是描述客观事物属性的数、字符以及…
暂无图片
编程学习 ·

数据库导出到excel解决科学计数法问题

用Navicat等工具导出数据到excel的时候,身份证等超过11位的数字会自动转换成科学计数法,末尾数字变成“0000”。如何解决?解决方式:给超过11位的数字末尾添加 \t查询的时候,给相关字段添加 \tSELECT name,CONCAT(idcard,\t) from lm_reg然后再将查询结果导出到excel。如…
暂无图片
编程学习 ·

JavaScript作用域--总结

JavaScript作用域是什么?咋一问让人确实很懵逼。作用域这个词耳熟能详,但作用域是什么,经常用却不知怎么说起。先从定义上来说,我觉得《不知道的JavaScript》一书说得很清晰,作用域是一套查找变量的规则。查找又从何说起?又是怎么一个查找法?说起这个不得不说JavaScript…
暂无图片
编程学习 ·

Python科学计算系列12—积分变换

1.拉普拉斯变换及逆变换拉普拉斯变换公式拉普拉斯逆变换公式例子:代码如下:from sympy import * from sympy.integrals import laplace_transformt, s, a = symbols(t s a) # 拉普拉斯变换 F1 = laplace_transform(sin(a * t), t, s) F2 = laplace_transform(exp(a * t), t, …
暂无图片
编程学习 ·

数据挖掘常用算法有哪些?分类、聚类、预测、关联规则

数据挖掘常用算法1 分类在数据挖掘的发展过程中,由于数据挖掘不断地将诸多学科领域知识与技术融入当中,因此,目前数据挖掘方法与算法已呈现出极为丰富的多种形式。从使用的广义角度上看,数据挖掘常用分析方法主要有分类、聚类、估值、预测、关联规则、可视化等。从数据挖掘…
暂无图片
编程学习 ·

Java学习日记01

Java学习日记01运用Markdown以及Typora安装编译器了解大致的学习路线 运用Markdown以及Typora计划任务安装编译器计划任务了解大致的学习路线计划任务链接: java学习路线资源 java学习日表结合思想
暂无图片
编程学习 ·

数据结构与算法(Python版)五十四:AVL树的定义和性能

平衡二叉查找树: AVL树的定义 我们来看看能够在key插入时一直保持平衡的二叉查找树: AVL树 AVL是发明者的名字缩写: G.M. AdelsonVelskii and E.M. Landis 利用AVL树实现ADT Map, 基本上与BST的实现相同 不同之处仅在于二叉树的生成与维护过程 AVL树的实现中, 需要对每个节…