912. 排序数组

难度中等98

给你一个整数数组 nums，请你将该数组升序排列。

示例 1：

1
2
输入：nums = [5,2,3,1]
输出：[1,2,3,5]

示例 2：

1
2
输入：nums = [5,1,1,2,0,0]
输出：[0,0,1,1,2,5]

排序算法复习题

归并排序

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
class Solution {
public:
    vector<int> temp;
    void mergeSort(vector<int>&nums,int l,int r){
        if(l>=r)return;//左指针偶遇右指针
        int mid=(l+r)>>1;

        mergeSort(nums,l,mid);
        mergeSort(nums,mid+1,r);

        // 现在l-mid mid+1-r是有序的
        //考虑合并的情况
        int i=l;
        int j=mid+1;
        int cnt=0;
        while(i<=mid&&j<=r){
            if(nums[i]<nums[j]){
                temp[cnt++]=nums[i++];
            }else{
                temp[cnt++]=nums[j++];
            }
        }
        while(i<=mid){
            temp[cnt++]=nums[i++];
        }
        while(j<=r){
            temp[cnt++]=nums[j++];
        }
        for (int i = 0; i < r - l + 1; ++i) nums[i + l] = temp[i];


    }
    vector<int> sortArray(vector<int>& nums) {
        temp.resize((int)nums.size(), 0);
        mergeSort(nums, 0, (int)nums.size() - 1);
        return nums;


    }
};

插入排序

1
2


快速排序

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
class Solution {
public:
    //快速排序,本质上是分治的一种思想; 需要注意的是通过随机化来避免对这个算法特定的攻击从而达到平均复杂度O(nlgn)这个trick
    int partition(vector<int>&nums,int l,int r){
        int pivot=nums[r];
        int i=l-1;
        for(int j=l;j<=r-1;++j){
            if(nums[j]<=pivot){
                i=i+1;//扩展比pivot小的边界;
                swap(nums[i],nums[j]);
            }
        }
        swap(nums[i+1],nums[r]);
        return i+1;
    }   
    int randomized_partiton(vector<int>&nums,int l,int r){
         int i = rand() % (r - l + 1) + l;
        cout<<i<<endl;
        swap(nums[r],nums[i]);//选择pivot然后存放到最右端;
        return partition(nums,l,r);
    }
    void quicksort(vector<int>&nums,int l,int r){
        if(l<r){
            int pos=randomized_partiton(nums,l,r);
            quicksort(nums,l,pos-1);
            quicksort(nums,pos+1,r);
        }
    }

    vector<int> sortArray(vector<int>& nums) {
        srand((unsigned)time(NULL));
        quicksort(nums,0,(int)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
44
45
46
47
class Solution {
public:
    
    void maxheapify(vector<int>&nums,int i,int len){//左子树和右子树ok,A[i]可能不ok,维护最大堆性质;这里与算导的主要区别是算导的数组是1-n;这里是0-len(n-1)
       for(;(i<<1)+1<=len;){       
            int lson=(i<<1)+1;
            int rson=(i<<1)+2;
            int largest;
            if(lson<=len&&nums[lson]>nums[i]){
                largest=lson;
            }else{
                largest=i;
            }
            if(rson<=len&&nums[rson]>nums[largest]){
                largest=rson;
            }
            if(i!=largest){
                int temp=nums[i];
                nums[i]=nums[largest];
                nums[largest]=temp;
                i=largest;
            }else{break;}
        }      
    }
    void buildmaxheap(vector<int>&nums,int len){
        for(int i=len/2;i>=0;--i){
            maxheapify(nums,i,len);
        }
    }
    void heapsort(vector<int>&nums){
        int len=(int)nums.size()-1;
        buildmaxheap(nums,len);
        for(int i=len;i>=1;--i){
            int temp=nums[0];
            nums[0]=nums[i];
            nums[i]=temp;
            len-=1;
            maxheapify(nums,0,len);
        }
    }
    vector<int> sortArray(vector<int>& nums) {
        heapsort(nums);
        return nums;


    }
};

//另外关于排序算法

线性时间但是有限制的有:

计数排序:统计每一个数组各个数的个数然后排序,要求被排序的数组都是0-k的整数;$\Theta(n+k)$

基数排序:对于所有的数,首先通过加0统一所有的数位,然后对每一个数位进行计数排序(此时k=10,这个时候是O(n)),从低到高,虽然这是线性的但是可能系数K很大！ radix sort

桶排序: