编程实现直接插入排序、直接选择排序、Shell排序、快速排序、堆排序、二路归并排序等6种排序算法。 要求：

Question

1）被排序样本为由计算机产生长度为n的随机整数序列，这里n分别取20，500
2）程序中实现对排序过程中数据比较和移动次数的统计
3）对程序运行实际结果进行比较分析

Answer 1

// Ch08sort.cpp : Defines the entry point for the console application.
//默认是从小到大排序

#include <time.h>
#include <iostream>
#include <iomanip>

using namespace std;
//要排序的数组的长度，以及取值的范围
#define SIZE 10
#define MAX 10000
//---------------------------------插入排序----------------------------------------
//直接插入排序080201
//原理：每次将待排序的记录，按其关键字大小插入到前边已经排好序的子文件中的适当位置
int InsertSort(int arr[],int len){
int temp,j;
for(int i=1;i<len;i++){
if(arr[i]<arr[i-1]){
temp=arr[i];
j=i;
do{
arr[j]=arr[j-1];
j--;
}while(j>0&&arr[j-1]>temp);
arr[j] = temp;
}
}
return 0;
}

//SHELL排序 希尔排序 8.2.2
/*
先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。
所有距离为dl的倍数的记录放在同一个组中。先在各组内进行直接插人排序;
然后，取第二个增量d2<d1重复上述的分组和排序，直至所取的增量dt=1(dt<dt-l<…<d2<d1)，
即所有记录放在同一组中进行直接插入排序为止。
*/
int ModifiedInsertSort(int arr[],int n,int delta){
int temp;
for(int i=delta;i<n;i+=delta){
for(int j=i;j>=delta;j-=delta){
if(arr[j]<arr[j-delta]){
temp = arr[j];
arr[j] = arr[j-delta];
arr[j-delta] = temp;
}
}
}
return 0;
}
int ShellSort(int arr[],int len){
//
for(int delta=len/2;delta>0;delta/=2){
//分别对delta个子序列进行排序//
for(int j=0;j<delta;j++){
ModifiedInsertSort(&arr[j],len-j,delta);
}
}
return 0;
}

//1． 不设监视哨的算法描述
////注意： 当增量d=1时，ShellPass和InsertSort基本一致，只是由于没有哨兵而在内循环中增加了一个循环判定条件"j>0"，以防下标越界。
void ShellPass(int *R,int n,int d)
{//希尔排序中的一趟排序，d为当前增量
int i,j;
for(i=d+1;i<=n;i++) //将R[d+1．．n]分别插入各组当前的有序区
if(R[i] <R[i-d] ){
R[0]=R[i];j=i-d; //R[0]只是暂存单元，不是哨兵
do {//查找R[i]的插入位置
R[j+d]=R[j]; //后移记录
j=j-d; //查找前一记录
}while(j>0&&R[0] <R[j] );
R[j+d]=R[0]; //插入R[i]到正确的位置上
} //endif
} //ShellPass

void ShellSort11(int* R,int n)
{
int increment=n; //增量初值，不妨设n>0
do {
increment=increment/3+1; //求下一增量
ShellPass(R,n,increment); //一趟增量为increment的Shell插入排序
}while(increment>1);
} //ShellSort

/*
2．设监视哨的shell排序算法
算法分析
1．增量序列的选择
Shell排序的执行时间依赖于增量序列。
好的增量序列的共同特征：
① 最后一个增量必须为1；
② 应该尽量避免序列中的值(尤其是相邻的值)互为倍数的情况。
有人通过大量的实验，给出了目前较好的结果：当n较大时，比较和移动的次数约在nl.25到1.6n1.25之间。

2．Shell排序的时间性能优于直接插入排序
希尔排序的时间性能优于直接插入排序的原因：
①当文件初态基本有序时直接插入排序所需的比较和移动次数均较少。
②当n值较小时，n和n2的差别也较小，即直接插入排序的最好时间复杂度O(n)和最坏时间复杂度0(n2)差别不大。
③在希尔排序开始时增量较大，分组较多，每组的记录数目少，故各组内直接插入较快，后来增量di逐渐缩小，分组数逐渐减少，而各组的记录数目逐渐增多，但由于已经按di-1作为距离排过序，使文件较接近于有序状态，所以新的一趟排序过程也较快。
因此，希尔排序在效率上较直接插人排序有较大的改进。

3．稳定性
希尔排序是不稳定的。参见上述实例，该例中两个相同关键字49在排序前后的相对次序发生了变化。
*/

