分治思想下的两大排序

简介: 分治思想下的排序

❤️前言

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


💘一、分治思想

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

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

分而治之的实现具体有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);
}
相关文章
|
5月前
|
机器学习/深度学习 搜索推荐
【七大排序】最基础的排序——冒泡排序
【七大排序】最基础的排序——冒泡排序
37 4
|
5月前
|
存储 搜索推荐
【七大排序】堆排序详解
【七大排序】堆排序详解
61 3
|
6月前
|
算法 搜索推荐
【六大排序详解】中篇 :选择排序 与 堆排序
选择排序可以用扑克牌理解,眼睛看一遍所有牌,选择最小的放在最左边。然后略过刚才排完的那张,继续进行至扑克牌有序。这样一次一次的挑选,思路很顺畅。总结为: 每一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,直到全部待排序的数据元素排完 。
45 6
|
算法 搜索推荐
【八大排序(七)】归并排序初级篇-递归版
【八大排序(七)】归并排序初级篇-递归版
|
6月前
|
机器学习/深度学习 算法 搜索推荐
快速排序:高效分割与递归,排序领域的王者算法
快速排序:高效分割与递归,排序领域的王者算法
70 1
|
6月前
|
算法 搜索推荐 程序员
【十大排序】带你深入分析快速排序
【十大排序】带你深入分析快速排序
|
12月前
|
机器学习/深度学习 搜索推荐
八大排序(三)--------简单选择排序
八大排序(三)--------简单选择排序
44 0
八大排序——快速排序
八大排序——快速排序
【八大排序(四)】快排-到底多快才能追上奔驰车里的夏树?(下)
【八大排序(四)】快排-到底多快才能追上奔驰车里的夏树?(下)
【八大排序(四)】快排-到底多快才能追上奔驰车里的夏树?(下)
|
搜索推荐 算法
【八大排序之交换与归并排序】(二)
【八大排序之交换与归并排序】(二)
48 0