关于java:万字长文带你掌握Java数组与排序代码实现原理都帮你搞明白

32次阅读

共计 11081 个字符，预计需要花费 28 分钟才能阅读完成。

查找元素索引地位

根本查找

依据数组元素找出该元素第一次在数组中呈现的索引

public class TestArray1 {public static void main(String[] args) {
        // 定义一个数组
        int[] arr={10,20,70,10,90,100,1,2};
        // 依据元素查找出该元素在数组中第一次呈现的索引
        int index=getIndexByEle(arr,2);
        System.out.println("该元素第一次在数组中呈现的索引是："+index);
    }

    private static int getIndexByEle(int[] arr, int ele) {
        // 遍历数组，去查找
        for (int i = 0; i < arr.length; i++) {if (ele==arr[i]){return i;}
        }
        return  -1;// 如果咱们没有找到这个元素那么就返回 -1
    }
}

案例中查找元素 2 的索引，索引为 7；
运行后返回后果正确：

二分查找

应用二分查找查找出该元素在数组中第一次呈现的索引

  • 前提：该数组的元素必须有序
  • 思维：每一次都查找两头的元素，比拟大小就能缩小一半的元素

    具体代码实现：

public class TestArray2 {public static void main(String[] args) {
        // 二分查找：前提是数组元素必须有序
        int[] arr={10,20,30,40,50,60,70,80,90};
        int index=getIndexByEle(arr,40);
        System.out.println("该元素的索引是："+index);
    }

    private static int getIndexByEle(int[] arr, int ele) {
        // 定义最小索引，两头索引，最大索引
        int minIndex=0;
        int maxIndex=arr.length-1;
        int centerIndex=(minIndex+maxIndex)/2;
        while (minIndex<=maxIndex){
            // 如果需查找元素等于两头索引所对应元素，返回两头元素，示意找到
            if (ele==arr[centerIndex]){return centerIndex;}
            // 如果需查找元素大于两头索引所对应元素，挪动最小索引至两头索引处
            else if (ele>arr[centerIndex]){minIndex=centerIndex+1;}
            // 如果需查找元素小于两头索引所对应元素，挪动最大索引至两头索引处
            else if (ele<arr[centerIndex]){maxIndex=centerIndex-1;}
            // 从新计算两头索索引
            centerIndex=(minIndex+maxIndex)/2;
        }

        return -1;// 如果没有找到，就返回 -1
    }
}

案例中查找元素为 40，索引为 3；
运行后返回后果正确：

八大排序办法

冒泡排序

原理：数组元素两两比拟，替换地位，大元素往后放，通过一轮比拟后，最大的元素，就会被排到数组的最初

  • 图解：

代码局部：
先进行第一轮排序，看看成果：

public class ArraySort1 {public static void main(String[] args) {
        // 原理：数组元素两两比拟，后面元素大于前面元素则替换，否则不替换，每通过一轮，最大的元素会排到最初
        int[] arr={24,69,80,57,13};
        // 第一轮比拟, 遍历数组
        for (int i = 0; i < arr.length-1; i++) {
            // 从从第 0 个元素开始，前一个元素与后一个元素比拟
            if (arr[i]>arr[i+1]){
                // 满足条件则替换地位，利用 temp 两头变量存放元素
                int temp=arr[i];
                arr[i]=arr[i+1];
                arr[i+1]=temp;
            }
        }
        // 输入数组
        System.out.println(Arrays.toString(arr));

    }
}

上面进行多轮排序：
代码局部
笨办法：屡次 for 循环，比拟繁琐，反复循环，语句没养分，看看就好，次要是得能想到，为嵌套循环做筹备

