注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

widebright的个人空间

// 编程和生活

 
 
 

日志

 
 

插入排序(insertion sort)和快速排序(quick sort) 悲剧  

2011-08-18 15:37:34|  分类: 程序设计 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
早上去面试,有一道题目是给数组排序。要用伪码或者c代码实现。我觉得在这么短时间没能写出没有错误的快速排序的代码了。插入排序在元素个数比较小的时 候,性能应该是很不错的,所以就些了插入排序了。 结果思想是对了,细节地方还是搞错了,悲剧了,这都写不出来。以前写过选择排序,冒泡排序的,各种排序算法也都看过。看来上面都是要亲手自己做一遍比较好 啊。 回来参考 算法导论,写了一下,顺便吧快速排序也弄了一遍。

#include<stdio.h>
#include<stdlib.h>

void insertion_sort (int a[], int n) 
{
      int i=0;
      for (i=1; i< n; i++ )  {
         int k = i-1;
         int value = a[i];
         //printf ("a[%d]==%d\n",i , value);         
         while ((k >= 0) &&  (value < a[k]))
         {           
             // printf ("%d-%d\n",value , a[k]);
              a[k+1] = a[k]; 
              k--;
         }
         a[k+1] = value;        
      }
}

void  exchange (int *i , int *j)
{
    int x = *i;
    *i= *j;
    *j = x;
}

int partition ( int a[], int start, int end)
{
      int x = a[end];
      int i = start -1;
      int j;
      for (j = start; j < end; j++) {
            
             if (a[j] < x) {
                i++;
                exchange (&a[j],&a[i]);              
             } 
      }
                 
      exchange (&a[i+1],&a[end]);   
     
      return i+1;
     
}

int quick_sort ( int a[], int start, int end)
{     
      if ( start < end ) {
             int mid = partition(a,start,end);
             quick_sort(a, start, mid-1);
             quick_sort(a, mid+1, end);     
      }

}

int main(void) {

 int a[] = {3,4,56,78,67,9,1,9,23,22,423,122};
 int i = 0;
 int n = 12;
 
insertion_sort (a,n);

//quick_sort(a,0,11);

for ( i =0;i< n;i++) {
     printf("%d, ",a[i]);
}

printf ( "\n");


}
  评论这张
 
阅读(577)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017