冒泡排序作为最基础最简单的排序算法,实质是相邻两元素比较,若有序则跳过,若无序则交换。最多需 n-1 趟排序,第 i 趟需比较 n-i 次。所以时间复杂度为 o(n*n),是一种比较低效率的排序算法。不过对于初学者来说是必须掌握的一种算法。
冒泡排序有一点可以改进的地方,初学者可能没注意到。就是当序列已经整体有序时,就不需要再作不必要的比较了。可以设置一个布尔变量,当一趟下来未发生交换时,直接跳出循环,能够提高排序效率。
- package com.fairy.InnerSort;
- import java.util.Scanner;
- /**
- * 冒泡排序
- * @author Fairy2016
- *
- */
- public class BubbleSort {
- public static void sort(int a[], int n) {
- boolean flag = false;
- for (int i = 1; i <= n - 1; i++) {
- flag = false;
- for (int j = 1; j <= n - i; j++) {
- if (a[j] > a[j + 1]) {
- //交换a[j]与a[j+1]
- a[0] = a[j];
- a[j] = a[j + 1];
- a[j + 1] = a[0];
- //标记发生了交换
- flag = true;
- }
- }
- //若未发生交换,直接退出,排序已完成
- if (!flag) {
- break;
- }
- }
- }
- public static void Print(int a[], int n) {
- for (int i = 1; i <= n; i++) {
- System.out.print(a[i] + " ");
- }
- }
- public static void main(String args[]) {
- int n;
- int a[];
- Scanner scanner = new Scanner(System. in );
- while (scanner.hasNext()) {
- n = scanner.nextInt();
- if (n > 0) {
- a = new int[n + 1];
- for (int i = 1; i <= n; i++) {
- a[i] = scanner.nextInt();
- }
- sort(a, n);
- Print(a, n);
- }
- }
- scanner.close();
- }
- }
来源: http://www.jianshu.com/p/7c2dbd25b042