做练习前,请先看 十大经典排序算法(详解)

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

题目:

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

思路:

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

代码实现:

 1    // 单向扫描法,也可以使用双向扫描法
 2    public static void practice(int[] array) {
 3        int left = 0;
 4        int right = array.length - 1;
 5        int temp;
 6        while (left < right) {
 7            // 对 2 求余不位 0 则为奇数
 8            if (array[left] % 2 != 0) {
 9                left++;
10            // 如果为偶数则将该数放后面
11            } else {
12                temp = array[left];
13                array[left] = array[right];
14                array[right] = temp;
15                right--;
16            }
17        }
18    }

2、第 k 个元素

题目:

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

思路:

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

代码实现:

 1    public static int practice(int[] array, int left, int right, int k) {
 2        // 主元素的下标
 3        int midn = median(array, left, right);
 4        if (midn == k) {
 5            return array[midn];
 6        } else if (midn > k) {
 7            return practice(array, left, midn - 1, k);
 8        } else {
 9            return practice(array, midn + 1, right, k);
10        }
11    }
12
13    public static int median(int[] array, int left, int right) {
14        int mainElement = array[left];
15        int start = left + 1;
16        int end = right;
17        while (start <= end) {
18            while (start <= end && array[start] <= mainElement) {
19                start++;
20            }
21            while (start <= end && array[end] >= mainElement) {
22                end--;
23            }
24            if (start < end) {
25                int temp = array[start];
26                array[start] = array[end];
27                array[end] = temp;
28            }
29        }
30        int temp = array[left];
31        array[left] = array[end];
32        array[end] = temp;
33        return end;
34    }

3、超过一半的数字

题目:

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

思路:

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

代码实现:

 1    // 解法三:
 2    public static int method(int[] array) {
 3        int num = array[0];
 4        int count = 1;
 5        // 因为下标为0的数,已经当做变量的初值了,所以从1开始循环
 6        for (int i = 1; i < array.length; i++) {
 7            // count等于0表示该数已经被消去,重新记录新的数
 8            if (count == 0) {
 9                num = array[i];
10                count = 1;
11            } else {
12                // 相同计数增加
13                if (num == array[i]) {
14                    count++;
15                } else {
16                    count--;
17                }
18            }
19        }
20        // 由题意可知:一个数超过数组的一半则该数出现的次数比其他数的总次数还要多,所以剩下的肯定是那个数
21        return num;
22    }

加强:

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

思路:

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

代码实现:

 1    public static int method(int[] array) {
 2        int num = array[0];
 3        int count = 0;
 4        // 对于最后一个数单独计数
 5        int endCount = 0;
 6        // 数组的长度
 7        int length=array.length;
 8        // 因为所有数都需要比较,所以从0开始
 9        for (int i = 0; i < length; i++) {
10            if (array[i] == array[length - 1]) {
11                endCount++;
12            }
13            if (count == 0) {
14                num = array[i];
15                count = 1;
16            } else {
17                if (num == array[i]) {
18                    count++;
19                } else {
20                    count--;
21                }
22            }
23        }
24        // 如果最后一个数出现的次数等于数组长度的一半,则最后一个数肯定是那个数。
25        if (endCount == length / 2) {
26            return array[length - 1];
27        } else {
28            return num;
29        }
30    }

4、最小可用 ID

题目:

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

思路:

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

代码实现:

解法三:

 1    // 解法三
 2    public static int method(int[] array) {
 3        int length = array.length;
 4        // 因为是从1开始编码的,长度需要加1才不会越界
 5        int[] copyArray = new int[length + 1];
 6        for (int i = 0; i < array.length; i++) {
 7            if (array[i] < length + 1) {
 8                copyArray[array[i]] = 1;
 9            }
10        }
11        for (int i = 1; i <= length; i++) {
12            if (copyArray[i] != 0) {
13                return i;
14            }
15        }
16        return length + 1;
17    }

