专栏首页Michael阿明学习之路LeetCode 912. 排序数组(10种排序)

LeetCode 912. 排序数组(10种排序)

1. 题目

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

示例 1:
输入:nums = [5,2,3,1]
输出:[1,2,3,5]

示例 2:
输入:nums = [5,1,1,2,0,0]
输出:[0,0,1,1,2,5]
 
提示:
1 <= nums.length <= 50000
-50000 <= nums[i] <= 50000

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/sort-an-array 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

2. 解题

基础的排序算法,写一遍复习一下。 参考我的博客: 10种C++排序算法 快速排序quicksort算法优化 快速排序quicksort算法细节优化(一次申请内存/无额外内存排序)

2.1 插入排序

class Solution {
public:
    vector<int> sortArray(vector<int>& arr) {
        if(arr.size() <= 1)
        	return arr;
        int i, j;
        for(i = 0; i < arr.size(); ++i)
        {
        	for(j = i; j > 0; --j)
        	{
        		if(arr[j-1] > arr[j])
        			swap(arr[j-1],arr[j]);
        		else
        			break;
        	}
        }
        return arr;
    }
};

9 / 10 个通过测试用例,超时

2.2 冒泡排序

class Solution {
public:
    vector<int> sortArray(vector<int>& arr) {
        if(arr.size() <= 1)
        	return arr;
        int i, j;
        bool arrSorted = false;
        for(i = 0; i < arr.size(); ++i)
        {
        	arrSorted = true;
        	for(j = 1; j <= arr.size()-1-i; ++j)
        	{
        		if(arr[j-1] > arr[j])
        		{
        			swap(arr[j-1],arr[j]);
        			arrSorted = false;
        		}
        	}
        	if(arrSorted)
        		break;
        }
        return arr;
    }
};

超时

2.3 选择排序

class Solution {	//选择
public:
    vector<int> sortArray(vector<int>& arr) {
        if(arr.size() <= 1)
        	return arr;
        int i, j, minIdx = 0;
        for(i = 0; i < arr.size()-1; ++i)
        {
        	minIdx = i;
        	for(j = i+1; j < arr.size(); ++j)
        	{
        		if(arr[minIdx] > arr[j])
        			minIdx = j;
        	}
        	swap(arr[i],arr[minIdx]);
        }
        return arr;
    }
};

超时

2.4 希尔排序

class Solution {	//希尔
public:
    vector<int> sortArray(vector<int>& arr) {
        if(arr.size() <= 1)
        	return arr;
        int i, j, gap = 1;
        for(gap = arr.size()/2; gap > 0; gap /= 2)
        {
	        for(i = gap; i < arr.size(); ++i)
	        {
	        	for(j = i; j-gap >= 0 && arr[j-gap]>arr[j]; j -= gap)
	        		swap(arr[j-gap],arr[j]);
	        }
	    }
        return arr;
    }
};

72 ms 15.8 MB

2.5 归并排序

class Solution {	//归并
	vector<int> temp;
public:
    vector<int> sortArray(vector<int>& arr) {
        if(arr.size() <= 1)
        	return arr;
        temp.resize(arr.size());
        mergeSort(arr,0, arr.size()-1);
        return arr;
    }

    void mergeSort(vector<int>& arr, int l, int r)
    {
    	if(l == r)
    		return;
    	int mid = l+((r-l)>>1);
    	mergeSort(arr,l,mid);
    	mergeSort(arr,mid+1,r);
    	merge(arr,l,mid,r);
    }

    void merge(vector<int>& arr, int l, int mid, int r)
    {
    	int i = l, j = mid+1, k = 0;
    	while(i <= mid && j <= r)
    	{
    		if(arr[i] <= arr[j])
    			temp[k++] = arr[i++];
    		else
    			temp[k++] = arr[j++];
    	}
    	while(i <= mid)
    		temp[k++] = arr[i++];
    	while(j <= r)
    		temp[k++] = arr[j++];
    	for(k = 0, i = l; i <= r; ++i,++k)
    		arr[i] = temp[k];
    }
};

52 ms 16 MB

2.6 快速排序

class Solution {	//快排
public:
    vector<int> sortArray(vector<int>& arr) {
        if(arr.size() <= 1)
        	return arr;
        qsort(arr,0, arr.size()-1);
        return arr;
    }

    void qsort(vector<int>& arr, int l, int r)
    {
    	if(l >= r)
    		return;
    	int Pl = l, Pr = l;
    	partition(arr,l,r,Pl,Pr);
    	qsort(arr,l,Pl-1);
    	qsort(arr,Pr+1,r);
    }

