关于排序的练习题

做练习前，请先看 十大经典排序算法（详解）

1、调整数组顺序使奇数位于偶数前面

题目：

  调整指定数组中数字的顺序，使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分，要求时间复杂度为 O(n)。

思路：

  和快排的思路相似，使用单向扫描法或双向扫描法，判断数的奇偶性然后进行换位。

代码实现：

    // 单向扫描法，也可以使用双向扫描法
    public static void practice(int[] array) {
        int left = 0;
        int right = array.length - 1;
        int temp;
        while (left < right) {
            // 对 2 求余不位 0 则为奇数
            if (array[left] % 2 != 0) {
                left++;
            // 如果为偶数则将该数放后面
            } else {
                temp = array[left];
                array[left] = array[right];
                array[right] = temp;
                right--;
            }
        }
    }

2、第 k 个元素

题目：

  以尽量高的效率求出一个乱序数组中按数值顺序的第 k 个元素值。

思路：

  和快排的解法相似，每次递归判断该主元素的下标，来进行折半查找。

代码实现：

    public static int practice(int[] array, int left, int right, int k) {
        // 主元素的下标
        int midn = median(array, left, right);
        if (midn == k) {
            return array[midn];
        } else if (midn > k) {
            return practice(array, left, midn - 1, k);
        } else {
            return practice(array, midn + 1, right, k);
        }
    }

    public static int median(int[] array, int left, int right) {
        int mainElement = array[left];
        int start = left + 1;
        int end = right;
        while (start <= end) {
            while (start <= end && array[start] <= mainElement) {
                start++;
            }
            while (start <= end && array[end] >= mainElement) {
                end--;
            }
            if (start < end) {
                int temp = array[start];
                array[start] = array[end];
                array[end] = temp;
            }
        }
        int temp = array[left];
        array[left] = array[end];
        array[end] = temp;
        return end;
    }

3、超过一半的数字

题目：

  数组中有一个数字出现的次数超过了数组长度的一半，找出这个数字。

思路：

• 解法一： 排序后返回 array[array.length/2]，时间复杂度 O(nlogn)。
• 解法二：直接使用上个题的代码得知下标为 array.length/2 的元素即可，O(n)，需要更改数组内容。
• 解法三：利用数组的特性，一个数超过数组的一半则该数出现的次数比其他数的总次数还要多。创建两个变量，一个存储当前数，一个存储当前数的个数，遍历数组，不同则消去相同则相加，具体看代码。

代码实现：

    // 解法三：
    public static int method(int[] array) {
        int num = array[0];
        int count = 1;
        // 因为下标为0的数，已经当做变量的初值了，所以从1开始循环
        for (int i = 1; i < array.length; i++) {
            // count等于0表示该数已经被消去，重新记录新的数
            if (count == 0) {
                num = array[i];
                count = 1;
            } else {
                // 相同计数增加
                if (num == array[i]) {
                    count++;
                } else {
                    count--;
                }
            }
        }
        // 由题意可知：一个数超过数组的一半则该数出现的次数比其他数的总次数还要多，所以剩下的肯定是那个数
        return num;
    }

加强：

  如果该数出现的个数正好是数组的一半，这么得到该数。

思路：

  由题意得该数组是一个偶数个数，所以使用上面的解法只有当最后一个数是那个数的时候才可能出错，因此我们只需要对最后一个数单独计数即可。

代码实现：

    public static int method(int[] array) {
        int num = array[0];
        int count = 0;
        // 对于最后一个数单独计数
        int endCount = 0;
        // 数组的长度
        int length=array.length;
        // 因为所有数都需要比较，所以从0开始
        for (int i = 0; i < length; i++) {
            if (array[i] == array[length - 1]) {
                endCount++;
            }
            if (count == 0) {
                num = array[i];
                count = 1;
            } else {
                if (num == array[i]) {
                    count++;
                } else {
                    count--;
                }
            }
        }
        // 如果最后一个数出现的次数等于数组长度的一半，则最后一个数肯定是那个数。
        if (endCount == length / 2) {
            return array[length - 1];
        } else {
            return num;
        }
    }

