落风的风
0%

排序算法java实现

Posted on Edited on In

用java实现归并排序、快速排序、冒泡排序、插入排序、堆排序。主要就是为了准备面试手撕排序代码

1 经典的基础的排序算法

[1]参考了《大话数据结构》的部分代码思想
[2] 本人原创、保留权利

经典的归并、快排、堆排序，基础的冒泡、插入、希尔、选择

可以拿力扣 912. 排序数组 来练手

1、归并排序

归并排序 MergeSort 就是利用 归并 的思想实现的排序方法。

假设初始序列含有n 个记录，则可以看成是n 个有序（内部有序）的子序列，每个子序列的长度为 1 , 然后两两归并，得到[n /2] ([x ]表示不小于x 的最小整数）个长度为2 或 1 的有序子序列；再两两归并，……，如此重复，直至得到一个长度为n 的有序序列为止。

1.1 递归实现

需要两个函数：一个函数mergeSort用来递归，将原数组平分为两个部分、分别递归调用生成有序数列；一个函数merge合并两个有序子数列，主要采用两个指针轮流后移的方法。

  • mergeSort实现递归调用

    • 递归的出口是最后一次递归的子数列长度为1 即 left == right
    • 每次循环递归两次、左半一次 右半一次

  • merge实现合并两有序子数列

    • 输入数组、输出数组、左索引、中间索引、右索引
    • 使用指针移动来实现

递归实现代码如下：

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
class Solution {
    public int[] sortArray(int[] nums) {
        //再来一个归并排序
        mergeSort(nums,0,nums.length-1);
        return nums;
    }
    private void mergeSort(int[] nums,int left,int right){
        if(left>=right) return; //子序列长度为1时跳出
        int mid = left + (right-left)/2;
        mergeSort(nums,left,mid);
        mergeSort(nums,mid+1,right);
        merge(nums,left,mid,right);
    }
    private void merge(int[] nums, int left,int mid, int right){
        //临时数组长度为left-right的元素个数就可以！
        int[] temp = new int[right-left+1];
        int k=0;
        int i = left;
        int j = mid+1;
        while(i<=mid &&j<=right){
            if(nums[i]<=nums[j]){
                temp[k++]=nums[i++];
            }else{
                temp[k++] =nums[j++];
            }
        }
        while(i<=mid) temp[k++] = nums[i++];
        while(j<=right) temp[k++] = nums[j++];
        for(int m=left;m<=right;m++){
            nums[m] = temp[m-left];
        }
    }
}

1.3 迭代实现

非递归的迭代做法更加直截了当，从最小的序列开始归并直至完成。即从最开始两两归并长度为1的子列、再两两归并长度为2的子列、再4、再8再、、、直接顺着一遍来就好了。需要两个函数MergePass、Merge和一个主函数MergeSort。

  • 一个是MergePass：
    • 用来将SR[]中相邻长度为s的子序列两两归并到TR[]
  • 一个是Merge实现合并两有序子数列
    • 输入数组、输出数组、左索引、中间索引、右索引
    • 使用指针推移实现
  • 主函数MergeSort实现迭代调用MergePass。
    • 一个while循环、k以两倍的速度增长
    • 每次循环都调用MergePass，参数数组要变换位置

迭代实现代码如下：

1
//我还不会....

2、快速排序

通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到使整个序列有序的目的。

我的解释是，通过一个简单高效的交换将待排序数组二分为两个（一个的所有数小于另一个的所有数），然后再分别排那两个二分的数组（当然分别排也是用这样的策略继续二分继续排）、

所以我们需要两个函数、一个是递归调用的，排数组就要排它的两个分开好了的子数组，一层层递归调用该函数；一个是如何将一个数组分成两个、一个数组的所有数小于另一个数组的所有数，通过指定一个枢纽，然后替换整理，将比枢纽小的数放在枢纽之前，比枢纽大的数放在枢纽之后。

2.1 递归实现

  • quickSort函数、递归调用。
  • findIndex函数 找到枢纽值合适的下标索引，并整理好数组。
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) {
        quickSort(nums,0,nums.length-1);
        return nums;
    }

    private void quickSort(int[] nums, int left,int right){
        if(left>=right) return;
        int mid = findIndex(nums,left,right);
        //分别排左边和右边的元素
        quickSort(nums,left,mid-1);
        quickSort(nums,mid+1,right);
    }

    //写一个子函数整理好数组，并且将小于基准的放于基准之前，将大于基准的放于基准之后，返回基准的位置
    private int findIndex(int[] nums, int left, int right){
        
        //随机选择一个作为基准
        int rand = new Random().nextInt(right-left+1)+left;
        swap(nums,rand,right);//交换到最后去

        int i = left;//标识基准应该在的位置
        int flag = nums[right]; //最后一个值作为基准
        //遍历 判断元素与flag的大小并移动元素
        for(int j=left;j<right;j++){
            if(nums[j]<=flag){
                //比flag小||==，移动到i的位置来
                if(i!=j) swap(nums,i,j);
                i++;
            }
        }
        //最后要将flag移动到i位置上来
        swap(nums,i,right);
        return i;
    }

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

