azl397985856 commented 2 years ago

912. 排序数组

入选理由

暂无

题目地址

https://leetcode-cn.com/problems/sort-an-array/

前置知识

数组

排序

题目描述


给你一个整数数组 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

bzlff commented 2 years ago

class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        n = len(nums)

        def quick_sort(left, right):
            if left >= right:
                return nums
            privot = left
            i = left
            j = right

            while i < j:
                while i < j and nums[j] > nums[privot]:
                    j -= 1
                while i < j and nums[i] <= nums[privot]:
                    i += 1
                nums[i], nums[j] = nums[j], nums[i]

            nums[privot], nums[j] = nums[j], nums[privot]
            quick_sort(left, j - 1)
            quick_sort(j + 1, right)

            return nums

        return quick_sort(0, n - 1)

maggiexie00 commented 2 years ago

def sortArray(self, nums):
    if len(nums)<=1:
        return nums
    mid=len(nums)//2
    left=self.sortArray(nums[:mid])
    right=self.sortArray(nums[mid:])
    return self.merge(left,right)
def merge(self,left,right):
    i,j=0,0
    res=[]
    while i<len(left) and j<len(right):
        if left[i]<=right[j]:
            res.append(left[i])
            i+=1
        else:
            res.append(right[j])
            j+=1
    res+=left[i:]
    res+=right[j:]
    return res

xiayuhui231 commented 2 years ago

题目

排序数组 https://leetcode-cn.com/problems/sort-an-array/comments/

思路

试了很多次，常规的排序算法会超时，所以选用了希尔排序

代码

class Solution {
public:

    vector<int> sortArray(vector<int>& nums) {
        Shell_Sort(nums);
        return nums;

    }
        void Shell_Sort(vector<int>& nums){
        int n = nums.size();
        int i,j,gap;
        for(gap = n/2;gap>0;gap /=2){
            for(i=0;i<gap;i++){
                for(j=i+gap;j<n;j+=gap){
                    if(nums[j] < nums[j-gap]){
                        int tmp = nums[j];
                        int k = j-gap;
                        while(k >= 0 && nums[k] > tmp){
                            nums[k+gap] = nums[k];
                            k -= gap;
                        }
                        nums[k+gap] = tmp;
                    }
                }
            }
        }
    }
};

复杂度

时间复杂度:O(nlogn) 空间复杂度:O(1)

tensorstart commented 2 years ago

思路

快排

代码

var sortArray = function(nums) {
    let sort=function (nums, lo, hi) {
        if (lo >= hi) {
            return;
        }
        // 对 nums[lo..hi] 进行切分
        // 使得 nums[lo..p-1] <= nums[p] < nums[p+1..hi]
        let p = partition(nums, lo, hi);

        sort(nums, lo, p - 1);
        sort(nums, p + 1, hi);
    }
    // 对 nums[lo..hi] 进行切分
    let partition=function (nums, lo, hi) {
        let pivot = nums[lo];
        // 之后都要正确维护这个边界区间的定义
        let i = lo + 1, j = hi;
        // 当 i > j 时结束循环，以保证区间 [lo, hi] 都被覆盖
        while (i < j) {
            while (i < j && nums[i] <= pivot) {
                i++;
                // 此 while 结束时恰好 nums[i] > pivot
            }
            while (i < j && nums[j] >= pivot) {
                j--;
                // 此 while 结束时恰好 nums[j] <= pivot
            }
            // 此时 [lo, i) <= pivot && (j, hi] >= pivot
            swap(nums, i, j);
        }
        // 将 pivot 放到合适的位置，即 pivot 左边元素较小，右边元素较大
        //因为一开始将nums[lo]赋值给了pivot
        swap(nums, lo, l);
        return l;
    }

    // 原地交换数组中的两个元素
    let swap=function (nums, i, j) {
        let temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
    // 排序整个数组（原地修改）
    sort(nums, 0, nums.length - 1);
    return nums;
};
## 复杂度分析
时间O(nlogn)
空间O(logn)

houyanlu commented 2 years ago

思路

使用的是快排，轴值需要随机选取，不然TLE

代码


class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        quickSort(nums, 0, nums.size() - 1);
        return nums;
    }

    // 以首元素为轴值, 会超时
    int partition(vector<int>& nums, int first, int end) {
        int i = first;
        int j = end;
        swap(nums[i], nums[i + rand() % (j - i)]); //随机选取一个作为轴值

        while (i < j) {
            while (i < j && nums[j] >=nums[i]) {
                j--;
            }

            if (i < j) {
                swap(nums[i], nums[j]);
                i++;
            }

            while (i < j && nums[i] <= nums[j]) {
                i++;
            }

            if (i < j) {
                swap(nums[i], nums[j]);
                j--;
            }
        }

        return i;
    }

    void quickSort(vector<int>& nums, int first, int end) {
        if (first >= end) {
            return;
        }

        int pos = partition(nums, first, end);
        quickSort(nums, first,   pos - 1);
        quickSort(nums, pos + 1, end);
    }
};

