Java学习笔记 第五天 数组与排序

今天主要调试了数组及其排序方法，用了两种排序法：快排，堆排。由于部分语句较长，截图截不下，我先稍微总结两句，然后直接上输出和代码了

总结：

1.Java中的while，if等具有判断性的语句不支持while( (int)information )这样的写法，原因之前有说过：Boolean类型的值不接受0,1，只接受true，false。

2.关于静态函数的使用：这里直接放个链接，这个博主写的非常好：点击这里

3.应有逻辑的创建类及其方法，这可以使程序结构非常清晰

4.ArrayList 型数组可以直接输出：System.out.println(arr)；

5.arr.length用在多维数组上的话：

   int[][] arr = new int[][]{{1, 2, 3}, {4, 5, 6, 7}, {8, 9}}；则arr.length的值为3，arr[1].length的值为4，arr[2].length的值为2；以此类推多维；

6.ArrayList型数组无法直接访问与修改元素，前者需要.get(index)后缀，后者需要.set(index，targetNumber)后缀。如int t = arr.get(3)，则t的值为arr数组下标为3的元素。再如arr.set(2, 9)，则arr数组下标为2的元素被替换为数字9

7.函数及其说明我放在代码里了，两个函数我之前都出过一期C++的博客：快排，堆排；如果是和我一样有C基础的朋友们可以去看看。我用Java写的时候直接引用了ArrayList动态数组，但是未定义类型Type，我觉得用int做展示足够了，定义类型的好处与用法详见我堆排的那篇博客。

输出：

 

代码：

/**
 * @author 阿白
 * @version v1.8
 * 希望毕业能直接找到工作，，，
 * */
import java.util.*;
 
