【华为OD题库-088】数字最低位排序-Java

题目

给定一个非空数组(列表)，元素数据类型为整型
请按照数组元素十进制最低位从小到大进行排序
十进制最低位相同的元素，相对位置保持不变
当数组元素为负值时，十进制最低位等同于去除符号位后对应十进制值最低位
输入描述
给定一个非空数组(列表)
其元素数据类型为32位有符号整数
数组长度为[1,1000]
输出描述
排序后的数组
示例1:
输入
1,2,5,-21,22,11,55,-101,42,8,7,32
输出
1,-21,11,-101,2,22,42,32,5,55,7,8

思路

简单排序题，因为要求相对位置不变，所以需要稳定的排序算法，
常见的稳定排序有：冒泡排序，插入排序，归并排序
不稳定的排序有：选择排序，快速排序
本文作为对排序的回顾，写了上述所有的排序算法代码

题解

package hwod;

import java.util.Arrays;
import java.util.Scanner;


public class NumSortLowest {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int[] nums = Arrays.stream(sc.nextLine().split(",")).mapToInt(Integer::parseInt).toArray();
        int[] res = mergeSort(nums);
        for (int i = 0; i < res.length; i++) {
            if (i != 0) System.out.print(",");
            System.out.print(res[i]);
        }
    }


    // 冒泡排序,稳定，可取
    private static int[] bubblingSort(int[] nums) {
        for (int i = 0; i < nums.length - 1; i++) {
            int flag = 0;
            for (int j = 0; j < nums.length - 1 - i; j++) {
                if (Math.abs(nums[j]) % 10 > Math.abs(nums[j + 1]) % 10) {
                    swap(nums, j, j + 1);
                    flag = 1;
                }
            }
            if (flag == 0) break;
        }

        return nums;
    }

    // 插入排序，稳定可取
    private static int[] insertSort(int[] nums) {
        for (int i = 1; i < nums.length; i++) {
            int key = nums[i];
            int j = i - 1;
            while (j >= 0 && Math.abs(nums[j]) % 10 > Math.abs(key) % 10) {
                nums[j + 1] = nums[j];
                j--;
            }
            nums[j + 1] = key;
        }

        return nums;
    }

    //归并排序,稳定可取
    private static int[] mergeSort(int[] nums) {

        recur2(nums, 0, nums.length - 1);
        return nums;
    }

    private static void recur2(int[] nums, int start, int end) {
        if (start >= end) return;
        int mid = start + end >> 1;
        recur2(nums, start, mid);
        recur2(nums, mid + 1, end);
        int i = start, j = mid + 1, k = 0;
        int[] tmp = new int[end - start + 1];
        while (i <= mid || j <= end) {
            if (j > end || (i <= mid && Math.abs(nums[i]) % 10 <= Math.abs(nums[j]) % 10)) {
                tmp[k++] = nums[i++];
            } else {
                tmp[k++] = nums[j++];
            }
        }
        for (int m = 0; m < tmp.length; m++) {
            nums[start + m] = tmp[m];
        }
    }
    //选择排序，不稳定，本题不可取
    private static int[] selectSort(int[] nums) {
        for (int i = 0; i < nums.length - 1; i++) {
            int minIdx = i;
            for (int j = i + 1; j < nums.length; j++) {
                if (Math.abs(nums[minIdx]) % 10 > Math.abs(nums[j]) % 10) {
                    minIdx = j;
                }
            }
            if (minIdx != i) {
                swap(nums, i, minIdx);
            }
        }

        return nums;
    }

    // 快速排序,不稳定,本题不可取
    private static int[] quickSort(int[] nums) {

        recur(nums, 0, nums.length - 1);

        return nums;
    }

    private static void recur(int[] nums, int start, int end) {
        if (start >= end) return;
        int i = start, j = end, pivot = nums[i];
        while (i < j) {
            while (Math.abs(nums[j]) % 10 > Math.abs(pivot) % 10 && i < j) j--;
            while (Math.abs(nums[i]) % 10 <= Math.abs(pivot) % 10 && i < j) i++;
            if (i < j) {
                swap(nums, i, j);
            }
        }
        swap(nums, i, start);
        recur(nums, start, i - 1);
        recur(nums, i + 1, end);
    }


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

}

推荐

如果你对本系列的其他题目感兴趣，可以参考华为OD机试真题及题解（JAVA），查看当前专栏更新的所有题目。