复杂度分析

时间复杂度：O(nlogn)
空间复杂度：O(logn) 取决于递归树的深度

maybetoffee commented 2 years ago

class Solution {
    //merge sort
    public int[] sortArray(int[] nums) {
        int[] temp = new int[nums.length];
        mergeSort(nums, 0, nums.length-1, temp);
        return nums;
    }

    private void mergeSort(int[] nums, int start, int end, int[] temp){
        if(start >= end){
            return;
        }

        int mid = (start + end)/2;
        mergeSort(nums, start, mid, temp);
        mergeSort(nums, mid+1, end, temp);

        merge(nums, start, end, temp);
    }

    private void merge(int[] nums, int start, int end, int[] temp){
        int mid = (start + end)/2;
        int left = start, right = mid+1;
        int i = left;

        while(left <= mid && right <=end){
            if(nums[left] <= nums[right]){
                temp[i++] = nums[left++];
            }else{
                temp[i++] = nums[right++];
            }
        }

        while(left <= mid){//now right part is already in temp
            temp[i++] = nums[left++];
        }
        while(right <= end){//now left part is already in temp
            temp[i++] = nums[right++];
        }

        for(int index = start; index<= end; index++){
            nums[index] = temp[index];
        }
    }
}

Yongxi-Zhou commented 2 years ago

思路

快排，要随机选指针

代码

        class Solution:
        def sortArray(self, nums: List[int]) -> List[int]:
            self.helper(nums, 0, len(nums) - 1)
            return nums

        def helper(self, nums, start, end):
            if start >= end:
                return 
            pivot = self.partition(nums, start, end)
            self.helper(nums, start, pivot - 1)
            self.helper(nums, pivot + 1, end)

        def partition(self, nums, start, end):
            idx = random.randint(start, end)
            # idx = end
            nums[idx], nums[end] = nums[end], nums[idx]
            pivot = nums[end]
            wall = start
            for i in range(start, end + 1):
                if nums[i] < pivot:
                    nums[wall], nums[i] = nums[i], nums[wall]
                    wall += 1
            nums[end], nums[wall] = nums[wall], nums[end]
            return wall

复杂度

time O(NlogN) space O(logN，递归树深度)

duantao74520 commented 2 years ago

思路：归并排序：代码： class Solution { public: void swap(vector& nums, int i, int j) { int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; } void MergeSort(vector& nums, int left, int right) { if (left >= right) return; // 只有一个的时候返回 int mid = (left+right)/2; MergeSort(nums, left, mid); MergeSort(nums, mid+1, right); // 合并两个数组，也就是将left到right的数组排序 int i = left, j = mid+1; vector temp; while(i <= mid && j <= right) { if (nums[i] <= nums[j]) { temp.emplace_back(nums[i]); i++; } else { temp.emplace_back(nums[j]); j++; } } while(i <= mid ) { temp.emplace_back(nums[i]); i++; } while(j <= right) { temp.emplace_back(nums[j]); j++; } for (i = left ; i <= right ; i++) { nums[i] = temp[i-left]; } } vector sortArray(vector& nums) { // 官方sort //std::sort(nums.begin(), nums.end()); // 冒泡排序

     // 快排
    // 归并排序
    /*核心思想:
        递归，把数组一分为二，然后再合并两个有序列表，使得合并后的数组也是有序的。
    */
    MergeSort(nums, 0, nums.size()-1);
     return nums;

}

}; 复杂度： onLog(n)

zzz607 commented 2 years ago

思路

归并排序，计数排序

代码

func sortArray(nums []int) []int {
    // return countSort(nums)
    return mergeSort(nums)
}

