冒泡排序算法的C++,Java和Python实现和冒泡排序算法三种语言效率的比较

冒泡排序原理：

这一篇百度经验讲得很好，我不多说了

https://jingyan.baidu.com/article/6525d4b13f920bac7d2e9484.html

他讲的是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 <iostream>
#include<time.h>  

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<arr.length;k++){
            System.out.print(arr[k]+",");
        }
        System.out.println();
    }

    private static final int a[] = {5,9,7,6,1,8,13,4};

    public static void main(String[] args) throws NoSuchMethodException {


        methodExecutionTime(BubbleSort.class.getMethod("bubbleSort", new Class[]{int[].class}));
    }

    public static void bubbleSort(int []a){
        int n = a.length;
        for(int i=0;i<n-1;i++){
            for(int j=0;j<n-1-i;j++){
                if(a[j]>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-8
import time


def 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 nums

nums = [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