几种排序算法
发布日期:2021-07-18 15:07:55 浏览次数:2 分类:技术文章

本文共 4962 字,大约阅读时间需要 16 分钟。

简单实现了常见的几种内部排序算法,包括冒泡(Bubble),插入(Insert),快速排序(Quick Sort),堆排序(Heap Sort),归并(Merge),希尔排序(Shell Sort),并对这些算法的耗时在伪随机数上进行了简单的测试。
  说明:

  • 没有实现计数、基数排序等线性复杂度的算法;
  • 各算法只是对算法思想的一次简单模拟,没有过多的优化;
  • 各排序主程序接口参数均为整型数组及元素个数;
  • 程序计时使用了glibc的gettimeofday(),因此。。。;
  • 归并排序中,每次调用都申请和释放堆空间,因此比较耗时。可以采用原地归并、使用全局/静态的方法加以优化;
  • 快速排序中,对待排子序列的长度进行的了判断,对短序列进行优先排序可以减小函数的递归深度(而不是次数);
  • 希尔排序中,为了简洁,步长因子统一取做2.2(11/5)。
  下面是主程序,
#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
          //~ gettimeofday() typedef void (*SORTFUN)(int *a, int n); #define ASIZE 24*1024 //~ array size#define SCOUNT 6 //~ number of sort methodenum {BUBBLE, INSERT, QSORT, HEAP, MERGE, SHELL};char *fname[SCOUNT] =
         
{
"Bubble", "Insert", "Qsort",
"Heap", "Merge", "Shell"
}; SORTFUN fpointer[SCOUNT]; //~ pointers to sort functions int array[SCOUNT][ASIZE]; //~ array(s) under sort. long timeused[SCOUNT]; //~ time taken by every sort function /*******************Generate random data*********************/voidgen_data(void){
srand(time(NULL)); //~ rand seeding
for(int i = 0; i < ASIZE; ++i) //~ generate random array[0]
{
array[0][i] = rand() % ASIZE;
}
for(int i = 1; i < SCOUNT; ++i) //~ copy array[0] to the rest
{
for(int j = 0; j < ASIZE; ++j)
{
array[i][j] = array[i-1][j];
}
}
//NOTE: using TWO loops to maximize caching} /***********************Time the time**********************/longtimer(void) //~ Current Time by millisecond{
struct timeval tv;
gettimeofday(&tv, NULL);
return (tv.tv_sec * 1000 + tv.tv_usec / 1000);}intmain(int AC, char **AV) //~ Both of AC and AV are fascinating ^_^{
gen_data();
 //NOTE: to disable a function, just comment it out below.
fpointer[BUBBLE] = bubble_sort;
fpointer[INSERT] = insert_sort;
fpointer[QSORT] = quick_sort;
fpointer[HEAP] = heap_sort;
fpointer[MERGE] = merge_sort;
fpointer[SHELL] = shell_sort;
 for(int i = 0; i < SCOUNT; ++i)
{
long starttime = timer();
SORTFUN fp = fpointer[i];
if(fp)
fp(array[i], ASIZE);
timeused[i] = timer() - starttime;
}
 //~ Header
printf("%%Method\t\t%%Time\t\t%%Elements\n");
printf("-----------------------------------------\n");
//~ result
for(int i = 0; i < SCOUNT; ++i)
{
printf("%s\t\t%ld\t\t%d\n", fname[i], timeused[i], ASIZE);
}
printf("\n");
return 0;}  各种排序,/************************Bubble Sort**************************/voidbubble_sort(int *a, int n){
for(int i = n - 1; i > 0; --i)
{
int issorted = 0; //~ flag, for some optimition
for(int j = 0; j < i; ++j)
{
if(a[j] > a[j+1])
{
issorted = 1;
int tmp = a[j];
a[j] = a[j+1];
a[j+1] = tmp;
}
}
if(!issorted)
break;
}} /************************Insert Sort**************************/voidinsert_sort(int *a, int n){
for(int i = 0; i < n - 1; ++i)
{
int j = i + 1;
int tmp = a[j];
while(j > 0 && tmp < a[j-1])
{
a[j] = a[j-1];
--j;
}
a[j] = tmp;
}} /************************Quick Sort**************************/intpartition(int *a, int n) //~ seperate a[], using a[0] as pivot{
int l = 0, r = n;
int pivot = a[l];
while(l < r)
{
while( l < r && a[--r] > pivot) ;
a[l] = a[r];
while(l < r && a[++l] < pivot) ;
a[r] = a[l];
}
a[l] = pivot;
return l; //~ return the final index of pivot}voidquick_sort(int *a, int n){
if(n <= 1)
return;
int m = partition(a, n);
if(m <= n / 2)
{
quick_sort(a, m);
quick_sort(a + m + 1, n - m - 1);
}
else
{
quick_sort(a + m + 1, n - m - 1);
quick_sort(a, m);
}} /************************Quik Sort**************************/voidsift(int *a, int i, int n) //~ sift to rebuild the heap rooted by a[i]{
int tmp = a[i];
while(2*i + 1 < n)
{
int j = 2*i + 1;
if(j + 1 < n && a[j+1] > a[j])
++j;
if(a[j] > tmp)
{
a[i] = a[j];
i = j;
}
else
break;
}
a[i] = tmp;}voidheap_sort(int *a, int n){
for(int i = (n-2) / 2; i >= 0; --i) //~ build heap
{
sift(a, i, n);
}
for(int i = 1; i < n; ++i) //~ rebuild the decreasing heap over and over
{
int tmp = a[0];
a[0] = a[n-i];
a[n-i] = tmp;
sift(a, 0, n - i);
}} /***********************Merge Sort**********************/voidmerge_sort(int *a, int n){
if(n == 1)
return;
int *ext = (int*)malloc(sizeof(int) * n / 2);
merge_sort(a, n / 2);
merge_sort(a + n / 2, (n + 1) / 2);
 memcpy(ext, a, n / 2 * sizeof(int));
int i = 0, j = n / 2, k = 0;
while(i < n / 2 && j < n)
{
if(a[j] < ext[i])
a[k++] = a[j++];
else
a[k++] = ext[i++];
}
while(i < n / 2)
a[k++] = ext[i++];
while(j < n)
a[k++] = a[j++];
free(ext);} /***********************Shell Sort**********************/voidshell_sort(int * a, int n){
int step = n / 2;
while(step > 0)
{
for(int i = step; i < n; ++i)
{
int tmp = *(a + i);
int j = i - step;
while(j >= 0 && tmp < *(a + j))
{
*(a + j + step) = *(a + j);
j -= step;
}
*(a + j + step) = tmp;
}
if(step == 2)
step = 1;
else
step = step * 11 / 5; //~ integer is better
}}
对测试结果做一下简要的总结:
快排不是盖的,在我有限的随机测试中,它始终是最快的;
这里的归并排序由于堆内存的频繁申请与释放,相比同量级的其它算法,是最慢的;
希尔排序相当给力,尽管步长因子选择很粗糙,但在我的测试中,还是超过了堆排序。这从侧面证明了,在接近有序时插入排序是很快的。事实上,插入排序,由于其简洁性,常常做为高级排序算法的末级算法(局部算法)。


原文地址:http://www.dutor.net/index.php/2010/10/sorts-of-sort-methods/

转载地址:https://blog.csdn.net/iteye_21199/article/details/82478687 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:Oracle Security API - FND_FUCTION.TEST
下一篇:常用的几个字符串Hash函数

发表评论

最新留言

第一次来,支持一个
[***.172.111.71]2022年05月22日 10时09分39秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

最新文章