func mergeSort(nums []int) []int {
    var merge func(src, help []int, li, mi, hi int) 
    merge = func(src, help []int, li, mi, hi int) {
        for i, p, q := li, li, mi + 1; i <= hi; i++ {
            if p > mi {
                help[i] = src[q]
                q++
            } else if q > hi {
                help[i] = src[p]
                p++
            } else {
                if src[p] <= src[q] {
                    help[i] =  src[p]
                    p++
                } else {
                    help[i] = src[q]
                    q++
                }
            }
        }

        for i := li; i <= hi; i++ {
            src[i] = help[i]
        }
    }

    var sort func(src, help []int, li, hi int)
    sort = func(src, help []int, li, hi int) {
        if li == hi { return }
        mi := (li + hi) / 2
        sort(src, help, li, mi)
        sort(src, help, mi + 1, hi)
        merge(src, help, li, mi, hi)
    }

    help := make([]int, len(nums))
    sort(nums, help, 0, len(nums) - 1)

    return nums
}

func countSort(nums []int) []int {
    offset := 50000
    cache := make([]int, 100001)
    for _, d := range nums {
        cache[d + offset]++
    }

    numsIdx := 0
    for idx, count := range cache {
        if count == 0 {
            continue
        }

        val := idx - offset
        for i := 0; i < count; i++ {
            nums[numsIdx] = val
            numsIdx++
        }
    }

    return nums
}

复杂度分析
归并排序

时间复杂度：O(NlogN)
空间复杂度：O(N)

计数排序

时间复杂度：O(N)，虽然有一个嵌套的循环，但是若数组不重复，则里面的循环只执行一次；若每个元素重复k次，则总循环次数应该是(N/K)*K，还是O(N)
空间复杂度：O(1)，虽然空间是固定的，但是是最大值

1973719588 commented 2 years ago

# 快速排序
import random
class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        def partition(nums, left, right):
            flag = random.randint(left, right)
            pixov = nums[flag]

            nums[left], nums[flag] = nums[flag], nums[left]

            while left < right:
                while left < right and nums[right] >= pixov:
                    right -= 1
                nums[left] = nums[right]
                while left < right and nums[left] <= pixov:
                    left += 1
                nums[right] = nums[left]

            nums[left] = pixov

            return left

        def quickpai(nums, left, right):
            #不要忘记下面两句代码，就算return的是空，也得需要return的
            if left >= right:
                return
            mid = partition(nums, left, right)
            quickpai(nums, left, mid-1)
            quickpai(nums, mid+1, right)

        quickpai(nums, 0, len(nums)-1)

        return nums

时间复杂度：O(logN) 空间复杂度：O(logN)

currybeefer commented 2 years ago

归并排序：

    vector<int> sortArray(vector<int>& nums) 
    {
        return MergeSort(nums);
    }
    vector<int> MergeSort(vector<int>& array)
    {
        if(array.size()<=1)
            return array;

        int mid=array.size()/2;
        vector<int> left;
        vector<int> right;
        for(int i=0;i<mid;i++)
            left.push_back(array[i]);
        for(int i=mid;i<array.size();i++)
            right.push_back(array[i]);

        left.assign(MergeSort(left).begin(),MergeSort(left).end());
        right.assign(MergeSort(right).begin(),MergeSort(right).end());

        return Merge(left,right);
    }
    vector<int> Merge(vector<int>& left, vector<int>& right)
    {
        vector<int> temp;
        int pl=0;
        int pr=0;
        while(pl<left.size() && pr<right.size())
        {
            if(left[pl]<right[pr])
                temp.push_back(left[pl]);
            else 
                temp.push_back(right[pr]);

            pl++;
            pr++;
        }
        if(pl<left.size())
        {
            for(pl;pl<left.size();pl++)
            {
                temp.push_back(left[pl]);
            }
        }
        if(pr<right.size())
        {
            for(pr;pr<right.size();pr++)
            {
                temp.push_back(right[pr]);
            }
        }
        return temp;
    }

时间复杂度：O(nlogn) 空间复杂度：O(n)

leetcode-pp / 91alg-7-daily-check

【Day 36 】2022-05-06 - 912. 排序数组 #39

912. 排序数组

入选理由

题目地址

前置知识

题目描述

题目

思路

代码

复杂度

思路

代码

思路

代码

思路

代码

复杂度

思路

代码