【Leetcode刷题篇】- 数组排序

100 阅读 0 评论 66 点赞

我是靠谱客的博主迅速铃铛，这篇文章主要介绍【Leetcode刷题篇】- 数组排序，现在分享给大家，希望可以做个参考。

给你一个整数数组 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：插入排序

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    // 插入排序
    public int[] sortArray(int[] nums) {
        for(int i=1;i<nums.length;i++){
            for(int j=i-1;j>=0&&nums[j]>nums[j+1];j--){
                // 交换
                swap(nums,j,j+1);
            }
        }
        return nums;
    }
    // 交换两数
    public void swap(int[] nums,int i,int j){
        int temp = nums[i];
        nums[i]  = nums[j];
        nums[j]  = temp;
    } 
}

解题思路：冒泡排序

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    // 冒泡排序-稳定排序
    public int[] sortArray(int[] nums) {
        for(int i=nums.length-1;i>=0;i--){
            for(int j=0;j<i;j++){
                if(nums[j]>nums[j+1]){
                    // 交换
                    swap(nums,j,j+1);
                }
            }
        }
        return nums;
    }

    public void swap(int[] nums,int i,int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

解题思路三、选择排序

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    // 选择排序
    public int[] sortArray(int[] nums) {
        for(int i=0;i<nums.length-1;i++){
            int minIndex = i;
            for(int j=i+1;j<nums.length;j++){
                minIndex = nums[minIndex]>nums[j]?j:minIndex;
            }
            swap(nums,i,minIndex);
        }
        return nums;
    }
    // 交换
    public void swap(int[] nums,int i,int j){
        int temp = nums[i];
        nums[i]  = nums[j];
        nums[j]  = temp;
    }
}

解题思路四：归并排序

复制代码

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
class Solution {
    // 归并排序
    public int[] sortArray(int[] nums) {
        mergeSort(nums,0,nums.length-1);
        return nums;
    }
    // 归并排序
    public void mergeSort(int[] nums,int l,int r){
        if(l>=r){
            return;
        }
        int mid = l + ((r-l)>>1);
        mergeSort(nums,l,mid);
        mergeSort(nums,mid+1,r);
        merge(nums,l,mid,r);
    }
    // 归并
    public void merge(int[] nums,int l,int mid,int r){
        // 归并
        int[] temp = new int[r-l+1];
        // 索引
        int index = 0;
        int p1 = l;
        int p2 = mid+1;
        // 继续走
        while(p1<=mid&&p2<=r){
            temp[index++] = nums[p1]<nums[p2]?nums[p1++]:nums[p2++];
        }
        while(p1<=mid){
            temp[index++] = nums[p1++];
        }
        while(p2<=r){
            temp[index++] = nums[p2++];
        }
        // 复制完
        for(int i=0;i<temp.length;i++){
            nums[l+i] = temp[i];
        }

    }
}

解题思路五、快速排序

复制代码

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
class Solution {
    // 快速排序
    public int[] sortArray(int[] nums) {
        quickSort(nums,0,nums.length-1);
        return nums;
    }
    public void quickSort(int[] nums,int l,int r){
        if(l<r){
            int[] arr = sort(nums,l,r);
            quickSort(nums,l,arr[0]-1);
            quickSort(nums,arr[1]+1,r);
        }
    }

    public int[] sort(int[] nums,int L,int R){
        int less = L-1;
        int more = R;
        while(L<more){
            if(nums[L]>nums[R]){
                swap(nums,L,--more);
            }else if(nums[L]<nums[R]){
                swap(nums,L++,++less);
            }else{
                L++;
            }
        }
        //最后交换
        swap(nums,more,R);
        return new int[]{less+1,more};
    }

    // 交换
    public void swap(int[] nums,int i,int j){
        int temp = nums[i];
        nums[i]  = nums[j];
        nums[j]  = temp;
    }
}

解题思路：堆排序

复制代码

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
class Solution {
    // 堆排序
    public void slipDown(int[] nums,int parentIndex,int length){
        while(2*parentIndex+1<length){
            int childIndex = 2*parentIndex+1;
            if(childIndex+1<length&&nums[childIndex+1]>nums[childIndex]){
                childIndex = childIndex+1;
            }
            if(nums[parentIndex]>nums[childIndex]){
                break;
            }
            swap(nums,parentIndex,childIndex);
            parentIndex = childIndex;
        }
    }

    public int[] sortArray(int[] nums) {
        for(int i=nums.length/2;i>=0;i--){
            slipDown(nums,i,nums.length);
        }
        for(int i=nums.length-1;i>=0;i--){
            swap(nums,0,i);
            slipDown(nums,0,i);
        }
        return nums;
    }

    public void swap(int[] nums,int i,int j){
        int temp = nums[i];
        nums[i]  = nums[j];
        nums[j]  = temp;
    }
}