黑马程序员技术交流社区

标题: 关于数组排序，最大值，最小值，二分超找 [打印本页]

---

作者: 董将    时间: 2012-12-19 12:58
标题: 关于数组排序，最大值，最小值，二分超找
import java.util.Arrays;
/*
Arrays.sort(数组)
Arrays.binarySearch(数组, key)
*/

class SortDemo {
        public static void main(String[] args) {
                int[] arr = {40, 25, 68, 58, 77, 13, 9, 28, 63};
                sort3(arr);
                System.out.println(Arrays.toString(arr));
               
                int index = binarySearch(arr, 63);
                System.out.println(index);
               
//                int index = indexOf(arr, 9);
//                System.out.println(index);
/*
                String str = Arrays.toString(arr);
                System.out.println(str);
               
                sort1(arr);//排序了
               
                str = Arrays.toString(arr);
                System.out.println(str);
               
                sort2(arr);
                str = Arrays.toString(arr);
                System.out.println(str);
*/
/*
                sort3(arr);
                System.out.println(Arrays.toString(arr));               
*/               
        }
       
        public static int binarySearch(int[] arr, int key) {
                //默认的范围是整个数组
                int begin = 0;//范围的开始
                int end = arr.length-1;//范围的结束
                int m; //范围的中心点
                while(begin <= end) {
                        m = (begin + end) / 2;//找到当前范围的中心。
                        if(arr[m] == key) {//让key与中心点元素进行比较，如果相等，说明找到了。
                                return m;//返回m.
                        }
                        if(key > arr[m]) {//当key比大于中心点元素
                                begin = m + 1;//开始位置从中心点+1
                        } else {
                                end = m - 1;//当key比中心点元素小，那么结束位置就是中间点-1
                        }
                }
                return -1;
        }
       
        /*
         *把参数在数组中的下标位置返回
         */
        public static int indexOf(int[] arr, int key) {
                // 遍历所有的元素
                for(int i = 0; i < arr.length; i++) {
                        //当每个元素与key比较，如果相等，把当前元素的下标返回
                        if(arr[i] == key) {
                                return i;
                        }
                }
                //当循环结束，还没有返回。
                //说明没有找到，那么返回-1，因为没有下标为负数，表示没有找到。
                return -1;
        }
       
        /*
         *冒泡
         *外循环走一格，内循环走完。
         *这时会有一最大值沉底！这说明一下躺就不用再给这个最大值排序。
         */
        public static void sort3(int[] arr) {
                for(int i = 0; i < arr.length; i++) {
                        for(int j = 0; j < arr.length-i-1; j++) {
                                if(arr[j] > arr[j+1]) {
                                        swap(arr, j, j + 1);
                                }
                        }
                }
        }
       
        public static void swap(int[] arr, int x, int y) {
                int t = arr[x];
                arr[x] = arr[y];
                arr[y] = t;
        }
       
        //int[] arr = {9,8,2,3,5,6,1,4,7};
        public static void sort2(int[] arr) {
                for(int i = 0; i < arr.length - 1; i++) {
                        for(int j = i + 1; j < arr.length; j++) {
                                if(arr[i] > arr[j]) {
                                        int t = arr[i];
                                        arr[i] = arr[j];
                                        arr[j] = t;
                                }
                        }
                }
        }
       
        /*
         *选择排序
         */
        public static void sort1(int[] arr) {
                /*
                 *锁定0 ~ 8
                 *当锁定0位置时，把0~9之间最大值的下标找到，然后让0与最大值下标交换
                 *当锁定1位置时，把1~9之间最大值的下标找到，然后让1与最大值下标交换
                 */
                for(int i = 0; i < arr.length - 1; i++) {
                        int maxIndex = maxIndex(arr, i);
                        //i 与 maxIndex交换
                        if(i != maxIndex) {//如果i本身就是最大值下标，那就没有必要去交换了。
                                swap(arr, i, maxIndex);
                        }
                }
        }
       
        // 从指定的位置，即from开始，向后查找，找出最大的值的下标。
        public static int maxIndex(int[] arr, int from) {
                int maxIndex = from;//maxIndex表示下标
                for(int i = from + 1; i < arr.length; i++) {
                        if(arr[maxIndex] < arr[i]) {
                                maxIndex = i;
                        }
                }
                return maxIndex;
        }

/*       
        // 求参数数组中，最大的值的下标
        public static int maxIndex(int[] arr) {
                int maxIndex = 0;//maxIndex表示下标
                for(int i = 1; i < arr.length; i++) {
                        if(arr[maxIndex] < arr[i]) {
                                maxIndex = i;
                        }
                }
                return maxIndex;
        }
*/
       
        // 求参数数组中的最大值
        public static int max(int[] arr) {
                int max = arr[0];
                for(int i = 1; i < arr.length; i++) {
                        if(max < arr[i]) {
                                max = arr[i];
                        }
                }
                return max;
        }
}
欢迎补充各种排序方式

---

作者: 许庭洲    时间: 2012-12-19 20:00
值得学习ing!

---

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

黑马程序员IT技术论坛 X3.2