黑马程序员技术交流社区

标题: java基础之排序 [打印本页]
作者: 0416-孙磊    时间: 2015-5-8 22:03
标题: java基础之排序
2、数组排序
        冒泡排序：
                A: 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
                B: 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
                C: 针对所有的元素重复以上的步骤，除了最后一个。
                D: 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
               
                public static void bubbleSort(int[] arr) {
                        // 外循环控制比较的次数
                        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;
                                        }
                                }
                        }
                }
       
        选择排序：
                每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。
                每次比较仅做一次交换。
                public static void selectionSort(int[] arr) {
                        // 外循环控制比较的次数
                        for (int i = 0; i < arr.length - 1; i++) {
                                // 定义变量，用于记录每次比较中最小值的索引
                                int mark;
                                // 内循环控制每次比较中，元素比较的过程。每次需要比较的数据是逐渐减少的。
                                for (int j = i + 1; j < arr.length; j++) {
                                        mark = i;
                                        if (arr[mark] > arr[j]) {
                                                mark = j;
                                        }
                                        // 判断，如果最小值不是每次比较时的第一个，将这个最小值交换到每次比较的起始索引处。
                                        if (mark != i) {
                                                int temp = arr;
                                                arr = arr[mark];
                                                arr[mark] = temp;
                                        }
                                }
                        }
                }
       
        练习：对字符串中字符进行自然排序。
                思路：
                        A:把字符串转换成字符数组。
                        B:对字符数组进行排序。
                        C:把排序后的字符数组转换成字符串。
                // main method
                main {
                        String s = "basckd";
                        // A:
                        char[] chs = s.toCharArray();
                        // B:
                        bubbleSort(chs);
                        // C:
                        String result = new String(chs); // String.copyValueOf();  // String.valueOf();
                }
                // 排序方法(采用冒泡排序)
                public static void bubbleSort(char[] chs) {
                        for (int i = 0; i < chs.length - 1; i++) {
                                for (int j = 0; j < chs.length - 1 - i; j++) {
                                        if (chs[j] > chs[j + 1]) {
                                                char temp = chs[j];
                                                chs[j] = chs[j + 1];
                                                chs[j + 1] = temp;
                                        }
                                }
                        }
                }
3、数组查找。
        问题提出：        已知int[] arr = {37, 92, 54, 18, 76};
                                求元素92索引是多少？
        普通查找：遍历数组，把数组中的元素与给定的值依次进行比较，一旦查找到，返回该元素索引，如果没有，返回-1.
                public static void commonSearch(int[] arr, int target) {
                        for (int i = 0; i < arr.length; i++) {
                                if (arr == target) {
                                        return i;
                                }
                        }
                        return -1;
                }
       
        思考：效率问题。如果数组较大，想查找的元素位于数组索引较大处，要将数组全部遍历才能找到。
       





欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) 黑马程序员IT技术论坛 X3.2