排序比较器

#include "sort.h" #include<QDebug> #include<QTime> Sort::Sort() { data = nullptr; num = 0; } int Sort::GetDataLength() { return num; } Sort::~Sort() { if(data != nullptr) //释放空间 { delete data; delete data0; } } //初始化数据 void Sort::InitData0(int length) { num = length; data0 = new int[num]; //动态申请空间 data = new int[num]; for(int i = 0;i<num;++i) { int temp1 = qrand()%1000; int temp2 = qrand()%1000; data0[i] = temp1*temp2; //产生1000000以内的随机数 // data0[i] = qrand()%RAND_MAX; //随机产生最大为32767的整数 } } void Sort::InitData() { memcpy(data,data0,sizeof(int)*num); //从原始数据中拷贝数据至测试数据中 } //简单插入排序 void Sort::SimInsSort() //1 4 3 2 7 9 5 { int i,j,temp; for( i = 1;i<num;++i) { temp = data[i]; //当前待比较的数 for( j = i-1;j>=0;--j) { if(temp<data[j]) data[j+1] = data[j]; //数据向后移动 else break; } data[j+1] = temp; //插入 } } //希尔排序 void Sort::ShellSort() //1 4 3 2 7 9 5 { int gap = 1; //间隔 while (gap < num / 3) // 动态定义间隔序列 { gap = gap * 3 + 1; } int i,j,temp; for(;gap>0;gap/=3) { for( i = gap;i<num;++i) { temp = data[i]; for(j = i-gap;j>=0;j-=gap) { if(temp<data[j]) data[gap+j] = data[j]; else break; } data[j+gap] = temp; } } } //冒泡排序算法 void Sort::BubSort() { int flag = 0; for(int i = 1;i<num;++i) { if(0 == flag) { flag = 1; for(int j = 0;j<num-i;++j) { if(data[j]>data[j+1]) { int temp = data[j]; data[j] = data[j+1]; data[j+1] = temp; flag = 0; } } } } } //设定基准,并返回基准的位置 //6 int Sort::Partion(int low, int high) //1 3 3 7 10 { //int piv = low; int temp = data[low]; while(low<high) { while(low<high) { if(data[high]>=temp) --high; else break; } data[low] = data[high]; while(low<high) { if(data[low]<=temp) ++low; else break; } data[high] = data[low]; } data[low] = temp; return low; } //堆化:建立以当前元素i为根节点的大根堆 void Sort::Heapify(int length,int i) { int left_chi = i*2+1,rig_chi = i*2+2; int large = i; if(left_chi<length && data[left_chi]>data[large]) large = left_chi; if(rig_chi < length && data[rig_chi]>data[large]) large = rig_chi; if(large != i) { //交换当前元素与其孩子的最大值 int t = data[i]; data[i] = data[large]; data[large] = t; Heapify(length,large); } } //初始化大根堆 void Sort::InitMaxHeap(int length) { for(int i = length/2-1;i>=0;--i) Heapify(length,i); } //合并两个有序序列 void Sort::Merge(int beg, int mid, int end) { int i1 = beg,j1 = mid; int i2 = mid+1,j2 = end; //i2，j2为第二个有序序列的首部和尾部 int *temp = new int[end-beg+1]; ////此处需要在堆中申请内存，否则百万级的数据，程序会崩溃 int temp_index = 0; while(i1<=j1 && i2<=j2) { if(data[i1]<data[i2]) { temp[temp_index++] = data[i1]; ++i1; } else if(data[i1]>data[i2]) { temp[temp_index++] = data[i2]; ++i2; } else { temp[temp_index++] = data[i1]; temp[temp_index++] = data[i2]; ++i1; ++i2; } } //将剩下的元素复制进排序好的暂时空间中 while(i1<=j1) { temp[temp_index++] = data[i1]; ++i1; } while(i2<=j2) { temp[temp_index++] = data[i2]; ++i2; } //复制回原数组 for(int i = beg,k = 0;i<=end;++i,++k) { data[i] = temp[k]; } delete temp; } //二路归并排序 void Sort::MergeSort(int beg,int end) { if(beg<end) { int mid = (beg+end)/2; MergeSort(beg,mid); //归并左半边 MergeSort(mid+1,end); //归并右半边 Merge(beg,mid,end); //左右合并 } } //计数排序 void Sort::CountSort() { int max = data[0],min = data[0]; //获取元素中的最小值和最大值 for(int i = 0;i<num;++i) { if(max<data[i]) max = data[i]; if(min>data[i]) min = data[i]; } int dif = max-min; //最大值和最小值的差值 //int fre[dif+1]; // 频率数组 int *fre = new int[dif+1]; //此处需要在堆中申请内存，否则百万级的数据，程序会崩溃 for(int i = 0;i<dif+1;++i) fre[i] = 0; //初始化为零 for(int i = 0;i<num;++i) { ++fre[data[i]-min]; //统计每个数的频率 } //输出到原数组 for(int i = 0,j = 0;i<num;++i) { while(fre[j] <= 0) ++j; data[i] = j+min; --fre[j]; } delete fre; } //分发和收集 void Sort::DisAndCol(int exp) { int bucs[10]; for(int i = 0;i<10;++i) bucs[i] = 0; //统计频率 for(int i = 0;i<num;++i) { int d = (data[i] / exp) %10; ++bucs[d]; } //统计在本次分发之后收集的位置 for(int i = 1;i<10;++i) { bucs[i] = bucs[i-1]+bucs[i]; } //int temp[num]; int *temp = new int[num]; //此处需要在堆中申请内存，否则十万以上的数据，程序会崩溃 for(int i = 0;i<num;++i) temp[i] = data[i]; for(int i = num-1;i>=0;--i) { int d = (temp[i]/exp)%10; //取得单个位数 data[bucs[d]-1] = temp[i]; //复制回原数组 --bucs[d]; //减去一个计数 } delete temp; } //基数排序 void Sort::RadSort() { //int b = 6; ////6代表数字的位数,此处默认最大是6位，即100000 int b = 7; ////7代表数字的位数,此处默认最大是7位，即1000000 for(int i = 0;i<b;++i) { int exp = pow(10,i); DisAndCol(exp); } } //快速排序 void Sort::QuiSort(int low,int high) { if(low<high) { int par_index = Partion(low,high); QuiSort(low,par_index-1); QuiSort(par_index+1,high); } } //堆排序 void Sort::HeapSort() { int length = num; InitMaxHeap(length); //初始化大根堆 for(int i = 0;i<num-1;++i) { //交换堆头元素和堆尾元素 int t = data[0]; data[0] = data[num-i-1]; data[num-i-1] = t; --length; Heapify(length,0); //每次交换后都从头部开始往下调整,调整的元素数目减一 } } //简单选择排序 void Sort::SimSelSort() { int i,j,min_index; for( i = 0;i<num;++i) { min_index = i; for(j = i;j<num;++j) {