数据结构 --数组排序

时间：2010-07-18 来源：bluedrum

Andrew Huang [email protected] 常见数组排序方式 --------------------------------------------------------------------------- 一般有四大类，以都是指升序排列。 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排序将如何进行？