交换排序算法

交换排序的基本思想是：两两比较待排序记录的关键字，发现两个记录的次序相反时即进行交换，直到没有反序的记录为止。
    　应用交换排序基本思想的主要排序方法有：冒泡排序和快速排序。

1，冒泡排序：冒泡算法的平均时间复杂度为O(n²)

   排序方法：

    将被排序的记录数组R[1..n]垂直排列，每个记录R[i]看作是重量为R[i].key的气泡。根据轻气泡不能在重气泡之下的原则，从下往上扫描数组R：凡扫描到违反本原则的轻气泡，就使其向上"飘浮"。如此反复进行，直到最后任何两个气泡都是轻者在上，重者在下为止。

 

算法实例：R（l..n)是待排序的文件，采用自下向上扫描，对R做冒泡排序

void BubbleSort(SeqList R)
{
    int i,j,KEY;
    BOOL exchange; //交换标志

    for(i =1,i
    {
        exchange = FALSE;//每趟排序开始前标志置为false
        for(j= n-1;j>=i;j--)
        {
            if(R[j+1].key > R[j].key)
            {
                KEY = R[j+1];
                R[j+1] = R[j];
                R[j] = KEY;
                exchange = TRUE;
            }
        }
        if(!exchange) //本次没有发生交换，整个排序已ok，提前结束排序
        {
            return;
        }

    }
}

2,快速排序算法：

它采用了一种分治的策略，通常称其为分治法(Divide-and-ConquerMethod)：分治法的基本思想是：将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题，然后将这些子问题的解组合为原问题的解。
在R[low..high]中任选一个记录作为基准(Pivot)，以此基准将当前无序区划分为左、右两个较小的子区间R[low..pivotpos-1)和R[pivotpos+1..high]，并使左边子区间中所有记录的关键字均小于等于基准记录(不妨记为pivot)的关键字pivot.key，右边的子区间中所有记录的关键字均大于等于pivot.key，而基准记录pivot则位于正确的位置(pivotpos)上，它无须参加后续的排序。

 

算法实现：

//划分算法：调用Partition(R，low，high)时，对R[low..high]做划分，并返回基准记录的位置
int Partition(SeqList R,int i,int j)
{
    RecType pivot = R[i];//用区间第一个的记录作为基准

    while(i
    {
        while(i= pivot.key)
        {
           j--;//从右向左扫描，查找第1个关键字小于pivot.key的记录R[j]
        }
        if(i < j)
        {
            R[i++] = R[j];//将R[j]的值放在R[i]的位置上，然后i指针加1，此时j指针在R[j]不动，
                          //   等待下面i指针找到的比pivot大的值放进来,
        }

        while(i
        {
            i++;// /从左向右扫描，查找第1个关键字大于pivot.key的记录R[i]
        }
        if(i
        {
            R[j--] = R[i];//同理上面
        }

    }
    R[i] = pivot.key;//基准记录已被最后定位
    return i;
}
//快速排序算法QuickSort:对R[low..high]快速排序
void QuickSort(SeqList R,int low,int high)
{
    int pivotposition;
    if(low < high)
    {
        pivotpostion = Partion(R,low,high);
        QuickSort(R,low,pivotpostion - 1);//对左区间递归排序
        QuickSort(R,pivotpostion + 1,high);//对右区间递归排序
    }
}

尽管快速排序的最坏时间为O(n²)，但就平均性能而言，它是基于关键字比较的内部排序算法中速度最快者，快速排序亦因此而得名。它的平均时间复杂度为O(nlgn)。快速排序是非稳定的，例如[2，2，1]。