分治思想下的两大排序

简介: 分治思想下的排序

❤️前言

本文介绍两种基于分治思想的经典排序算法: 归并排序快速排序


💘一、分治思想

分治思想,就是将原问题分解为几个规模较小但类似于原问题的子问题,递归地求解这些子问题,然后在合并这些子问题的解来建立原问题的解。

从上面的解释中我们可以看出,分而治之的思维是靠递归来实现的,所以说,分而治之是一种思维,而递归就是具体的实现。
在这里插入图片描述

分而治之的实现具体有2个步骤:
1.找出基线条件,这种条件必须尽可能简单。

  1. 不断将问题分解(或者说缩小规模),直到符合基线条件。

💞二、归并排序

1.实现方法

归并排序的核心思想是分治思想
分:将未排序的数组从中间分割成2部分,依次类推直至无法分割。
治:当无法再分割时,便可以对分区的元素进行两两合并
简而言之,就是左边排好序+右边排好序+归(合)并让整体有序
值得注意的是在对分区进行合并时,需要一个额外的辅助数组来暂存合并的结果,最后再复制到原数组中。
在这里插入图片描述

2.动图分析

在这里插入图片描述

3.代码模板

//合并函数
void merge(int arr[], int l, int mid, int r)
{
    int n = r - l + 1;
    //辅助数组
    int* help = (int*)malloc(n * sizeof(int));
    int index = 0;
    int p1 = l, p2 = mid + 1;
    while (p1 <= mid && p2 <= r) {
        if (arr[p1] <= arr[p2])
            help[index++] = arr[p1++];
        else
            help[index++] = arr[p2++];
    }
    while (p1 <= mid) {
        help[index++] = arr[p1++];
    }
    while (p2 <= r) {
        help[index++] = arr[p2++];
    }
    //复制到原数组
    for (int i = 0; i < n; i++) {
        arr[l + i] = help[i];
    }
}
//递归实现归并排序
void merge_sort(int arr[], int l, int r)
{
    if (l >= r)
        return;
    int mid = ( l + r  ) / 2;
    //排序左边
    merge_sort(arr, l, mid);
    //排序右边
    merge_sort(arr, mid + 1, r);
    //合并
    merge(arr, l, mid, r);
}

💖三、快速排序

1.实现方法

快速排序的核心思想同样也是分治思想
但是快速排序在分组的时候已经根据元素的大小来分组了,因此,合并时快速排序只需要把两个分组合并起来就可以了。而归并排序则需要对两个有序的数组根据大小进行合并。

快速排序的实现:
1、先调整区间,使小于等于基数x的在左边 ,大于等于基数x 的在右边。
2、递归处理基数x的左右段。

在这里插入图片描述

2.动图分析

在这里插入图片描述

3.代码模板

//递归实现快速排序
void quick_sort(int q[], int l, int r)
{
    if (l >= r) return;
    int i = l - 1, j = r + 1, x = q[l + r >> 1];
    while (i < j)
    {
        do i++; while (q[i] < x);
        do j--; while (q[j] > x);
        if (i < j)
        {
           //交换数据
            int tmp;
            tmp = q[i];
            q[i] = q[j];
            q[j] = tmp;
        }
    }
    //递归处理左右两段
    quick_sort(q, l, j), quick_sort(q, j + 1, r);
}
相关文章
|
12月前
|
存储 监控 NoSQL
九大核心NoSQL数据库及使用场景详解
【10月更文挑战第6天】在当今大数据与云计算飞速发展的时代,NoSQL数据库以其灵活的数据模型、可扩展性和高性能,成为了众多应用场景下的首选。本文将为您详细介绍九大核心NoSQL数据库及其典型使用场景,帮助您在工作和学习中更好地选择和应用。
434 3
|
存储 Java 测试技术
JAVA-MAVEN初学者教程(配置、pom.xml、依赖管理等)
JAVA-MAVEN初学者教程(配置、pom.xml、依赖管理等)
2563 0
|
城市大脑 运维 安全
IDC报告:中国软件安全网关、中国信息和数据安全市场份额双冠!
近日,国际权威分析机构IDC发布《2022年上半年中国IT安全软件市场跟踪报告》,阿里云以31.0%的市场份额获得“中国软件安全网关市场份额”第一,实现五连冠!同时,在新增的“中国信息和数据安全”项目,以6.8%的市场份额同样位居第一。
620 0
|
11月前
|
运维 Kubernetes Cloud Native
Kubernetes云原生架构深度解析与实践指南####
本文深入探讨了Kubernetes作为领先的云原生应用编排平台,其设计理念、核心组件及高级特性。通过剖析Kubernetes的工作原理,结合具体案例分析,为读者呈现如何在实际项目中高效部署、管理和扩展容器化应用的策略与技巧。文章还涵盖了服务发现、负载均衡、配置管理、自动化伸缩等关键议题,旨在帮助开发者和运维人员掌握利用Kubernetes构建健壮、可伸缩的云原生生态系统的能力。 ####
|
存储 SQL NoSQL
详解数据库管理系统(DBMS)
【8月更文挑战第31天】
2948 0
|
存储 数据可视化 安全
软件需求分析文档怎么写?
软件需求分析文档怎么写?
1058 0
|
机器学习/深度学习 人工智能 算法
【AI大模型应用开发】【补充知识】文本向量化与向量相似度(含Python代码)
【AI大模型应用开发】【补充知识】文本向量化与向量相似度(含Python代码)
338 0
|
存储 算法
多目标粒子群算法(MOPSO)的原理和matlab实现
初学者面对多目标优化问题可能比较困难,写下这篇博客记录一下自己学习的心得,希望能和大家一起交流学习。采用粒子群求单目标优化问题的原理很好理解,就是通过对粒子群的速度和位置不断来更新粒子群的最优适应度(也就是目标函数),达到寻优的目的。但是多目标优化问题就比较难办了,由于目标函数有多个,如果同样使用粒子群算法,那么适应度怎么设置?怎么确定全体最优的粒子?这些问题都是比较棘手的。
|
算法 C语言
经典算法之深度优先搜索(DFS)
经典算法之深度优先搜索(DFS)
经典算法之深度优先搜索(DFS)
|
JSON 前端开发 数据格式
二进制流下载文件
二进制流下载文件
461 0
二进制流下载文件