//---------------------------------交换排序----------------------------------------
//交换排序－－－冒泡排序，快速排序
//原理：两两比较待排序记录的关键字，发现两个记录的次序相反时即进行交换，直到没有反序的记录为止。
//冒泡排序080301
int BubbleSort(int arr[],int len){
int k,temp ;
for(int i=0;i<len-1;i++){
k = i;
for(int j=i+1;j<len;j++){
if(arr[j]<arr[k])
k = j;
}
if(k!=i){
temp = arr[i];
arr[i] = arr[k];
arr[k] = temp;
}
}
return 0;
}
//优化的冒泡排序
int ImprovedBubbleSort(int arr[],int len){
bool noswap;
int temp;
for(int i=0;i<len;i++){
noswap = true;
for(int j=len-1;j>i;j--){
if(arr[j]<arr[j-1]){
temp = arr[j];
arr[j] = arr[j-1];
arr[j-1] = temp;
noswap = false;
}
}
if(noswap){
break;
}
}
return 0;
}

//快速排序080302
int Partition(int arr[],int len,int i,int j){
int pivot = arr[i];
while(i<j){
while(i<j&&arr[j]>=pivot){
j--;
}
if(i<j){
arr[i++] = arr[j];
}
while(i<j&&arr[i]<=pivot){
i++;
}
if(i<j){
arr[j--] = arr[i];
}
}
arr[i] = pivot;
return i;
}
int QuickSort(int arr[],int len,int low=0,int high=SIZE){
int pivotpos;
if(low<high){
pivotpos = Partition(arr,len,low,high);
QuickSort(arr,len,low,pivotpos-1);
QuickSort(arr,len,pivotpos+1,high);
}
return 0;
}

//---------------------------------选择排序----------------------------------------
//直接选择排序080401
//原理：每一趟从待排序的记录中选出关键字最小的记录，顺序放到已排好序的子文件的最后
int StraightSelect(int arr[],int len){
int temp=0;
int k;
for(int i=0;i<len;i++){
k=i;
for(int j=k+1;j<len;j++){
if(arr[j]<arr[k]){
k = j;
}
}
if(k!=i){
temp = arr[k];
arr[k] = arr[i];
arr[i] = temp;
}
}
return 0;
}

//---------------------------------归并排序----------------------------------------
//归并排序：
int Merge(int arr[],int len){

return 0;
}

//---------------------------------分配排序----------------------------------------
//桶排序,箱排序8.6
//事先知道序列中的记录都位于某个小区间段[0，m)内
// 将具有相同值的记录都分配到同一个桶中，然后依次按照编号从桶中取出记录，组成一个有序序列
int BucketSort(int arr[],int len){
int max = MAX;//最大值
int *count = new int[max];
int i;
for(i=0;i<max;i++){
count[i] = 0;
}
for(i=0;i<len;i++){
count[arr[i]]++;
}
for(i=0;i<len;){
for(int j=0;j<max;j++){
while(count[j]>0){
arr[i++] = j;
count[j]--;
}
}
}
return 0;
}

//打印数组
int printarr(int arr[],int len){

for(int i=0;i<len;i++){
if(i%10==0)
cout<<endl;
cout<<setw(4)<<arr[i]<<" ";
}
cout<<endl;
return 0;
}

int main()
{
int arr[SIZE];
int len = sizeof(arr)/sizeof(arr[0]);//SIZE
srand( (unsigned)time( NULL ) );
for(int i=0;i<len;i++){
arr[i] =rand()%MAX;
}
cout<<"生成数组："<<endl;
printarr(arr,len);
// StraightSelect(arr,len);
// InsertSort(arr,len);
// BubbleSort(arr,len);
// QuickSort(arr,len);
// ImprovedBubbleSort(arr,len);
// ShellSort(arr,len);
BucketSort(arr,len);
cout<<endl<<"排序后得到的数组："<<endl;
printarr(arr,len);

return 0;
}