java的冒泡_Java 排序算法

今天药忘吃喽~ 2022-11-04 00:53 73阅读 0赞

冒泡排序：

比较相邻两个数的大小，如果左边大于右边，就交换左右两边的数据，否则不交换，当第一轮比较完成后，序列数中最大的数会排序到最右边；然后在进行其他数比较，比较原理相同，完成比较后，序列数会从左到右从小到大排列；

原始数据：9 8 10 7 6 0 11

第一轮循环：比较的数据(9 8 10 7 6 0 11)

8 9 10 7 6 0 11　　(第1次比较，交换)

8 9 10 7 6 0 11　　 (第2次比较，不交换)

8 9 7 10 6 0 11　　 (第3次比较，交换)

8 9 7 6 10 0 11　　 (第4次比较，交换)

8 9 7 6 0 10 11　　 (第5次比较，交换)

8 9 7 6 0 10 11　　 (第6次比较，不交换)

第二轮循环：比较的数据(9 8 10 7 6 0)

8 9 7 6 0 10　　(第1次比较，交换)

8 7 9 6 0 10　　(第2次比较，交换)

8 7 6 9 0 10　　(第3次比较，交换)

8 7 6 0 9 10　　(第4次比较，交换)

8 7 6 0 9 10　　(第5次比较，不交换)

第三轮循环：比较的数据(8 9 7 6 0)

8 9 7 6 0　　(第1次比较，不交换)

8 7 9 6 0　　(第2次比较，交换)

8 7 6 9 0　　(第3次比较，交换)

8 7 6 0 9　　(第4次比较，交换)

第四轮循环：比较的数据(8 7 6 0)

7 8 6 0　　(第1次比较，交换)

7 6 8 0　　(第2次比较，交换)

7 6 0 8　　(第3次比较，交换)

第五轮循环：比较的数据(7 6 0)

6 7 0　　(第1次比较，交换)

6 0 7　　(第2次比较，交换)

第六次循环：比较的数据(6 0)

0 6　　(比较一次，交换)

总结：7个数总共要比较6轮(数组长度arr.length-1次)，在第一轮中要每个数之间要比较6次，第二轮中剩余的数要比较5次，以此类推；

程序示例：

public class BubbleSort \{

public static void main(String\[\] args) \{

int\[\] arr = \{9, 8, 10, 7, 6, 0, 11\};

int count1 = 0;

int count2 = 0;

for (int i = arr.length - 1; i > 0; i--) \{ //外层控制循环次数

for (int j = 0; j < i; j++) \{//内层控制比较次数

count1++;

if(arr\[j\] > arr\[j+1\])\{

count2++;

int temp = arr\[j\];

arr\[j\] = arr\[j+1\];

arr\[j+1\] = temp;

//遍历数组

for (int i = 0; i < arr.length; i++) \{

System.out.print(arr\[i\]+",");

System.out.println();

System.out.println("总共需要比较"+ count1+"轮"); //21

System.out.println("总共需要交换"+ count2+"次"); //13

选择排序：

每次都从需要排序的元素中挑选出最小的数和最前面的数进行交换。最小元素的挑选：先把首元素假设为最小的元素然后一次和后面的元素比较，如果发现更小的交换数组元素的下标

原始数据：9 8 10 7 6 0 11

第一轮循环：比较原始数据(9 8 10 7 6 0 11)

0 8 10 7 6 9 11

第二轮循环：比较剩余的元素(8 10 7 6 9 11)

6 10 7 8 9 11

第三轮循环：比较剩余的元素(10 7 8 9 11)

7 10 8 9 11

第四轮循环：比较剩余的元素(10 8 9 11)

8 10 9 11

第五轮循环：比较剩余的元素(10 9 11)

9 10 11

第六轮循环：比较剩余的元素(10 11)

10 11

程序实现：

public classSelectSort \{public static voidmain(String\[\] args) \{int arr\[\] = \{9, 8, 10, 7, 6, 0, 11\};int count1 = 0;int count2 = 0;for (int i = 0; i < arr.length - 1; i++) \{int min =i; //先假设首元素是最小的for (int j = i+1; j < arr.length; j++) \{

count1++;if(arr\[j\]

min=j;

\}if(min !=i)\{ //如果比较最后发现了更小的元素，则min!=i，则交换首元素和最小的元素；

count2++;int temp =arr\[min\];

arr\[min\]=arr\[i\];

arr\[i\]=temp;

\}for (int i = 0; i < arr.length; i++) \{

System.out.print(arr\[i\]+",");

System.out.println();

System.out.println("总共需要比较"+ count1+"轮"); //21

System.out.println("总共需要交换"+ count2+"次"); //5

总结：