3、堆排序

堆是具有下列性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的 值，称为大顶堆；或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。堆排序（Heap Sort ) 就是利用堆（假设利用大顶堆）进行排序的方法。

基本思想是，将待排序的序列构造成一个大顶堆。此时，整个序列的最大值就是堆顶的根结点。将它移走（其实就是将其与堆数组的末尾元素交换，此时末尾元素就是最大值），然后将剩余的n - 1 个序列重新构造成一个堆，这样就会得到n 个元素中的次大值。如此反复执行，便能得到一个有序序列了。

3.1 堆排序的性能

堆排序的时间复杂度为O(nlogn)。由于堆排序对原始记录的排序 状态并不敏感，因此它无论是最好、最坏和平均时间复杂度均为O(nlogn)。

空间复杂度上，它只有一个用来交换的暂存单元，也非常的不错。不过由于记录 的比较与交换是跳跃式进行，因此堆排序也是一种不稳定的排序方法。

由于初始构建堆所需的比较次数较多，因此，它并不适合待排序序列个数 较少的情况

3.2 代码实现

主要要做的两个工作：1、将一个无序序列构成一个堆；2、在交换堆顶元素之后，如何调整剩余元素成为一个堆。（交换堆顶元素：每次将最大、次大的放到数组的n-1、n-2位置上，所以最后数组就有序了）

  • 构建大顶堆
    • 用到一个for循环，循环每个有子节点的结点，即从i=length/2;i>0;i--
    • 每次循环调用heapAdjust(nums,i,length)，，每一次循环都将当前结点子树的最大值交换到这个结点上来了！！
  • 调整剩余元素成为一个堆
    • heapAdjust函数！！一个循环，循环从当前结点的左子节点开始，每次递增二，，讲不太清楚、这个函数最关键。

代码实现：

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
class Solution {
    public int[] sortArray(int[] nums) {
        //来装逼写一下 堆排序
        heapSort(nums);
        return nums;
    }

