冒泡排序法
? 原始数据：3 2 7 6 8
? 第1次循环：（最大的跑到最右边）
? 2 3 7 6 8（3和2比较，2<3 所以2和3交换位置）
? 2 3 7 6 8（3和7比较，3<7 所以不需要交换位置）
? 2 3 6 7 8（6和7比较，6<7 所以6和7交换位置）
? 2 3 6 7 8（7和8比较，7<8 所以不需要交换位置）
? 经过第1次循环，此时剩下参与比较的数据：2 3 6 7
? 第2次循环：
? 2 3 6 7（2和3比较，2<3，所以不需要交换位置）
? 2 3 6 7（3和6比较，3<6，所以不需要交换位置）
? 2 3 6 7? (6和7比较，6<7，所以不需要交换位置）
? 经过第2次循环，此时剩下参与比较的数据是：2 3 6
? 第3次循环：
? 2 3 6（2和3比较，2<3，所以不需要交换位置）
? 2 3 6（3和6比较，3<6，所以不需要交换位置）
? 经过第3次循环，此时剩下参与比较的数据是：2 3
? 第4次循环
?? 2 3（2和3比较，2<3，所以不需要交换位置）
??
? public class BubbleSort{
???? public static void main(String[] args){
?????? //这是int类型的数组对象
?????? int[] arr = {3,2,6,7,8};
?????? //经过冒泡排序算法对以上数组中元素进行排序
?????? //冒泡排序算法的核心是什么？
??????
?????? //7条数据，循环6次。以下的代码可以循环6次（冒泡排序法采用外层循环）
?????? int count = 0;
?????? for(int i=arr.length-1;i>0;i--){
????????? //不管是否需要交换，总之是要比较一次的
????????? count++;
???????? //9 8 10? 7 6 0 11
???????? for(int j=0;j<i；j++){
?????????? if(arr[i]>arr[j+1]){
????????????? //交换位置
???????????? //arr[j]和arr[j+1]交换
??????????? int temp;
??????????? temp = arr[j];
??????????? arr[j] = arr[j+1];
??????????? arr[j+1] = temp;
?????????? }
???????? }
??????? }
??????? System.out.println("比较次数:”+count);
?????? //输出结果
?????? for(int i=0;i<arr.length;i++){
?????????? System.out.println(arr[i]);
?????? }
????? }
?}
?
选择排序法比冒泡排序法的效率高
?高在交换位置上
?选择排序的交换位置是有意义的
?每一次从这“堆”参与比较的数据当中“找出最小值”
拿这个最小值和“参与比较的这堆最前面的元素”交换位置
?循环一次，然后找出参加比较的这堆数据中最小的。拿这个最小的值和
最前面的数据交换位置。
参与比较的数据：3 1 6 2 5
第1次循环之后的结果是： 1 3 6 2 5
下次参与比较的数据：3 6 2 5
第2次循环之后的结果是：2 6 3 5
下次参与比较的数据是：6 3 5
第3次循环之后的结果是：3 6 5
?下次参与比较的数据是： 6 5
第4次循环之后的结果是： 5 6
注意：5条数据，循环4次
冒泡排序和选择排序实际上比较的次数没变
交换位置的次数减少了
3 2 6 1 5
? 假设：
???? 第1个3是最小的
???? 3和2比较，发现2更小，所以此时最小的是2
???? 继续拿着2往下比对，2和6比较，2仍然是最小的
???? 继续拿着2往下比对，2和1比对，发现1更小，所以此时最小的是1
???? 继续拿着1往下比对，1和5比对，发现1还是小的，所以1就是最小的
???? 拿着1和最左边的3交换位置
?
? 2 6 3 5
?? 假设：
????? 第1个2是最小的
????? ……
??
? 6 3 5
? 假设6是最小的，6和3比对，发现3更小，所以此时最小的是3
? ……
?public class SelectSort{
??? public static void main(String[] args){
???????? int[] arr = {3,1,6,2,5};
???????? int count = 0;
???????? //选择排序
????? //5个数据循环4次（外层循环4次）
???? for(int i=0;i<arr.length-1;i++){
?????? //i的值是0 1 2 3
????? //i正好是“参加比较的这堆数据中”最左边那个元素的下标
???? //i是一个参与比较的这堆数据中的起点下标
??? //假设起点i下标位置上的元素是最小的
???????? int min = I;
???????? for(int j=i+1;j<arr.length;j++){
????????? count++;
?????????? if(arr[j]<arr[min]){
????????????? min = j;?? //最小值的元素下标是j?
???????? }
?? }
? //当i和min相等时，表示最初猜测是对的
?//当i和min不相等时，表示最初猜测是错的，有比这个元素更小的元素
//需要拿着这个更小的元素和最左边的元素交换位置
?if(min!=i){
?? //表示存在更小的数据
? //arr[min]最小的数据
?//arr[i]最前面的数据
??? int temp;
??? temp = arr[min];
??? arr[min = arr[i];
??? arr[i] = temp;
??? }
? }
? System.out.println("比较次数"+count);
? //排序之后遍历
? for(int i=0;i<arr.length;i++){
????? System.out.println(arr[i]);
?? }
?}
}
?数组的元素查找
?? 数组元素查找两种方式：
????? 第一种方式：一个一个挨着找，直到找到为止
????? 第二种方式：二分法查找（算法），这个效率较高
?public class ArraySearch{
?? public static void main(String[] args){
????? //这个例子演示第一种方式
????? int[] arr = {4,5,6,87,8};
???? //需求：找出87的下标。一个一个挨着找
???? for(int i=0;i<arr.length;i++){
?????? if(arr[i]==87){
????????? System.out.println("87元素的下标是："+i);
????????? return;
?????? }
???? }
??? //程序执行到此处，表示没有87
?? System.out.println("87不存在该元素！");
??
? //最好以上的程序封装到一个方法，思考：传什么参数？返回什么值？
?//传什么：第一个参数是数组，第二个参数是被查找的元素
?//返回值：返回被查找的这个元素的下标，如果找不到返回-1
?int index = arraySearch(arr,87);
?System.out.println(index == -1?"该元素不存在1":"该元素下标是："+index):
? }
? //从数组中检索某个元素的下标（返回的是第一个元素的下标）
?//arr 被检索的数组
//ele 被检索的元素
//大于等于0的数表示元素的下标，-1表示该元素不存在
? public static void arraySearch(int[] arr,int ele){
????? for(int i=0;i<arr.length;i++){
????????? if(ele == arr[i]){
????????????? return I;
????????? }
?????? }
?? return -1;
? }
}
关于查找算法中的：二分法查找
10（下标0）11 12 13 14 15 16 17 18 19 20（下标10） arr数组
通过二分法查找，找出18这个元素的下标：
?（0+10）/2-->中间元素的下标：5
拿着中间这个元素和目标要查找的元素进行对比：
? 中间元素是：arr[5]-->15
? 15<18(被查找的元素）
? 被查找的元素18在目前中间元素15的右边
再重新计算一个中间元素的下标：
? 开始下标是：5+1
? 结束下标是：10
? （6+10）/2-->8
?8下标对应的元素arr[8]是18
?? 找到的中间元素正好和被查找的元素18相等，表示找到了：下标为8
?二分法查找的终止条件：一直折半，直到中间的那个元素恰好是被查找的元素
?
二分法查找算法是基于排序的基础之上。（没有排序的数据是无法查找的）
?publc class ArrayUtil{
?? public static void main(String[] args){
????? int[] arr = {100,200,230,235,600,1000,2000,9999);
????? //找出arr这个数据中200所在的下标
???? //调用方法
???? int index = binarySearch(arr,200);
???? System.out.println(index==-1?"该元素不存在!":"该元素下标”+index);
??? }
?? // dest 目标元素
? //-1表示该元素不存在，其他表示返回该元素的下标
?? public static void binarySearch(int[] arr,int dest){
???? //开始下标
???? int begin = 0;
??? //结束下标
???? int end = arr.length-1;
????
???? //开始元素的下标只要在结束元素下标的左边，就有机会继续循环
???? while(begin<=end){
???? //中间元素下标
???? int mid = (begin+end)/2;
???? if(arr[mid]==dest){
?????? return mid;
???? }else if(arr[mid]<dest){
?????? //目标在“中间”的右边
????? //开始元素下标需要发生变化（开始元素的下标需要重新赋值）
????? begin = mid +1;? //一直加
???? }else{
????? //arr[mid]>dest
????? //目标在“中间”的左边
???? //修改结束元素的下标
?????? end = mid -1;? //一直减
???? }
??? }
?? return -1;
?}
? 10（下标是0） 23 56 89 100 111 222 235 500 600（下标9）arr数组
?目标：找出600的下标
?（0+9）/2-->4(中间元素的下标）
?arr[4]这个元素就是中间元素：arr[4]是100
?100<600
? 说明被查找的元素在100的右边
? 那么此时开始下标变成：4+1
?
?（5+9）/2-->7（中间元素的下标）
?? arr[7]对应的值是：235
?? 235<600
?? 说明被查找的元素在235的右边
??
?? 开始下标有进行了转变：7+1
?? （8+9）/2-->8
???? arr[8]-->500
???? 500<600
???? 开始元素的下标又发生了变化：8+1
???? (9+9)/2-->9
???? arr[9]是600，正好和600相等，此时找到了