题解 | #牛的品种排序II#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param cows int整型一维数组 
     * @return int整型一维数组
     */
  /**
  方法一：计数排序适用于0-9这种，时间复杂度O(n)
  */
      public int[] sortCows(int[] cows) {
        int n = cows.length;
        int[] count = new int[3];

        // 统计每个品种的数量
        for (int i = 0; i < n; i++) {
            count[cows[i]]++;
        }

        // 重构原始牛群数组
        int index = 0;
        for (int i = 0; i < 3; i++) {
            while (count[i] > 0) {
                cows[index++] = i;
                count[i]--;
            }
        }

        return cows;
    }
  /**
  方法二：冒泡或者选择排序 时间复杂度O(n2)
  */
   public int[] sortCows (int[] cows) {
        for (int i = 0; i < cows.length; i++) {
            for (int j = i+1; j < cows.length; j++) {
                if(cows[i]>cows[j]){
                    int temp = cows[i];
                    cows[i] = cows[j];
                    cows[j] = temp;
                }
            }
        }
        return cows;
    }
}

本题知识点分析:

1.数组遍历

2.数组下标索引赋值

3.排序（八大排序任选即可）

本题解题思路分析：

1.计数排序应该是最方便的 先统计每个品种的数量，然后重构原始牛群数组即可

2.冒泡或者选择排序之类的，要O(N2)

看面试官要求时间复杂度，如果没要求，直接一个冒泡，不过现在考冒泡的公司应该没有了吧，计数排序还是要知道的。

本题使用编程语言: Java

如果对您有帮助的话，可以点个赞~