public class ArraySort1 {public static void main(String[] args) {
        // 原理：数组元素两两比拟，后面元素大于前面元素则替换，否则不替换，每通过一轮，最大的元素会排到最初
        int[] arr={24,69,80,57,13};
        // 第一轮比拟, 遍历数组
        for (int i = 0; i < arr.length-1; i++) {
            // 从从第 0 个元素开始，前一个元素与后一个元素比拟
            if (arr[i]>arr[i+1]){
                // 满足条件则替换地位，利用 temp 两头变量存放元素
                int temp=arr[i];
                arr[i]=arr[i+1];
                arr[i+1]=temp;
            }
        }
        // 输入数组
        System.out.println(Arrays.toString(arr));

        // 第二轮比拟, 遍历数组
        for (int i = 0; i < arr.length-1-1; i++) {if (arr[i]>arr[i+1]){int temp=arr[i];
                arr[i]=arr[i+1];
                arr[i+1]=temp;
            }
        }
        // 输入数组
        System.out.println(Arrays.toString(arr));

        // 第三轮比拟, 遍历数组
        for (int i = 0; i < arr.length-1-1-1; i++) {if (arr[i]>arr[i+1]){int temp=arr[i];
                arr[i]=arr[i+1];
                arr[i+1]=temp;
            }
        }
        // 输入数组
        System.out.println(Arrays.toString(arr));

        // 第四轮比拟, 遍历数组
        for (int i = 0; i < arr.length-1-1-1-1; i++) {if (arr[i]>arr[i+1]){int temp=arr[i];
                arr[i]=arr[i+1];
                arr[i+1]=temp;
            }
        }
        // 输入数组
        System.out.println(Arrays.toString(arr));
    }
}

应用嵌套循环（语句精简，没有废话）：

