数据结构之排序的概念及分类

ゝ一纸荒年。 2022-05-31 07:52 211阅读 0赞

**排序的概念**

排序的一般定义：排序是计算机内经常进行的一种操作，其目的是将一组“无序”的数据元素调整为“有序”的数据元素。  
例如：将下列关键字序列  
52,49, 80, 36, 14, 58, 61, 23, 97, 75  
调整为  
14,23, 36, 49, 52, 58, 61 ,75, 80, 97

**排序的数学定义**：假设含***n***个数据元素的序列为**\{ R1, R2, …, Rn \}**其相应的关键字序列为**\{ K1, K2, …, Kn \}**这些关键字相互之间可以进行比较，即在它们之间存在着这样一个关系 ：**Kp1**≤**Kp2**≤**…**≤**Kpn**按此固有关系将上式记录序列重新排列为**\{ Rp1, Rp2, …**，**Rpn \}**的操作称作排序。

**排序的示例**

**![70][]**

到这里，可能有人发现了问题，按总评排序后为什么张无忌的排名比郭靖靠前呢？这就涉及排序的稳定性范畴了。

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

上例中稳定的排序应该如下图：

![70 1][]

上面我们一直在强调**关键字**，有时候我们需要排序的数列关键字不止一个，怎么办呢?这就要说一下多关键字排序了。

**多关键字排序**：

1.排序结果首先按关键字**1**进行排序；

2. 当关键字**1**相同时按关键字**2**进行排序；  
**……**

3. 当关键字**n-1**相同时按关键字**n**进行排序。

**多关键字排序的示例：**

![70 2][]

既然是多关键字排序，那么就会有一个问题：多关键字排序算法是否比单关键字排序算法更复杂？

要回答这个问题呢，首先要了解一下排序的关键操作，比较和交换。

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

交换：数据元素之间需要交换才能得到预期结果。

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

我们就用一个小例子来看一下

#include <stdio.h>
    
    // 定义结构体
    typedef struct _tag_DataElem
    {
        char desc[20];          // 比较关键字描述
        int key1;               // 关键字1
        int key2;               // 关键字2
    } DataElem;
    
    // 比较算法1
    int compare1(DataElem* ld, DataElem* rd)
    {
        int ret = 0;
        // 比较元素1关键字1大于比较元素2关键字1，返回1
        if( ld->key1 > rd->key1 )
        {
            ret = 1;
        }
        // 比较元素1关键字1等于比较元素2关键字1，比较关键字2
        else if( ld->key1 == rd->key1 )
        {    		
        		// 比较元素1关键字2大于比较元素2关键字2，返回1
            if( ld->key2 > rd->key2 )
            {
                ret = 1;
            }
            
        		// 比较元素1关键字2小于比较元素2关键字2，返回-1
            if( ld->key2 < rd->key2 )
            {
                ret = -1;
            }
        }
        // 比较元素1关键字1小于比较元素2关键字1，返回-1
        else
        {
            ret = -1;
        }
        
        return ret;
    }
    
    // 比较算法2
    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;
    }

从上述代码中我们发现，算法1比较中规中矩，算法2运用了一个小技巧，因为比较的是两位数，所以将2个两位数关键字组合成一个4位数的关键字，然后再比较。我们不考虑编程的技巧，单从时间复杂度来看，他们都是O(1)，所以多关键字比较的算法并不一定比单个关键字比较的算法复杂。

**排序的分类**

由于待排序的记录数量不同，使得排序过程中涉及的存储器不同，所以可将排序方法按存储方式分为**内部排序**和**外部排序**。

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

既然是排序，那么每一个排序算法都会有优劣。如何进行审判呢？

**排序的审判：**

1.时间性能：关键性能差异体现在比较和交换的数量；

2.辅助存储空间：为完成排序操作需要的额外的存储空间，必要时可以**“**空间换时间**”**；

3.算法的实现复杂性：过于复杂的排序法会影响代码的可读性和可维护性，也可能影响排序的性能。

[70]: /images/20220531/1e1ad3e5f42a40cdaa0bdb0d00de05a4.png
[70 1]: /images/20220531/437b77cc99ac49869113a6c85f7a758f.png
[70 2]: /images/20220531/e6c4780965f44a179d4745db91b7c3f8.png