Posted on 2008-01-01 14:37
MiweiDev 阅读(1299)
评论(0) 编辑 收藏 引用 所属分类:
数据结构与算法(逻辑思考)
#include<iostream>
#include<algorithm>
#include<windows.h>
using namespace std;
#define N 300000
//#define RANDOM
#define MYDEBUG
int* array=NULL;
void Maopao(int* array,int begin,int last)
{
for(int i = begin; i < last-1; i++)
{
for(int j = begin; j < last-1-i; j++)
{
if(array[j] > array[j+1])
swap(array[j], array[j+1]);
}
}
}
void Xuanze(int* array,int begin,int last)
{
for(int i = begin; i < last-1; i++)
{
int index = begin;
for(int j = begin+1; j < last-i; j++)
{
if(array[index] < array[j])
index = j;
}
swap(array[index], array[last-i-1]);
}
}
void Charu(int* array,int begin,int last)
{
int j = 0;
for(int i = 1; i < last; i++)
{
int temp=array[i];
for(j=i-1;j>=begin&&temp<array[j];j--)
array[j+1] = array[j];
array[j+1] = temp;
}
}
void Heapsort2(int* array,int begin,int end)
{
//建堆
int index = 0;
int temp;
int l,r;
for(int i=end/2-1;i>=0;i--)
{
temp = array[i];
index = i;
while(true)
{
l = index*2+1;
r = index*2+2;
if(l>=end)
break;
if(r>=end)
r = l;
else
r = (array[r]>array[l])?r:l;
if(temp<array[r])
array[index] = array[r];
else
break;
index = r;
}
array[index] = temp;
}
//堆排
for(int i=0;i<end-1;i++)
{
temp = array[end-1-i];
array[end-1-i] = array[0];
//堆中还有多少元素?end-i-1
index = 0;
while(true)
{
l = index*2+1;
r = index*2+2;
if(l>end-i-2)
break;
if(r>end-i-2)
r = l;
else
r = (array[r]>array[l])?r:l;
if(temp<array[r])
array[index] = array[r];
else
break;
index = r;
}
array[index] = temp;
}
}
void Heapsort(int* array,int begin,int end)
{
//建堆
int index = 0;
int temp;
for(int i=0;i<end;i++)
{
index = i;
temp = array[i];
while(index>0&&array[(index-1)/2]<temp)
{
array[index] = array[(index-1)/2];
index = (index-1)/2;
}
array[index] = temp;
}
int l,r;
//堆排
for(int i=0;i<end-1;i++)
{
temp = array[end-1-i];
array[end-1-i] = array[0];
//堆中还有多少元素?end-i-1
index = 0;
while(true)
{
l = index*2+1;
r = index*2+2;
if(l>end-i-2)
break;
if(r>end-i-2)
r = l;
else
r = (array[r]>array[l])?r:l;
if(temp<array[r])
array[index] = array[r];
else
break;
index = r;
}
array[index] = temp;
}
}
void QSort(int* array,int begin,int end) //array包含end索引
{
if(begin>=end)
return;
int mid = begin;
int l = begin+1;
int r = end;
while(l<=r)
{
while(array[l]<array[mid])l++; //从左到右找一个比mid大的
while(array[r]>array[mid])r--;//
if(l<r)
swap(array[l],array[r]);
else
break;
l++;
r--;
}
swap(array[mid],array[r]);
QSort(array,begin,r-1);
QSort(array,r+1,end);
}
void Quicksort(int* array,int begin,int end)
{
int index = begin;
for(int i=begin;i<end;i++)
if(array[i]>array[index])
index = i;
swap(array[end-1],array[index]); //垫底 防止l越界
QSort(array,begin,end-2);
}
void Shell(int* array,int begin,int end)
{
int num = end - begin;
int h[20];
h[0] = 1;
int i =1;
int j,k,l,temp;
for(;h[i-1]<num;i++)
{
h[i]=h[i-1]*3+1;
}
i-=2;
while(i>=0)
{
for(j=0;j<h[i];j++)
{
for(k=begin+j+h[i];k<end;k+=h[i])
{
temp = array[k];
for(l = k-h[i];l>=begin&&temp<array[l];l-=h[i])
array[l+h[i]] = array[l];
array[l+h[i]] = temp;
}
}
i--;
}
}
void Test(char* str,void(*fn)(int*,int,int))
{
for(int i=0;i<N;i++) //从大到小,最坏情况
array[i] = N-i;
#ifdef RANDOM
random_shuffle(array,array+N); //随机情况
#endif
DWORD time = GetTickCount();//得到当前时间
fn(array,0,N); //排序
time = GetTickCount()-time;
cout<<str<<"耗时: "<<time<<"毫秒"<<endl;
#ifdef MYDEBUG
for(int i=0;i<20;i++)
cout<<array[i]<<ends;
cout<<endl;
#endif
}
void main()
{
srand(GetTickCount());
array = new int[N];
//Test("选择排序",Xuanze);
//Test("插入排序",Charu);
//Test("冒泡排序",Maopao);
//Test("快速排序",Quicksort);
Test("希尔排序",Shell);
Test("堆排序",Heapsort);
Test("堆排序2",Heapsort2);
}