    private void heapSort(int[] nums){
        //1 遍历调用adjustHeap，形成大顶堆
        //从最后一个非叶子节点 向左向上 遍历每个非叶子节点 （最后一个非叶子节点的索引是len/2-1）
        //每次调整当前i节点下为大顶堆，最终使整个数成为大顶堆
        for(int i=nums.length/2-1;i>=0;i--){
            //调用adjustHeap函数 参数：i指当前节点的索引，后面指节点能处于最大索引（这里是整棵树）
            adjustHeap(nums,i,nums.length-1);
        }

        //2 遍历并交换元素，并调整大顶堆
        for(int end = nums.length-1;end>=0;end--){
            //堆顶交换到待排序数组的最后一个位置
            swap(nums,0,end);
            //重新对堆进行调整,注意此时待排序数组的长度-1了！！
            adjustHeap(nums,0,end-1); //end-1是可达的最后一个索引位置
        }

    }
    /**
     * 调整大顶堆（仅是调整过程，建立在大顶堆已构建的基础上）
     * @param nums 数组
     * @param i  表示当前节点的位置，要调整当前节点下的子堆成为大顶堆
     * @param end 待排序数组最后一个可达的索引位置
     */
    private void adjustHeap(int[] nums, int i, int end){
        int temp = nums[i]; //先记录当前节点的值
        //向下一层循环遍历，每次找左右子节点中的较大的那个与当前节点i的值比较
        for(int k = 2*i+1;k<=end;k = 2*k+1){
            if(k+1<=end&&nums[k]<nums[k+1]) k = k+1; //如果右节点大，就指向右节点
            if(nums[k]>temp){
                //如果左右子节点比temp大，那就将大值赋值到父节点i上面，并记录最后temp应该去的位置
                nums[i] = nums[k];
                i = k;//记录最后temp应该去的位置
            }else{
                break; //如果子节点小于等于父节点，即该节点本身就满足大顶堆条件，直接跳出
            }
        }
        nums[i] = temp; //将temp放到它应该在的地方
    }

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

4、冒泡排序

一个位置进行一次遍历，每次遍历从后往前，交换相邻两元素，将最小的值放到该位置.

1
2
3
4
5
for(int i=1;i<length;i++){
    for(int j=length-1; j>=i; j--){
    	if n(j)<n(j-1) 就交换位置;
    }
}

优化后的冒泡排序

  • 为了避免已经有序的数列重复循环比较、引入一个标记变量flag,如果有数据交换置为true，为真才进行下一次循环。如果flag仍为false表示i位置之后是有序的，外层循环就不必继续了，此时的数组就是最终的结果

  • 复杂度分析

    • 最坏的情况是O(n2)，挺低效的。

4.1 代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
package com.leetcode.sort;

public class BubbleSort {
    public static void main(String[] args){
        int[] nums=new int[]{5,4,8,1,3,9,7,2};
        BubbleSort(nums);
        for(int i:nums) System.out.println(i);
    }
    public static void BubbleSort(int[] nums){
        boolean flag = true;
        for(int i=1;i<nums.length&&flag;++i){
            flag =false;
            for(int j=nums.length-1;j>=i;--j){
                if(nums[j]<nums[j-1]){
                    int temp = nums[j];
                    nums[j]=nums[j-1];
                    nums[j-1] = temp;
                    flag = true;
                }
            }
        }
    }

}

5、插入排序

直接插入排序的基本操作是将一个记录插入到已经排 好序的有序表中，从而得到一个新的、记录数增1 的有序表。

需要一个多余的辅助空间、如果要把最后面的元素移到前面来，每一个元素都要挪一次位置。

平均比较和移动的次数为n^2/4。时间复杂度也是O(n2)。但比冒泡排序和简单选择排序性能好一点。

5.1 代码实现

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
package com.leetcode.sort;

public class InsertSort {
    public static void main(String[] args){
        int[] nums=new int[]{5,4,8,1,3,9,7,2};
        InsertSort(nums);
        for(int i:nums) System.out.println(i);
    }
    private static void InsertSort(int[] nums){
        for(int i=1;i<nums.length;++i){
            //判断如果当前元素较小 就标记为mask
            if(nums[i]<nums[i-1]) {
                int mask = nums[i];
                int j;
                nums[i]=nums[i-1];
                //将大于mask的元素都后移一格，将mask插入到合适的位置
                for (j = i - 2; j >= 0 && mask < nums[j]; j--) {
                    nums[j + 1] = nums[j];
                }
                nums[j + 1] = mask;
            }

        }
    }

}

2 排序算法的性能和稳定性分析

2.1 排序算法的时间复杂度

这个结论三岁蒙童都应该知道吧，经典排序O(NlogN)，基础排序O(N^2)。但是为什么呢？要分析分析

对于冒泡、插入和选择，他们的最坏和平均时间复杂度都是O(N^2)，因为都是双重循环，这点没什么疑问。特别的对于插入排序和冒泡排序（含flag标识），如果数组本身就是有序的，那么最好的时间复杂度是O(N)，因为只用搜索一次，根本就不需要插入或者交换。

所以主要看三个经典排序：归并、快排、堆排序的时间复杂度

1 归并排序：

一共只需要归并O(logN)次，每次归并需要比较N次，所以时间复杂度是O(NlogN)。归并排序的最好、最坏、平均的时间复杂度都是O(NlogN)。归并时需要用到一个临时数组，因此认为需要O(N)的辅助空间。

2 堆排序：

初始建堆的时间复杂度是O(N)，每次调整堆的时间复杂度是O(logN)，共需要调整N次，所以时间复杂度是O(NlogN)。同样堆排序的最好、最差、平均时间复杂度也都是O(NlogN)。堆排序不需要递归，除去堆本身占用的空间、只使用一个交换单元，空间复杂度是O(1)。

3 快速排序：

快排的时间复杂度可以这么理解：

