//头文件定义
#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(\ 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(\排序时间%lf\ return 0; }
//改进冒泡算法 ---检测已排序好的尾部段，不再排序