python哪种算法效率最高_冒泡排序算法的C++,Java和Python实现和冒泡排序算法三种语言效率的比较...

冒泡排序原理&＃xff1a;

这一篇百度经验讲得很好&＃xff0c;我不多说了

他讲的是C语言&＃xff0c;没有关系&＃xff0c;冒泡原理都是一样的

空间复杂度是O(1)

时间最优复杂度是O(n),时间最差复杂度是O(n^2);

时间最优复杂度推导

假如我们要对一个数组1,2,4,5进行升序排序&＃xff0c;我们第一趟循环就完成了&＃xff0c;即3次&＃xff0c;理想的情况下只需排序一趟&＃xff0c;以此类推&＃xff0c;n个数只需n-1次即可排序完成。所以复杂度是O(n)

时间最差复杂度推导

假如我们对一个数组5,4,2,1进行升序排序&＃xff0c;这个数组正好是全降序&＃xff0c;所以要三趟循环,第一趟比较3次&＃xff0c;交换3次&＃xff0c;第二趟比较2次&＃xff0c;交换2次&＃xff0c;第三趟比较1次&＃xff0c;交换1次。所以是3*2*1&＃61;6次

继续推广,n个数在最差情况下需要n(n-1)/2次比较和交换才能完成&＃xff0c;所以时间复杂度为O(n^2)

C&＃43;&＃43;实现

/**

* &＃64;author cjy

* &＃64;Date 2018/6/19 15:00.*/#include#include

using namespacestd;void print(int a[],intn)

{for (int k &＃61; 0; k

{

cout<

}

}intmain()

{

clock_t startTime, endTime;

startTime&＃61;clock();int a[8] &＃61; { 5,9,7,6,1,8,13,4};//获取数组的长度

int n &＃61; sizeof(a) / sizeof(a[0]);//第一个元素只需要和n-1个元素进行比较//第二个元素只需要和n-2个元素进行比较//以此类推

for (int i &＃61; 0; i

{//第一个元素只需要和n-1个元素进行比较//第二个元素只需要和n-2个元素进行比较//以此类推

for (int j &＃61; 0; j

{//只要前面的元素大于后面的元素&＃xff0c;立即交换

if (a[j] > a[j &＃43; 1])

{int temp &＃61;a[j];

a[j]&＃61; a[j &＃43; 1];

a[j&＃43; 1] &＃61;temp;

}

}

cout<<"第" <

print(a, n);

}

cout<<"最终结果" <

print(a, n);

endTime&＃61;clock();

cout<<"Totle Time :" <<(double)(endTime - startTime)*1000 / CLOCKS_PER_SEC <<"ms" <

system("pause");return 0;

}

Java实现

package com.xgt.util;import java.lang.reflect.Method;/**

* &＃64;author cjy

* &＃64;Date2018/6/19 15:25.

*/

public class BubbleSort {

static void print(int[] arr,int n)

{

for(int k&＃61;0;k

System.out.print(arr[k]&＃43;",");}

System.out.println();}

private static final int a[] &＃61; {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&＃61; a.length; for(int i&＃61;0;i

for(int j&＃61;0;j

if(a[j]>a[j&＃43;1]){

int temp&＃61; a[j]; a[j] &＃61; a[j&＃43;1]; a[j&＃43;1] &＃61; temp;}

}

System.out.println("第"&＃43;(i&＃43;1)&＃43;"个步骤"); print(a,n);}

System.out.println("最终结果"); print(a,n);}

/**

* 计算方法执行时间

* &＃64;param method 所有方法都是Method类的对象

*/

private static void methodExecutionTime (Method method) {

long begin&＃61; System.nanoTime();try {

method.invoke(new BubbleSort(), a);} catch (Exception e) {

e.printStackTrace();}

long end&＃61; System.nanoTime() - begin; System.out.println(method.getName() &＃43; "方法耗时&＃xff1a;" &＃43; end/1000 &＃43; "纳秒");}

}

Python实现

#!/usr/bin/env python#coding:utf-8

importtimedefbubbleSort(nums):for i in range(len(nums)-1): #这个循环负责设置冒泡排序进行的次数

for j in range(len(nums)-i-1): #&＃xff4a;为列表下标

if nums[j] > nums[j&＃43;1]:

t&＃61;nums[j];

nums[j]&＃61; nums[j&＃43;1];

nums[j&＃43;1] &＃61;t;print"第",i&＃43;1,"步骤"

print(nums)returnnums

nums&＃61; [5,9,7,6,1,8,13,4];

start&＃61;time.time()

bubbleSort(nums)

end&＃61;time.time()print (end-start)*1000000,"微秒"

语言

Java

Python

C&＃43;&＃43;

平均时间(ms)

1322

999

24

Java运行时间控制台截图

Python运行时间截图

C&＃43;&＃43;运行时间截图

效率排行&＃xff1a;C&＃43;&＃43;>Python>Java