内部排序算法总结

交换排序

普通排序

void BaseSort(int a[], int n)
{
    int i,j;
    int k;
    for(i=0;i<n-1;i++)
    {
        for(j=i+1;j<n;j++)
        {
            if(arr[i]<arr[j])
                swap(&arr[i],&arr[j]);
        }
    }
}

冒泡排序

void BubbleSort(int a[], int n)
{
    int i,j;
    for(i=0;i<n-1;i++)
    {
        for(j=0;j<n-i-1;j++)
        {
            if(arr[j]<arr[j+1])         //稳定排序
                swap(&arr[j],&arr[j+1]);
        }
    }
}

改进的冒泡排序

void BubbleSort_B(int a[], int n)
{
    int i,j;
    int flag=1;
    for(i=0;i<n-1&&flag;i++)
    {
        flag=0;
        for(j=0;j<n-i-1;j++)
        {
            if(arr[j]<arr[j+1])         //稳定排序
            {
                flag=1;
                swap(&arr[j],&ar[j+1]);
            }
        }
    }
}

快速排序

快速排序的基本思想是:通过一趟排序,将序列中的数据分割为两部分,其中一部分的所有数值都比另一部分小,按照如上方法,对两部分数据分别进行快速排序,直到参与排序的两部分都有序为止

空间复杂度:在排序过程中只需要常数级的辅助空间O(1)。每次递归调用需要开辟一定的栈空间,这个空间总大小为nlog2n,所以快排空间复杂度为O(nlog2n)。

void QuickSort(int arr[],int left,int right)
{
    if(left>=right)                     //如果左边索引大于或等于右边索引,则该组序列整理完毕
        return;
    
    int i=left;
    int j=right;
    int key=arr[i];
    while(i<j)
    {   
        //这里只能是'<=或>=',因为当key=arr[i]=arr[j]时会出问题,故快排是不稳定算法
        while((i<j)&&(key<=arr[j]))     //从右向左找小于key的数
        {
            j--;
        }
        arr[i]=arr[j];                  //将该数赋给arr[i]

        while((i<j)&&(key>=arr[i]))     //从左向右找大于key的数
        {
            i++;
        }
        arr[j]=arr[i];                  //将该数赋给arr[j]
    }
    arr[i]=key;                         //将key赋值给arr[i]
    QuickSort(arr,left,i-1);            //递归调用key两边的新区间,对新区间在调用快排
    QuickSort(arr,i+1,right);
}

插入排序

插入排序就是将一条记录插入到一组有序的序列中,继而得到一个有序的、数据个数加1的新的序列。可以视为两部操作,一步是插入,一步是排序。

通常将待排序序列视为两部分:一部分为有序序列,通常在排序开始之时将序列中的第一个数据视为一个有序序列,另一部分为待排序序列。例如arr[0]与arr[1…9]。

直接插入排序

void InsertSort(int arr[], int n)
{
    int i,j;
    //初始时默认arr[0]为有序arr[1...n]无序
    for(i=1;i<n;i++)    
    {
        int tmp=arr[i];
        if(tmp>arr[i-1])    //后一个数大于前一个数,稳定排序
        {
            for(j=i-1;j>=0&&tmp>arr[j];j--)
            {
                arr[j+1]=arr[j];
            }
            arr[j+1]=tmp;
        }
    }
}

折半插入排序

折半插入排序是对直接插入排序的改进。在直接插入排序中主要的时间消耗在数据的比较和移动上。

由于前半部分的序列已经有序,在为新数据寻找插入点时可以采取折半查找的方法来提高寻找效率。

int BinarySort(int arr[], int n)
{
    int i,j;
    int low,high,m;
    int tmp;
    for(i=1;i<n;i++)
    {
        tmp=arr[i];
        low=0;
        high=i-1;
        while(low<=high)
        {
            m=(low+high)/2;
            if(tmp>arr[m])
                high=m-1;
            else
                low=m+1;
        }

        for(j=i-1;j>=high+1;j--)
        {
            arr[j+1]=arr[j];
        }
        arr[high+1]=tmp;
    }
}

折半插入排序节省了排序过程中比较的次数,但是移动的次数与直接插入排序相同,所有时间复杂度仍为0(n2)。

希尔排序

无论是直接插入排序还是折半插入排序,都是将待排序序列视为一个分组。而希尔排序将原始序列按照下标的一定增量分为多个序列,在每个序列中执行直接插入排序。随着增量的减少,每组包含的数据越来越多,当增量减至1,所有的分组重新整合为一个序列,此时排序结束。

void ShellSort(int arr[], int n)
{
    int i,j,d;
    int tmp;
    d=n/2;
    while(d>0)
    {
        for(i=d;i<n;i++)
        {
            tmp=arr[i];
            j=i-d;
            while(j>=0 && tmp>arr[j])
            {
                arr[j+d]=arr[j];
                j=j-d;
            }
            arr[j+d]=tmp;
        }
        d=d/2;
    }
}

希尔排序比直接插入排序多设置了一个步长增量,从而有效的减少了每轮比较的次数和比较的轮数,明显降低了时间消耗。

希尔排序的时间复杂度难以估量,通常认为是O(n1.3)。且是不稳定排序。

选择排序

选择排序的基本思想是:从待排序的序列中选出最大值(最小值),交换该元素与待排序序列头部元素,直到所有待排序的数组元素排序完毕为止。

简单选择排序

与直接插入排序类似,简单选择排序也可以将序列视为两部分,只是直接插入排序初始的有序序列有一个元素,简单选择排序初始的整个序列视为待排序序列,有序序列为空。

