八大排序（一）--------排序的基本概念与分类

开场白

大家好！你们经常网购吗？

网上购物已经逐渐成为大家生活中不可缺少的一环，但大家有没有思考过，其实，在我们进行网上购物时已经用到了排序。没想到吧，生活处处皆学问。

下面我以自身为例，给大家揭示这个神秘的面纱。假如小编最近想买一部电脑，可上了某电子商务网站去搜索，可搜索后发现（如下图所示），竟然有91万多相关的商品。如此之多，让我如何选择呢。

下面的有些购物达人给我出主意了，排序呀。对呀，排序就行了(如下图所示)。我完全可以根据自己的需要对搜索到的商品进行排序，比如按销量从高到低、再按价格从低到高，将最符合我预期的商品列在前面，最终找到我愿意购买的商家，非常方便。

那么网站是如何做到快速排序的呢？这就是我们今天要讲解的重要内容--------排序。

排序的基本概念与分类

排序是我们生活中经常会面对的问题。同学们做操时会按照从矮到高排列；老师查看上课出勤情况时，会按学生学号顺序点名；高考录取时，会按成绩总分降序依次录取等。那排序的严格定义是什么呢？

假设含有n个记录的序列为{r₁，r₂,…，r_n}，其相应的关键字分别为{K₁，K₂,…，k_n}，需确定1，2，…，n的一种排列P₁，P₂,…，P_n，使其相应的关键字满足K_p1<=K_p2<=…<=K_pn。非递减(或非递增)关系，即使得序列成为一个按关键字有序的序列{r_p1,r_p2,…,r_pn}，这样的操作就称为排序。

注意我们在排序问题中，通常将数据元素称为记录。显然我们输入的是一个记录集合，输出的也是一个记录集合，所以说，可以将排序看成是线性表的一种操作。

排序的依据是关键字之间的大小关系，那么，对同一个记录集合，针对不同的关键字进行排序，可以得到不同的序列。

这里关键字k_i，可以是记录r的主关键字，也可以是次关键字，甚至是若干数据项的组合。比如我们某些大学为了选拔在主科上更优秀的学生，要求对所有学生的所有科目总分降序排名，并且在同样总分的情况下将语数外总分做降序排名。这就是对总分和语数外总分两个次关键字的组合排序.

1.排序的稳定性

也正是由于排序不仅是针对主关键字，那么对于次关键字，因为待排序的记录序列中可能存在两个或两个以上的关键字相等的记录，排序结果可能会存在不唯一的情况，我们给出了稳定与不稳定排序的定义。

假设K_i=K_j，(1<=i<=n，1<=j<=n，i不等于j)，且在排序前的序列中r_i领先于r_j(即i<j)。如果排序后；r_i仍领先于r_j，则称所用的排序方法是稳定的；反之，若可能使得排序后的序列中r_j领先于r_i,则称所用的排序方法是不稳定的。

2.内排序与外排序

根据在排序过程中待排序的记录是否全部被放置在内存中，排序分为内排序和外排序。

内排序是在排序整个过程中，待排序的所有记录全部被放置在内存中。外排序是由于排序的记录个数太多，不能同时放置在内存中，整个排序过程需要在内外存之间多次交换数据才能进行。我们这里主要就介绍内排序的多种方法。

如下图所示，对于内排序来说，排序算法的

性能主要受三个方面的影响：

1.时间性能

排序是数据处理中经常执行的一种操作，往 往属于系统的核心部分，因此排序算法的时间开 销是衡量其好坏的最重要标志。在内排序中，主要进行两种操作：比较和移动。比较指关键字之间的比较，这是要做排序最起码的操作。移动指记录从一个位置移动到另一个位置，事实上，移动可以通过改变记录的存储方式来予以避免。总之，高效率的内排算法应该是具有尽可能少的关键字比较次数和尽可能少的记录移动次数。

2.辅助空间

评价排序算法的另一个主要标准是执行算法所需要的辅助存储空间。辅助存储空间是除了存放待排序所占用的存储空间之外，执行算法所需要的其他存储空间。

3.算法的复杂性

注意这里指的是算法本身的复杂度，而不是指算法的时间复杂度。显然算法过于复杂也会影响排序的性能。

根据排序过程中借助的主要操作，我们把内排序分为插入排序、交换排序、选择排序和归并排序。可以说，这些都是比较成熟的排序技术，已经被广泛地应用于许许多多的程序语言或数据库当中，甚至它们都已经封装了关于排序算法的实现代码。因此，我们学习这些排序算法的目的更多地不是为了在现实中编程排序算法，而是通过学习来提高我们编写算法的能力，以便于去解决更多复杂和灵活的应用性问题。

完整更详细的排序分类：

本专栏一共要讲解8种排序的算法，按照算法的复杂度分为两大类，冒泡排序、简单选择排序和直接插入排序属于简单算法，而希尔排序、堆排序、归并排序、快速排序，计数排序属于改进算法。后面我们将依次讲解。

3.排序用到的结构与函数

为了讲清楚排序算法的代码，我先用一个实例（排序用的顺序表结构），此结构也将用于之后我们要讲的排序算法。

#define MAXSIZE 10000     //用于要排序数组个数最大值
typedef struct  SeqList
{
    int r[MAXSIZE+1];//用于存储要排序数组，r[0]用作哨兵或临时变量
    int length;//用于记录顺序表的长度
}SqList;

另外，由于排序最常用的操作是数组的两个元素的交换，我们把它写成函数，以方便后面使用。

//交换L中数组r的下标为i和j的值
void swap(SqList*L,int i,int j)
{
    int tmp=L->r[j];
    L->r[i]=L->r[j];
    L->r[j]=temp;
}

好了，说了这么多，我们来看第一个排序算法。