大话数据结构-9.2 排序的基本概念与分类 - 高飞网

9.2 排序的基本概念与分类

2017-01-22 22:27:56.0

9.2.1 排序的稳定性

    假设ri=rj(1≤i≤n,1≤j≤n,i≠j),且在排序前的序列中ri领先于rj(i<j)。如果排序后ri仍领先于rj,则称所有的排序方法是稳定的;反之若可能使得排序后的序列中rj领先于ri,则称所用的排序方法是不稳定的。

9.2.2 内排序与外排序

    内排序是在排序整个过程中,待排序的所有记录全部被旋转在内存中。外排序是由于排序的记录个数太多,不能同时旋转在内存,整个排序过程需要在内外存之间多次交换才能进行。

  1. 时间性能
    在内排序中,主要进行两种操作:比较和移动。高效率的内排序算法应该具有尽可能少的关键字比较和记录移动次数。
  2. 辅助空间
    辅助存储空间是除了存放待排序所占用的存储空间外,执行算法所需要的其他存储空间。
  3. 算法的复杂度
    注意,这里指的是算法本身的复杂度,而不是指算法的时间复杂度。显然算法过于复杂也会影响排序的性能。
    根据排序过程中借助的主要操作,把内排序分为:插入排序、交换排序、选择排序和归并排序。

9.2.3 排序用到的结构与函数

    算法用到的结构:

/* 排序用的数据结构与函数 */
/* 没有特殊说明,按照升序排序 */

#ifndef SORT_H_
#define SORT_H_
#define MAXSIZE  10     /* 用于排序数组个数最大值,可根据需要修改 */
typedef struct
{
    int r[MAXSIZE+1];   /* 用一存储要排序的数组,r[0]用作哨兵或临时变量 */
    int length;         /* 用于记录顺序表的长度 */
}SqList;

    交换函数:

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