void SelectSort(int arr[], int n)
{
    int i,j,max;
    for(i=0;i<n;i++)
    {
        max=i;
        for(j=i+1;j<n;j++) //找出最大元素的下标
        {
            if(arr[max]<arr[j])
                max=j;
        }
        if(i!=max)
            swap(&arr[i],&arr[max]);
    }
}

堆排序

一般用一维数组顺序存储堆中的数据,二叉堆中所有非终端结点的值均不小于(大于)其左、右孩子的值。堆顶为最大值则为大根堆,最小值则为小根堆。

堆排序的实现有2个关键问题:

  1. 调整一个无序序列,使其成为一个堆。
  2. 堆顶元素输出后调整剩余的序列,使其成为一个堆。

根据完全二叉树的定义:最后一个非叶子结点在一维数组中的下标为i=(n-1)/2。结点左右孩子的下标分别为lChild=i*2+1,rChild=lChild+1。

void HeapAdjust(int arr[], int i, int n)
{
    int nChild;
    int tmp;
    for(;2*i+1<n;i=nChild)
    {
        nChild=2*i+1;  //子节点的位置=2*(父节点位置)+1
        if(nChild<n-1&&arr[nChild+1]>arr[nChild])    //得到子节点中较大的节点
            ++nChild;
        if(arr[i]<arr[nChild])  //如果较大的子节点大于父节点,那么把较大的子节点往上移动,替换它的父节点
        {
            tmp=arr[i];
            arr[i]=arr[nChild];
            arr[nChild]=tmp;
        }
        else
            break;
    }
}
void HeapSort(int arr[], int n)
{
    int i;
    //对序列中的每个非叶子节点执行调整算法,使该序列成为一个堆
    for(i=(n-1)/2;i>=0;i--)
        HeapAdjust(arr, i, n);
    //从最后一个元素开始对序列进行调整,不断缩小调整的范围直到第一个元素
    for(i=n-1;i>0;i--)
    {
        //把第一个元素和当前的最后一个元素交换
        //保证当前最后一个位置存放的是现在这个序列中最大的元素
        arr[i]=arr[0]^arr[i];
        arr[0]=arr[0]^arr[i];
        arr[i]=arr[0]^arr[i];
        //不断缩小调整heap的范围,每一次调整完毕保证第一个元素是当前序列的最大值
        HeapAdjust(arr, 0, i);
    }
}

归并排序

该算法是分治法的一个典型应用,将已有有序的两个子序列合并,在过程中对其元素进行比较排序,从而得到一个完整有序的序列。

void Merge(int arr[],int tmp[],int start,int mid,int end)
{
    int i=start,j=mid+1,k=start;
    while(i!=mid+1 && j!=end+1)
    {
        if(arr[i]>=arr[j])
            tmp[k++]=arr[j++];
        else
            tmp[k++]=arr[i++];
    }
    while(i!=mid+1)
        tmp[k++]=arr[i++];
    while(j!=end+1)
        tmp[k++]=arr[j++];
    for(i=start;i<end;i++)
        arr[i]=tmp[i];
}
void MergeSort(int arr[],int tmp[],int start,int end)
{
    int mid;
    if(start<end)
    {
        mid=(start+end)/2;
        MergeSort(arr,tmp,start,mid);
        MergeSort(arr,tmp,mid+1,end);
        Merge(arr,tmp,start,mid,end);
    }
}

基数排序

基数排序是计数排序和桶排序的衍生,是一种基于分配式排序思想和多关键字排序思想的算法,其主要思想为“分配”和“收集”。

计数排序

计数排序思想是,当输入的元素是n个[0,k]之间的整数时,设置一个中间数组tmp[n],使用tmp[data]记录序列中元素data出现的次数。

例如:数组a[10]={2,0,5,8,2,4,3,3,7,5}。最大值为8,建立中间变量tmp[8]。通过tmp[a[i]]记录元素a[i]出现的次数。在输出排序结果。

桶排序

桶排序的思想是:对于包含n条记录的序列,每条记录对应的关键字为k1~kn,首先将这个序列划分成m个子区间(桶),每个桶都是一组n/m的序列,然后根据某种映射关系,将关键字对应的序列映射到第i个桶中,再对每个桶中的所有元素进行比较,之后依次输出所有数据,得到有序序列。

多关键字排序

多关键字排序,就是根据一个序列中的多个关键字排序。在某些情况下,一个序列中的每条记录,没有一个唯一的关键字可以确定这个记录在序列中的位置。

MSD、LSD最高最低优先法,根据关键字的某种顺序来进行层次化的多关键字排序。

链式基数排序

#define MAXD 8
typedef struct node
{
    char keys[MAXD];
    struct node* next;
}RecType;
void RadixSort(RecType *&p,int r,int d)
{
    RecType *head[MAXD], *tail[MAXD], *t;
    int i,j,k;
    for(i=d-1;i>=0;i--)
    {
        for(j=0;j<r;j++)
            head[j]=tail[j]=NULL;

        while(p!=NULL)
        {
            k=p->keys[i]-'0';
            if(head[k]==NULL)
            {
                head[k]=p;
                tail[k]=p;
            }
            else
            {
                tail[k]->next=p;
                tail[k]=p;
            }
            p=p->next;
        }
        p=NULL;

        for(j=0;j<r;j++)
        {
            if(head[j]!=NULL)
            {
                if(p==NULL)
                {
                    p=head[j];
                    t=tail[j];
                }
                else
                {
                    t->next=head[j];
                    t=tail[j];
                }
            }
        }
        t->next=NULL;
    }
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据