1.课题要求

设计程序，利用随机函数产生20000个随机整数(1~100000)， 完成下面功能:

(1)对这些数分别进行直接插入排序、折半插入排序、希尔排序、冒泡排序、快速排序、简单选择排序、堆排序2-路归并排序、链式基数排序，并把排序结果保存到文件中。

(2) 分析上述排序算法的性能(以运行程序所花费的时间为准进行对比)，找出较快的排序方法。

(3)计算并输出所选排序算法中比较的次数和数据移动的次数。

(4)若排序的整数增加到100000个、100000000个，排序结果有什么变化，请分析并验证。

2.课题分析

这一课题主要考查我们对所有排序方法的应用，10大经典排序的互相结合，本质并不难，首先，先简单地介绍一下10大经典排序。

(1)冒泡排序

冒泡排序是我们最早接触编程的时候所接触的第一个排序方法，它的时间复杂度最坏为O(n2),又称为"沉底法",每次交换相邻的两个位置，如果前面的数比后面的数大，那么就交换他们，迭代n-1次就可以确定每一个数的位置。

i∈[0,N-1)               //循环N-1遍
   j∈[0,N-1-i)           //每遍循环要处理的无序部分
     swap(j,j+1)          //两两排序（升序/降序）

(2)选择排序

选择排序也是我们常用的排序方法，