排序的稳定性

如果i==j,且i在j前面,排序完成后i仍旧在j前面则这个排序算法是稳定的，否则不稳定.

多关键字排序

先按关键字1排序，关键词1相同则按2排序。。。 n

排序中的关键操作

　　1、比较：任意两个数据元素通过比较操作确定先后顺序。

　　2、交换: 数据元素之间需要交换才能得到预期结果

对于多关键字排序，只需要在比较操作时同时考虑多个关键字即可!

内排序

排序过程不需要访问外存就可以完成（数据可以全部装载到内存）

外排序

待排序数据量太大，整个排序过程不能在内存完成。

排序的审判

时间性能（主要）

　　主要体现在比较和交换的数量

2、辅助存储空间

　　完成排序需要的额外存储空间

　　必要时可以空间换时间

3、算法的实现复杂性

　　过于复杂的算法会影响代码的可读性和可维护性，也可能影响排序的性能

 

多关键字比较示例：

MultiCompare.c

#include 
     
      typedef struct _tag_DataElem{    char desc[20];    int key1;    int key2;} DataElem;int compare1(DataElem* ld, DataElem* rd){    int ret = 0;        if( ld->key1 > rd->key1 )    {        ret = 1;    }    else if( ld->key1 == rd->key1 )    {        if( ld->key2 > rd->key2 )        {            ret = 1;        }                if( ld->key2 < rd->key2 )        {            ret = -1;        }    }    else    {        ret = -1;    }        return ret;}int compare2(DataElem* ld, DataElem* rd){    return (ld->key1*100 + ld->key2) - (rd->key1*100 + rd->key2);}int main(){    DataElem d1 = {
   "d1", 91, 80};    DataElem d2 = {
   "d2", 91, 88};        printf("Compare1 %s and %s: %d\n", d1.desc, d2.desc, compare1(&d1, &d2));    printf("Compare2 %s and %s: %d\n", d1.desc, d2.desc, compare2(&d1, &d2));        return 0;}
     

 

选择排序：

从左往右，每地 i 趟 找出i下标后面最小的元素，然后放到 i 的位置

由于在直接选择排序中存在着不相邻元素之间的互换，因此，直接选择排序是一种不稳定的排序方法。

SelectionSort.c

#include 
     
      void println(int array[], int len){    int i = 0;        for(i=0; i
     

 

插入排序

通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应的位置并插入。

直接插入排序属于稳定的排序，最坏为O(n^2)，为O(1)。

InerstionSort.c

#include 
     
      void println(int array[], int len){    int i = 0;        for(i=0; i
      
       =0) && (array[j]>temp); j--)        {            array[j+1] = array[j];            k = j;        }                array[k] = temp;    }}int main(){    int array[] = {
   21, 25, 49, 25, 16, 8};    int len = sizeof(array) / sizeof(*array);         println(array, len);        InertionSort(array, len);        println(array, len);        return 0;}
      
     

 

冒泡排序：

从后往前，相邻的两个元素对比，如果后面比前面小，则交换位置，一趟下来则首位元素为最小元素

稳定排序

#include 
     
      void println(int array[], int len){    int i = 0;        for(i=0; i
      
       i; j--)        {            if( array[j] < array[j-1] )            {                swap(array, j, j-1);                                exchange = 1;            }        }    }}int main(){    int array[] = {
   21, 25, 49, 25, 16, 8};    int len = sizeof(array) / sizeof(*array);         println(array, len);        BubbleSort(array, len);        println(array, len);        return 0;}