  • 最优的情况下，每次取得的基准都能平分两个数组，这样跟归并排序一样、一共需要O(logN)次递归。然后每次递归，整理数组将比基准小的元素放到基准之前的复杂度是O(N)…所以最优的时间复杂度是O(NlogN)
  • 最坏的情况下，每次取得的基准取到最大（小）的数，每次都只排好了一个元素。这样就需要O(N)次递归，所以相应的时间复杂度就是O(N^2)….这样的情况肯定是不多的，但是在数组本身是有序的情况下，每次取基准时就会出现这样的情况！！
  • 平均时间复杂度还是O(NlogN)的。平均空间复杂度递归栈的大小O(logN)

2.2 排序算法的稳定性

“假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。“ [百度百科]

稳定性，简单的来讲就是相同的元素，在排序前后，其相对位置是一致的！！本来在前的排完序之后依然在前面

1 冒泡排序（稳定）
每次比较相邻的两个元素，把较小的移到前面去，如果两元素相等肯定不会傻到多交换一次。所以是稳定的。

2 插入排序（稳定）

每次先比较当前元素与前一个元素的大小，只有当前元素小于前一个元素，才会将当前元素插入到前面那个已经排好序的序列中，元素相同，先插入的元素还是在前面。所以也是稳定的。（因为根本就没有交换的过程，只有插入、根本不可能乱序）

3 选择排序（不稳定）

选择排序，每次从当前位置向后遍历无序的部分，将无序部分最小的那个元素交换到当前位置上来。交换的过程可能将前面的元素交换到了较后的位置。举个栗子：序列4 6 4 2 5，第一次交换将第一个4与2交换了，改变了两个4之前的相对位置。因此是不稳定的！！

4 快速排序（不稳定）

快排典型的不稳定，快排之所以不稳定的原因，在于最后移动基准的时候，将基准移到了和基准相同的元素的前面（导致顺序发生了变化）。举个例子：1 2 6 7 8 5 9 5，选择最后一个5作为基准的话，一趟排序之后，会将6与基准5的位置交换，也就改变了两个5之前的先后关系。

5 堆排序（不稳定）

可以这么说，1 最初从数组创建堆的过程，原始序列中项目顺序的信息可能就丢失了。2另外，在调整堆的过程中，数据的先后顺序也极有可能出现改变。因此堆排序是不稳定的。

举个栗子：{2a，2b，2b}三个2的数组这里用abc标识最初的顺序。建堆的过程中已经有序不调整，然后我们会将2a移动到数组末尾（作为最大的元素）…显然这时数据的先后关系已经改变了。

在举一个栗子：原始序列：{1、5、2a，3、2b，6、2c}；建堆之后的序列：{1、2b，2a，3、5、6、2c}；堆排序之后的序列：{1、2c，2b，2a，3、5、6}….显而易见，顺序改变了。

6 归并排序（稳定）

归并排序只需要考虑两两归并的过程中，顺序有没有可能改变。显然两个本来子序列，只要归并出现相对的元素时，先选择前一个子序列的元素，就可以保证相同元素的顺序不变！！因此归并排序是稳定的。（换句话说，只要没有交换，就一定是稳定的…..我暂时这么理解、不知道对不对）

2.3 排序算法的选择

这里没有看到讲的特别好的博客，自己随便扯一扯

1 对于小数据量或者基本有序的数据，可以使用插入排序或者冒泡排序，（千万别快排）

2 对于排序稳定性有要求、并且对空间没有限制的情况，用归并排序，归并排序稳定，但需要额外的O(n)空间

3 对于稳定性无要求，并且数据没有基本有序的情况，可以使用快排

4 对于数据量特别大的情况可以使用堆排序，堆排序对数据的是否有序不敏感，并且不用递归、除去堆以外无需要多余的空间。

3 排序的变种力扣题

剑指 Offer 51. 数组中的逆序对

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。

示例 1:

输入: [7,5,6,4]
输出: 5

思路：利用归并排序！！