public class ArraySort1 {public static void main(String[] args) {
        // 原理：数组元素两两比拟，后面元素大于前面元素则替换，否则不替换，每通过一轮，最大的元素会排到最初
        int[] arr={24,69,80,57,13};
        // 嵌套 for 循环，外层循环轮数，内层对每一轮内元素进行比拟
        for (int i = 0; i < arr.length - 1; i++) {for (int j = 0; j < arr.length-1-i; j++) {if (arr[j]>arr[j+1]){
                    // 替换地位
                    int temp=arr[j];
                    arr[j]=arr[j+1];
                    arr[j+1]=temp;
                }
            }
        }
        System.out.println(Arrays.toString(arr));

}

冒泡排序就介绍到这里~~~

抉择排序

原理：从 0 索引处开始，顺次和前面的元素进行比拟，小的元素往前放，通过一轮比拟后，最小的元素就会呈现在最小索引处
图解：

代码局部：多轮排序(优化前)

public class ArraySort2 {public static void main(String[] args) {
        // 原理：从 0 索引处开始，顺次个前面的元素进行比拟，小的元素往前放，通过一轮比拟，最小的元素就呈现在最小索引处
        int[] arr={24,69,80,57,13};
        // 第一轮比拟，从 0 索引处开始比
        int index=0;
        for (int i = 1; i < arr.length; i++) {if (arr[index]>arr[i]){int temp=arr[index];
                arr[index]=arr[i];
                arr[i]=temp;
            }
        }
        System.out.println(Arrays.toString(arr));
        // 第二轮
        index=1;
        for (int i = 1+index; i < arr.length; i++) {if (arr[index]>arr[i]){int temp=arr[index];
                arr[index]=arr[i];
                arr[i]=temp;
            }
        }
        System.out.println(Arrays.toString(arr));
        // 第三轮
        index=2;
        for (int i = 1+index; i < arr.length; i++) {if (arr[index]>arr[i]){int temp=arr[index];
                arr[index]=arr[i];
                arr[i]=temp;
            }
        }
        System.out.println(Arrays.toString(arr));
        // 第四轮
        index=3;
        for (int i = 1+index; i < arr.length; i++) {if (arr[index]>arr[i]){int temp=arr[index];
                arr[index]=arr[i];
                arr[i]=temp;
            }
        }
        System.out.println(Arrays.toString(arr));

    }
}

优化代码：嵌套循环：

public class ArraySort2 {public static void main(String[] args) {
        // 原理：从 0 索引处开始，顺次个前面的元素进行比拟，小的元素往前放，通过一轮比拟，最小的元素就呈现在最小索引处
        int[] arr={24,69,80,57,13};
        // 第一轮比拟，从 0 索引处开始比
        for (int index = 0; index < arr.length-1; index++) {for (int i = 1+index; i < arr.length; i++) {if (arr[index]>arr[i]){int temp=arr[index];
                    arr[index]=arr[i];
                    arr[i]=temp;
                }
            }
        }
        System.out.println(Arrays.toString(arr));
}

抉择排序就介绍到这里~~~

间接插入排序

原理：从 1 索引处开始，将前面的元素与前一位比，小于前一位则替换，再与前一位比，如果小于再替换，如此循环，插入之前的有序列表中使之仍放弃有序

（办法 1）：代码实现：

public class ArraySort3 {public static void main(String[] args) {
        // 间接插入排序：从 1 索引处开始，将前面的元素，插入之前的有序列表中使之仍放弃有序
        int[] arr={3,2,1,0,10,20,30,7,8};
        // 外层循环定义轮次
        for (int i = 1; i < arr.length; i++) {
            // 内层循环进行比拟插入
            int j=i;
            while (j>0 && arr[j]<arr[j-1]){int temp=arr[j];
                arr[j]=arr[j-1];
                arr[j-1]=temp;
                j--;
            }
        }
        System.out.println(Arrays.toString(arr));

    }
}

（办法 2）代码实现：

public class ArraySort3 {public static void main(String[] args) {
        // 间接插入排序：从 1 索引处开始，将前面的元素，插入之前的有序列表中使之仍放弃有序
        int[] arr={3,2,1,0,10,20,30,7,8};
        // 外层循环定义轮次
        for (int i = 0; i < arr.length; i++) {for (int j = i; j >0 ; j--) {if (arr[j]<arr[j-1]){int temp=arr[j];
                    arr[j]=arr[j-1];
                    arr[j-1]=temp;
                }
            }
        }
        System.out.println(Arrays.toString(arr));
}

因为很多中央须要应用前后元素值替换，因而封装成一个办法：代码如下：

public static void swapValue(int[] arr,int i,int j){int temp=arr[i];
        arr[i]=arr[j];
        arr[j]=temp;
    }

应用本人封装的办法：

for (int i = 0; i < arr.length; i++) {for (int j = i; j >0 ; j--) {if (arr[j]<arr[j-1]){
                    /*
                    int temp=arr[j];
                    arr[j]=arr[j-1];
                    arr[j-1]=temp;
                    */
                    // 间接调用替换办法，封装思维
                    swapValue(arr,j,j-1);
                }
            }
        }

间接插入排序就介绍到这里~~~

希尔排序

希尔排序又称放大增量排序

  • 根本思维：先将原表按增量 ht 分组；每个子文件依照直接插入法排序。同样，用下一个增量 ht/ 2 将文件再分为自问见，在直接插入法排序。直到 ht= 1 时整个文件排好序。
  • 要害：抉择适合的增量。
  • 希尔排序算法 9 -3：能够通过三重循环来实现。

图示：

** 将数组按步长为 5 的距离两两分为一组，每组两个元素进行比拟大小，小的搁置于后面，大的搁置于前面；
由此排序一次后，大抵能够将整个数组中较小的元素放在后面，较大的放在前面。**

上面数组长度为 8，第一次距离取 4，第二次距离取 2，第三次距离取 1，具体实现见下图：

代码实现(应用克努特序列，正当抉择增量)：

public class ArraySort4 {public static void main(String[] args) {
        // 希尔排序，对插入排序的优化，核心思想就是正当的选取增量，通过一轮排序后，就会让序列大抵有序
        // 而后一直的放大增量，进行插入排序，直到增量为 1 整个排序完结
        // 间接插入排序，其实就是增量为 1 的希尔排序