4、最小可用 ID

题目：

  在非负数组（乱序）中找到最小的可分配 ID（从 1 开始编号）。例如：{1,5,6,3,8,7,2}，最小的可分配 ID 为 4。

思路：

• 解法一：暴力解法从 1 开始查找每个自然数是否在数组中，时间复杂度 O(n²)。
• 解法二：先将数组排序，然后在遍历，时间复杂度 O(nlogn)。
• 解法三：创建一个临时数组长度为指定数组的长度加一，遍历指定数组将数组中的数按值赋值给临时数组的指定下标，遍历临时数组查看那个下标为被赋值即可。
• 解法四：使用单向扫描或双向扫描，确定主元素在排序后的下标。然后利用数组的特性，判断主元素是否等于当前下标加一，如果相等则表明可分配 ID 在主元素的右边，如果不相等则表示可分配 ID 在主元素的左边，递归调用即可查找最小可分配 ID。

代码实现：

解法三：

    // 解法三
    public static int method(int[] array) {
        int length = array.length;
        // 因为是从1开始编码的，长度需要加1才不会越界
        int[] copyArray = new int[length + 1];
        for (int i = 0; i < array.length; i++) {
            if (array[i] < length + 1) {
                copyArray[array[i]] = 1;
            }
        }
        for (int i = 1; i <= length; i++) {
            if (copyArray[i] != 0) {
                return i;
            }
        }
        return length + 1;
    }

解法四

    // 解法四
    public static int method(int[] array, int left, int right) {
        if (left <= right) {
            // median方法是一个双向扫描查找主元素的下标
            int mid = median(array, left, right);
            // 如果相等表示左稠密，去右边查找
            if (mid + 1 == array[mid]) {
                return method(array, mid + 1, right);
            } else {
                return method(array, left, mid - 1);
            }
        } else {
            // 因为下标从0开始，所以加一
            return left + 1;
        }
    }

    public static int median(int[] array, int left, int right) {
        int mainElement = array[left];
        int start = left + 1;
        int end = right;
        while (start <= end) {
            while (start <= end && array[start] <= mainElement) {
                start++;
            }
            while (start <= end && array[end] >= mainElement) {
                end--;
            }
            if (start < end) {
                int temp = array[start];
                array[start] = array[end];
                array[end] = temp;
            }
        }
        int temp = array[left];
        array[left] = array[end];
        array[end] = temp;
        return end;
    }

5、合并有序数组

题目：

  给定两个排序后的数组 A 和 B，以及 A 数组元素的个数和 B 数组元素的个数，其中 A 的末端有足够的缓冲空间容纳 B。编写一个方法将 B 合并入 A 并排序。

思路：

• 解法一：暴力解法，先将 B 数组拷贝到 A 数组中然后排序。
• 解法二：创建两个指针分别指向 a 数组元素的末尾和 b 数组元素的末尾，同时遍历 a 、b 两个数组，将大的元素放到数组 a 的末尾即可，最后如果 b 数组没有遍历完，则将剩下的元素合入到 a 数组即可。

代码实现：

    // 解法二，m 表示 a 数组元素的个数，n 表示 b 数组元素的个数
    public void merge(int[] a, int m, int[] b, int n) {
        int pointer = a.length - 1;
        int pointera = m - 1;
        int pointerb = n - 1;
        while (pointera >= 0 && pointerb >= 0) {
            if (a[pointera] >= b[pointerb]) {
                a[pointer--] = a[pointera--];
            } else {
                a[pointer--] = b[pointerb--];
            }
        }
        if (pointerb >= 0) {
            for (int i = pointerb; i >= 0; i--) {
                a[pointer--] = b[i];
            }
        }
    }

6、逆序对个数

