归并排序挖坑法

心已赠人 2021-12-19 16:33 229阅读 0赞

我看的快速排序解析：https://blog.csdn.net/na\_hanqiannan/article/details/82080980

代码：

#include<iostream>
    #include<cstring>
    #define N 100000+10
    using namespace std;
    int a[N],n,s;
    void q_sort(int l,int r)
    {
         
        int i=l,j=r,pivot=a[l],index=l;
        //i从左边开始查找
        //j从右边往左查找
        //pivot是坑
        //index是坑的位置
        while(i<=j){
        //如果i》j的话，交换的目的就相反
            while(a[j]>pivot&&i<=j)j--;//从右往左找到一个《=pivot的数
            if(i<=j){
                a[index]=a[j];//填坑
                index=j;//坑的位置改变
                i++;//其实index要么在I上要么在j上，所以坑填好了I++避免下次有找到他自己
            }
            while(a[i]<pivot&&i<=j)i++;//和上面差不多
            if(i<=j){
                a[index]=a[i];
                index=i;
                j--;
            }
        }
        a[index]=pivot;//最后的坑补上

if(l<index)q\_sort(l,index\-1);

if(index<r)q\_sort(index\+1,r);

return;
    }
    int main()
    {
        cin>>n;
        for(int i=1;i<=n;i++)cin>>a[i];
        q_sort(1,n);
        for(int i=1;i<=n;i++)cout<<a[i]<<" ";
        cout<<endl;
    }

转载于:https://www.cnblogs.com/jzxnl/p/11070764.html

发表评论取消回复

表情：

评论列表（有 0 条评论，229人围观）

还没有评论，来说两句吧...

相关阅读

相关《算法》笔记 4 - 归并排序

归并方法自顶向下的归并排序实现性能分析优化：切换到插入排序自底向上的归并排序归并方法

今天药忘吃喽~/ 2023年06月04日 10:53/ 0 赞/ 9 阅读

相关分治法-归并排序

一、前言归并排序归并排序是建立在归并操作上的一种有效的排序算法，速度仅次于快速排序，为稳定排序算法，一般用于对总体无序，但是各子项相对有序的数列。该算法是采用分

落日映苍穹つ/ 2022年11月16日 05:47/ 0 赞/ 208 阅读

相关 Data Structure--排序--快速排序(挖坑法)--快速排序(前后指针法)

快速排序快速排序(挖坑法) 快速排序(前后指针法) 对于下面要讲的两种进行快排的函数来说,我们都需要利用下面的这两个函数,一个是获取中间值的接口,一个是快

拼搏现实的明天。/ 2022年11月03日 10:38/ 0 赞/ 182 阅读

相关【数据结构】快速(QuickSort)排序之——挖坑法

快速排序的定义：快速排序(Quick Sort)是一种有效的排序[算法][Link 1]。虽然算法在最坏的情况下运行时间为O(n^2)，但由于平均运行时间为O(nlogn)

古城微笑少年丶/ 2022年06月16日 12:19/ 0 赞/ 238 阅读

相关归并排序 java（分治法）

归并排序：归并排序是将给定的数列，尽可能地数量相同的两个数列。然后通过递归调用进行排序，排序完毕后的，将两个已经排好序的数列

以你之姓@/ 2022年05月31日 07:36/ 0 赞/ 261 阅读

相关算法排序----归并排序法

归并排序法，实际上也是分治法的一个范例。主要的思路分为三步: 1.将序列分为两个子序列。 2.对这两个子序列分别进行归并排序，即一直拆分到只有一个元素。

分手后的思念是犯贱/ 2022年05月19日 13:50/ 0 赞/ 221 阅读

相关 java归并排序及分治法

归并排序采用分治法的思想：将原问题分解为若干规模较小但类似于原问题的子问题，递归地求解这些子问题，再合并这些子问题的解来建立原问题的解。分治模式在每层递归时都有三个步骤：

川长思鸟来/ 2022年05月15日 03:12/ 0 赞/ 227 阅读

相关归并类排序-----归并排序

/归并（Merge）排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合

绝地灬酷狼/ 2022年05月03日 01:56/ 0 赞/ 297 阅读

相关归并排序挖坑法

我看的快速排序解析：https://blog.csdn.net/na\_hanqiannan/article/details/82080980 代码： includ

心已赠人/ 2021年12月19日 16:33/ 0 赞/ 230 阅读

相关分治法——归并排序

归并排序归并排序是成功应用分治法的完美例子，归并排序是按照记录在序列中的位置对序列进行划分。【问题】应用归并排序方法对一个记录序列进行升序排序。归并排序（m

￡神魔★判官ぃ/ 2021年06月22日 15:36/ 0 赞/ 497 阅读