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

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

2024-10-30 04:21:03   211人阅读

比较的算法有插入排序，堆排序，合并排序，快速排序和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排序


联系
我们