首页 > 代码库 > 算法有插入排序,堆排序,合并排序,快速排序和stooge排序

算法有插入排序,堆排序,合并排序,快速排序和stooge排序

比较的算法有插入排序,堆排序,合并排序,快速排序和stooge排序,
先说一下比较结果
1,比较插入和stooge排序,stooge的表现如此之差,数组大小在2000时
     InsertSort VS StoogeSort ‘s Running Time:     16ms:47672ms;
     Terribly! Isn‘t It?
      所以在后面的比较中,没有带stooge这个垃圾算法
2,插入排序,堆排序,合并排序,快速排序运行时间对比

(网易博客的表格功能太差了,不爽,只好以文本对齐展现给大家了):

运行时间为MS

数据级别:          10000     50000   100000   200000   1 000 000      10 000 000(列举了3次运行情况)

Insert_sort:            125       3625      16953      67640     2431156        omit     

 Heap_sort:            15          110        281          594           4500            (47906   110141 115109)

Merge_sort:          16           140      422          1047         16281           2604610 

Quick_sort :           15           47        125           266            2891             (258187   272031 139140)

说明:数据是有随机生成的,没有任何分布规律。

机器配置,P4 2.8G,256M,


结论与个人感想:

a。快速排序果然是快,数据越大优势越明显,并且实现上也较为简单。理论上它的平均时间和归并排序,堆排序都是一样的(在最坏情况还还不如它们),都是O(nlog2n),但实际运行来看比它们两者的速度都快一倍以上。COOL!

b. 合并排序需要额外相同规模的数组,空间复杂度为O(n)。从具体实现来看,这只是一种理论上的优秀算法,想法比较简单直接,但实现上比quicksort 复杂,运行时间也差,在数据很大的时候运行时间是heapsort的两倍,更不用说quicksort了,常数 C make effect。

c.堆排序利用了二分树的结构,将时间复杂度降到O(nlog2n),理论上和实现上表现都不错,并且发现在数据量是
10 000 000时,甚至优于快排,????为什么呢??。又对5 000 000时做测试。heapsort三次运行时间(25109,25531,25203)quciksort三次运行时间(35687,37094, 39609),快排在这时不如堆排序了,有意思,不知什么原因?



#include<cstdlib>
#include<iostream>
#include<fstream>
#include<ctime>

using namespace std;
const int size=100000;
static int count=0;
//插入排序
void insert_sort(int *,int,int);
//快速排序
int partition(int *, int ,int );
void quick_sort(int *, int ,int);
void quick_sort_rec(int *, int ,int);
//合并排序
void merge(int *,int,int,int);
void merge_sort(int *, int ,int);
//堆排序
void BuildMaxHeap(int *,int );
void MaxHeapify(int *,int,int);
void heap_sort(int *,int ,int );
//stoogesort
void stooge_sort(int *, int, int);

int run_sort(void (*al)(int *,int,int),int *a,int start,int end)
{
    clock_t t0,t1;
    t0=clock();
    (*al)(a,start,end);
    t1=clock();
    return t1-t0;
}

int main()
{
    int i;
    ofstream fout("compare.txt",ios::app);
    int *array0=new int[size];
    int *array_b=new int[size];
    time_t t;
   
    srand(time(&t));
    for( i=0; i<size; i++)
    {
        array_b[i]=rand();
        //if(i%1000==0)
        //    cout<<array[i]<<endl;
    }
    fout<<endl;
    fout<<"测试数组size="<<size<<endl;
    //测试插入排序
    for( i=0; i<size; i++)
    {
        array0[i]=array_b[i];
    }   
    i=run_sort(insert_sort,array0,0,size-1);   
    cout<<"Insert Sort Running Time:"<<i<<endl;
    fout<<"Insert Sort Running Time:"<<i<<endl;

    //测速堆排序
    for( i=0; i<size; i++)
    {
        array0[i]=array_b[i];
    }   
    i=run_sort(heap_sort,array0,0,size-1);   
    cout<<"Heap Sort Running Time:"<<i<<endl;
    fout<<"Heap Sort Running Time:"<<i<<endl;
    //测试合并排序
    for( i=0; i<size; i++)
    {
        array0[i]=array_b[i];
    }   
    i=run_sort(merge_sort,array0,0,size-1);   
    cout<<"Merge Sort Running Time:"<<i<<endl;
    fout<<"Merge Sort Running Time:"<<i<<endl;
   
    //测试快速排序
    for( i=0; i<size; i++)
    {
        array0[i]=array_b[i];
    }   
    i=run_sort(quick_sort_rec,array0,0,size-1);   
    cout<<"Quick Sort Running Time:"<<i<<endl;
    fout<<"Quick Sort Running Time:"<<i<<endl;
   
    /*//测试stooge排序
    for( i=0; i<size; i++)
    {
        array0[i]=array_b[i];
    }   
    i=run_sort(stooge_sort,array0,0,size-1);   
    cout<<"Stooge Sort Running Time:"<<i<<endl;
    fout<<"Stooge Sort Running Time:"<<i<<endl;
     */
   return 0;
}

