排序算法时间复杂度比较

1、排序算法比较主要容：1）利用随机函数产生 10000 个随机整数，对这些数进行多种方法 排序。2 ）至少采用 4种方法实现上述问题求解 （可采用的方法有插入排 序、希尔排序、起泡排序、快速排序、选择排序、堆排序、归并排序）， 并把排序后的结功能果保存在不同的文件里。3 ）给出该排序算法统计每一种排序方法的性能 （以运行程序所花 费的时间为准进行对比） ，找出其中两种较快的方法。程序的主要功能：1. 随机数在排序函数作用下进行排序2. 程序给出随机数排序所用的时间。算法及时间复杂度（一）各个排序是算法思想：（1）直接插入排序：将一个记录插入到已排好的有序表中，从而得 到一个新的，记录数增加 1

2、的有序表。（2）冒泡排序：首先将第一个记录的关键字和第二个记录的关键字 进行比较，若为逆序， 则将两个记录交换， 然后比较第二个记录 和第三个记录的关键字。 依此类推，直到第 N-1 和第 N 个记录的 关键字进行过比较为止。 上述为第一趟排序， 其结果使得关键字 的最大纪录被安排到最后一个记录的位置上。 然后进行第二趟起 泡排序，对前 N-1 个记录进行同样操作。 一共要进行 N-1 趟起泡 排序。3）快速排序：通过一趟排序将待排记录分割成独立的两部分，其 中一部分记录的关键字均比另一部分记录的关键字小， 则可分别 对这两部分记录继续进行排序，已达到整个序列有序。4）选择排序：通过 N-I

3、次关键字间的比较，从 N-I+1 个记录中选 出关键字最小的记录，并和第 I （1=I=N）个记录交换。时间复杂度分析排序算法最差时间时间复杂度是否稳定？插入排序O(n2)O(n2)稳定冒泡排序O(n2)O(n2)稳定快速排序O(n2)O(n*log 2n)不稳定选择排序O(n2)O(n2)稳定10000 个数据的时间比较：算法名称用时插入排序122冒泡排序343快速排序7选择排序116程序源代码：package test;public class SortArray private static final int Min = 1;/生成随机数最小值private static final

4、int Max = 10000;/生成随机数最大值private static final int Length = 10000;/ 生成随机数组长度 ( 测 试的朋友建议不要超过 40000,不然你要等很久 , 如果你电脑配置绝对 高的情况下你可以再加个 0 试试)public static void main(String args) 数组长度： +Length+, Min ： +Min+, Max：+Max);long begin;long end;int arr = getArray(Length);begin = System.currentTimeMillis();insertSo

5、rt(arr.clone();end = System.currentTimeMillis();插入法排序法消耗时间 :+(end-begin)+ 毫秒);begin = System.currentTimeMillis();bubbleSort(arr.clone();end = System.currentTimeMillis();冒泡发排序法消耗时间 :+(end-begin)+ 毫秒);begin = System.currentTimeMillis();fastSort(arr.clone(),0,arr.length-1);end = System.currentTimeMilli

6、s();快速排序法消耗时间 :+(end-begin)+ 毫 秒);begin = System.currentTimeMillis(); choiceSort(arr.clone();end = System.currentTimeMillis();System.out.println(选择排序法消耗时间 :+(end-begin)+ 毫秒);/* 生成随机数数组* param length数组长度* return int*/private static int getArray(int length)if(length=0)return null;int arr = new intleng

7、th;for (int i = 0; i arr.length; i+) int temp = (int)(Min+Math.random()*(Max-Min-1);arri = temp;return arr;/* 快速发排序* param arr需要排序的数组* param left数组最小下标 ( 一般是 0)* param right 数组最大下标 ( 一般是 Length-1)* return int*/right)private static int fastSort(int arr,int left,int if(left right)int s = arrleft;int i

8、 = left;int j = right + 1;while(true)/ 向右找大于 s 的元素的索引 while(i+1 arr.length & arr+i -1 & arr-j s);/如果 i = j 推出循环if(i = j)break;else/ 教化 i 和 j 位置的元素int t = arri;arri = arrj;arrj = t;arrleft = arrj;arrj = s;/对左面进行递归fastSort(arr,left,j-1);/对右面进行递归fastSort(arr,j+1,right);return arr;/* 插入法排序* param arr 需要

9、排序的数组* return int*/private static int insertSort(int arr) for(int i = 1;i arr.length;i+) int temp = arri;int j = i - 1; while(temp arrj) arrj+1 = arrj; j-;if(j = -1)break;arrj+1 = temp;return arr;/* 冒泡发排序* param arr 需要排序的数组* return int*/private static int bubbleSort(int arr) for(int i = 0;i arr.leng

10、th;i+)/ 比较两个相邻的元素 for(int j = 0;j arrj+1) int t = arrj;arrj = arrj+1; arrj+1 = t; return arr;/* 选择法排序* param arr* return*/private static int choiceSort(int arr)for(int i = 0;i arr.length;i+)int m = i;for(int j = i + 1;j arr.length;j+)/ 如果第 j 个元素比第 m 个元素小，将 j 赋值给 mif(arrj arrm)m = j;/交换 m和 i 两个元素的位置i

11、f(i != m)int t = arri;arri = arrm;arrm = t;return arr; 経“翦腺鸨卅im 蛀a饨im細聽昌 龍皿:卵孵段f懈丫專 0000T 卿 ri 巴w *00001 ：okk fcwsii aerklTifrTE)GTIwAy uiPJfioJd uai|ddv awfl eq i Jo = !屮!)j Juj niej(o=二屮 6uerjje| nu=jje)ji (jjb uiuud piOA 5冋s eieAud馬诲轴由耳壷峑e mejed .馬诲由丄* */总结：好的算法编程技巧高效率好的程序。1、做什么都需要耐心，做设计写程序则更需要耐心。一开始的 时候，好不容易写好了程序， 可是等最后调试的时候发现错误很隐蔽， 就很费时间了。 后来我先在纸上构思出函数的功能和参数， 先把各小 部分编好才编主函数 , 考虑好接口之后才动手编，这样就比较容易成 功了。2、做任何事情我决定都应该有个总体规划。之后的工作按照规 划逐步展开完成。 对于一个完整的程序设计， 首先需要总体规划写程 序的步骤，分块写