Java之数组排序及二分法查找

冷不防 2022-05-12 09:26 225阅读 0赞

首先先介绍两种最基本的数组排序方法：**冒泡法**和**选择法**。  
**冒泡法排序：**依次比较相邻的两个元素，如果第一个比第二个大，则交换他们两个，如此一轮比较下来会产生一个最大的数位于数组末尾，第二次比较则进行到数组长度-1个元素，以此类推。

/** * 冒泡法排序(从小到大) * @param a 需要排序的数组 * @return 排序完成后的数组 */
        public static int[] sort1(int[] a) {
            for(int i = 0;i < a.length-1;i++) {
                for(int j = 0;j < a.length-1-i;j++) {
                    if(a[j]>a[j+1]) {
                        int temp;
                        temp = a[j];
                        a[j] = a[j+1];
                        a[j+1] = temp;
                    }
                }
            }
            return a;       
        }

**选择法排序：**先用第一个元素依次和剩下的元素进行比较，如果此元素大于另一个元素，则交换他们，依次类推，直至比较到最后一个元素。

/** * 选择法排序 * @param a * @return */
        public static int[] sort2(int[] a) {
            for(int i = 0;i < a.length;i++) {
                for(int j = i+1;j < a.length;j++) { 
                    if(a[i]>a[j]) {
                        int temp;
                        temp = a[i];
                        a[i] = a[j];
                        a[j] = temp;
                    }
                }
            }
            return a;
        }

**二分法查找：** 使用二分法查找的数组必须是已经进行排序好的数组，首先定义一个初始下标，一个结尾下标，然后用需要查找的数同数组中的中间元素进行对比，如果相等，则返回中间数组元素下标，如果大于此元素，则让初始下标等于中间下标加一，再次进行对比，直到返回一个中间下标或者未找到，反之亦然。（中间下标 = （初始下标 + 结尾下标） / 2）

/** * 二分法查找 * @param a 需要进行检索的数组 * @param idx 需要检索的值 * @return 检索结果（该值下标或-1：未找到） */
        public static int index(int[] a,int idx) {
            int min = 0;
            int max = a.length-1;   
            while(min <= max) {
                int middle = (min + max)/2;
                if(a[middle] == idx) {
                    return middle;
                }
                if(idx > a[middle]) {
                    min = middle+1;
                }
                else {
                    max = middle - 1;
                }
            }
            return -1;      
        }

下面对以上方法进行测试

public static void main(String[] args) {
            int[] a = {
       3,10,15,11,6,7};
            for(int x:sort1(a)) {
                System.out.print(x + "\t");
            }
            System.out.println();
            int[] b = {
       5,1,3,7,2,44,12,3};
            for(int y:sort2(b)) {
                System.out.print(y + "\t");
            }
            System.out.println();
            int[] c = sort2(b);
            System.out.println(index(c,22));
        }
        /** * output: * 3 6 7 10 11 15 * 1 2 3 5 7 12 44 * -1 */