Chinaunix首页 | 论坛 | 博客
  • 博客访问: 1630401
  • 博文数量: 311
  • 博客积分: 7778
  • 博客等级: 少将
  • 技术积分: 4186
  • 用 户 组: 普通用户
  • 注册时间: 2009-11-09 19:59
个人简介

蓝点工坊(http://www.bluedrum.cn) 创始人,App和嵌入式产品开发。同时也做相应培训和外包工作。 详细介绍 http://pan.baidu.com/s/1y2g88

文章存档

2012年(3)

2011年(115)

2010年(170)

2009年(23)

分类: C/C++

2010-07-18 01:10:01

Andrew Huang
 
常见数组排序方式
---------------------------------------------------------------------------
 一般有四大类,以都是指升序排列。
  1.冒泡排序法
      它是从数组的一端开始,依次对相邻两元素进行比较,当前面数比后面数大时,就进行一次交换,就好象最大值慢慢从数组从底部,缓缓上升到顶部,就象气泡从水底向上运动一样。
  冒泡法的工作过程,以一个字符数组dcab的第一轮排序为例。
    排序前:dcab
    第一遍 adcb
    第二遍 abdc
    第三遍 abcd
 
      这种方法优点是实现简单易懂。缺点比较次数较多。
  
 
 
  2.直接选择排序法
      第一趟扫描所有数据,选择其中最小的一个与第一个数据互换;第二趟从第二个数据开始向后扫描,选择最小的与第二个数据互换;依次进行下去,进行了(n-1)趟扫描以后就完成了整个排序过程。
 
      选择排序工作过程,以一个字符数组bdac排序为例:
    初始 bdac
    第一遍adbc ,//扫描一次找到a后,将其第一个位置的b交换
    第二遍abdc  //扫描第二次找b
    第三遍abcd
       这一种排序类似于冒泡排序,但是它的优点是交换次数大大减少
 
   3.直接插入排序:
    
     首先对数组头两元素进行比较并排序,然后将第三个元素与排好序前二个元素进行比较,插在它应在位置上。接着取第四个元素,把它插入到已排好了前三个元素组成数组中,重复这个过程直到最后一个元素。
  以字符dcab为例
    排序前dcab
    第一遍cdab
    第二遍acdb
    第三遍abcd

 
     插入排序法在最坏情况下的交换次数与冒泡选择排序一样多,而平均情况下比另两种稍好。
  当然,插入排序有两个优点:(一)、排序进度与被排序数组的初始顺序好坏有关。好则快,坏则慢,所以特别合适那些基本已排序的数组。(二)、如果数组是按照两个关键字排序的,则在一次插入排序之后,数组仍按两个关键字排序。
 
  4.快速排序.
    快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。它采用了一种分治的策略,通常称其为分治法(Divide-and-ConquerMethod)。
     快速排序是对冒泡排序的一种改进。它的基本思想是:通过一躺排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按次方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。
 
   
     
   当分区足够少时,比如(小于10)时,可以直接采用其它排序方法进排序。
 
标准C库的排序函数
----------------------------------------------------------------------------
 
  标准C库已经实现内置数组快速排序函数 qsort();因此开发,一般是更多是采用这函数
 
  void qsort( void *base, size_t num, size_t width, int ( *compare )(const void *elem1, const void *elem2 ) );
 
参数:
  base:排序数组的基址.
  num :排序元素个数
  width:排序元素宽度
  compare:比较函数指针。用于判断两个元素之间的大小关系。如果这个为空,则默认采用字典排序方式比较.
  要求这个函数返回跟strcmp一样,如elem1>emlem2,返回大于0的值,相等返回0,小于返回负数。
 
1.字符数组排序
  
 

int char_cmp( const void *a , const void *b )
{
   return *(char *)a - *(int *)b;
}

#define ARY_SIZE(a) (sizeof((a))/sizeof(a[0]))

void test1()
{
  char word[] = {'A','K','f','d','G'};
  
  qsort(word,ARY_SIZE(word),sizeof(word[0]),char_cmp);
  
}

 

int str_cmp( const void *a , const void *b )
{
   return strcmp((char *)a, *(int *)b);
}

#define ARY_SIZE(a) (sizeof((a))/sizeof(a[0]))

void test2()
{
  char * str[] = {"hxy","Andrew","hi","abc","hello"};
  
  qsort(str,ARY_SIZE(str),sizeof(str[0]),str_cmp);
  
}


?double排序将如何进行?


阅读(1952) | 评论(0) | 转发(1) |
给主人留下些什么吧!~~