算法基础(一)| 快速排序和归并排序详解

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

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

🔥本文已收录于算法基础系列专栏: 算法基础教程 免费订阅,持续更新。

timer 排序 归并,# 算法基础教程,算法,排序算法,快速排序,归并排序

快速排序

算法详解

不稳定,基于分治思想。

期望复杂度:nlogn,最坏 n 2 n^2 n2

  • 确定分界点

    常用分界点:取左边界q[l],取中间值q[(1+r)/2],取右边界q[r],随机值。

  • 调整区间

    保证左边数都小于等于x,右边数大于等于x即可。

    timer 排序 归并,# 算法基础教程,算法,排序算法,快速排序,归并排序

  • 递归处理左右两端

    左边排好序,右边排好序。

重点是如何调整区间:

常见思路:

  1. 双数组法(比较耗费空间)

    再开两个数组,分别是a[],b[].

    然后对于原数组q,如果q[i] ≤ x,则将x存入a[]中,否则存入b[]中。

    最后先将a[]存入q中,再将b[]存入数中。

  2. 双指针法

    采用双指针的思想。设置哨兵x进行比较。

    timer 排序 归并,# 算法基础教程,算法,排序算法,快速排序,归并排序

    让i,j向中间移动,如果i ≤ x,则继续移动,否则等待交换,如果 j ≥ x ,则继续移动,否则等待交换。当i和j都等待交换的时候,交换ij,然后继续移动。直到i大于为止。

    timer 排序 归并,# 算法基础教程,算法,排序算法,快速排序,归并排序

    timer 排序 归并,# 算法基础教程,算法,排序算法,快速排序,归并排序

例题:快速排序

给定你一个长度为 n 的整数数列。

请你使用快速排序对这个数列按照从小到大进行排序。

并将排好序的数列按顺序输出。

输入格式

输入共两行,第一行包含整数 n。

第二行包含 n 个整数(所有整数均在 1∼ 1 0 9 10^9 109 范围内),表示整个数列。

输出格式

输出共一行,包含 n 个整数,表示排好序的数列。

数据范围

1≤n≤100000

输入样例:

5
3 1 2 4 5

输出样例:文章来源地址https://www.toymoban.com/news/detail-832640.html

1 2 3 4 5

算法模板

#include <bits/stdc++.h>

using namespace std;

const int N = 1e6 +10;

int q[N];

void quick_sort(int q[], int l, int r)
{
    if (l >= r) return;
    //如果数组中就一个数,直接返回

    int x = q[l], i = l - 1, j = r + 1;
    //随机取数,注意这里i要在左边界左边,j要在右边界右边,是因为采用dowhile循环,开场会先执行一次。
    while (i < j)
    {
        do i ++ ; while (q[i] < x);
        do j -- ; while (q[j] > x);
        if (i < j) swap(q[i], q[j]);
        //当两侧都停下后,交换位置即可。
    }
	//递归地调用函数,排序左右两边。同时注意这里可能存在问题。
    quick_sort(q, l, j);
    quick_sort(q, j + 1, r);
}

int main()
{
    int n;
    scanf("%d", &n);

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

    quick_sort(q, 0, n - 1);

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

    return 0;
}

对于模板中的

    int x = q[l], i = l - 1, j = r + 1;
    while (i < j)
    {
        do i ++ ; while (q[i] < x);
        do j -- ; while (q[j] > x);
        if (i < j) swap(q[i], q[j]);
        // 同时注意这里可能存在问题。
        // 假设是[1,2] x = 1,多轮交换过后一直是[0,1],死循环就出不来了。
    }
	
    quick_sort(q, l, j);//如果这里是j的话,x 就一定不能取到q[r]
	//quick_sort(q, l, i - 1);如果这里是i的话,x 就一定不能取到q[l]
	//quick_sort(q, i, r);
    quick_sort(q, j + 1, r);

详解

timer 排序 归并,# 算法基础教程,算法,排序算法,快速排序,归并排序

timer 排序 归并,# 算法基础教程,算法,排序算法,快速排序,归并排序

timer 排序 归并,# 算法基础教程,算法,排序算法,快速排序,归并排序

归并排序

算法详解

稳定,思想:分治

时间复杂度:nlogn

timer 排序 归并,# 算法基础教程,算法,排序算法,快速排序,归并排序

