【剑斩OFFER】算法的暴力美学——排序数组

一、题目描述

二、算法原理

本题使用快排和归并排序都能解决这道题目，这里使用的归并排序，归并排序的思想和快排的思想都是进行分治的思想，对于归并排序的实现和思路，请各位看这篇博客：https://blog.csdn.net/2403_84958571/article/details/147355114?fromshare=blogdetail&sharetype=blogdetail&sharerId=147355114&sharerefer=PC&sharesource=2403_84958571&sharefrom=from_link

这篇博客超级详细的，这里就不再赘述了。

三、代码实现

class Solution { public: vector<int> sortArray(vector<int>& nums) { vector<int> tmp(nums.size());//创建一数组，防止后面操作干扰到原数组 nums Quicksort(0,nums.size() - 1,nums,tmp); return nums; } void Quicksort(int l,int r,vector<int>& nums,vector<int>& tmp) { if(l >= r) return; int keyi = l + (r - l) / 2; Quicksort(l,keyi,nums,tmp);//左边：【 l , keyi 】 Quicksort(keyi + 1,r,nums,tmp);//右边：【keyi + 1,r 】 int begin1 = l,end1 = keyi;//左边数组 int begin2 = keyi + 1,end2 = r;//右边数组 int index = l;//遍历起始点 while(begin1 <= end1 && begin2 <= end2)//比较遍历 { if(nums[begin1] > nums[begin2]) tmp[index++] = nums[begin2++]; else tmp[index++] = nums[begin1++]; } while(begin1 <= end1) tmp[index++] = nums[begin1++];//把左边剩余的数字放到 tmp while(begin2 <= end2) tmp[index++] = nums[begin2++];//把右边剩余的数字放到 tmp for(int i = l;i < index;i++) nums[i] = tmp[i];//把 tmp 里面的数字放回到原数组 nums } };