0.目录

1.

2.

3.

4.

1.排序的基本概念

排序的一般定义：

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

排序的数学定义：

排序的示例：

问题：

• 按总评排序后为什么张无忌的排名比郭靖靠前呢？

排序的稳定性：

稳定性排序示例：

多关键字排序：

• 排序时需要比较的关键字多余一个
• 排序结果首先按关键字1进行排序
• 当关键字1相同时按关键字2进行排序
• ......
• 当关键字n-1相同时按关键字n进行排序

多关键字排序示例：

问题：

• 多关键字排序是否比单关键字排序更复杂？

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

演示多关键字的比较：

#include 
    
     #include "Object.h"using namespace std;using namespace StLib;struct Test : public Object{    int key1;    int key2;    Test(int k1, int k2)    {        key1 = k1;        key2 = k2;    }    bool operator == (const Test& t)    {        return (key1 == t.key1) && (key2 == t.key2);    }    bool operator != (const Test& t)    {        return !(*this == t);    }    bool operator < (const Test& t)    {        return (key1 < t.key1) || ((key1 == t.key1) && (key2 < t.key2));    }    bool operator >= (const Test& t)    {        return !(*this < t);    }    bool operator > (const Test& t)    {        return (key1 > t.key1) || ((key1 == t.key1) && (key2 > t.key2));    }    bool operator <= (const Test& t)    {        return !(*this > t);    }};int main(){    Test t1(3, 4);    Test t2(2, 5);    Test t3(3, 5);    cout << "(t1 > t2) : " << (t1 > t2) << endl;    cout << "(t1 > t3) : " << (t1 > t3) << endl;    return 0;}
    

运行结果为：

(t1 > t2) : 1(t1 > t3) : 0

排序中的关键操作：

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

排序的审判：

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

StLib中的排序类设计：

定义StLib中的排序类（Sort.h）：

#ifndef SORT_H#define SORT_H#include "Object.h"namespace StLib{class Sort : public Object{private:    Sort();    Sort(const Sort&);    Sort& operator = (const Sort&);    template 
    
         static void Swap(T& a, T&b)    {        T c(a);        a = b;        b = c;    }public:};}#endif // SORT_H
    

2.选择排序

选择排序的基本思想：

第 i 次选择排序示例：

实现选择排序（在Sort.h中）：

public:    template 
    
         static void Select(T array[], int len, bool min2max = true)    {        for(int i=0; i
     
       array[j]) : (array[min] < array[j]) )                {                    min = j;                }            }            if( min != i )            {                Swap(array[i], array[min]);            }        }    }
     
    

main.cpp测试：

#include 
    
     #include "Sort.h"using namespace std;using namespace StLib;int main(){    int array[] = {3, 1, 2, 5, 4};    Sort::Select(array, 5);    for(int i=0; i<5; i++)    {        cout << array[i] << endl;    }    cout << "~~~" << endl;    Sort::Select(array, 5, false);    for(int i=0; i<5; i++)    {        cout << array[i] << endl;    }    return 0;}
    

运行结果为：

12345~~~54321

3.插入排序

插入排序的基本思想：

第 i 次插入排序示例：

实现插入排序（在Sort.h中）：

public:    template 
    
         static void Insert(T array[], int len, bool min2max = true) // 一边比较一边移动    {        for(int i=1; i
     
      =0) && (min2max ? (array[j]>e) : (array[j]
     
    

mian.cpp测试：

#include 
    
     #include "Sort.h"using namespace std;using namespace StLib;int main(){    int array[] = {3, 1, 2, 5, 4};    Sort::Insert(array, 5);    for(int i=0; i<5; i++)    {        cout << array[i] << endl;    }    cout << "~~~" << endl;    Sort::Insert(array, 5, false);    for(int i=0; i<5; i++)    {        cout << array[i] << endl;    }    return 0;}
    

运行结果为：

12345~~~54321

4.小结

• 排序是数据元素从无序到有序的过程
• 排序具有稳定性，是选择排序算法的因素之一
• 比较和交换是排序的基本操作
• 多关键字排序与单关键字排序无本质区别
• 排序的时间性能是区分排序算法好坏的主要因素
• 选择排序每次选择未排元素中的最小元素
• 插入排序每次将第 i 个元素插入前面 i-1 个已排元素中
• 选择排序是不稳定的排序法，插入排序是稳定的排序方法
• 选择排序和插入排序的时间复杂度为 O(n²)