排序(快速排序 归并排序)

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

目录

一、快速排序

思路

模板

注意点

二、归并排序

思路

动画演示

模板

注意点

三、习题

1.第k个数

2.数组中的逆序对*


一、快速排序

时间复杂度:

平均情况O(nlog2n)

最坏情况O(n^2)

思路

1. 确定分界点x (可取为q[l]、q[r]或 q[(l + r) / 2])

【x被称为支点(pivot),也称为枢轴元素。】

排序(快速排序 归并排序)

2. 划分区间 ( 将区间[l, r]划分为 <= x 和 >= x )【重点

排序(快速排序 归并排序)

3. 利用递归把小于基准值元素的子数列和大于基准值元素的子数列进行排序

模板

void quick_sort(vector<int>& q, int l, int r)
{
	if (l >= r) return;
	int x = q[(r + l) >> 1], i = l - 1, j = r + 1;
	while (i < j)
	{
		do i++; while (q[i] < x);
		do j--; while (q[j] > x);
		if (i < j) std::swap(q[i], q[j]);
	}
	quick_sort(q, l, j);
	quick_sort(q, j + 1, r);
}

注意点

【注意边界问题】

取左端点或右端点作为支点元素的方法比较简单,但是在某些情况下可能会导致快速排序算法出现最坏情况。

例如待排序数组已经有序或者接近有序的情况下。在这种情况下,取左端点或右端点作为支点元素会导致分割出来的左右两个子数组极度不平衡,导致算法效率变得极低。

取中间点作为支点元素的方法可以避免快速排序算法出现最坏情况,但是需要额外的计算来确定中间点的位置,可能会导致效率降低。因此,一般来说,随机选择法或三数取中法更常用,它们都可以避免最坏情况的发生,同时具有较高的效率和良好的性能。

切忌将 q[i] < x 改为 q[i] <= x 或是将 q[j] > x 改为 q[j] >= x ,会导致满足条件的数组下,指针无限移动,无限循环。

当支点选择q[l]时,递归填入区间必须为[l, j]和[j + 1, r];当支点选择q[r]时,递归递归填入区间必须为[l, i]和[i + 1, r],否则会触发边界问题。

二、归并排序

时间复杂度:O(nlog2n)

思路

1. 确定分界点

2. 递归排序

3. 归并(合二为一)【重点

动画演示

排序(快速排序 归并排序)

排序(快速排序 归并排序)

模板

const int N = 1000;
vector<int> tmp(N);
void merge_sort(vector<int>& q, int l, int r)
{
	if (l >= r) return;
	int mid = (l + r) >> 1;
	merge_sort(q, l, mid);
	merge_sort(q, mid + 1, r);
	int i = l, j = mid + 1, k = 0;
	while (i <= mid && j <= r)
		if (q[i] <= q[j]) tmp[k++] = q[i++];
		else tmp[k++] = q[j++];
	while (i <= mid) tmp[k++] = q[i++];
	while (j <= r) tmp[k++] = q[j++];
	
	for (i = l, j = 0; i <= r; ++i, ++j) q[i] = tmp[j];
}

注意点

  1. 确定归并排序的边界条件:在实现归并排序时,需要确定递归终止的边界条件,一般是当待排序数组的大小小于等于1时,直接返回即可。

  2. 数组下标越界问题:在归并排序中,需要使用一个临时数组来存储排序结果,如果临时数组的大小不够或者在操作数组时下标越界,会导致程序出错。

  3. 归并排序的稳定性:归并排序是一种稳定的排序算法,即排序后相同元素的相对位置不变。在实现归并排序时,需要注意保持排序的稳定性。

  4. 归并排序的时间和空间复杂度:归并排序的时间复杂度为O(nlogn),空间复杂度为O(n),在排序大规模数据时,可能会出现内存溢出等问题,需要注意。

  5. 优化归并排序:归并排序虽然时间复杂度很好,但是在实际应用中可能会出现一些效率问题。可以通过一些优化措施来提高归并排序的效率,例如使用循环代替递归、使用插入排序优化小数组的排序等。

三、习题

1.第k个数

排序(快速排序 归并排序)

支点选择出来后,选择递归的范围。

当k <= i,递归左区间 [l, i]。

当k >= j,递归右区间 [j, r]。

时间复杂度:

n + n / 2 + n / 4 + ... <= 2n
O(n)

#include<iostream>

class solution
{
public:
	int quick_sort(int q[], int l, int r, int k)
	{
		if (l >= r) return q[l];
		int x = q[(l + r) >> 1], i = l - 1, j = r + 1;
		while (i < j)
		{
			do i++; while (q[i] < x);
			do j--; while (q[j] > x);
			if (i < j) std::swap(q[i], q[j]);
		}
		if (k <= j) return quick_sort(q, l, j, k);
		return quick_sort(q, j + 1, r, k);
	}
};
int main()
{
    const int N = 1000;
	int q[N];
	int n, k;
	scanf("%d%d", &n, &k);

	for (int i = 0; i < n; i++) scanf("%d", &q[i]);

	std::cout << solution().quick_sort(q, 0, n - 1, k - 1) << std::endl;
    // 传入(k - 1)来指向第k小目标的坐标

    return 0;
}

2.数组中的逆序对*

排序(快速排序 归并排序)

 利用数组局部有序性,在归并过程中利用两指针之差来计算出对应的逆序数。