解法四

 1    // 解法四
 2    public static int method(int[] array, int left, int right) {
 3        if (left <= right) {
 4            // median方法是一个双向扫描查找主元素的下标
 5            int mid = median(array, left, right);
 6            // 如果相等表示左稠密,去右边查找
 7            if (mid + 1 == array[mid]) {
 8                return method(array, mid + 1, right);
 9            } else {
10                return method(array, left, mid - 1);
11            }
12        } else {
13            // 因为下标从0开始,所以加一
14            return left + 1;
15        }
16    }
17
18    public static int median(int[] array, int left, int right) {
19        int mainElement = array[left];
20        int start = left + 1;
21        int end = right;
22        while (start <= end) {
23            while (start <= end && array[start] <= mainElement) {
24                start++;
25            }
26            while (start <= end && array[end] >= mainElement) {
27                end--;
28            }
29            if (start < end) {
30                int temp = array[start];
31                array[start] = array[end];
32                array[end] = temp;
33            }
34        }
35        int temp = array[left];
36        array[left] = array[end];
37        array[end] = temp;
38        return end;
39    }

5、合并有序数组

题目:

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

思路:

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

代码实现:

 1    // 解法二,m 表示 a 数组元素的个数,n 表示 b 数组元素的个数
 2    public void merge(int[] a, int m, int[] b, int n) {
 3        int pointer = a.length - 1;
 4        int pointera = m - 1;
 5        int pointerb = n - 1;
 6        while (pointera >= 0 && pointerb >= 0) {
 7            if (a[pointera] >= b[pointerb]) {
 8                a[pointer--] = a[pointera--];
 9            } else {
10                a[pointer--] = b[pointerb--];
11            }
12        }
13        if (pointerb >= 0) {
14            for (int i = pointerb; i >= 0; i--) {
15                a[pointer--] = b[i];
16            }
17        }
18    }

6、逆序对个数

题目:

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

思路:

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

代码实现:

 1    // 统计逆序对的个数
 2    static int count = 0;
 3  
 4    // 第一次调用 left为 0 ,right为 array.length - 1
 5    public static void sort(int[] array, int left, int right) {
 6        if (left < right) {
 7            int mid = (left + right) / 2;
 8            // 对左边进行排序
 9            sort(array, left, mid);
10            // 对右边进行排序
11            sort(array, mid + 1, right);
12            // 合并
13            merge(array, left, mid, right);
14        }
15    }
16
17    public static void merge(int[] array, int left, int mid, int right) {
18        // 创建一个辅助的临时数组
19        int[] tempArray = new int[right - left + 1];
20        // 记录临时数组的下标
21        int tempIndex = 0;
22        // 左边的指针
23        int leftPointer = left;
24        // 右边的指针
25        int rightPointer = mid + 1;
26        while (leftPointer <= mid && rightPointer <= right) {
27            // 如果左边的元素小于等于右边的元素,则将左边的元素,存入临时数组,否则相反
28            if (array[leftPointer] <= array[rightPointer]) {
29                tempArray[tempIndex++] = array[leftPointer++];
30            } else {
31                tempArray[tempIndex++] = array[rightPointer++];
32                count += mid - leftPointer + 1;
33            }
34        }
35        // 将左序列剩下的元素,拷贝到临时数组中
36        while (leftPointer <= mid) {
37            tempArray[tempIndex++] = array[leftPointer++];
38        }
39        // 将右序列剩下的元素,拷贝到临时数组中
40        while (rightPointer <= right) {
41            tempArray[tempIndex++] = array[rightPointer++];
42        }
43        // 将临时数组拷贝到原数组中
44        System.arraycopy(tempArray, 0, array, left, tempArray.length);
45    }

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 则移动右指针,如果小了则移动左指针。

代码实现:

 1    public static List<String> practice(int[] array, int k) {
 2        List<String> list = new ArrayList<>();
 3        int left = 0;
 4        int right = array.length-1;
 5        while (left < right) {
 6            if ((array[left] + array[right]) < k) {
 7                left++;
 8            } else if ((array[left] + array[right]) > k) {
 9                right--;
10            } else {
11                list.add("(" + array[left] + "," + array[right] + ")");
12                left++;
13                right--;
14            }
15        }
16        return list;
17    }

8、最短无序连续子数组

题目:

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

例如:

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

