- /**
- * 冒泡排序: Java
- *
- * @author skywang
- * @date 2014/03/11
- */
- public class BubbleSort {
- /*
- * 冒泡排序
- *
- * 参数说明:
- * a -- 待排序的数组
- * n -- 数组的长度
- */
- public static void bubbleSort1(int[] a, int n) {
- int i,j;
- for (i=n-1; i>0; i--) {
- // 将 a[0...i] 中最大的数据放在末尾
- for (j=0; j<i; j++) {
- if (a[j]> a[j+1]) {
- // 交换 a[j] 和 a[j+1]
- int tmp = a[j];
- a[j] = a[j+1];
- a[j+1] = tmp;
- }
- }
- }
- }
- /*
- * 冒泡排序 (改进版)
- *
- * 参数说明:
- * a -- 待排序的数组
- * n -- 数组的长度
- */
- public static void bubbleSort2(int[] a, int n) {
- int i,j;
- int flag; // 标记
- for (i=n-1; i>0; i--) {
- flag = 0; // 添加一个标记, 如果一趟遍历中发生了交换, 则标记为 true, 否则为 false. 如果某一趟没有发生交换, 说明排序已经完成!
- // 将 a[0...i] 中最大的数据放在末尾
- for (j=0; j<i; j++) {
- if (a[j]> a[j+1]) {
- // 交换 a[j] 和 a[j+1]
- int tmp = a[j];
- a[j] = a[j+1];
- a[j+1] = tmp;
- flag = 1;
- }
- }
- if (flag==0)
- break; // 退出算法
- }
- }
- public static void main(String[] args) {
- int i;
- int[] a = {20,40,30,10,60,50};
- System.out.printf("before sort:");
- for (i=0; i<a.length; i++)
- System.out.printf("%d", a[i]);
- System.out.printf("\n");
- bubbleSort1(a, a.length);
- //bubbleSort2(a, a.length);
- System.out.printf("after sort:");
- for (i=0; i<a.length; i++)
- System.out.printf("%d", a[i]);
- System.out.printf("\n");
- }
- }
冒泡排序时间复杂度
冒泡排序的时间复杂度是 O(N2).
假设被排序的数列中有 N 个数. 遍历一趟的时间复杂度是 O(N), 需要遍历多少次呢? N-1 次! 因此, 冒泡排序的时间复杂度是 O(N2).
冒泡排序稳定性
冒泡排序是稳定的算法, 它满足稳定算法的定义.
算法稳定性 -- 假设在数列中存在 a[i]=a[j], 若在排序之前, a[i] 在 a[j] 前面; 并且排序之后, a[i] 仍然在 a[j] 前面. 则这个排序算法是稳定的!
来源: http://www.bubuko.com/infodetail-2718896.html