C++排序算法 总括

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);
}

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理