    void partition(vector<int>& arr, int l, int r, int& Pl, int& Pr)
    {	
    	selectMid(arr,l,r);
    	int P = arr[l];
    	int i = l, j = r;
    	while(i < j)
    	{
    		while(i < j && P < arr[j])//没有等于号,哨兵都在左侧
    			j--;
    		swap(arr[i], arr[j]);
    		while(i < j && arr[i] <= P)
    			i++;
    		swap(arr[i], arr[j]);
    	}
    	Pl = Pr = i;
    	for(i = i-1; i >= l; --i)//聚集左侧与哨兵相等的到中间
    	{
    		if(arr[i] == P)
    		{
    			Pl--;
    			swap(arr[i], arr[Pl]);
    		}
    	}
    }

    void selectMid(vector<int>& arr, int l, int r)
    {
    	int mid = l+((r-l)>>1);
    	if(arr[mid] > arr[r])
    		swap(arr[mid],arr[r]);
    	if(arr[l] > arr[r])
    		swap(arr[l], arr[r]);
    	if(arr[mid] > arr[l])
    		swap(arr[mid], arr[l]);
    }
};

52 ms 15.6 MB 96 ms 15.8 MB(删除聚集哨兵操作后的用时)

2.7 堆排序

class Solution {	//堆排序, 建堆(升序建大堆,降序建小堆)
public:
    vector<int> sortArray(vector<int>& arr) {
        if(arr.size() <= 1)
        	return arr;
        for(int i = arr.size()/2-1; i >= 0; --i)
    		adjust(arr,i,arr.size());//建堆
        for(int i = arr.size()-1; i >= 0; --i)
        {
        	swap(arr[i],arr[0]);
        	adjust(arr,0,i);
        }
        return arr;
    }

    void adjust(vector<int>& arr, int i, int len)
    {
    	int lchild = 2*i+1, rchild = 2*i+2, maxIdx = i;
    	while(lchild < len)
    	{
    		if(lchild < len && arr[lchild] > arr[maxIdx])
    			maxIdx = lchild;
    		if(rchild < len && arr[rchild] > arr[maxIdx])
    			maxIdx = rchild;
    		if(maxIdx != i)
    		{
    			swap(arr[i],arr[maxIdx]);
    			lchild = 2*maxIdx+1;
                rchild = lchild+1;
    			i = maxIdx;
    		}
            else
                break;
    	}
    }
};

72 ms 15.8 MB

2.8 计数排序

class Solution {	//计数排序
public:
    vector<int> sortArray(vector<int>& arr) {
        if(arr.size() <= 1)
        	return arr;
        int i, j = 0, min, max;
        min = max = arr[0];
        for(i = 1; i < arr.size(); ++i)
        {
        	min = arr[i] < min ? arr[i] : min;
        	max = arr[i] > max ? arr[i] : max;
        }
        const int N = max-min+1;
        vector<int> count(N,0);
        for(i = 0; i < arr.size(); ++i)
        	count[arr[i]-min]++;
        for(i = 0; i < N; ++i)
        {
        	while(count[i]--)
        		arr[j++] = i+min;
        }
        return arr;
    }
};

36 ms 16.1 MB

2.9 桶排序

  • 数据装桶,桶内快排
class Solution {	//桶排序
public:
    vector<int> sortArray(vector<int>& arr) {
        if(arr.size() <= 1)
            return arr;
        int i, j = 0, min, max;
        min = max = arr[0];
        for(i = 1; i < arr.size(); ++i)
        {
            min = arr[i] < min ? arr[i] : min;
            max = arr[i] > max ? arr[i] : max;
        }
        if(min == max)
            return arr;
        int div = 1000;//桶个数
        int space = (max-min)/div+1;
        vector<int> temp(arr.size());
        vector<int> bucketsize(div,0);
        vector<int> bucketPos(div,0);
        for(i = 0; i < arr.size(); ++i)
            bucketsize[(arr[i]-min)/space]++;
        bucketPos[0] = bucketsize[0];
        for(i = 1; i < div; ++i)
            bucketPos[i] += bucketPos[i-1] + bucketsize[i];//桶结束位置的下一个
        for(i = 0; i < arr.size(); ++i)
            temp[--bucketPos[(arr[i]-min)/space]] = arr[i];
        for(i = 0; i < div; ++i)
        {
            if(bucketsize[i] > 1)
            {
                qsort(temp,bucketPos[i],bucketPos[i]+bucketsize[i]-1);
            }
        }
        for(i = 0; i < arr.size(); ++i)
            arr[i] = temp[i];
        return arr;
    }

