查找元素索引位置

基本查找

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

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相关技术文章或行业资讯，欢迎大家关注和转发文章！