        int[] arr={46,55,13,43,17,94,5,70,11,25,110,234,1,3,66};
        shellSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    private static void shellSort(int[] arr) {
        // 定义一个增量
        /*
        // 第一轮
        int h=4;
        for (int i = h; i < arr.length; i++) {for (int j = i; j > h-1 ; j-=h) {if (arr[j]<arr[j-h]){swapValue(arr,j,j-h);
                }
            }
        }
        // 第二轮
        h=2;
        for (int i = h; i < arr.length; i++) {for (int j = i; j > h-1 ; j-=h) {if (arr[j]<arr[j-h]){swapValue(arr,j,j-h);
                }
            }
        }
        // 第三轮
        h=1;
        for (int i = h; i < arr.length; i++) {for (int j = i; j > h-1 ; j-=h) {if (arr[j]<arr[j-h]){swapValue(arr,j,j-h);
                }
            }
        }
        */

        // 希尔排序外围代码
        // 希尔排序的思维，正当的选取增量
        // 第一次增量能够选取数组长度的一半，而后一直的减半
        /*for (int h = arr.length / 2; h > 0; h /= 2) {for (int i = h; i < arr.length; i++) {for (int j = i; j > h - 1; j -= h) {if (arr[j] < arr[j - h]) {swapValue(arr, j, j - h);
                    }
                }
            }
        }*/
        // 增量的选取抉择数组长度的一半，还不是很正当，咱们能够应用一种序列，叫做克努特序列
        //int h = 1;
        //h = h * 3 + 1; //1,4,13,40,121,364
        // 依据克努特序列选取咱们的第一次增量
        int jiange = 1;
        while (jiange <= arr.length / 3) {jiange = jiange * 3 + 1;}
        for (int h = jiange; h > 0; h = (h - 1) / 3) {for (int i = h; i < arr.length; i++) {for (int j = i; j > h - 1; j -= h) {if (arr[j] < arr[j - h]) {swapValue(arr, j, j - h);
                    }
                }
            }
        }
    }

        // 封装元素替换办法
    public static void swapValue(int[] arr,int i,int j){int temp=arr[i];
        arr[i]=arr[j];
        arr[j]=temp;
    }

}

希尔排序就介绍到这里~~~

疾速排序

原理：分治法：比大小，再分区

  • 从数组中取出一个数，作为基准数
  • 分区：将比这个数大或等于的书全放到他的左边，小于他的数全放到他的右边。
  • 再对左右区间反复第二步，直到各区间只有一个数。

实现思路

  • 将基准数挖出造成第一个坑
  • 由后向前找比它小的数，找到后挖出此数填到前一个坑中
  • 由前向后找比它大或等于的数，找到后也挖出此数填到前一个坑中。
  • 再反复执行上述两步骤

代码实现：

public class ArraySort5 {public static void main(String[] args) {
        // 定义一个数组
        int[] arr={10,3,34,45,11,35,255,4,-1,-9,79,123};
        quickSort(arr,0,arr.length-1);
        System.out.println(Arrays.toString(arr));
    }