  • 两两归并的时候我们可以很方便的计算逆序对的个数，
  • 前后两个子序列，如果选择的是前一个子序列的元素，那么就无逆序对（因为前面的>后面的）
  • 如果后面子序列的元素的大，说明该元素大于前面序列的i到mid的所有元素，所以逆序对的个数count += (mid-i+1)

代码：建一个全局count就好了….

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
class Solution {
    int count = 0;
    public int reversePairs(int[] nums) {
        //不管怎么说 反正要先写一个归并排序
        mergeSort(nums,0,nums.length-1);
        return count;
    }

    private void mergeSort(int[] nums, int left, int right){
        if(left>=right) return;
        int mid = left + (right-left)/2;
        mergeSort(nums,left,mid);
        mergeSort(nums,mid+1,right);
        merge(nums,left,mid,right);
    }
    private void merge(int[] nums, int left, int mid, int right){
        int[] temp = new int[right-left+1];
        int k = 0; //临时数组索引
        int i= left;
        int j = mid+1;
        while(i<=mid&&j<=right){
            if(nums[i]<=nums[j]){
                temp[k++] = nums[i++];
            }else{
                count += (mid-i+1); //这里加上count就ok
                temp[k++] = nums[j++];
            }
        }
        while(i<=mid) temp[k++] = nums[i++];
        while(j<=right) temp[k++] = nums[j++];
        for(int m = left;m<=right;m++){
            nums[m] = temp[m-left];
        }
    }
}

215. 数组中的第K个最大元素

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

例：输入: [3,2,1,5,6,4] 和 k = 2 输出: 5

解法一：快速排序！！

思路：

  • 要找k大的数，就是要找n-k+1小的数，就是找n-k索引的数