题目：

  一个数列，如果左边的数大，右边的数小，则称这两个数为一个逆序对。求出一个数列中有多少个逆序对。

思路：

  直接使用归并排序，在数组合并时，如果左边元素大于右边元素，则表明该右边这个元素能和左边的元素组成 mid - leftPointer + 1个逆序对。

代码实现：

    // 统计逆序对的个数
    static int count = 0;
  
    // 第一次调用 left为 0 ，right为 array.length - 1
    public static void sort(int[] array, int left, int right) {
        if (left < right) {
            int mid = (left + right) / 2;
            // 对左边进行排序
            sort(array, left, mid);
            // 对右边进行排序
            sort(array, mid + 1, right);
            // 合并
            merge(array, left, mid, right);
        }
    }

    public static void merge(int[] array, int left, int mid, int right) {
        // 创建一个辅助的临时数组
        int[] tempArray = new int[right - left + 1];
        // 记录临时数组的下标
        int tempIndex = 0;
        // 左边的指针
        int leftPointer = left;
        // 右边的指针
        int rightPointer = mid + 1;
        while (leftPointer <= mid && rightPointer <= right) {
            // 如果左边的元素小于等于右边的元素，则将左边的元素，存入临时数组，否则相反
            if (array[leftPointer] <= array[rightPointer]) {
                tempArray[tempIndex++] = array[leftPointer++];
            } else {
                tempArray[tempIndex++] = array[rightPointer++];
                count += mid - leftPointer + 1;
            }
        }
        // 将左序列剩下的元素，拷贝到临时数组中
        while (leftPointer <= mid) {
            tempArray[tempIndex++] = array[leftPointer++];
        }
        // 将右序列剩下的元素，拷贝到临时数组中
        while (rightPointer <= right) {
            tempArray[tempIndex++] = array[rightPointer++];
        }
        // 将临时数组拷贝到原数组中
        System.arraycopy(tempArray, 0, array, left, tempArray.length);
    }

7、排序数组中找和的因子

题目：

  给定已排序的数组 arr 和 k，不重复打印 array 中所有相加和为 k 的不降序二元组。

例如：

 输入：array = {-8, -4, -3, 0, 2, 4, 5, 8, 9, 10}，k = 10
 输出：[(0,10), (2,8)]

思路：

  以例子为例，-8 是数组中最小的数，如果想凑成 k，需要一个较大的数。所以我们创建俩个指针，左指针指向-8，右指针指向 10，如果 -8 + 10 大于 10 则移动右指针，如果小了则移动左指针。

代码实现：

    public static List<String> practice(int[] array, int k) {
        List<String> list = new ArrayList<>();
        int left = 0;
        int right = array.length-1;
        while (left < right) {
            if ((array[left] + array[right]) < k) {
                left++;
            } else if ((array[left] + array[right]) > k) {
                right--;
            } else {
                list.add("(" + array[left] + "," + array[right] + ")");
                left++;
                right--;
            }
        }
        return list;
    }

8、最短无序连续子数组

题目：

  给定一个整数数组，你需要寻找一个连续的子数组，如果对这个子数组进行升序排序，那么整个数组都会变为升序排序，你找到的子数组应是最短的，请输出它的长度。要求：O(n)。

例如：

 输入：array = {2, 3, 7, 5, 4, 6, 8}
 输出：4，因为只有{7, 5, 4, 6}需要排序。

思路：

  在升序数组中，右边的数总是大于左边的数。所以判断数组无序的范围是：
如果左边存在一个数大于右边最小的数，则该数的下标是结果数组的起点。如果右边存在一个数小于左边最大的数，则该数的下标是结果数组的终点。

