【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]);
            else
                i++;
        }
        _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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43