冒泡排序
(一)排序过程分析
现在有一个数组,共有六个元素,{1,4,7,2,3,5},要求把他们按照从小到大的顺序排列,每一趟排序将较大的值交换到最右边,下面进行排序过程分析。
(二)排序过程分析
第一趟比较.png第一趟比较结束,得到{1,4,2,3,5,7},共比较5次;
第二趟比较.png第二趟比较结束,得到{1,2,3,4,5,7},共比较4次;
第三趟比较.png第三趟比较结束,得到{1,2,3,4,5,7},共比较3次;
第四趟比较.png第四趟比较结束,得到{1,2,3,4,5,7},共比较2次;
第五趟比较.png 第五趟比较结束,得到{1,2,3,4,5,7},共比较1次;
至此,已经无法再进行比较,该序列已经有序,冒泡排序结束。由上述过程可知,冒泡排序的本质就是元素之间的交换,共6个数,执行5趟排序比较,若有n个数,则是执行n-1趟比较,每一趟从左到右比较相邻的两个数,如果大的数在左边则进行交换,在每一趟比较结束后,该趟最大的数在最右边。
时间复杂度分析:第一趟比较,是n个数进行比较;第二趟比较,是n-1个数进行比较;第三趟比较,是n-2个数进行比较......所以这是一个等差数列求和最后得O(N2)(2是N的上标值,因为简书不支持latex)。
(二)Java代码
public class BubbleSort {
public static void main(String[] args) {
int[] shus= {1,4,7,2,3,5};
//外面比较的是几趟
for (int i = 1; i <= shus.length-1; i++) {
//第i趟从a[0]开始到a[n-i+1]都与他们的下一个数比较
for (int j = 0; j < shus.length-i; j++) {
if (shus[j] > shus[j+1]) {
int temp = shus[j];
shus[j] = shus[j+1];
shus[j+1] = temp;
}
}
}
print(shus);
}
public static void print(int shus[]) {
for (int i = 0; i < shus.length; i++) {
System.out.print(shus[i] + " ");
}
}
}
网友评论