数据结构之----排序问题

一. 排序的概念

排序,是指将一个数据元素序列排列成为一个有序序列的过程
排序可以分成比较型排序和分布型排序两大类

比较型排序

通过比较各元素关键字的相对大小序列进行排序(包括简单排序,合并排序,快速排序和堆排序等);

分布型排序

根据关键字本身的某种特征将序列排序(如基数排序,散列排序等)

选择,插入和冒泡排序法都属于简单排序法,共同点是:排序方法非常直观,易于理解,算法的编程实现比较容易

选择排序

基本思想来自于人们对排序过程最直接的认识---不断的从待排序序列中挑选出关键字最小的元素,依次放在已排序列的最后明知道待排序序列中所有元素都被选完,从而得到一个有序序列.
具体步骤如下:
设待排序线性表为L,选择排序过程共执行下列N-1遍步骤:
① 在第i此挑选中(1 <= i <= N-1)重复下列过程:让元素L[i]依次宇元素L[i+1],L[i+2]...,L[N]比较,如果L[i].key > L[j].key(i<j<=N),就交换元素L[i]与L[j]在线性表中的位置;
② i=i+1
在第i步骤作执行完以后,线性表L中前i个元素已按照关键字递增的顺序排列.在第N-1步操作完成以后,就得到了已排序线性表L
选择排序算法的C过程

void Swap(Element &x,Element &y)
{
    Element temp;
    temp=x;
    x=y;
    y=temp;
}

void SelectSort(List &L)
{
    int i,j;
    for (i=1;i<=N-1;i++)
        for (j=i+1;j<=N;j++)
            if (L[i].key>L[j].key)
                swap(L[i],L[j]);
}

过程SelectSort实现了对线性表L的选择排序,其中又调用过程Swap以实现元素L[i]与L[j]的位置交换.过程Swap(&x,&y)作为一个通用程序可预先定义,其作用是交换变量x,y的值.

冒泡排序

冒泡排序(Bubble Sort)是一种有趣的排序技术,其基本思想是在排序过程中,对线性表中相邻两个元素的关键字的值进行比较,当不满足顺序要求时就交换这两个元素在线性表中的位置.这样,关键字值较小的元素就会想水中的气泡一样逐层"浮起",直至完成排序过程.
设给定待排序序列为线性表L,在某一遍扫描中,对元素L[i]与L[i+1]的关键字进行比较,若L[i].key>L[i+1].key,则交换L[]与L[]的位置,这样重复进行扫描,直到在某一遍扫描时不存在L[i].key>L[i+1].key的情况,排序过程即告结束
冒泡排序的C过程
下面介绍中,其过程Swap的说明见上面的选择排序中.布尔变量anotherpass在每一遍开始时被赋予值为false.当进行一次交换数据操作,变量anotherpass就被赋值为true.如果某一遍扫描结束后变量anotherpass的值仍为false,就可以结束排序过程

void BubbleSort(List &L)
{
    int i,bottom;
    boolean anotherpass;
    bottom=N;
    do {
        anotherpass =false;
        for (i=1;i<bottom;i++)
            if (L[i].key>L[i+1].key) {
                Swap(L[i],L[i+1]);
                anotherpass=true;
            }
        bottom-1;
        } while (anotherpass &&bottom>1);
}