【912.排序数组】

2023-10-22 00:36

文章标签 数组排序 912

本文主要是介绍【912.排序数组】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一、题目描述

在这里插入图片描述

二、算法原理

2.1快速排序

在这里插入图片描述

2.2归并排序

在这里插入图片描述

三、代码实现

3.1快排代码实现

class Solution {
public:int getRandom(int left,int right,vector<int>& nums){return nums[rand()%(right-left+1)+left];}void _sortArray(int left,int right,vector<int>& nums){if(left>right){return ;}int key=getRandom(left,right,nums);int l=left-1,r=right+1,i=left;while(i<r){if(nums[i]<key)swap(nums[++l],nums[i++]);else if(nums[i]>key)swap(nums[i],nums[--r]);elsei++;}_sortArray(left,l,nums);_sortArray(r,right,nums);}vector<int> sortArray(vector<int>& nums) {srand(time(NULL));_sortArray(0,nums.size()-1,nums);return nums;}
};

3.2归并代码实现

class Solution {
public:void mergeSort(vector<int>& nums,int left,int right){if(left>=right){return;}int mid=left+(right-left)/2;mergeSort(nums,left,mid);mergeSort(nums,mid+1,right);//合并两个有序数组vector<int> v(right-left+1);int cur1=left,cur2=mid+1,i=0;while((cur1<=mid)&&(cur2<=right)){if(nums[cur1]<nums[cur2]){v[i++]=nums[cur1++];}else{v[i++]=nums[cur2++];}}while(cur1<=mid) v[i++]=nums[cur1++];while(cur2<=right) v[i++]=nums[cur2++];//还原数组for(int i=left;i<=right;i++){nums[i]=v[i-left];}}vector<int> sortArray(vector<int>& nums) {mergeSort(nums,0,nums.size()-1);return nums;}
};