一、冒泡排序法

冒泡排序法

原始数据: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

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

//i的值是0 1 2 3

//i正好是“参加比较的这堆数据中”最左边那个元素的下标

//i是一个参与比较的这堆数据中的起点下标

//假设起点i下标位置上的元素是最小的

int min = I;

for(int j=i+1;j

count++;

if(arr[j]

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

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

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

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相等,此时找到了