冒泡排序原理：
这一篇百度经验讲得很好，我不多说了
他讲的是C语言，没有关系，冒泡原理都是一样的
空间复杂度是O(1)
时间最优复杂度是O(n),时间最差复杂度是O(n^2);
时间最优复杂度推导
假如我们要对一个数组1,2,4,5进行升序排序，我们第一趟循环就完成了，即3次，理想的情况下只需排序一趟，以此类推，n个数只需n-1次即可排序完成。所以复杂度是O(n)
时间最差复杂度推导
假如我们对一个数组5,4,2,1进行升序排序，这个数组正好是全降序，所以要三趟循环,第一趟比较3次，交换3次，第二趟比较2次，交换2次，第三趟比较1次，交换1次。所以是3*2*1=6次
继续推广,n个数在最差情况下需要n(n-1)/2次比较和交换才能完成，所以时间复杂度为O(n^2)
C++实现
/*** @author cjy* @Date 2018/6/19 15:00.*/#include#include using namespace std;void print(int a[],int n){ for (int k = 0; k < n; k++) { cout << a[k] << endl; }}int main(){ clock_t startTime, endTime; startTime = clock(); int a[8] = { 5,9,7,6,1,8,13,4 }; //获取数组的长度 int n = sizeof(a) / sizeof(a[0]); //第一个元素只需要和n-1个元素进行比较 //第二个元素只需要和n-2个元素进行比较 //以此类推 for (int i = 0; i < n - 1; i++) { //第一个元素只需要和n-1个元素进行比较 //第二个元素只需要和n-2个元素进行比较 //以此类推 for (int j = 0; j < n - i - 1; j++) { //只要前面的元素大于后面的元素，立即交换 if (a[j] > a[j + 1]) { int temp = a[j]; a[j] = a[j + 1]; a[j + 1] = temp; } } cout << "第" << i + 1 << "步骤" << endl; print(a, n); } cout << "最终结果" << endl; print(a, n); endTime = clock(); cout << "Totle Time : " << (double)(endTime - startTime)*1000 / CLOCKS_PER_SEC << "ms" << endl; system("pause"); return 0;}
Java实现
package com.xgt.util;import java.lang.reflect.Method;/** * @author cjy * @Date 2018/6/19 15:25. */public class BubbleSort { static void print(int[] arr,int n) { for(int k=0;k a[j+1]){ int temp = a[j]; a[j] = a[j+1]; a[j+1] = temp; } } System.out.println("第"+(i+1)+"个步骤"); print(a,n); } System.out.println("最终结果"); print(a,n); } /** * 计算方法执行时间 * @param method 所有方法都是Method类的对象 */ private static void methodExecutionTime (Method method) { long begin = System.nanoTime(); try { method.invoke(new BubbleSort(), a); } catch (Exception e) { e.printStackTrace(); } long end = System.nanoTime() - begin; System.out.println(method.getName() + "方法耗时：" + end/1000 + "纳秒"); }} Python实现
#!/usr/bin/env python# coding:utf-8import timedef bubbleSort(nums): for i in range(len(nums)-1): # 这个循环负责设置冒泡排序进行的次数 for j in range(len(nums)-i-1): # ｊ为列表下标 if nums[j] > nums[j+1]: t = nums[j]; nums[j] = nums[j+1]; nums[j+1] = t; print"第",i+1,"步骤" print(nums) return numsnums = [5,9,7,6,1,8,13,4];start = time.time()bubbleSort(nums)end = time.time()print (end-start)*1000000,"微秒"
| 语言 | Java | Python | C++ |
| 平均时间(ms) | 1322 | 999 | 24 |
Java运行时间控制台截图
Python运行时间截图
C++运行时间截图
效率排行：C++>Python>Java