内容发布更新时间 : 2024/5/20 11:16:17星期一 下面是文章的全部内容请认真阅读。

1

排序算法比较

主要内容：

1)利用随机函数产生

10000个随机整数，对这些数进行多种方法

排序。

2）至少采用4种方法实现上述问题求解（可采用的方法有插入排序、希尔排序、起泡排序、快速排序、选择排序、堆排序、归并排序），并把排序后的结功能果保存在不同的文件里。

3）给出该排序算法统计每一种排序方法的性能（以运行程序所花费的时间为准进行对比），找出其中两种较快的方法。

程序的主要功能：

1.随机数在排序函数作用下进行排序 2.程序给出随机数排序所用的时间。

算法及时间复杂度

（一）各个排序是算法思想：

（1）直接插入排序：将一个记录插入到已排好的有序表中，从而得

到一个新的，记录数增加1的有序表。

（2）冒泡排序：首先将第一个记录的关键字和第二个记录的关键字

进行比较，若为逆序，则将两个记录交换，然后比较第二个记录和第三个记录的关键字。依此类推，直到第N-1和第N个记录的

1

2

关键字进行过比较为止。上述为第一趟排序，其结果使得关键字的最大纪录被安排到最后一个记录的位置上。然后进行第二趟起泡排序，对前N-1个记录进行同样操作。一共要进行N-1趟起泡排序。

（3）快速排序：通过一趟排序将待排记录分割成独立的两部分，其

中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，已达到整个序列有序。 （4）选择排序：通过N-I次关键字间的比较，从N-I+1个记录中选

出关键字最小的记录，并和第I（1<=I<=N）个记录交换。

时间复杂度分析

排序算法 插入排序 冒泡排序 快速排序 选择排序 最差时间 O(n2) O(n2) O(n2) O(n2) 时间复杂度 O(n2) O(n2) O(n*log2n) O(n2) 是否稳定？ 稳定 稳定 不稳定 稳定

2 1

3

10000个数据的时间比较：

算法名称 插入排序 冒泡排序 快速排序 选择排序 用时 122 343 7 116 程序源代码：

/**********************************************************************************************

package test;

public class SortArray {

private static final int Min = 1;//生成随机数最小值 private static final int Max = 10000;//生成随机数最大值 private static final int Length = 10000;//生成随机数组长度(测试的朋友建议不要超过40000,不然你要等很久,如果你电脑配置绝对高的情况下你可以再加个0试试)

public static void main(String[] args) {

System.out.println(\数组长度：\：\Max：\ long begin; long end;

int arr[] = getArray(Length);

3 1