首页 > > 程序设计 > Java技术 >

java基础（16）、数组的高级应用--冒泡排序、选…

2018-06-18 02:00:17来源：未知阅读 ()

数组排序

一.　　冒泡排序

二.　　选择排序

三.　　优化选择排序

四.　　二分法查找算法的实现

一.　　冒泡排序

将数组元素按【从小到大排序】为例

　　思路：依次对临近的两个元素对比，将最大值放在数组最后；再将剩余的元素对比，大值放在剩余元素的最后. . . 以此循环，最后元素就是按从小到大排列。

1.1.　　做之前，先了解这个操作：把数组的最大值放在末尾

　　将元素1和元素2对比，如果元素1的值大，则元素2和元素1的值互换（此时元素2为大值）；再让元素2和元素3对比. . ( 保留大值). . 元素3和元素4对比 . . . 依次类推，对比完全部的元素后（因是按照当前元素和下一个元素进行的对比，所以当前元素为倒数第二个元素时，就可完成全部的元素对比，也就是对比了【数组长度-1次】），则最后的元素就是最大值；

1             for (int i = 0; i < arr.length - 1; i++) {
2                 //若当前元素比下一个元素大，则将这两个元素互换
3                 if(arr[i] > arr[i+1]){    
4                     int temp = arr[i];
5                     arr[i] = arr[i+1];
6                     arr[i+1] = temp;
7                 }

1.2.　　【1.1】的基础上，将其余的元素按照从小到大循环排序：

　　使用【1.1】的方法，将剩下的元素再进行最大值的对比（对比的次数比【1.1】的少一次，就可进行剩余元素的对比）；按此思路循环即可（循环一次，大值就放在【循环元素的】后面；当循环到第二个元素时，第一个元素就是最小值，也就是循环了【数组长度-1次】）。

 1         int[] arr = {1,3,5,1,2,7,9};
 2         //2、循环一次，就将一个大值放在数组后面；当循环到第二个元素时，第一个元素就已经是最小值，故循环【数组长度 - 1次】即可。
 3         for(int j = 0 ;j < arr.length - 1 ;j++){    
 4             for (int i = 0; i < arr.length - 1 - j; i++) {
 5                 //1、若当前元素比下一个元素大，则将这两个元素互换
 6                 if(arr[i] > arr[i+1]){    
 7                     int temp = arr[i];
 8                     arr[i] = arr[i+1];
 9                     arr[i+1] = temp;
10                 }
11             }
12         }
13         for (int i = 0; i < arr.length; i++) {
14             System.out.print(arr[i]+" ");
15         }

二.　　选择排序法

将数组元素按【从小到大排序】为例

　　思路：将第一个元素与之后的元素对比，若有值比其小的元素，则将这两个元素互换（保证第一个元素为最小值）；然后第二个元素与之后的元素对比 . . . 依次循环。

2.1.　　做之前，先了解这个操作：将数组的最小值放在最前面

　　　思路：将第一个元素，与之和的元素挨个对比，期间若有值比其大的元素，则将这两个元素互换（循环到【数组长度-1次】后，则完成所有元素的对比）。

        for (int i = 0; i < arr.length - 1; i++) {
            //如果第一个元素比之后的元素大，则和其元素互换，循环完毕后，arr[0]是数组的最小值。
            if(arr[0] > arr[i+1]){
                int temp = arr[0];
                arr[0] = arr[i + 1];
                arr[i + 1] = temp;
            }
        }

2.2.　　【2.1】的基础上，将其余的元素按照从小到大循环排序：

　　使用【2.1】的（内部）循环后，再将第二个元素与之后的所有元素进行对比（因是第二元素个开始，故循环的次数比【2.1】少一次），按此思路（外部）循环即可（每次循环对比的次数，都比上一次少一次）

　　分析1：（外部）循环第一次，用第一个元素和其他元素对比；循环第二次，用第二个元素与其他元素对比 . . . 故（外部）循环的次数【i】与做对比的元素索引符合【arr[i]】

　　分析2：（内部）循环对比的次数，每次比上次少一次，将外部循环的次数【i】，符合内部循环的循环初始值。　

 1         int[] arr = {1,3,5,1,2,7,9};
 2         
 3         for (int j = 0; j < arr.length; j++) {
 4             //2、因每完成一次循环，下次循环次数需要少一次；外部循环的值给内部循环，可达到该效果
 5             for (int i = j; i < arr.length - 1; i++) {
 6                 //1、如果第一个元素比之后的元素大，则和其元素互换，循环完毕后，arr[j]是其在内与之后元素中的的最小值。
 7                 if(arr[j] > arr[i+1]){
 8                     int temp = arr[j];
 9                     arr[j] = arr[i + 1];
10                     arr[i + 1] = temp;
11                 }
12             }
13         }

三. 　　优化选择排序法

将数组元素按【从小到大排序】为例

　　因选择排序法需要进行某元素与之后所有的元素对比，并进行元素互换的过程，若数组的长度很长，则元素互换需要耗费较多资源

　　优化思路：再选择排序法的基础上，设置变量index（代表起点对比元素的索引），和变量value（代表起点元素的值），当出现比其值小的元素时，将该元素的值和索引赋值给变量（赋值耗费的资源大大低于元素互换）；然后将代表最小值的变量索引与起点元素索引对比，若不相同，则将起点元素与最小值元素互换（这样循环下去，以较少的元素互换次数，即可完成排序）。

 1         for (int i = 0; i < arr.length - 1; i++) {
 2             int index = i;
 3             int value = arr[i];
 4             //若出现比起点元素值更好的元素，将该元素的索引和值赋给起点元素变量。
 5             for (int j = i + 1; j < arr.length; j++) {
 6                 if (value > arr[j]) {
 7                     value = arr[j];
 8                     index = j;
 9                 }
10             }
11             //若最小值的索引（index）与起点索引不同，则将最小值的元素和起点元素互换
12             if (i != index) {
13                 int temp = arr[i];
14                 arr[i] = arr[index];
15                 arr[index] = temp;
16             }
17         }

四.　　二分法查找算法的实现

使用前提：数组元素必须是从小到大有序排列的

1、设置变量：左边界索引变量、右边界索引变量、中间值索引变量、需要查询的值；

1     int min = 0;    //左边界索引
2     int max = arr.length - 1;    //右边界索引
3     int mid = (min + max) / 2;    //中间值索引
4     int value = 1;    //需要查询的值

2、循环条件：若中间值和需要查找的值（value）不相等，则while循环（若相等，则直接返回中间值索引）；

1     while (arr[mid] != value) {
2     
3     }

3、循环体：判断要查询的值和中间值的大小，若比中间值小，则将右边界索引改为中间值索引-1，反之则将左边界改为索引+1；形成新的查询区域，再计算出新的中间索引；如此循环查询；

1     if (value > arr[mid]) {
2         min = mid + 1;
3     } else if (value < arr[mid]) {
4         max = mid - 1;
5     }
6     mid = (min + max) / 2;    //重新计算中间的索引值

4、停止循环：若“中间值到边界都还没有匹配成功”则停止循环，并返回一个不存在的索引（如 -1）；

1     if (min > max) {
2         return -1;
3     }

5、根据返回值判断。

1     if (index == -1) {
2         System.out.println("no such element");
3     } else {
4         System.out.println("index is : " + index);
5     }

完整代码

 1 public class Demo1 {
 2     /*
 3      * 二分查找 折半查找 前提:要找的数组必须是有序的. 每次都用中间的元素和要找的元素进行比较
 4      */
 5 
 6     public static void main(String[] args) {
 7         int[] arr = { 1, 2, 3, 6, 7, 8, 9 };
 8         int index = binarySearch(arr, 3);
 9         // 对返回值进行判断
10         if (index == -1) {
11             System.out.println("no such element");
12         } else {
13             System.out.println("index is : " + index);
14         }
15     }
16 
17     // 自定义方法,折半查找
18     public static int binarySearch(int[] arr, int value) {
19         int min = 0;                 // 左边界索引
20         int max = arr.length - 1;     // 右边界索引
21         int mid = (min + max) / 2;     // 中间值索引
22 
23         while (arr[mid] != value) {
24             // 判断要找的数落在左边还是右边
25             if (value > arr[mid]) {
26                 min = mid + 1;
27             } else if (value < arr[mid]) {
28                 max = mid - 1;
29             }
30             
31             mid = (min + max) / 2; // 重新计算中间的索引
32             
33             // 没有找到的条件判断
34             if (min > max) {
35                 return -1;
36             }
37         }
38         return mid;
39     }
40 }