  • 快速排序，直到基准的索引等于n-k为止。索引小于基准、排基准左边的数；索引大于基准、排基准右边的数

代码：只需要改动quickSort中的内容，加上返回值！

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
class Solution {
    public int findKthLargest(int[] nums, int k) {
        //要找k大的数，就是要找n-k+1小的数，就是找n-k索引的数
        //快速排序，直到基准的索引等于n-k为止
        int n = nums.length; 
        return quickSort(nums,0,n-1,n-k);
    }
    private int quickSort(int[] nums, int left, int right,int k2){
        if(left>=right) return nums[left];
        int index = findIndex(nums,left, right);
        //再分别排左右两边的数组
        if(k2==index) return nums[index];
        return k2<index? quickSort(nums,left,index-1,k2): quickSort(nums,index+1,right,k2);
    }
    private int findIndex(int[] nums, int left, int right){
        //随机选一个数放到最后
        int rand = new Random().nextInt(right-left+1)+left;
        swap(nums,rand,right);
        
        int falg = nums[right];//选择基准
        int i = left; //基准应该处于的位置
        for(int j=left;j<right;j++){
            if(nums[j]<falg){
                if(i!=j) swap(nums,i,j);
                i++;
            }
        }
        swap(nums,i,right);
        return i;
    }
    private void swap(int[] nums,int i, int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

解法二：堆排序（最小堆）

思路：

  • 用优先队列的思路也很清晰，要找第k大的，就是找n-k+1小的

  • 维护一个容量为k的小顶堆，，先进k个数，剩下的n-k个数依次进入，堆顶一共出了n-k个较小的数，最后堆的堆顶就是第n-k+1小的数

  • 可以先判断是否小于堆顶元素，如果小于堆顶就直接“丢弃”，否则出堆顶然后进该元素

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int findKthLargest(int[] nums, int k) {
        //用优先队列的思路也很清晰，要找第k大的，就是找n-k+1小的 用小顶堆
        int n = nums.length;
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        for(int i=0;i<n;i++){
            if(i<k){
                queue.offer(nums[i]);
                continue;
            }
            if(nums[i]<=queue.peek()) continue; //如果比堆顶还小就直接不要了
            queue.poll(); 
            queue.offer(nums[i]);
        }
        return queue.peek();
    }
}

剑指 Offer 45. 把数组排成最小的数

输入一个非负整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。

示例 1: 输入: [10,2] 输出: “102”
示例 2: 输入: [3,30,34,5,9] 输出: “3033459”

解法一：快速排序！！（其他经典排序也可以的）

  • 本质上是要做一个排序：第一位上的数最小的放最前面；第一位相等时，第二位最小的放前面；当位数截断时，该最后一位和相同的后面一位比较

  • 上面是直接能想到的，，但是这个排序就显得很复杂。其实可以等价为 两个数x y拼接：xy或yx，拼接的结果越小，那么就是那个小结果的前后关系

  • 具体可以写一个快速排序，在判断元素大小的部分，使用拼接判断大小的规则。注意需要用到字符串的compareTo()方法

代码：判断条件(nums[j]+""+flag).compareTo(flag+""+nums[j])<0

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 String minNumber(int[] nums) {
        //手写快排，然后指定比较大小的方式
        quickSort(nums,0,nums.length-1);
        StringBuilder sb = new StringBuilder();
        for(int i:nums) sb.append(i);
        return sb.toString();
    }

    private void quickSort(int[] nums, int left, int right){
        if(left>=right) return;
        int index = findIndex(nums,left, right);
        quickSort(nums,left,index-1);
        quickSort(nums,index+1,right);
    }

    private int findIndex(int[] nums, int left, int right){
        //随机找一个基准
        int rand = new Random().nextInt(right-left+1)+left;
        swap(nums,rand,right);

        int flag = nums[right];
        int i = left;
        for(int j=left;j<right;j++){
            if((nums[j]+""+flag).compareTo(flag+""+nums[j])<0){
                if(i!=j) swap(nums,i,j);
                i++;
            }
        }
        swap(nums,i,right);
        return i;
    }

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

解法二：字符串数组的sort()函数

  • 直接将数组转为字符串数组，然后调用sort()，并使用lamda表达式，指定排序方式….
  • 记住int类型数组不能直接用lamda表达式比较，，只有引用类型的Integer和String才可以

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public String minNumber(int[] nums) {
        //所以先老老实实的转数组类型，再调用sort()API
        int n = nums.length;
        String[] str = new String[n];
        for(int i=0;i<n;i++) str[i] = String.valueOf(nums[i]);
        //调用sort 指定规则排序
        Arrays.sort(str,(o1,o2)-> (o1+o2).compareTo(o2+o1));
        StringBuilder sb = new StringBuilder();
        for(String s:str) sb.append(s);
        return sb.toString();
    }
}
-------------感谢阅读没事常来-------------