代码示例
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
/** * @author: 791202.com * Java冒泡排序算法只会操作相邻的两个数据。每次冒泡操作都会对相邻的两个元素进行比较，看是否满足大小关系要求。 * 如果不满足就让它俩互换。一次冒泡会让至少一个元素移动到它应该在的位置，重复n 次， * 就完成了 n 个数据的排序工作。 **/ public class BubbleSort { public void bubbleSort(Integer[] arr, int n) { if (n <= 1) return; //如果只有一个元素就不用排序了 for (int i = 0; i < n; ++i) { // 提前退出冒泡循环的标志位,即一次比较中没有交换任何元素，这个数组就已经是有序的了 boolean flag = false; for (int j = 0; j < n - i - 1; ++j) { //此处你可能会疑问的j<n-i-1，因为冒泡是把每轮循环中较大的数飘到后面， // 数组下标又是从0开始的，i下标后面已经排序的个数就得多减1，总结就是i增多少，j的循环位置减多少 if (arr[j] > arr[j + 1]) { //即这两个相邻的数是逆序的，交换 int temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; flag = true; } } if (!flag) break;//没有数据交换，数组已经有序，退出排序 } } public static void main(String[] args) { Integer arr[] = {2, 4, 7, 6, 8, 5, 9}; SortUtil.show(arr); BubbleSort bubbleSort = new BubbleSort(); bubbleSort.bubbleSort(arr, arr.length); SortUtil.show(arr); } } |
时间复杂度
如果我们的数据正序，只需要走一趟即可完成排序。所需的比较次数C和记录移动次数M均达到最小值，即：Cmin=n-1;Mmin=0;所以，冒泡排序最好的时间复杂度为O(n)。
如果很不幸我们的数据是反序的，则需要进行n-1趟排序。每趟排序要进行n-i次比较(1≤i≤n-1)，且每次比较都必须移动记录三次来达到交换记录位置。在这种情况下，比较和移动次数均达到最大值：
即最坏情况下时间复杂度为O(n2)【n的平方】。所以，冒泡排序总的平均时间复杂度为：O(n2) 。
0
