快速排序+归并排序

小鱼儿 2023-01-18 11:28 5阅读 0赞

#include<iostream>
    #include<vector>
    
    using namespace std;
    
    void quicksort(vector<int> &v,int low,int high) {
    	if(low>=high) return;
    	int key=v[low],begin=low,end=high;
    	while(begin<end) {
    	    while(begin<end && v[end]>key) {
    	        end--;
    	    }
    	    if(begin<end) v[begin++]=v[end];
    		
    	    while(begin<end && v[begin]<=key) {
    		begin++;
    	    }
    	    if(begin<end) v[end--]=v[begin];
    	}
    	
    	v[begin]=key;
    	quicksort(v,low,begin-1);
    	quicksort(v,begin+1,high);
    	return;
    	
    }
    
    void mergesort(vector<int> &v,vector<int> &copy,int low,int high) {
    	if(low>=high) return;
    	int mid=(low+high)/2;
    	int low1=low,high1=mid,low2=mid+1,high2=high,index=low;
    	mergesort(copy,v,low1,high1);
    	mergesort(copy,v,low2,high2);
    	
    	while(low1<=high1 && low2<=high2) {
    	    copy[index++]=v[low1]<v[low2]?v[low1++]:v[low2++];
    	}
    	
    	while(low1<=high1) {
    	    copy[index++]=v[low1++];
    	}
    	
    	while(low2<=high2) {
    	    copy[index++]=v[low2++];
    	}
    	return;
    	
    }
    
    int main() {
    	
    	vector<int> v={2,7,8,3,1,9,6,4};
    	vector<int> copy(v.size(),0);
    	mergesort(v,copy,0,v.size()-1);
    	v.assign(copy.begin(), copy.end());
    	//quicksort(v,0,v.size()-1);
    	for(auto &w:v)
    	    cout<<w<<" ";
    	cout<<endl;
    	return 0;
    }

发表评论取消回复

表情：

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

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

相关阅读

相关排序：归并排序和快速排序

力扣leetcode：912.排序数组，可以用来练习排序算法题目：给你一个整数数组 `nums`，请你将该数组升序排列。目录归并排序快速排序 --------

梦里梦外;/ 2023年09月28日 16:36/ 0 赞/ 29 阅读

相关快速排序+归并排序

include<iostream> include<vector> using namespace std; void qu

小鱼儿/ 2023年01月18日 11:28/ 0 赞/ 6 阅读

相关排序算法之插入排序、归并排序、快速排序

我的算法基本功太差了，有必要进行练习，就用经典算法——排序和搜索，来试试吧。以下是插入排序和归并排序： \ifndef SomeSort\_H \define SomeS

àì夳堔傛蜴生んèń/ 2022年09月30日 07:05/ 0 赞/ 229 阅读

相关堆排序、归并排序、快速排序总结

昨天刚把这三个排序算法复习了一遍，其中归并排序和快速排序特别的重要，一定要熟练并理解透彻！以下排序的结果都默认为非递减 1、堆排序（默认大顶堆）堆排序的思想：首先

浅浅的花香味﹌/ 2022年09月28日 13:19/ 0 赞/ 182 阅读

相关快速排序、归并排序、堆排序的实现

最近总是遇到面试问到归并排序的问题，下面我们来走一遍。 1、快速排序参考严蔚敏数据结构教材，下面是本人写的快速排序实现： include<iostream>

我会带着你远行/ 2022年08月07日 07:37/ 0 赞/ 201 阅读

相关排序：快速排序和归并排序

快速排序快速排序递归实现 //快速排序递归实现 void qsort_once(int arr, int low, int high) {

超、凢脫俗/ 2022年07月27日 15:56/ 0 赞/ 240 阅读

相关快速排序，归并排序，堆排序python实现

http://blog.csdn.net/u011608357/article/details/37724329 快速排序的时间复杂度最好情况下为O(n\lo

淡淡的烟草味﹌/ 2022年07月17日 02:53/ 0 赞/ 281 阅读

相关排序——归并与快速排序

I. 归并排序归并排序思想 1. 将数组一分为二（折半）; 2. 分别将两部分数组进行排序； 3. 将排序好的两部分数组进行合并成新的有序数组。动态图

亦凉/ 2022年05月14日 11:51/ 0 赞/ 258 阅读

相关插入排序、归并排序、快速排序的比较

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RYSDky

清疚/ 2022年04月15日 05:11/ 0 赞/ 235 阅读

相关排序算法：归并排序、快速排序

相关博客： [排序算法：冒泡排序、插入排序、选择排序、希尔排序][Link 1] [排序算法：归并排序、快速排序][Link 2] [排序算法：桶排序、计数排序、基

落日映苍穹つ/ 2022年03月22日 18:56/ 0 赞/ 376 阅读