今天主要调试了数组及其排序方法，用了两种排序法：快排，堆排。由于部分语句较长，截图截不下，我先稍微总结两句，然后直接上输出和代码了
总结：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做展示足够了，定义类型的好处与用法详见我堆排的那篇博客。
输出：代码：
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类型数组测试："); ArrayListarr3 = 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 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 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 的前k大问题测试："); ArrayList arr3 = new ArrayList<>(Arrays.asList(1, 3, 6, 2, 7, 4, 8, 5, 9, 0)); System.out.println("原数组为：" + arr3); ArrayList 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{ 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 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 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 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 topK(ArrayList arr, int size, int k, boolean instruct){ ArrayList 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; } } }
