Java数组练习

Myth丶恋晨 2021-12-10 07:34 416阅读 0赞

# Java数组练习 #

### 文章目录 ###

*  Java数组练习
 *   *  一、依次输出Java元素的值
     *  二、数组排序（选择排序）
     *  三、“数三退一”
     *  四、二分法查找（折半查找）

## 一、依次输出Java元素的值 ##

public class InputArrayElem {
        public static void main(String[] args) {
            int[] a = {1, 5, 3, 7, 9, 2, 4, 8, 6};
            for (int i = 0; i < a.length; i++) {
                System.out.print(a[i] + " ");
            }
        }
    }

输出结果如下：  
![输出结果][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L015c2t5OTg0_size_16_color_FFFFFF_t_70]

## 二、数组排序（选择排序） ##

public class ArraySort {
        /**
         * 选择排序-每遍历外部循环一次，就能遍历出来一个最小的数（即依次可以遍历出第一个最小、第二最小... ...）
         *
         * @param args
         */
        public static void main(String[] args) {
            int[] a = {1, 5, 3, 7, 9, 2, 4, 8, 6};
            for (int i = 0; i < a.length; i++) {
                for (int j = i + 1; j < a.length; j++) {
                    if (a[i] > a[j]) {
                        int temp = a[i];
                        a[i] = a[j];
                        a[j] = temp;
                    }
                }
            }
            inputArrayElem(a);
        }
    
        private static void inputArrayElem(int a[]) {
            for (int i = 0; i < a.length; i++) {
                System.out.print(a[i] + " ");
            }
        }
    }

输出结果如下：  
![程序输出结果][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L015c2t5OTg0_size_16_color_FFFFFF_t_70 1]

上面这张排序效率不是很高，因为每次交换的每一个内部循环都要交换多次。  
想要提高效率的大致思路是：我们可以在比较的时候，记录本次循环中的“最小值”，如果发现下面有比它小的值，则记录其位置，然后更换“最小值”就行了。代码如下：

public class ArraySort {
        /**
         * 选择排序（高效率版）-每遍历外部循环一次，就能遍历出来一个最小的数（即依次可以遍历出第一个最小、第二最小... ...）
         *
         * @param args
         */
        public static void main(String[] args) {
            int[] a = {1, 5, 3, 7, 9, 2, 4, 8, 6};
            int k,temp;
            for (int i = 0; i < a.length; i++) {
                k = i;//记录当前位置
                for (int j = k + 1; j < a.length; j++) {
                    if (a[k] > a[j]) {
                        k = j;
                    }
                }
                if (k != i) {
                    temp = a[i];
                    a[i] = a[k];
                    a[k] = temp;
                }
            }
            inputArrayElem(a);
        }
    
        /**
         * 输出数组元素
         *
         * @param a 数组名称
         */
        private static void inputArrayElem(int a[]) {
            for (int i = 0; i < a.length; i++) {
                System.out.print(a[i] + " ");
            }
        }
    }

## 三、“数三退一” ##

规则如下：“数三退一”意思就是，很多人手拉手围成一圈，首先事先确定一个开头的人，从开头的人依次开始报数，数到三的退出，退出的人的下一位重新开始报数，以此类推，剩余一个人，游戏结束。问题如下：现在有500个人玩数三退一的游戏，问最后剩余的那个人，刚开始排名是什么，请编写算法实现（双向回环列表）。

*  数三退一
     */
    public class CalcuNumber {
        public static void main(String[] args) {
            boolean arr[] = new boolean[500];
            for(int i = 0;i<arr.length;i++){
                arr[i] = true;
            }
            int leftCount = arr.length;//剩余人数
            int countNum = 0;//计数器
            int index = 0;//现在数到第几个人
    
            while (leftCount > 1){
                if(arr[index] == true){
                    countNum++;//如果还在圈里，则继续报数
                    if(countNum == 3){
                        countNum = 0;//计数器归零
                        arr[index] = false;//数到三的退出
                        leftCount--;
                    }
                }
                index ++;
                if(index == arr.length){//数到头后，从头继续开始数
                    index = 0;
                }
            }
            for(int i = 0;i < arr.length;i++){
                if(arr[i] == true){
                    System.out.println(i);
                }
            }
    
        }
    }

输出结果：  
![输出结果][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L015c2t5OTg0_size_16_color_FFFFFF_t_70 2]输出结果为435，即最后剩余的那个人排名是436。

## 四、二分法查找（折半查找） ##

通常情况下，查找都是建立在已经排好序的基础上，否则，只能进行从头开始查找，效率低下。二分法实现的思路是在已经排好序（假设从小到大排列）的基础上，取出中间的数和要查找的数进行比较，如果比中间的数小，则以中间的数的左侧的数为终点，以开头的数为起点继续进行二分查找；如果比中间数大，则以中间数的右侧的数为起点，原来的终点不变，继续进行查找，以此类推，直至查找结束。示例如下：

public class SearchNumber {
        public static void main(String[] args) {
            int array[] = {1,3,6,8,9,10,12,18,24,32};
            int i = 12;//要查找的数
            System.out.println(binarySearch(array,i));
        }
    
        /**
         * 二分查找
         * @param array 数组
         * @param number 要查找的数
         * @return 查找的数在数组中的位置，-1表示为未找到
         */
        private static int binarySearch(int array[], int number){
            int start = 0;
            int end = array.length - 1;
            while (start <= end){
                int m = (start + end) / 2;
                if(array.length == 0){
                    return -1;
                }
                if(number == array[m]){
                    return m;
                }
                if(number > array[m]){
                    start = m + 1;
                }else if(number < array[m]){
                    end = m - 1;
                }
            }
            return -1;
        }
    }

输出结果：  
![输出结果][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L015c2t5OTg0_size_16_color_FFFFFF_t_70 3]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L015c2t5OTg0_size_16_color_FFFFFF_t_70]: /images/20211210/c212f043ac004332a81b5dfffb19a1f1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L015c2t5OTg0_size_16_color_FFFFFF_t_70 1]: /images/20211210/8212e4bce98b4dc6ab337566f97bb895.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L015c2t5OTg0_size_16_color_FFFFFF_t_70 2]: /images/20211210/512a974a92fc4675ac89db6dc524961f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L015c2t5OTg0_size_16_color_FFFFFF_t_70 3]: /images/20211210/fe9fef19b4bc4fee963f35957015c65c.png