leetcode解题之排序数组

143 阅读 0 评论 95 点赞

我是靠谱客的博主儒雅钢笔，这篇文章主要介绍leetcode解题之排序数组，现在分享给大家，希望可以做个参考。

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

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
示例 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
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

主要考察的是排序算法的基本功，这里只给出个人比较熟悉的算法，其他的请自行查找相关资料

复制代码

class Solution {
    public int[] sortArray(int[] nums) {
        //快速排序
        // quickSort(nums,0,nums.length-1);
        //选择排序
        // selectSort(nums);
        //冒泡
        bubbleSort(nums);
        return nums;
    }
    private void quickSort(int[] nums,int low,int high){
        if(low<high){
        int index = getIndex(nums,low,high);
        quickSort(nums,low,index-1);
        quickSort(nums,index+1,high);
        }   
    }
    private int getIndex(int[] nums,int low,int high){
        //左端作为基准
        int tem = nums[low];
        while(low<high){
            //队尾元素大于等于基准,队尾向前移动
            while(low<high&&nums[high]>=tem){
                high--;
            }
            //队尾元素小于基准，将队尾元素赋值给low
            nums[low] = nums[high];
            //队首元素小于等于基准，队首向后移动
            while(low<high&&nums[low]<=tem){
                low++;
            }
            //当队首元素大于基准，将其赋值给high
            nums[high] = nums[low];
        }
        nums[low] = tem;
        return low;
    }
    //选择排序
    private void selectSort(int[] nums){
        for(int i=0;i<nums.length-1;i++){
            int minValueIndex = i;
            for(int j=i;j<nums.length;j++){
                if(nums[j]<nums[minValueIndex]){
                    minValueIndex = j;
                }
            }
            //将最小的元素和i位置元素互换
            int tem = nums[i];
            nums[i] = nums[minValueIndex];
            nums[minValueIndex]=tem;
        }
    }
    //冒泡
    private void bubbleSort(int[] nums){
        int len = nums.length;
        for(int i=0;i<len-1;i++){
            for(int j=0;j<len-i-1;j++){
                if(nums[j]>nums[j+1]){
                    int tem = nums[j];
                    nums[j]=nums[j+1];
                    nums[j+1]=tem;
                }
            }
        }
    }
}

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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
class Solution {
    public int[] sortArray(int[] nums) {
        //快速排序
        // quickSort(nums,0,nums.length-1);
        //选择排序
        // selectSort(nums);
        //冒泡
        bubbleSort(nums);
        return nums;
    }
    private void quickSort(int[] nums,int low,int high){
        if(low<high){
        int index = getIndex(nums,low,high);
        quickSort(nums,low,index-1);
        quickSort(nums,index+1,high);
        }   
    }
    private int getIndex(int[] nums,int low,int high){
        //左端作为基准
        int tem = nums[low];
        while(low<high){
            //队尾元素大于等于基准,队尾向前移动
            while(low<high&&nums[high]>=tem){
                high--;
            }
            //队尾元素小于基准，将队尾元素赋值给low
            nums[low] = nums[high];
            //队首元素小于等于基准，队首向后移动
            while(low<high&&nums[low]<=tem){
                low++;
            }
            //当队首元素大于基准，将其赋值给high
            nums[high] = nums[low];
        }
        nums[low] = tem;
        return low;
    }
    //选择排序
    private void selectSort(int[] nums){
        for(int i=0;i<nums.length-1;i++){
            int minValueIndex = i;
            for(int j=i;j<nums.length;j++){
                if(nums[j]<nums[minValueIndex]){
                    minValueIndex = j;
                }
            }
            //将最小的元素和i位置元素互换
            int tem = nums[i];
            nums[i] = nums[minValueIndex];
            nums[minValueIndex]=tem;
        }
    }
    //冒泡
    private void bubbleSort(int[] nums){
        int len = nums.length;
        for(int i=0;i<len-1;i++){
            for(int j=0;j<len-i-1;j++){
                if(nums[j]>nums[j+1]){
                    int tem = nums[j];
                    nums[j]=nums[j+1];
                    nums[j+1]=tem;
                }
            }
        }
    }
}