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

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

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

 

类别

排序方法

最好时间

最坏时间

平均时间

空间复杂度

稳定性

序列特征

适用于

插入排序

直接插入排序

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();
}

热门文章

暂无图片
编程学习 ·

java后端重点

java基础,设计模式,jvm原理,spring+springmvc原理及源码,linux,mysql事务隔离与锁机制,mongodb,http/tcp,多线程,分布式架构(dubbo,dubbox,spring cloud),弹性计算架构,微服务架构(springboot+zookeeper+docker+jenkins),java性能优化,以及相关的项目管理等…
暂无图片
编程学习 ·

2020年6月份所有文章汇总

历史汇总:2020年5月份所有文章汇总 2020年4月份所有文章汇总 2020年3月份所有文章汇总 2020年2月份所有文章汇总 2020年1月份所有文章汇总 2019年度所有文章汇总 2018年度所有文章汇总2020年6月份原创文章:写简历没模板?别怕,这些开源项目帮你搞定! 推荐几款基于 Markdown…
暂无图片
编程学习 ·

使用go语言寻找最长不含有重复字符的字串,统计数量

go语言Map例题(寻找最长不含有重复字符的字串 )要求 a := abcdabc 那么得出统计说是4,实现下方代码 解题思路lastOccurred[x]不存在,或者无需操作 lastOccurred[x] >= start -> 更新start 更新lastOccurred[x],更新maxLengthfunc lengthOfNonRepeatingSubstr(s strin…
暂无图片
编程学习 ·

Node.Js+React.Js+Git的基本开发环境配置

1、基本开发环境的配置 主要包括node.Js的基本安装、React的基本安装、GIT的安装以及git可视化工具sourceTree的基本安装。 (1)node.Js的安装 官网搜索node.Js,下载安装包,进行傻瓜式安装(点击下一步就可以)。(2)React的基本安装 首先创建一个项目文件夹, cd 到需要创…
暂无图片
郑州普通话 ·

学习笔记六——循环神经网络

一、RNN 前馈神经网络&#xff1a;信息往一个方向流动。包括MLP和CNN 循环神经网络&#xff1a;信息循环流动&#xff0c;网络隐含层输出又作为自身输入&#xff0c;包括RNN、LSTM、GAN等。 RNN模型结构如下图所示&#xff1a; 展开之后相当于堆叠多个共享隐含层参数的前馈…
暂无图片
代理记账 ·

学习笔记六——循环神经网络

一、RNN 前馈神经网络&#xff1a;信息往一个方向流动。包括MLP和CNN 循环神经网络&#xff1a;信息循环流动&#xff0c;网络隐含层输出又作为自身输入&#xff0c;包括RNN、LSTM、GAN等。 RNN模型结构如下图所示&#xff1a; 展开之后相当于堆叠多个共享隐含层参数的前馈…
暂无图片
cgfy ·

学习笔记六——循环神经网络

一、RNN 前馈神经网络&#xff1a;信息往一个方向流动。包括MLP和CNN 循环神经网络&#xff1a;信息循环流动&#xff0c;网络隐含层输出又作为自身输入&#xff0c;包括RNN、LSTM、GAN等。 RNN模型结构如下图所示&#xff1a; 展开之后相当于堆叠多个共享隐含层参数的前馈…
暂无图片
coreui ·

Heap Sort 讲解

Heap Sort sorts a group of unordered elements using the Heap data structure. The sorting algorithm using a Min Heap is as follows: Heapify all elements into a Min HeapRecord and delete the top elementPut to top element into an array T that stores all so
暂无图片
未来博客 ·

Heap Sort 讲解

Heap Sort sorts a group of unordered elements using the Heap data structure. The sorting algorithm using a Min Heap is as follows: Heapify all elements into a Min HeapRecord and delete the top elementPut to top element into an array T that stores all so
暂无图片
建站日记 ·

[react] 你觉得react上手快不快?它有哪些限制?

[react] 你觉得react上手快不快&#xff1f;它有哪些限制&#xff1f; 相对vue来说不快。 限制 需要学习JSX需要工程化的配置需要对原生JavaScript有相当的掌握react只是一个UI层面的库&#xff0c;像vue内置了动画处理、keep-alive等功能&#xff0c;react则需要去找第三方库…
暂无图片
mfbz ·

学习笔记六——循环神经网络

一、RNN 前馈神经网络&#xff1a;信息往一个方向流动。包括MLP和CNN 循环神经网络&#xff1a;信息循环流动&#xff0c;网络隐含层输出又作为自身输入&#xff0c;包括RNN、LSTM、GAN等。 RNN模型结构如下图所示&#xff1a; 展开之后相当于堆叠多个共享隐含层参数的前馈…
暂无图片
mfbz ·

AOV网是否存在回路-拓扑排序-C++

拓扑排序是对测试AOV网是否存在回路的方法&#xff01; 拓扑排序的过程中&#xff0c;由于需要查找所有以某顶点为尾的弧&#xff0c;即找到该顶点的所有出边&#xff0c;故图要采用邻接表的存储方式。但拓扑排序较邻接表的存储方式有一点不同&#xff0c;由于要查找入度为0的点…
暂无图片
珊珊日记 ·

学习笔记六——循环神经网络

一、RNN 前馈神经网络&#xff1a;信息往一个方向流动。包括MLP和CNN 循环神经网络&#xff1a;信息循环流动&#xff0c;网络隐含层输出又作为自身输入&#xff0c;包括RNN、LSTM、GAN等。 RNN模型结构如下图所示&#xff1a; 展开之后相当于堆叠多个共享隐含层参数的前馈…
暂无图片
珊珊日记 ·

AOV网是否存在回路-拓扑排序-C++

拓扑排序是对测试AOV网是否存在回路的方法&#xff01; 拓扑排序的过程中&#xff0c;由于需要查找所有以某顶点为尾的弧&#xff0c;即找到该顶点的所有出边&#xff0c;故图要采用邻接表的存储方式。但拓扑排序较邻接表的存储方式有一点不同&#xff0c;由于要查找入度为0的点…