冒泡排序
冒泡排序(Bubble Sort)是基于交换的排序,每次遍历需要排序的元素,依次比较相邻的两个元素的大小,如果前一个元素大于后一个元素则两者交换,保证最后一个数字一定是最大的(假设按照从小到大排序),即最后一个元素已经排好序,下一轮只需要保证前面 n-1
个元素的顺序即可。
之所以称为冒泡,是因为最大/最小的数,每一次都往后面冒,就像是水里面的气泡一样。
排序(假设从小到大)的步骤如下:
- 从头开始,比较相邻的两个数,如果第一个数比第二个数大,那么就交换它们位置。
- 从开始到最后一对比较完成,一轮结束后,最后一个元素的位置已经确定。
- 除了最后一个元素以外,前面的所有未排好序的元素重复前面两个步骤。
- 重复前面 1 ~ 3 步骤,直到所有元素都已经排好序。
例如,我们需要对数组 [98,90,34,56,21]
进行从小到大排序,每一次都需要将数组最大的移动到数组尾部。
交换具体逻辑如下图所示:
接下来两轮排序确定好了第二个和第三个的位置,其实这个数组已经完成排序了,一共 5 个数,冒泡 4 次即可。
紫色表示已经排好的元素,橙红色表示正在比较/交换的元素,可以看出前面两次排序之后,已经确定好了最大两个数的位置。
java代码
查看代码
public class BubbleSort {
public static void bubbleSort(int[] nums) {
int size=nums.length;
for(int i=0;i<size-1;i++) {
System.out.println("第"+(i+1)+"轮交换开始");
for(int j=0;j<size-1-i;j++) {
if(nums[j]>nums[j+1]) {
int temp=nums[j+1];
nums[j+1]=nums[j];
nums[j]=temp;
}
printf(nums);
}
}
}
public static void printf(int[] nums) {
for (int num : nums) {
System.out.print(num + " ");
}
System.out.println("");
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int[]nums = new int[]{98,90,34,56,21};
printf(nums);
bubbleSort(nums);
}
}
测试结果