以数组的中间部分来分,分为左边和右边。

  • 确定分界点。mid = (1+r)/2;

  • 递归排序left和right。

  • 合二为一(重点)。合成一个有序的数组。

    合并的方法:双指针法。

    timer 排序 归并,# 算法基础教程,算法,排序算法,快速排序,归并排序

    timer 排序 归并,# 算法基础教程,算法,排序算法,快速排序,归并排序

    timer 排序 归并,# 算法基础教程,算法,排序算法,快速排序,归并排序

    由于归并排序是稳定的,因此在两数相同的时候可以把第一个数字移动到尾部。

    timer 排序 归并,# 算法基础教程,算法,排序算法,快速排序,归并排序

例题:归并排序

给定你一个长度为 n 的整数数列。

请你使用归并排序对这个数列按照从小到大进行排序。

并将排好序的数列按顺序输出。

输入格式

输入共两行,第一行包含整数 n n n

第二行包含 n n n 个整数(所有整数均在 1∼ 1 0 9 10^9 109 范围内),表示整个数列。

输出格式

输出共一行,包含 n n n 个整数,表示排好序的数列。

数据范围

1≤n≤100000

输入样例:

5
3 1 2 4 5

输出样例:

1 2 3 4 5

算法模板

#include <iostream>

using namespace std;

const int N = 1e5 + 10;

int a[N], tmp[N];

void merge_sort(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);

    //=========归并的过程===========
    //k表示已经归并的数,i为指向左半边序列的起点,j为指向右半边序列的起点。
    int k = 0, i = l, j = mid + 1;
    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 ++ ];

    //存回q数组中
    for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];
}

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

    merge_sort(a, 0, n - 1);

    for (int i = 0; i < n; i ++ ) printf("%d ", a[i]);

    return 0;
}

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

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

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

相关文章

  • 【排序算法】归并排序与快速排序

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

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

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

    2024年02月07日
    浏览(40)
  • 非递归算法——快速排序、归并排序

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

    2023年04月08日
    浏览(72)
  • 排序算法乱炖: 快速排序、归并排序、冒泡排序

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

    2024年02月11日
    浏览(48)
  • 【数据结构】 七大排序详解(贰)——冒泡排序、快速排序、归并排序

    ==冒泡排序(Bubble Sort)==也是一种简单直观的排序算法。它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会

    2024年02月09日
    浏览(123)
  • 【数据结构】排序算法(二)—>冒泡排序、快速排序、归并排序、计数排序

    👀 樊梓慕: 个人主页  🎥 个人专栏: 《C语言》《数据结构》《蓝桥杯试题》《LeetCode刷题笔记》《实训项目》 🌝 每一个不曾起舞的日子,都是对生命的辜负 目录 前言 1.冒泡排序 2.快速排序 2.1Hoare版 2.2占坑版 2.3前后指针版 2.4三数取中对快速排序的优化 2.5非递归版 3.归

    2024年02月08日
    浏览(54)
  • 【数据结构与算法】归并排序详解:归并排序算法,归并排序非递归实现

    归并排序是一种经典的排序算法,它使用了分治法的思想。下面是归并排序的算法思想: 递归地将数组划分成较小的子数组,直到每个子数组的长度为1或者0。 将相邻的子数组合并,形成更大的已排序的数组,直到最终得到一个完全排序的数组。 归并排序的过程可以分为三

    2024年01月22日
    浏览(70)
  • 【算法】排序算法(插入排序、希尔排序、选择排序、冒泡排序、快速排序、归并排序、基数排序、堆排序)

    插入排序 :插入排序、希尔排序 选择排序 :选择排序、堆排序 交换排序 :冒泡排序、快速排序 归并排序 基数排序(又叫桶排序) (1)思路图解 从头开始比较相邻元素的值(就是从下标较小的元素开始),使值较大的元素逐渐从前移向后部,就像水里的气泡一样,越来越大,向上

    2024年03月25日
    浏览(54)
  • ①归并排序、快速排序 、堆排序、计数排序[算法、代码模板、面试题]

    个人简介:Java领域新星创作者;阿里云技术博主、星级博主、专家博主;正在Java学习的路上摸爬滚打,记录学习的过程~ 个人主页:.29.的博客 学习社区:进去逛一逛~ ⚪步骤 归并排序 : 归并排序是一种分治法(Divide and Conquer)的经典排序算法,它的基本思想是将原始数组

    2024年02月04日
    浏览(40)
  • 【数据结构与算法】:非递归实现快速排序、归并排序

    🔥 个人主页 : Quitecoder 🔥 专栏 :数据结构与算法 上篇文章我们详细讲解了递归版本的快速排序,本篇我们来探究非递归实现快速排序和归并排序 快速排序的非递归实现主要依赖于栈(stack)来模拟递归过程中的函数调用栈。递归版本的快速排序通过递归调用自身来处理子

    2024年03月24日
    浏览(55)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包