代码实现：

    public static int practice(int[] array) {
        int length = array.length;
        int max = array[0];
        int min = array[length - 1];
        // 左指针和右指针
        int left = 0, right = -1;
        for (int i = 0; i < length; i++) {
            // 从左往右开始遍历，如果发现右边的数小于左边最大的数，则记录下来
            if (max > array[i]) {
                right = i;
            } else {
                // 记录左边最大的数
                max = array[i];
            }
            // 从右往左开始遍历，如果发现左边的大于右边最小的数，则记录下来
            if (min < array[length - i - 1]) {
                left = length - i - 1;
            } else {
                // 记录右边最小的数
                min = array[length - i - 1];
            }
        }
        return right - left + 1;
    }

9、前 k 个数

题目：

  求海量数据（正整数）按逆序排列的前 k 个数（topK），因为数据量太大，不能全部存储在内存中，只能一个一个地从磁盘或者网络上读取数据，请设计一个高效的算法来解决这个问题。
  用户先输入 K，代表要求得的 topK，随后的输入 N 个数，输入-1 代表输入终止。请输出 topK，从小到大，空格分割。

思路：

  所谓 topK 就是只维护数值大的数，用户每输入一个数和该数组中最小的数比较，大的话则交换，小的话则舍去。可以利用小顶堆的性质，每次将输入的数和推顶进行比较，如果交换的话则再次将该数组堆化即可。最后利用堆排序将数组逆序打印即可。

代码实现：

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        // 输入topK
        int k = scanner.nextInt();
        // 创建一个小顶堆
        int[] heap = new int[k];
        int value = scanner.nextInt();
        // 只要用户输入的数不为-1则一直执行
        while (value != -1) {
            if (count < k) {
                // 如果个数小于堆的容量，则直接存储
                heap[count] = value;
                count++;
                if (count == k) {
                    // 如果加满，则将数组堆化
                    pile(heap, heap.length);
                }
            } else {
                if (value > heap[0]) {
                    // 如果大于，则将和推顶元素互换，再进行堆化
                    heap[0] = value;
                    pile(heap, heap.length);
                }
            }
            // 获取用户输入的数
            value = scanner.nextInt();
        }
        // 输出结果
        for (int i = heap.length; i > 1; i--) {
            System.out.print(heap[0] + " ");
            heap[0] = heap[i - 1];
            pile(heap, i);
        }
        System.out.print(heap[0] + " ");
    }


    // 将数组小顶堆化，第一次length参数传入 array.length
    public static void pile(int[] array, int length) {
        // array.length/2-1得到最小的有子节点的节点
        for (int i = length / 2 - 1; i >= 0; i--) {
            smallTopPile(array, i, length);
        }
    }

    // 将指定堆转换为小顶堆
    public static void smallTopPile(int[] array, int root, int length) {
        int left = root * 2 + 1;
        int right = root * 2 + 2;
        // 判断是否有左节点
        if (left >= length) {
            return;
        }
        // 用于存储最小节点的下标
        int min;
        // 如果右节点存在且小于左节点则执行
        if (right < length && array[right] < array[left]) {
            min = right;
        } else {
            min = left;
        }
        // 如果父节点，小于等于子节点则结束递归，否则进行交换并继续向下递归
        if (array[root] <= array[min]) {
            return;
        } else {
            int temp = array[root];
            array[root] = array[min];
            array[min] = temp;
        }
        smallTopPile(array, min, length);
    }

10、数组能排成的最小数（特殊排序）

题目：

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

例如：

 输入：array = {3, 32, 321}，则打印出这 3 个数字能排成的最小数字。
 输出：321323

思路：

  这个题可以理解为对字符串进行升序排序，当字符串 "3" 加 "32" 大于 "32" 加 "3" 时，3 放在 32 的后面，否则相反。

代码实现：

    public static int practice(Integer[] array) {
        Arrays.sort(array, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                // 设置排序规则
                String s1 = o1 + "" + o2;
                String s2 = o2 + "" + o1;
                return s1.compareTo(s2);
            }
        });
        StringBuilder stringBuilder = new StringBuilder();
        for (Integer integer : array) {
            stringBuilder.append(integer);
        }
        return Integer.parseInt(stringBuilder.toString());
    }