思路:

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

代码实现:

 1    public static int practice(int[] array) {
 2        int length = array.length;
 3        int max = array[0];
 4        int min = array[length - 1];
 5        // 左指针和右指针
 6        int left = 0, right = -1;
 7        for (int i = 0; i < length; i++) {
 8            // 从左往右开始遍历,如果发现右边的数小于左边最大的数,则记录下来
 9            if (max > array[i]) {
10                right = i;
11            } else {
12                // 记录左边最大的数
13                max = array[i];
14            }
15            // 从右往左开始遍历,如果发现左边的大于右边最小的数,则记录下来
16            if (min < array[length - i - 1]) {
17                left = length - i - 1;
18            } else {
19                // 记录右边最小的数
20                min = array[length - i - 1];
21            }
22        }
23        return right - left + 1;
24    }

9、前 k 个数

题目:

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

思路:

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

代码实现:

 1    public static void main(String[] args) {
 2        Scanner scanner = new Scanner(System.in);
 3        // 输入topK
 4        int k = scanner.nextInt();
 5        // 创建一个小顶堆
 6        int[] heap = new int[k];
 7        int value = scanner.nextInt();
 8        // 只要用户输入的数不为-1则一直执行
 9        while (value != -1) {
10            if (count < k) {
11                // 如果个数小于堆的容量,则直接存储
12                heap[count] = value;
13                count++;
14                if (count == k) {
15                    // 如果加满,则将数组堆化
16                    pile(heap, heap.length);
17                }
18            } else {
19                if (value > heap[0]) {
20                    // 如果大于,则将和推顶元素互换,再进行堆化
21                    heap[0] = value;
22                    pile(heap, heap.length);
23                }
24            }
25            // 获取用户输入的数
26            value = scanner.nextInt();
27        }
28        // 输出结果
29        for (int i = heap.length; i > 1; i--) {
30            System.out.print(heap[0] + " ");
31            heap[0] = heap[i - 1];
32            pile(heap, i);
33        }
34        System.out.print(heap[0] + " ");
35    }
36
37
38    // 将数组小顶堆化,第一次length参数传入 array.length
39    public static void pile(int[] array, int length) {
40        // array.length/2-1得到最小的有子节点的节点
41        for (int i = length / 2 - 1; i >= 0; i--) {
42            smallTopPile(array, i, length);
43        }
44    }
45
46    // 将指定堆转换为小顶堆
47    public static void smallTopPile(int[] array, int root, int length) {
48        int left = root * 2 + 1;
49        int right = root * 2 + 2;
50        // 判断是否有左节点
51        if (left >= length) {
52            return;
53        }
54        // 用于存储最小节点的下标
55        int min;
56        // 如果右节点存在且小于左节点则执行
57        if (right < length && array[right] < array[left]) {
58            min = right;
59        } else {
60            min = left;
61        }
62        // 如果父节点,小于等于子节点则结束递归,否则进行交换并继续向下递归
63        if (array[root] <= array[min]) {
64            return;
65        } else {
66            int temp = array[root];
67            array[root] = array[min];
68            array[min] = temp;
69        }
70        smallTopPile(array, min, length);
71    }

10、数组能排成的最小数(特殊排序)

题目:

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

例如:

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

思路:

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

代码实现:

 1    public static int practice(Integer[] array) {
 2        Arrays.sort(array, new Comparator<Integer>() {
 3            @Override
 4            public int compare(Integer o1, Integer o2) {
 5                // 设置排序规则
 6                String s1 = o1 + "" + o2;
 7                String s2 = o2 + "" + o1;
 8                return s1.compareTo(s2);
 9            }
10        });
11        StringBuilder stringBuilder = new StringBuilder();
12        for (Integer integer : array) {
13            stringBuilder.append(integer);
14        }
15        return Integer.parseInt(stringBuilder.toString());
16    }

标题:关于排序的练习题
作者:Yi-Xing
地址:http://zyxwmj.top/articles/2019/11/18/1574088001295.html
博客中若有不恰当的地方,请您一定要告诉我。前路崎岖,望我们可以互相帮助,并肩前行!