首页 > 代码库 > 算法有插入排序,堆排序,合并排序,快速排序和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++;
}
先说一下比较结果
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排序
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。