public class HelloWorld {
    public static void main(String[] a) {
        System.out.println("今天主要测试各种数组与排序方式：\n");
        Test.arrayTest.normalArrTest();
        Test.sortTest.quickSortTest();
        Test.sortTest.heapSortTest();
    }
}
class Test{
    static class arrayTest{
        static void normalArrTest(){
            System.out.println("普通类型数组测试：");
            int[] arr1 = new int[]{1, 2, 4, 7, 3, 6, 9, 8, 0, 5};
            int[][] arr2 = new int[][]{{1, 4, 6, 7}, {9, 2, 5, 8}, {3, 0}};
            System.out.println("arr.length的使用：\n" +
                    "   arr1.length = " + arr1.length +
                    "   \narr2[0].length = " + arr2[0].length +
                    "   \narr2.length = " + arr2.length);
            System.out.println("\nArrayList类型数组测试：");
            ArrayList<Integer> arr3 = new ArrayList<>(Arrays.asList(1, 3, 6, 2, 7, 4, 8, 5, 9));
            System.out.println("添加元素：arr3.add()");
            arr3.add(0);
            System.out.println("删除元素：arr3.remove()");
            arr3.remove(2);//删除下标为2的元素
            System.out.println("修改元素：arr3.set(index, element)");
            arr3.set(2, 10);//将下标为2的元素修改为10
            System.out.println("查找元素：arr3.contains()");
            boolean ans = arr3.contains(8);//查找元素 8 是否存在
        };
    }
    static class sortTest{
        static void quickSortTest(){
            System.out.println("快速排序测试：");
            System.out.println("普通数组的快速排序：");
            int[] arr = new int[]{1, 2, 4, 7, 3, 6, 9, 8, 0, 5};
            System.out.println("原数组为：");
            for(int i = 0; i < 10; i++) System.out.print(arr[i] + " ");
            Sorts.normalQuickSort(arr, 0, 10, true);
            System.out.println("排序后为：");
            for(int i = 0; i < 10; i++) System.out.print(arr[i] + " ");
            System.out.println("\nArrayList数组的快速排序：");
            ArrayList<Integer> arr1 = new ArrayList<>(Arrays.asList(1, 3, 6, 2, 7, 4, 8, 5, 9, 0));
            System.out.println("原数组为：" + arr1);
            Sorts.arraysQuickSort(arr1, 0, 10, true);
            System.out.println("排序后为：" + arr1);
            System.out.println("\n查资料时有人说函数调用的全是副本，无法更改原数组的值，，但我用着也没事a，，");
        }
        static void heapSortTest(){
            System.out.println("普通数组不再尝试了。\nArrayList数组的堆排序：");
            ArrayList<Integer> arr2 = new ArrayList<>(Arrays.asList(1, 3, 6, 2, 7, 4, 8, 5, 9, 0));
            System.out.println("原数组为：" + arr2);
            Sorts.HeapSort.sort(arr2, 10, true);
            System.out.println("排序后为：" + arr2);
            System.out.println("\n返回值为ArrayList<Integer>的前k大问题测试：");
            ArrayList<Integer> arr3 = new ArrayList<>(Arrays.asList(1, 3, 6, 2, 7, 4, 8, 5, 9, 0));
            System.out.println("原数组为：" + arr3);
            ArrayList<Integer> arr4 = Sorts.HeapSort.topK(arr3, 10, 5, true);
            System.out.println("前 5 小为：" + arr4);
            arr4 = Sorts.HeapSort.topK(arr3, 10, 5, false);
            System.out.println("前 5 大为：" + arr4);
        }
    }
}
class Sorts{
    /*
    * 快排：instruct==true时，从小到大排序，反之从大到小
    * 堆排：堆排序：同快排;
    *      TopK问题：instruct==true时，求前k小，从小到大排序；反之求前k大，从大到小排序
    * */
    static void normalQuickSort(int arr[], int left, int right, boolean instruct){
        if(left < right){
            int p = left;
            int index = p + 1;
            for(int i = index; i < right; i++){
                boolean judge = instruct ? arr[i] < arr[p] : arr[i] > arr[p];
                if(judge){
                    int t = arr[i];
                    arr[i] = arr[index];
                    arr[index] = t;
                    index++;
                }
            }
            int t = arr[p];
            arr[p] = arr[index - 1];
            arr[index - 1] = t;
            p = index - 1;
            normalQuickSort(arr, left, p, instruct);
            normalQuickSort(arr, p + 1, right, instruct);
        }
    }
    static void arraysQuickSort(ArrayList<Integer> arr, int left, int right, boolean instruct){
        if(left < right){
            int p = left;
            int index = p + 1;
            for(int i = index; i < right; i++){
                boolean judge = instruct ? arr.get(i) < arr.get(p) : arr.get(i) > arr.get(p);
                if(judge){
                    int t = arr.get(i);
                    arr.set(i, arr.get(index));
                    arr.set(index, t);
                    index++;
                }
            }
            int t = arr.get(p);
            arr.set(p, arr.get(index - 1));
            arr.set(index - 1, t);
            p = index - 1;
            arraysQuickSort(arr, left, p, instruct);
            arraysQuickSort(arr, p + 1, right, instruct);
        }
    }
    static class HeapSort{
        private static void down(ArrayList<Integer> arr, int parent, int size, boolean instruct){
            int child = parent * 2 + 1;
            while(child < size){
                boolean judge1 = false;
                if(child + 1 < size){//ins==true，构建大顶堆，否则构建小顶堆
                    judge1 = instruct ? arr.get(child + 1) < arr.get(child) : arr.get(child + 1) > arr.get(child);
                }
                if(child + 1 < size && judge1){
                    child++;
                }
                boolean judge2 = instruct ? arr.get(child) < arr.get(parent) : arr.get(child) > arr.get(parent);
                if(judge2){
                    int t = arr.get(child);
                    arr.set(child, arr.get(parent));
                    arr.set(parent, t);
                    parent = child;
                    child = parent * 2 + 1;
                }
                else {
                    break;
                }
            }
        }
        public static void sort(ArrayList<Integer> arr, int size, boolean instruct){
            for(int i = (size - 2) / 2; i >=0; i--){
                down(arr, i, size, instruct);
            }
            int end = size - 1;
            while(end > 0){
                int t = arr.get(0);
                arr.set(0, arr.get(end));
                arr.set(end, t);
                down(arr, 0, end, instruct);
                end--;
            }
        }
        public static ArrayList<Integer> topK(ArrayList<Integer> arr, int size, int k, boolean instruct){
            ArrayList<Integer> topKArray = new ArrayList<>();
            for(int i = 0; i < k; i++){
                topKArray.add(arr.get(i));
            }
            for(int i = (k - 2) / 2; i >= 0; i--){
                down(topKArray, i, k, !instruct);
            }
            for(int i = k; i < size; i++){
                boolean judge = instruct ? arr.get(i) < topKArray.get(0) : arr.get(i) > topKArray.get(0);
                if(judge){
                    topKArray.set(0, arr.get(i));
                    down(topKArray, 0, k, !instruct);
                }
            }
            sort(topKArray, k, !instruct);
            return topKArray;
        }
    }
}