    void qsort(vector<int>& arr, int l, int r)
    {
        if(l >= r)
            return;
        int Pl = l, Pr = l;
        partition(arr,l,r,Pl,Pr);
        qsort(arr,l,Pl-1);
        qsort(arr,Pr+1,r);
    }

    void partition(vector<int>& arr, int l, int r, int& Pl, int& Pr)
    {
        selectMid(arr,l,r);
        int P = arr[l];
        int i = l, j = r;
        while(i < j)
        {
            while(i < j && P < arr[j])//没有等于号,哨兵都在左侧
                j--;
            swap(arr[i], arr[j]);
            while(i < j && arr[i] <= P)
                i++;
            swap(arr[i], arr[j]);
        }
        Pl = Pr = i;
        for(i = i-1; i >= l; --i)
        {
            if(arr[i] == P)
            {
                Pl--;
                swap(arr[i], arr[Pl]);
            }
        }
    }

    void selectMid(vector<int>& arr, int l, int r)
    {
        int mid = l+((r-l)>>1);
        if(arr[mid] > arr[r])
            swap(arr[mid],arr[r]);
        if(arr[l] > arr[r])
            swap(arr[l], arr[r]);
        if(arr[mid] > arr[l])
            swap(arr[mid], arr[l]);
    }
};

40 ms 16.3 MB

2.10 基数排序

  • 注意处理负数,被坑了,负数%后越界,window不报错尽然。。
class Solution {	//基数排序
	vector<int> temp;
public:
    vector<int> sortArray(vector<int>& arr) {
        if(arr.size() <= 1)
        	return arr;
        int i, max = INT_MIN;
        long exp;
        temp.resize(arr.size());
        for(i = 0; i < arr.size(); ++i)
        {
            arr[i] += 50000;//便于负数处理
            max = arr[i] > max ? arr[i] : max;
        }
        for(exp = 1; max/exp > 0; exp*=10)
        	radix_sort(arr,exp);

        for(i = 0; i < arr.size(); ++i)
            arr[i] -= 50000;//还原
        return arr;
    }
    void radix_sort(vector<int>& arr, long exp)
    {
	    vector<int> bucketsize(10,0);
        int i;
        for(i = 0; i < arr.size(); ++i)
        	bucketsize[(arr[i]/exp)%10]++;
        for(i = 1; i < 10; ++i)
        	bucketsize[i] += bucketsize[i-1];//桶最后一个位置+1
        for(i = arr.size()-1; i >= 0; --i)
        	temp[--bucketsize[(arr[i]/exp)%10]] = arr[i];
        for(i = 0; i < arr.size(); ++i)
        	arr[i] = temp[i];
	}
};

56 ms 16 MB

3. 复杂度表

图片参考 https://leetcode-cn.com/problems/sort-an-array/solution/shi-er-chong-pai-xu-suan-fa-bao-ni-man-yi-dai-gift/

r 为排序数字的范围,d 是数字总位数,k 是数字总个数

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LeetCode 1243. 数组变换

    首先,给你一个初始数组 arr。然后,每天你都要根据前一天的数组生成一个新的数组。

    Michael阿明
  • LeetCode 1502. 判断能否形成等差数列

    如果一个数列中,任意相邻两项的差总等于同一个常数,那么这个数列就称为 等差数列 。

    Michael阿明
  • LeetCode 1426. 数元素(哈希set)

    给你一个整数数组 arr, 对于元素 x ,只有当 x + 1 也在数组 arr 里时,才能记为 1 个数。

    Michael阿明
  • 快速排序

    用户6404053
  • 浙大版《C语言程序设计(第3版)》题目集 习题9-5 通讯录排序

    输入n个朋友的信息,包括姓名、生日、电话号码,本题要求编写程序,按照年龄从大到小的顺序依次输出通讯录。题目保证所有人的生日均不相同。

    C you again 的博客
  • JavaScript实现八大内部排序算法

    ? 注:基数排序中:r是关键字的基数,d是长度,n是关键字的个数 1.插入排序 基本思想:在序号i之前的元素(0到i-1)已经排好序,本趟需要找到i对应的元素...

    用户1149564
  • 快速排序

    参考:http://www.cnblogs.com/skywang12345/p/3596746.html  下面上代码: #include<iostream>...

    xcywt
  • PHP四种排序算法(选择排序)

    阿沐
  • PHP四种排序算法(插入排序)

    阿沐
  • 多图养眼!Partition,荷兰国旗问题与随机快排

    Partition的过程:给定一个数组arr,和一个整数num。把小于等于num的数放在数组的左边,大于num的数放在数组的右边。

    行百里er

扫码关注云+社区

领取腾讯云代金券