void swap(int *a, int m,int n)
{
    int temp=a[m];
    a[m]=a[n];
    a[n]=temp;
}
void insert_sort(int *a,int start,int end)
{
    int i,j,key;
    for( i= start; i<end; i++)
    {
        //cout<<i<<" ";
        key=a[i];
        j=i-1;
        while(a[j]>key && j>=0)
        {
            a[j+1]=a[j];
            j--;
        }
        a[j+1]=key;
    }
}


int partition(int *a,int low,int high)
{
    int i,j;    
    int key=a[high];
    i=low-1;
    j=low;
    for( ; j<high; j++)
    {
        if(a[j]<=key)
        {
            i++;
            swap(a,i,j);
        }
    }
    swap(a,i+1,high);
    return i+1;
}
//递归调用次数太多 栈溢出!
void quick_sort_rec(int *a,int low,int high)
{
    int mid;
    if(low<high)
    {
      mid=partition(a,low,high);
    quick_sort_rec(a,low,mid-1);
    quick_sort_rec(a,mid+1,high);
    }
}
//非递归版 --迭代
void quick_sort(int *base,int start,int end)
{
    const int stacksize=1000;
    int *stack=new int[stacksize];
    int top=0;
    stack[top++]=start;
    stack[top++]=end-start+1;
    while(top!=0)
    {
        //cout<<top<<endl;
        top--;
        int r=stack[top];
        top--;
        int p=stack[top];       
        if(p>=r)
            continue;
        int m=partition(base,p,r);
        //push the left
        stack[top++]=p;
        stack[top++]=m-1;
        //push the right
        stack[top++]=m+1;
        stack[top++]=r;
    }
}
void merge(int *a,int p,int q,int r)
{
    int n1,n2;
    int i,j,k;
    //int *L=new int[size/2+2];
    //int *R=new int[size/2+2];
    int *L=new int[1000];
    int *R=new int[1000];
    if(r-q>998)
    {
        L=new int[size/2+3];
        R=new int[size/2+3];
    }
    n1=q-p+1;
    n2=r-q;
    for( i=0; i<n1; i++)
        L[i]=a[p+i-1];
    for( i=0; i<n2; i++)
        R[i]=a[q+i];
    L[n1+1]=100000000;
    R[n2+1]=100000000;
    i=0;
    j=0;
    for(k=p; k<=r; k++)
    {
        if(L[i]<=R[j])
        {
            a[k]=L[i];
            i++;
        }
        else
        {
            a[k]=R[j];
            j++;
        }
    }


    delete L;
    delete R;
}
void merge_sort(int *a,int p,int r)
{
    if(r%100000==0)
        cout<<r<<endl;
    if(p+5>r)
    {
        if(p<r)
            insert_sort(a,p,r);
    }
    else
    {
        int tt=(p+r)/2;
        merge_sort(a,p,tt);
        merge_sort(a,tt+1,r);
        merge(a,p,tt,r);
    }
}
void heap_sort(int *a,int start,int end)
{
    int i;
    int length=end-start;
    int hsize=length;
    BuildMaxHeap(a,hsize);
    for( i=length; i>1; i--)
    {
        swap(a,1,i);
        hsize--;
        MaxHeapify(a,1,hsize);
    }

}
void BuildMaxHeap(int *a,int size)
{
    int i;
    for( i=size/2; i>0; i--)
    {
        MaxHeapify(a,i,size);
    }
}
void MaxHeapify(int *a,int i,int size)
{
    int l,r,largest;
    l=2*i;
    r=2*i+1;
    if(l<=size &&a[l]>a[i])
        largest=l;
    else
        largest=i;
    if(r<=size && a[r]>a[largest])
        largest=r;
    if(largest!= i)
    {
        swap(a,i,largest);
        MaxHeapify(a,largest,size);
    }
}
//垃圾算法 坏我丢分!!
void stooge_sort(int *a, int i, int j)
{
    int k;
    if(a[i]>a[j])
        swap(a,i,j);
    if(i+1>=j)
    {
        //count--;
        return;
    }
    k=(j-i+1)/3;
    stooge_sort(a,i,j-k);
    stooge_sort(a,i+k,j);
    stooge_sort(a,i,j-k);
    count++;

}比较的算法有插入排序,堆排序,合并排序,快速排序和stooge排序,
先说一下比较结果
1,比较插入和stooge排序,stooge的表现如此之差,数组大小在2000时
     InsertSort VS StoogeSort ‘s Running Time:     16ms:47672ms;
     Terribly! Isn‘t It?
      所以在后面的比较中,没有带stooge这个垃圾算法
