最经做了一个实验,想试试冒泡和快排在速度方面的差距会有多大。随机生成一千万个数,放入一个数组里面,再分别使用冒泡和快排进行排序,代码如下
冒泡排序的代码如下:
package com.block.sort;import java.util.Random;/*** 冒泡* * @author ajie**/public class BubbleSort {static public void main(String... args) {int[] arr = new int[10000000];Random rad = new Random();for (int i = 0; i < arr.length; i++) {arr[i] = rad.nextInt();}// int arr[] = { 9, 12, 4, 21, 22, 10, 3, 5, 20 };long start = System.currentTimeMillis();// int[] arr = { 2, 3, 1, 0, 9, 4, 12, 5 };BubbleSort.sort(arr);/*for (int i = 0; i < arr.length; i++) {System.out.println(arr[i]);}*/System.out.println("耗时:" + (System.currentTimeMillis() - start) / 1000+" 秒");}public static void sort(int[] arr) {if (null == arr || arr.length <= 1) {return;}int i = 0, j = 0, temp = 0, len = arr.length;for (; i < len - 1; i++) {for (j = 0; j < len - i - 1; j++) {if (arr[j] > arr[j + 1]) {temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;}}}}}
快速排序的代码如下:
package com.block.sort;import java.util.Random;/*** 快速排序** * @author ajie**/public class QuickSort {public static void main(String[] args) {int[] arr = new int[10000000];Random rad = new Random();for (int i = 0; i < arr.length; i++) {arr[i] = rad.nextInt();}// int arr[] = { 9, 12, 4, 21, 22, 10, 3, 5, 20 };long start = System.currentTimeMillis();quickSort(arr);/*for (int i : arr) {System.out.println(i);}*/System.out.println("耗时:" + (System.currentTimeMillis() - start)+" 毫秒" );}public static void quickSort(int arr[]) {sort(arr, 0, arr.length - 1);}/*** 递归调用该方法* * @param arr* @param low* @param high*/public static void sort(int arr[], int low, int high) {if (low < high) {int partition = partition(arr, low, high);sort(arr, partition + 1, high);sort(arr, low, partition - 1);}}public static int partition(int[] arr, int low, int high) {while (low < high) {// 第一个和最后一个对比,如果小于,则后指针-1while (arr[high] >= arr[low] && low < high) {high--;}swap(arr, high, low);// 第一个和后指针位置的数作对比,如果小于,前指针+1;while (arr[low] <= arr[high] && low < high) {low++;}swap(arr, high, low);}return low;}/*** high和low交换* * @param arr* @param high* @param low*/public static void swap(int[] arr, int high, int low) {int temp = arr[high];arr[high] = arr[low];arr[low] = temp;}}
在我的电脑上运行冒泡,但是经过了很长时间,结果还没有出来,没办法,只好搬到云服务器上面运行了,把代码拷到我的阿里云服务器上面运行,经过了3个小时,怎么还没结束啊,我觉得不对劲了,因为服务器cpu一直满载,这样子下去我的cpu积分很快就会被用完了(阿里云ecs实例确实是个坑,买了服务器,跑起来还要耗油),最后也只能终止了,本以为三两个小时能出结果的,但是冒泡显然比我想象的要慢的多,我又只好把它搬到另外一台海外的服务器运行,那台不算cpu积分,即使cpu满载,也无所谓,考虑到运行时间过长,我只好使用后台进程的方式运行,然后把结果打印到文本上
java BubbleSort & >> res.log
运行结果
耗时:223906 秒
最终,结果远远超出了我的预想,花了223906秒,也就是约3732分钟,也就是约62个小时
好了,冒泡结果出来了,该快速排序上场了,快排没有使用后台运行,就直接运行了
java QuickSort
没想到,结果一下子就出来了
耗时:1802 毫秒
注意,单位是毫秒,也就是2秒都不用,真心是没有对比就没有伤害啊,这差距,不是天与地的差距,是太阳与地球的距离啊,所以说一个好的算法,在程序中担任了一个多么重要的角色啊,这能让你的程序效率大大提高。
上面的实验结果会因机器而异,仅供参考。我的服务器CPU参数如下:
Architecture:x86_64CPU op-mode(s): 32-bit, 64-bitByte Order: Little EndianCPU(s):1On-line CPU(s) list: 0Thread(s) per core: 1Core(s) per socket: 1Socket(s): 1NUMA node(s):1Vendor ID: GenuineIntelCPU family: 6Model: 61Model name: Virtual CPU a7769a6388d5Stepping: 2CPU MHz:2394.454BogoMIPS: 4788.90Hypervisor vendor:KVMVirtualization type: fullL1d cache: 32KL1i cache: 32KL2 cache: 4096KL3 cache: 16384KNUMA node0 CPU(s):0