5.排序

一.最小的k个数
1.题目描述：
输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。

2.示例：
输入：arr = [3,2,1], k = 2
输出：[1,2] 或者 [2,1]

3.解:
（1）我的答案：

冒泡排序

class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        int count = 0;
        int len = arr.length;
        boolean isSorted = true;
        while (count < len - 1) {
            isSorted = true;
            for (int i = 1; i < len - count; i++) {
                if (arr[i] < arr[i - 1]) {
                    int temp = arr[i];
                    arr[i] = arr[i - 1];
                    arr[i - 1] = temp;
                    isSorted = false;
                }
            }
            if (isSorted) break;
            count++;
        }
        return Arrays.copyOfRange(arr, 0, k);
    }
}

选择排序

class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        int len = arr.length;
        for (int i = 0; i < len - 1; i++) {
            int t = i;
            for (int j = i + 1; j < len; j++) {
                if (arr[t] > arr[j]) t = j;
            }
            if (t != i) {
                int temp = arr[t];
                arr[t] = arr[i];
                arr[i] = temp;
            }
        }
        return Arrays.copyOfRange(arr, 0, k);
    }
}

插入排序

class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        int len = arr.length;
        for (int i = 1; i < len; i++) {
            int temp = arr[i];
            int j;
            for (j = i - 1; j >= 0; j--) {
                if (temp < arr[j]) arr[j + 1] = arr[j];
                else break;
            }
            arr[j+1] = temp;
        }
        return Arrays.copyOfRange(arr, 0, k);
    }
}

快速排序

class Solution {

    private int index;
    private int temp;

    public int[] getLeastNumbers(int[] arr, int k) {
        quickSort(arr, 0, arr.length - 1);
        return Arrays.copyOfRange(arr, 0, k);
    }


    public void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            index = getIndex(arr, low, high);
            quickSort(arr, low, index - 1);
            quickSort(arr, index + 1, high);
        }

    }

    public int getIndex(int[] arr, int low, int high) {
        temp = arr[low];
        while (low < high) {
            while (low < high && arr[high] >= temp) high--;
            arr[low] = arr[high];
            while (low < high && arr[low] <= temp) low++;
            arr[high] = arr[low];
        }
        arr[low] = temp;
        return low;
    }
}

归并排序

class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        int[] temp = new int[arr.length];
        split(arr, temp, 0, arr.length - 1);
        return Arrays.copyOfRange(arr, 0, k);
    }

    private void split(int[] arr, int[] temp, int start, int end) {
        if (start == end) return;
        int mid = start + (end - start) / 2;
        split(arr, temp, start, mid);
        split(arr, temp, mid + 1, end);
        merge(arr, temp, start, end, mid);
    }

    private void merge(int[] arr, int[] temp, int start, int end, int mid) {
        int i = start;
        int j = mid + 1;
        int index = 0;
        while (i <= mid && j <= end) {
            if (arr[i] < arr[j]) temp[index++] = arr[i++];
            else temp[index++] = arr[j++];
        }
        while (i <= mid) {
            temp[index++] = arr[i++];
        }
        while (j <= end) {
            temp[index++] = arr[j++];
        }
        for (int t = 0; t < index; t++) arr[start + t] = temp[t];
    }
}

多路平衡归并+置换选择+最佳归并树 教程：https://blog.csdn.net/toTheAir/article/details/79950263

计数排序

class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        int[] count = new int[10001];
        int[] result = new int[k];
        int index = 0;
        for (int i = 0; i < arr.length; i++) count[arr[i]]++;
        for (int i = 0; i < count.length; i++) {
            while (count[i]-- > 0 && index < k) result[index++] = i;
            if (index == k) break;
        }
        return result;
    }
}

4.总结：
这个题非常有代表性，可以尝试多种排序方法。