下载文档原格式
//头文件定义
#include "stdafx.h"
#include
#include
#include
#include
#include
void bubbleSort(int *a,int len);//冒泡算法
void UpdBubbleSort1(int *a,int len);//改进冒泡算法1 ----找到一次循环的已排好序位置
void UpdbubbleSort2(int *a,int len); //改进冒泡算法2 --一次循环找到最大\最小值
void quickSort_update(int *a, int len, int k);
//改进快速排序--先使>8的块基本有序--实测比一般快速排序节约28%时间(59秒,1亿条随机数据，逆序数时间较长)
void qsort_improve(int *a,int low,int high, int k);//改进快速排序子算法
void InsertSort(int *a, int n); //直接插入排序
void shellSort(int *a, int n);//直接插入排序威力加强版本--希尔排序(适用逆序数，1亿逆序数据93s 1亿随机数据223s)
void ShellSort_local(int *a, int len, int dk);
void HeapSort(int *H,int length); //堆排序-step1:建堆2：n/2个父节点堆有序3、从堆尾元素依次和堆顶交换
void BuildingHeap(int *H, int length); //堆排序---子函数(逆序数据50s,1亿条随机数据133秒)
void HeapAdjust(int *H,int s, int length); //堆排序---子函数
unsigned long ulrand(void);//产生大的随机数
void selectSort(int *a, int n); //选择排序
int SelectMinKey(int *a, int n, int i);
void SelectSort_double(int *r,int n);
typedef int ElemType ;
void MergeSort(ElemType *r, ElemType *rf, int lenght);//归并排序(1亿逆序：30s 1亿随机：46s )
void Merge(ElemType *r,ElemType *rf, int i, int m, int n);
//65148-65149
/*
总结提升算法效率方法
1、减小循环次数，大循环在里面，小循环再外面-----循环次数多的话切换用时多，
2、侦测已完成任务，提前结束
3、递归算法占用的空间较大，容易溢出, 优点是算法复杂度低
*/
void QuickSort(int *a,int low,int high); //(全完逆序100w数据40分钟---已验证)
int LocalQuickSort(int *a,int low,int high);
void Swap(int *p1,int *p2);
void PrintArray(int *a,int len);
void InitArray(int *a,int len);
int first_posi=0;
int privotKey=0;
int SortOkSign=0;//无
//需交换的标志
#define lenArr 100000000
int lastChangePos=lenArr-1;//最后一次交换的位置
int gloData=0;
int k=0,m=0,n=0,x=0;
int *p= (int *) malloc(lenArr*sizeof(int));
int b[lenArr];
int main()
{
//int len=5;
if(p==NULL)
{
printf("malloc Error");
return 0;
}
clock_t start_2,end_2;
// InitArray(p,lenArr);
// start_1=clock(); //开始时间start_1,end_1,
// InsertSort(p,lenArr);
// UpdbubbleSort2(p,lenArr);
// QuickSort(p,0,lenArr-1);
//PrintArray(p,lenArr);
// quickSort_update(p,lenArr-1,10);
//InsertSort(p,lenArr);
// HeapSort(p,lenArr);
// MergeSort(p,b,lenArr);
// end_1=clock(); //结束时间
InitArray(p,lenArr);
// PrintArray(p,lenArr);
start_2=clock(); //结束时间
// shellSort(p,lenArr);
// bubbleSort(p,lenArr);
HeapSort(p,lenArr);
end_2=clock();
// PrintArray(p,lenArr);
double db2=(double)(end_2-start_2)/CLOCKS_PER_SEC;
printf("\n排序时间%lf",db2);
return 0;
}
//改进冒泡算法---检测已排序好的尾部段，不再排序