    // 疾速排序
    public static void quickSort(int[] arr,int start,int end) {
        // 找出分左右两区的索引地位，而后对左右两区进行递归调用
        if (start<end){int index=getIndex(arr,start,end);
            quickSort(arr,start,index-1);
            quickSort(arr,index+1,end);
        }
    }
    // 将基准数挖出造成第一个坑
    // 由后向前找比它小的数，找到后挖出此数填到前一个坑中
    // 由前向后找比它大或等于的数，找到后也挖出此数填到前一个坑中。// 再反复执行上述两步骤
    private static int getIndex(int[] arr, int start, int end) {
        int i=start;
        int j=end;
        int x=arr[i];
        while (i<j){
            // 由后向前找比它小的数，找到后挖出此数填到前一个坑中
            while (i<j&&arr[j]>=x){j--;}
            if (i<j){arr[i]=arr[j];
                i++;
            }
            // 由前向后找比它大或等于的数，找到后也挖出此数填到前一个坑中。while (i<j&&arr[i]<x){i++;}
            if (i<j){arr[j]=arr[i];
                j--;
            }

        }
        arr[i]=x;// 把基准数填到最初一个坑
        return i;
    }
}

疾速排序就介绍到这里~~~

归并排序

归并排序（Merge Sort）就是利用归并的思维实现排序的办法
原理：假如初始序列有 N 个记录，则能够看成是 N 个有序的子序列，每个子序列的长度为 1，而后两两归并，失去 N / 2 个长度为 2 或 1 的有序子序列，再两两归并。。。如此反复，直至失去一个长度为 N 的有序序列为止，这种排序办法称为 2 路归并排序

代码实现：

public class ArraySort6 {public static void main(String[] args) {
        // 原始待排序数组
        int[] arr={10,23,1,43,0,-3,1121,343,44,11,56,78,3,-1};
        // 咱们先给一个左右两边是有序的一个数组，先来进行归并操作
        //int[] arr={4,5,7,8,1,2,3,6};
        // 拆分
        chaifen(arr,0,arr.length-1);

        // 归并
        guiBing(arr,0,3,arr.length-1);

        // 输入原数组
        System.out.println(Arrays.toString(arr));
    }

    private static void chaifen(int[] arr, int startIndex, int endIndex) {
        // 计算两头索引
        int centerIndex=(startIndex+endIndex)/2;
        if (startIndex<endIndex){chaifen(arr,startIndex,centerIndex);
            chaifen(arr,centerIndex+1,endIndex);
            guiBing(arr,startIndex,centerIndex,endIndex);
        }
    }

    private static void guiBing(int[] arr, int startIndex, int centerIndex, int enIndex) {
        // 定义一个长期数组
        int[] tempArr=new int[enIndex-startIndex+1];
        // 定义右边数组的起始索引
        int i=startIndex;
        // 定义左边数组的起始索引
        int j=centerIndex+1;
        // 定义长期数组的起始索引
        int index=0;
        while (i<=centerIndex && j<=enIndex){if (arr[i]<=arr[j]){tempArr[index]=arr[i];
                i++;
            }else{tempArr[index]=arr[j];
                j++;
            }
            index++;
        }
        // 解决残余元素
        while (i<=centerIndex){tempArr[index]=arr[i];
            i++;
            index++;

        }
        while (j<=enIndex){tempArr[index]=arr[j];
            j++;
            index++;

        }
        // 将长期数组中的元素取到原数组中
        for (int k = 0; k < tempArr.length; k++) {arr[k+startIndex]=tempArr[k];
        }
    }
}

归并排序就介绍到这里~~~

基数排序

基数排序不同于之前的各类排序
后面的排序或多或少通过应用比拟和挪动记录来实现排序
而基数排序的实现不须要进行对关键字的比拟，只须要对关键字进行“调配”与“收集”两种操作即可实现

上面通过图来解释：

第一次排序：依照个位进行分组

分组后后果：

再将元素逐个取出：

第二次排序：依据十位上的数进行排序

再顺次将元素取出：

第三轮排序：依据百位上的数进行排序

最初将所有元素取出：

代码实现：

public class ArraySort7 {public static void main(String[] args) {
        // 基数排序：通过调配再收集的形式进行排序
        int[] arr={2,0,1,5,21,31,224,355,22,41,67,23,444,789,12,55,34,75};
        // 确定排序轮次
        // 获取数组中的最大值
        int max=getMax(arr);

        // 基数排序
        sortArray(arr);

        // 输入排序后的数组
        System.out.println(Arrays.toString(arr));

    }

