排序算法汇总

排序综述

概念

假设含有n个记录的序列为{r1,r2,r3,...,rn}，其关键字分别为{k1,k2,k3,...,kn}，需确定1,2,...,n的一种排列p1,p2,...,pn，使其关键字满足kp1<=kp2<=...<=kpn非递减（或非递增）关系，即使得序列成为一个按关键字有序的序列，这样的操作叫排序。

内排序和外排序

1、内排序是在排序整个过程中，待排序的所有记录全部放置在内存中；
2、外排序是由于排序的记录个数太多，不能同时放置在内存，整个排序过程需要在内外村之间多次交换才能进行。

这里只讨论内排序。

排序算法的性能

1、时间性能
排序算法的时间开销是衡量其好坏的最重要指标。在内排序中，主要进行两种操作：比较和移动。

高效率的内排序算法应该是具有尽可能少的关键字比较次数和尽可能少的记录移动次数。

2、辅助空间
辅助空间是除了存放待排序数据所占用的存储空间之外，执行算法所需要的其他存储空间。

3、内排序算法总览

交换排序

冒泡排序

/*交换x,y*/
void swap(int *x,int *y)
{
    int temp;
    temp=*x;
    *x=*y;
    *y=temp;
}
/*交换排序之冒泡排序*/
void BubbleSort(int a[],int length)
{
    int i,j;
    bool flag=true;//用于标记是否交换，如果没有交换直接跳过 
    for(i=0;i<length&&flag;i++){
        flag=false;
        for(j=length-2;j>=i;j--){
            if(a[j]>a[j+1]){
                swap(&a[j],&a[j+1]);
                flag=true;
            }
        }
    }
}

快速排序

int Patition(int a[],int low,int high)
{
    int pivotkey=a[low];
    while(low<high){
        while(low<high&&a[high]>pivotkey)
            --high;
        swap(&a[high],&a[high]);
        while(low<high&&a[low]<pivotkey)
            ++low;
        swap(&a[low],&a[high]);
    }
    return low;
}
void Qsort(int a[],int low,int high)
{
    int pivot;
    if(low<high){
        pivot=Patition(a,low,high);
        Qsort(a,low,pivot-1);
        Qsort(a,pivot+1,high);
    }
}

选择排序

简单选择排序

void SelectSort(int a[],int length)
{
    int i,j,min;
    for(i=0;i<length;i++){
        min=i;
        for(j=i+1;j<length;j++){
            if(a[min]>a[j])
                min=j;
        }
        if(i!=min)
            swap(&a[i],&a[min]);    
    }
}

堆排序

void HeapDown(int a[],int s,int m)
{
    int i,temp;
    temp=a[s];
    for(i=s*2;i<=m;i*=2){
        if(i<m&&a[i]<a[i+1])
            ++i;
        if(temp>=a[i])
            break;
        a[s]=a[i];
        s=i;
    }
    a[s]=temp;
}
void HeapSort(int a[],int length)
{
    int i,j;
    for(i=length/2;i>=0;i--)
        HeapDown(a,i,length-1);
    for(j=length-1;j>0;j--)
    {
        swap(&a[0],&a[j]);
        HeapDown(a,0,j-1);    
    }
}

插入排序

直接插入排序

void InsertSort(int a[],int length)
{
    int i,j,temp;
    for(i=1;i<length;i++){
        if(a[i]<a[i-1]){
            temp=a[i];
            for(j=i-1;j>=0&&a[j]>temp;j--)
                a[j+1]=a[j];
            a[j+1]=temp;
        }
    }
}

希尔排序

归并排序

void Merge(int S[],int T[],int s,int m,int t)
{
    int j,k,l;
    for(j=m+1,k=s;s<=m&&j<=t;k++){
        if(S[s]<S[j])
            T[k]=S[s++];
        else
            T[k]=S[j++];
    }
    if(s<=m){
        for(l=0;l<=m-s;l++)
            T[k+l]=S[s+l];
    }
    if(j<=t){
        for(l=0;l<=t-j;l++)
            T[k+l]=S[j+l];
    }
}
void MSort(int S[],int T1[],int s,int t)
{
    int m;
    int T2[200];
    if(s==t)
        T1[s]=S[s];
    else{
        m=(s+t)/2;
        MSort(S,T2,s,m);
        MSort(S,T2,m+1,t);
        Merge(T2,T1,s,m,t);
    }
}
void MergeSort(int a[],int length)
{
    MSort(a,a,0,length-1);
}