搜索内容

有一个问题?

如果您有任何疑问,可以在下面询问或输入您要寻找的!

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

Java 0 232
生成海报
前程有光
前程有光 2020-09-02 06:05
阅读需:0

查找元素索引位置

基本查找

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

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

案例中查找元素为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]

(方法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]

由于很多地方需要使用前后元素值交换,因此封装成一个方法:代码如下:

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]

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

希尔排序

希尔排序又称缩小增量排序

  • 基本思想:先将原表按增量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] h-1 ; j-=h) {
                if (arr[j] h-1 ; j-=h) {
                if (arr[j] 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=x){
                j--;
            }
            if (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

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

基数排序

基数排序不同于之前的各类排序
前面的排序或多或少通过使用比较和移动记录来实现排序
而基数排序的实现不需要进行对关键字的比较,只需要对关键字进行“分配”与“收集”两种操作即可完成

下面通过图来解释:

第一次排序:按照个位进行分组

分组后结果:

再将元素逐一取出:

第二次排序:根据十位上的数进行排序

再依次将元素取出:

第三轮排序:根据百位上的数进行排序

最后将所有元素取出:

代码实现:

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 (leftNodeIndexarr[maxIndex]){
            maxIndex=leftNodeIndex;
        }
        if(rightNodeIndexarr[maxIndex]){
            maxIndex=rightNodeIndex;
        }
        //我们来调换位置
        if(maxIndex!=index){
            int t=arr[maxIndex];
            arr[maxIndex]=arr[index];
            arr[index]=t;
            //调换完之后,可能会影响到下面的子树,不是大顶堆,我们还需要再次调换
            toMaxHeap(arr,size,maxIndex);
        }
    }

}

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

最后

感谢你看到这里,文章有什么不足还请指正,觉得文章对你有帮助的话记得给我点个赞,每天都会分享java相关技术文章或行业资讯,欢迎大家关注和转发文章!

评论
  • 消灭零回复