2,插入排序,堆排序,合并排序,快速排序运行时间对比

(网易博客的表格功能太差了,不爽,只好以文本对齐展现给大家了):

运行时间为MS

数据级别:          10000     50000   100000   200000   1 000 000      10 000 000(列举了3次运行情况)

Insert_sort:            125       3625      16953      67640     2431156        omit     

 Heap_sort:            15          110        281          594           4500            (47906   110141 115109)

Merge_sort:          16           140      422          1047         16281           2604610 

Quick_sort :           15           47        125           266            2891             (258187   272031 139140)

说明:数据是有随机生成的,没有任何分布规律。

机器配置,P4 2.8G,256M,


结论与个人感想:

a。快速排序果然是快,数据越大优势越明显,并且实现上也较为简单。理论上它的平均时间和归并排序,堆排序都是一样的(在最坏情况还还不如它们),都是O(nlog2n),但实际运行来看比它们两者的速度都快一倍以上。COOL!

b. 合并排序需要额外相同规模的数组,空间复杂度为O(n)。从具体实现来看,这只是一种理论上的优秀算法,想法比较简单直接,但实现上比quicksort 复杂,运行时间也差,在数据很大的时候运行时间是heapsort的两倍,更不用说quicksort了,常数 C make effect。

c.堆排序利用了二分树的结构,将时间复杂度降到O(nlog2n),理论上和实现上表现都不错,并且发现在数据量是
10 000 000时,甚至优于快排,????为什么呢??。又对5 000 000时做测试。heapsort三次运行时间(25109,25531,25203)quciksort三次运行时间(35687,37094, 39609),快排在这时不如堆排序了,有意思,不知什么原因?



#include<cstdlib>
#include<iostream>
#include<fstream>
#include<ctime>

using namespace std;
const int size=100000;
static int count=0;
//插入排序
void insert_sort(int *,int,int);
//快速排序
int partition(int *, int ,int );
void quick_sort(int *, int ,int);
void quick_sort_rec(int *, int ,int);
//合并排序
void merge(int *,int,int,int);
void merge_sort(int *, int ,int);
//堆排序
void BuildMaxHeap(int *,int );
void MaxHeapify(int *,int,int);
void heap_sort(int *,int ,int );
//stoogesort
void stooge_sort(int *, int, int);

int run_sort(void (*al)(int *,int,int),int *a,int start,int end)
{
    clock_t t0,t1;
    t0=clock();
    (*al)(a,start,end);
    t1=clock();
    return t1-t0;
}

int main()
{
    int i;
    ofstream fout("compare.txt",ios::app);
    int *array0=new int[size];
    int *array_b=new int[size];
    time_t t;
   
    srand(time(&t));
    for( i=0; i<size; i++)
    {
        array_b[i]=rand();
        //if(i%1000==0)
        //    cout<<array[i]<<endl;
    }
    fout<<endl;
    fout<<"测试数组size="<<size<<endl;
    //测试插入排序
    for( i=0; i<size; i++)
    {
        array0[i]=array_b[i];
    }   
    i=run_sort(insert_sort,array0,0,size-1);   
    cout<<"Insert Sort Running Time:"<<i<<endl;
    fout<<"Insert Sort Running Time:"<<i<<endl;

    //测速堆排序
    for( i=0; i<size; i++)
    {
        array0[i]=array_b[i];
    }   
    i=run_sort(heap_sort,array0,0,size-1);   
    cout<<"Heap Sort Running Time:"<<i<<endl;
    fout<<"Heap Sort Running Time:"<<i<<endl;
    //测试合并排序
    for( i=0; i<size; i++)
    {
        array0[i]=array_b[i];
    }   
    i=run_sort(merge_sort,array0,0,size-1);   
    cout<<"Merge Sort Running Time:"<<i<<endl;
    fout<<"Merge Sort Running Time:"<<i<<endl;
   
    //测试快速排序
    for( i=0; i<size; i++)
    {
        array0[i]=array_b[i];
    }   
    i=run_sort(quick_sort_rec,array0,0,size-1);   
    cout<<"Quick Sort Running Time:"<<i<<endl;
    fout<<"Quick Sort Running Time:"<<i<<endl;
   
    /*//测试stooge排序
    for( i=0; i<size; i++)
    {
        array0[i]=array_b[i];
    }   
    i=run_sort(stooge_sort,array0,0,size-1);   
    cout<<"Stooge Sort Running Time:"<<i<<endl;
    fout<<"Stooge Sort Running Time:"<<i<<endl;
     */
   return 0;
}

