排序比较器（上）
说在前面的废话：以前在学习数据结构排序那一章的时候就想，什么时候有空了，做一个排序比较器。比较这些排序的效果。最近刚好有空，就利用Qt的图形界面做了一个排序比较器。记录在此，方便自己，也希望有助于大家。
本文主要分以下几个部分叙述：
1、项目介绍
2、编写九大排序
3、在子线程中测试排序
4、等待框制作
5、结果
一、项目介绍
本程序是一个比较九大排序算法效率的演示程序。如下图所示：
用户可以通过选择数量规模，来选择需要测试的数量大小。数量规模数量级从10-1000000；本程序的原始数据随机生成的int型正整数数据，大小从0-1000000；还有，通过选择排序方式选择需要比较的排序算法，(可多选)；选择是否记录结果，将决定程序是否把随机生成的原始数据和排序的数据记录到文件中。同时，在右边的结果显示框，还可以显示程序运行的进度和结果。
二、编写九大排序
对于排序来说，总共有很多很多很多种，这里选择了基础的九大排序。如下图所示：
具体的代码如下：
//简单插入排序
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)
{
if(data[min_index] > data[j]) //选择最小数的下标
min_index = j;
}
if(min_index != i)
{
int t = data[min_index];
data[min_index] = data[i];
data[i] = t;
}
}
}
具体各排序原理在网上书上都有很多介绍，在此就不赘述了。
总共内容比较多，在这先写这些，剩下的见排序比较器（下）