第20节 排序的概念及分类

-------------------------------------资源来源于网络,仅供自学使用,如有侵权,联系我必删.

第一:

排序的一般定义

? 排序是计算机内经常进行的一种操作 ， 其目的是将一组“ 无序” 的数据元素调整为“ 有序” 的数据元素 。

例如 ： 将下列关键字序列
              52, 49, 80, 36, 14, 58, 61, 23, 97, 75
             调整为
              14, 23, 36, 49, 52, 58, 61 ,75, 80, 97

 

第二:

排序的稳定性

  如果在序列中有两个数据元素r [i]  和 r [j] 它 ， 它们的关键字 k[i ]  ==  k[j] 且在排序之前 ， 对象r[i]排在 r [j]  。 如果在排序之后 ， 对象 r[i] 仍在对象r [j] ， 则 的前面 ， 则称这个排序方法是稳定的 ， 否则称这个排序方法是不稳定的.

 

第三:

排序中的关键操作

? 比较
   任意两个数据元素通过比较操作确定先后次序
? 交换
  数据元素之间需要交换才能得到预期结果

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

 

第四:

多关键字比较操作

#include <stdio.h>

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;
}

第五:

内排序和外排序

? 内排序
   整个排序过程不需要访问外存便能完成
? 外排序
   待排序的数据元素数量很大 ， 整个序列的排序过程不可能在内存中完成

第六:

排序的审判

? 时间性能
  关键性能差异体现在比较和交换的数量
? 辅助存储空间
   为完成排序操作需要的额外的存储空间
   必要时可以“ 空间换时间”
? 算法的实现复杂性
   过于复杂的排序法会影响代码的可读性和可维护性 ， 也可能影响排序的性能

 

 

小结

?排序是数据元素从无序到有序的过程

? 排序具有稳定性 ， 是选择排序算法的因素之一
? 比较和交换是排序的基本操作
? 多关键字排序与单关键字排序无本质区别
? 排序的时间性能是区分排序算法好坏的主要因素