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排序将如何进行？
阅读(2017) | 评论(0) | 转发(1) |