void swap(int *a, int m,int n)
{
    int temp=a[m];
    a[m]=a[n];
    a[n]=temp;
}
void insert_sort(int *a,int start,int end)
{
    int i,j,key;
    for( i= start; i<end; i++)
    {
        //cout<<i<<" ";
        key=a[i];
        j=i-1;
        while(a[j]>key && j>=0)
        {
            a[j+1]=a[j];
            j--;
        }
        a[j+1]=key;
    }
}


int partition(int *a,int low,int high)
{
    int i,j;    
    int key=a[high];
    i=low-1;
    j=low;
    for( ; j<high; j++)
    {
        if(a[j]<=key)
        {
            i++;
            swap(a,i,j);
        }
    }
    swap(a,i+1,high);
    return i+1;
}
//递归调用次数太多 栈溢出!
void quick_sort_rec(int *a,int low,int high)
{
    int mid;
    if(low<high)
    {
      mid=partition(a,low,high);
    quick_sort_rec(a,low,mid-1);
    quick_sort_rec(a,mid+1,high);
    }
}
//非递归版 --迭代
void quick_sort(int *base,int start,int end)
{
    const int stacksize=1000;
    int *stack=new int[stacksize];
    int top=0;
    stack[top++]=start;
    stack[top++]=end-start+1;
    while(top!=0)
    {
        //cout<<top<<endl;
        top--;
        int r=stack[top];
        top--;
        int p=stack[top];       
        if(p>=r)
            continue;
        int m=partition(base,p,r);
        //push the left
        stack[top++]=p;
        stack[top++]=m-1;
        //push the right
        stack[top++]=m+1;
        stack[top++]=r;
    }
}
void merge(int *a,int p,int q,int r)
{
    int n1,n2;
    int i,j,k;
    //int *L=new int[size/2+2];
    //int *R=new int[size/2+2];
    int *L=new int[1000];
    int *R=new int[1000];
    if(r-q>998)
    {
        L=new int[size/2+3];
        R=new int[size/2+3];
    }
    n1=q-p+1;
    n2=r-q;
    for( i=0; i<n1; i++)
        L[i]=a[p+i-1];
    for( i=0; i<n2; i++)
        R[i]=a[q+i];
    L[n1+1]=100000000;
    R[n2+1]=100000000;
    i=0;
    j=0;
    for(k=p; k<=r; k++)
    {
        if(L[i]<=R[j])
        {
            a[k]=L[i];
            i++;
        }
        else
        {
            a[k]=R[j];
            j++;
        }
    }


    delete L;
    delete R;
}
void merge_sort(int *a,int p,int r)
{
    if(r%100000==0)
        cout<<r<<endl;
    if(p+5>r)
    {
        if(p<r)
            insert_sort(a,p,r);
    }
    else
    {
        int tt=(p+r)/2;
        merge_sort(a,p,tt);
        merge_sort(a,tt+1,r);
        merge(a,p,tt,r);
    }
}
void heap_sort(int *a,int start,int end)
{
    int i;
    int length=end-start;
    int hsize=length;
    BuildMaxHeap(a,hsize);
    for( i=length; i>1; i--)
    {
        swap(a,1,i);
        hsize--;
        MaxHeapify(a,1,hsize);
    }

}
void BuildMaxHeap(int *a,int size)
{
    int i;
    for( i=size/2; i>0; i--)
    {
        MaxHeapify(a,i,size);
    }
}
void MaxHeapify(int *a,int i,int size)
{
    int l,r,largest;
    l=2*i;
    r=2*i+1;
    if(l<=size &&a[l]>a[i])
        largest=l;
    else
        largest=i;
    if(r<=size && a[r]>a[largest])
        largest=r;
    if(largest!= i)
    {
        swap(a,i,largest);
        MaxHeapify(a,largest,size);
    }
}
//垃圾算法 坏我丢分!!
void stooge_sort(int *a, int i, int j)
{
    int k;
    if(a[i]>a[j])
        swap(a,i,j);
    if(i+1>=j)
    {
        //count--;
        return;
    }
    k=(j-i+1)/3;
    stooge_sort(a,i,j-k);
    stooge_sort(a,i+k,j);
    stooge_sort(a,i,j-k);
    count++;

}

算法有插入排序,堆排序,合并排序,快速排序和stooge排序