数据结构练习:自写的想法写归并排序 2020.11.20

简介: 数据结构练习:自写的想法写归并排序 2020.11.20


#include <iostream>
#include<vector>
using namespace std;
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
void merge_short(vector<int> &q,int l,int r);
void merge_short(vector<int> &q,int l,int r) 
{
  int mid=(l+r)/2;
  if(l==r)
    return;
  int left=l,right=r,i,r2=mid+1; 
  merge_short(q,l,mid);
  merge_short(q,mid+1,r);
  static vector<int> w;
  w.clear();
  //将较小的数据存放在临时数组中 
  while(l<=mid&&r2<=r)
  {
    if(q[l]<=q[r2])
    {
      w.push_back(q[l++]);
    }
    else
    {
      w.push_back(q[r2++]);
    }
  }
  while(l<=mid)w.push_back(q[l++]);//将l到r的剩余数据存储到w中 
  while(r2<=r)w.push_back(q[r2++]);
  for(i=left;i<=mid;i++)//将w中排好序的数据填充到原数组中 
  {
    q[i]=w[i-left];
  }
  for(int j=mid+1;j<=right;j++,i++)
  {
    q[j]=w[i-left];
  }
  return;
}
int main(int argc, char** argv) {
  vector<int> a;
  int i=0,n;
  cin>>n;
  for(i=0;i<n;i++)
  {
    int b;
    cin>>b;
    a.push_back(b);
  }
  merge_short(a,0,a.size()-1);
  for(i=0;i<a.size();i++)
  {
    printf("%d  ",a[i]);
   } 
  return 0;
}


相关文章
|
3天前
|
搜索推荐 C语言
数据结构(C语言)之对归并排序的介绍与理解
归并排序是一种基于分治策略的排序算法,通过递归将数组不断分割为子数组,直到每个子数组仅剩一个元素,再逐步合并这些有序的子数组以得到最终的有序数组。递归版本中,每次分割区间为[left, mid]和[mid+1, right],确保每两个区间内数据有序后进行合并。非递归版本则通过逐步增加gap值(初始为1),先对单个元素排序,再逐步扩大到更大的区间进行合并,直至整个数组有序。归并排序的时间复杂度为O(n*logn),空间复杂度为O(n),且具有稳定性,适用于普通排序及大文件排序场景。
|
22天前
|
存储 人工智能 算法
【C++数据结构——内排序】二路归并排序(头歌实践教学平台习题)【合集】
本关任务是实现二路归并算法,即将两个有序数组合并为一个有序数组。主要内容包括: - **任务描述**:实现二路归并算法。 - **相关知识**: - 二路归并算法的基本概念。 - 算法步骤:通过比较两个有序数组的元素,依次将较小的元素放入新数组中。 - 代码示例(以 C++ 为例)。 - 时间复杂度为 O(m+n),空间复杂度为 O(m+n)。 - **测试说明**:平台会对你编写的代码进行测试,提供输入和输出示例。 - **通关代码**:提供了完整的 C++ 实现代码。 - **测试结果**:展示代码运行后的排序结果。 开始你的任务吧,祝你成功!
33 10
|
5月前
|
存储 搜索推荐 算法
【初阶数据结构篇】归并排序和计数排序(总结篇)
归并排序(MERGE-SORT)是建⽴在归并操作上的⼀种有效的排序算法,该算法是采⽤分治法(Divide andConquer)的⼀个⾮常典型的应⽤。
73 0
|
7月前
|
存储 算法 数据安全/隐私保护
【Python学习篇】Python实验小练习——高级数据结构(五)
【Python学习篇】Python实验小练习——高级数据结构(五)
87 1
【数据结构】红黑树——领略天才的想法
【数据结构】红黑树——领略天才的想法
|
3月前
|
算法 搜索推荐 Shell
数据结构与算法学习十二:希尔排序、快速排序(递归、好理解)、归并排序(递归、难理解)
这篇文章介绍了希尔排序、快速排序和归并排序三种排序算法的基本概念、实现思路、代码实现及其测试结果。
71 1
|
3月前
【初阶数据结构】打破递归束缚:掌握非递归版快速排序与归并排序
【初阶数据结构】打破递归束缚:掌握非递归版快速排序与归并排序
|
3月前
|
算法
蓝桥杯宝藏排序 | 数据结构 | 快速排序 归并排序
蓝桥杯宝藏排序 | 数据结构 | 快速排序 归并排序
|
7月前
|
算法
数据结构与算法-归并排序
数据结构与算法-归并排序
39 2
|
7月前
|
搜索推荐
深入理解数据结构第六弹——排序(3)——归并排序
深入理解数据结构第六弹——排序(3)——归并排序
55 1

热门文章

最新文章