    private static void sortArray(int[] arr) {
        // 定义二维数组，放 10 个桶
        int[][] tempArr=new int[10][arr.length];
        // 定义统计数组
        int[] counts=new int[10];
        int max=getMax(arr);
        int len=String.valueOf(max).length();
        // 循环轮次
        for (int i = 0,n=1; i < len; i++,n*=10) {for (int j = 0; j < arr.length; j++) {
                // 获取每个位上的数字
                int ys=arr[j]/n%10;
                tempArr[ys][counts[ys]++]=arr[j];
            }
            // 取出桶中的元素
            int index=0;
            for (int k = 0; k < counts.length; k++) {if (counts[k]!=0){for (int h = 0; h < counts[k]; h++) {
                        // 从桶中取出元素放回原数组
                        arr[index]=tempArr[k][h];
                        index++;
                    }
                    counts[k]=0;// 革除上一次统计的个数
                }
            }
        }
    }

    private static int getMax(int[] arr) {int max=arr[0];
        for (int i = 0; i < arr.length; i++) {if (arr[i]>max){max=arr[i];
            }
        }
        return max;
    }
}

基数排序就介绍到这里~~~

堆排序

堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种抉择排序

  • 将待排序序列结构成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。
  • 将其与开端元素进行替换，此时开端就为最大值
  • 而后将残余 n - 1 个元素从新结构成一个堆，这样就会失去 n 个元素的次小值
  • 如此重复的执行，便能失去一个有序序列了

    代码实现：

public class ArraySort8 {public static void main(String[] args) {
        // 定义一个数组
        int[] arr={1,0,6,7,2,3,4,5,8,9,10,52,12,33};

        // 调整成大顶堆的办法
        // 定义开始调整的地位
        int startIndex=(arr.length-1)/2;
        // 循环开始调
        for (int i = startIndex; i >=0 ; i--) {toMaxHeap(arr,arr.length,i);
        }
        //System.out.println(Arrays.toString(arr));
        // 通过下面的操作后，曾经把数组变成一个大顶堆，把根元素和最初一个元素进行调换
        for (int i = arr.length-1; i >0; i--) {
            // 进行调换
            int temp=arr[0];
            arr[0]=arr[i];
            arr[i]=temp;
            // 换完之后，咱们再把残余元素调成大顶堆
            toMaxHeap(arr,i,0);
        }
        System.out.println(Arrays.toString(arr));

    }

    /**
     *
     * @param arr 要排序的数组
     * @param size 调整的元素个数
     * @param index 从哪里开始调整
     */
    private static void toMaxHeap(int[] arr, int size, int index) {
        // 获取左右字节的索引
        int leftNodeIndex=index*2+1;
        int rightNodeIndex=index*2+2;
        // 查找最大节点所对应的索引
        int maxIndex=index;
        if (leftNodeIndex<size && arr[leftNodeIndex]>arr[maxIndex]){maxIndex=leftNodeIndex;}
        if(rightNodeIndex<size && arr[rightNodeIndex]>arr[maxIndex]){maxIndex=rightNodeIndex;}
        // 咱们来调换地位
        if(maxIndex!=index){int t=arr[maxIndex];
            arr[maxIndex]=arr[index];
            arr[index]=t;
            // 调换完之后，可能会影响到上面的子树，不是大顶堆，咱们还须要再次调换
            toMaxHeap(arr,size,maxIndex);
        }
    }

}

堆排序就介绍到这里~~~

最初

感激你看到这里，文章有什么有余还请斧正，感觉文章对你有帮忙的话记得给我点个赞，每天都会分享 java 相干技术文章或行业资讯，欢送大家关注和转发文章！

正文完
java
发表至： java
2020-09-02
 0
关于java:Spring-Boot-2x基础教程使用集中式缓存Redis
关于java:LeetCode033搜索旋转排序数组
关于java:你还在-for-循环里使用-拼接字符串明天不用来上班了
一时技痒撸了个动态线程池源码放Github了