排序(快速排序 归并排序)

class Solution {
public:
	int reversePairs(vector<int>& nums)
	{
		int tmp[nums.size()];
		return merge_sort(nums, tmp, 0, nums.size() - 1);
	}
private:
	long long merge_sort(vector<int>& q, int tmp[], int l, int r)
	{
		if (l >= r) return 0;
		int mid = (l + r) >> 1;
		long long res = merge_sort(q, tmp, l, mid) + merge_sort(q, tmp, mid + 1, r);

		int k = 0, i = l, j = mid + 1;
		while (i <= mid && j <= r)
			if (q[i] <= q[j]) tmp[k++] = q[i++];
			else
			{
				res += (mid + 1 - i);
				tmp[k++] = q[j++];
			}
		while (i <= mid) tmp[k++] = q[i++];
		while (j <= r) tmp[k++] = q[j++];
		
		for (i = l, j = 0; i <= r; i++, j++) q[i] = tmp[j];
		return res;
	}
};

tip:

leetcode上创建临时数组tmp必须要使用int来创建,用vector创建会导致超时的错误。文章来源地址https://www.toymoban.com/news/detail-431563.html

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

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

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

相关文章

  • 选择排序、归并排序、快速排序

    1.选择排序 选择排序算法的实现思路有点类似插入排序,也分已排序区间和未排序区间。但是选择排序每次会从未排序区间中找到最小的元素,将其放到已排序区间的末尾。 Java代码实现如下。 ps:选择排序的最好情况时间复杂度、最坏情况和平均情况时间复杂度都为 O(n2),

    2024年02月12日
    浏览(40)
  • 排序(快速排序 归并排序)

    目录 一、快速排序 思路 模板 注意点 二、归并排序 思路 动画演示 模板 注意点 三、习题 1.第k个数 2.数组中的逆序对* 时间复杂度: 平均情况O(nlog2n) 最坏情况O(n^2) 1. 确定分界点x (可取为q[l]、q[r]或 q[(l + r) / 2]) 【x被称为 支点(pivot) ,也称为 枢轴元素 。】 2. 划分区间

    2024年02月02日
    浏览(28)
  • 【排序算法】归并排序与快速排序

           🔥🔥 欢迎来到小林的博客!!       🛰️博客主页:✈️小林爱敲代码       🛰️博客专栏:✈️ 算法训练笔记       🛰️社区 :✈️ 进步学堂       🛰️欢迎关注:👍点赞🙌收藏✍️留言 今天给大家分享两种排序,一种是

    2024年01月19日
    浏览(39)
  • 排序算法二 归并排序和快速排序

    目录 归并排序 快速排序 1 挖坑法​编辑 2 Hoare法 快排的优化 快排的非递归方法 七大排序算法复杂度及稳定性分析 归并排序是建立在归并操作上的一种有效的排序算法,将以有序的子序列合并,得到完全有序的序列,即先使每个子序列有序,在使子序列段间有序.若将两个有序的

    2024年02月07日
    浏览(40)
  • 快速排序和归并排序(递归实现)

    算法采用了分治的思想 arr先保证局部有序,再慢慢变得整体有序 实际并没有分割数组

    2024年04月14日
    浏览(37)
  • 非递归算法——快速排序、归并排序

    哈喽大家好,我是保护小周ღ,本期为大家带来的是常见排序算法中的 快速排序、归并排序,非递归算法, 分享所有源代码,粘贴即可运行,保姆级讲述 , 包您一看就会,快来试试吧~ 目录 一、递归的缺陷 1.1 栈是什么,数据结构“栈”又是什么,他们之间有什么区别?

    2023年04月08日
    浏览(72)
  • 【数据结构】快速排序,归并排序

    1.hoare版本 根据动图的演示,整理的思路如下, 1.定义left,right,key。key默认是左边第一个元素,像两个指针,左边找比key大的,右边找比k小的,找到的话,交换二者,往返这个过程,当left与right相遇时,交换key和此时相遇的值. 单趟下来,6出现在正确的位置。 1.为什么大循环

    2024年01月20日
    浏览(42)
  • 排序算法乱炖: 快速排序、归并排序、冒泡排序

    1. 快速排序原地版 最好情况的时间复杂度 :O(nlogn),logn为递归的层数,n为每层递归中总的时间复杂度。 最差情况的时间复杂度 :O(n*n) 2. 快速排序空间换时间版 最好情况的时间复杂度 :低于O(nlogn) 思想 :分治。分而治之 ,递归的把数据一分为二,直到数组中只有一个元素

    2024年02月11日
    浏览(48)
  • 算法基础15 —— 分治算法(归并排序 + 快速排序)

    分治法的基本概念、思想 分治法是一种很重要的算法。 字面解释,分治分治,分而治之。就是把一个复杂的问题分成两个或更多的相同或相似的子问题,再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解,原问题的解即子问题的解的合并。 不难发现,分

    2024年02月03日
    浏览(53)
  • 算法基础(一)| 快速排序和归并排序详解

    ⭐写在前面的话:本系列文章旨在复习算法刷题中常用的基础算法与数据结构,配以详细的图例解释,总结相应的代码模板,同时结合例题以达到最佳的学习效果。本专栏面向算法零基础但有一定的C++基础的学习者。若C++基础不牢固,可参考:10min快速回顾C++语法,进行语法

    2024年02月21日
    浏览(53)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包