考研数据结构——内部排序

waitwolf

2020-06-26

考研数据结构——排序

直冒简希，快堆并基

直接插入排序

算法思路：将待排序的关键字与已经排好的部分有序序列的中关键字从后往前进行比较，插入到合适位置，直至所有关键字都被插入到有序序列中

void insertSort(int R[],int n)//数组元素个数
{
    int i,j;
    int temp;
    for(i=1;i<n;i++)//直接从第二个元素开始，因为第一个元素组成的序列一定有序
    {
        temp=R[i];
        j=i-1;
        while(j>0&&temp<R[j])
        {
            R[j+1]=R[j];
            --j;
        }
        R[j+1]=temp;
    }
}

冒泡排序

算法思路：每一趟排序从第一个关键字开始，与其后一个进行比较，如果前一个大于后一个则交换，否则不交换，这样第一趟就可以把序列中最大的关键字交换到最后，第二趟可以把第二大的关键字交换到倒数第二个位置上......排序结束的条件是在一趟排序过程中没有发生关键字交换。

void bubbleSort(int R[],int n)
{
    int i,j,flag,temp;
    for(i=n-1;i>=1;--i)
    {
        flag=0;
        for(j=i;j<=i;j++)
        {
            if(R[j-1]>R[j])
            {
                temp=R[j];
                R[j]=R[j-1];
                R[j-1]=temp;
                flag=1;//发生了关键字交换
            }
        }
        if(flag==0)
            return;
    }
}

简单选择排序

算法思路：从无序序列中每趟挑出一个最小的关键字，与第i个关键字交换。

void selectSort(int R[],int n)
{
    int i,j,k,temp;
    for(i=0;i<n;i++)
    {
        k=i;
        //从无序序列中挑出最小的一个关键字
        for(j=k+1;j<n;j++)
            if(R[k]>R[j])
                k=j;
        //将上面挑出的最小关键字与i位置上的关键字交换
        temp=R[i];
        R[i]=R[k];
        R[k]=temp;
    }
}

希尔排序

算法思路：将序列按照规则划分为几个子序列，分别对这几个子序列进行直接插入排序。缩小增量，最后一个增量一定是1。如有10个关键字，第一个增量为5，则0-5，1-6，2-7，3-8，4-9；第二个增量为3，则0-3-6-9，1-4-7，2-5-8；第三个增量为1，直接插入排序。

//考研数据结构需重点掌握其执行流程
void shellSort(int R[],int n)
{
    int temp;
    for(int gap=n/2;gap>0;gap/=2)
    {
        for(int i=gap;i<n;i++)
        {
            temp=R[i];
            int j;
            for(j=1;j>=gap&&R[j-gap]>temp;j-=gap)
                R[j]=R[j-gap];
            R[j]=temp;
        }
    }
}

快速排序

算法思路：每一趟选择序列的第一个关键字作为枢轴，将序列中比枢轴小的放到枢轴前面，比枢轴大的放到枢轴后面。

void quickSort(int R[],int low,int high)
{
    int temp;
    int i=low,j=high;//指向头尾关键字
    if(low<high)
    {
        temp=R[low];//第一个数作为枢轴
        while(i<j)
        {
            //从后往前扫描，遇到比枢轴小的关键字，停到这里
            while(j>i&&R[j]>=temp)
                --j;
            //将j位置上这个比枢轴小的值放到前面i位置上
            if(i<j)
            {
                R[i]=R[j];
                ++i;
            }
            //从前往后扫描，遇到比枢轴大的关键字，停到这里
            while(i<j&&R[i]<temp)
                ++i;
            //将i位置上这个比枢轴大的值放到后面j位置上
            if(i<j)
            {
                R[j]=R[i];
                --j;
            }
        }
        //i和j相遇后，把枢轴放入这个i等于j的位置
        R[i]=temp;
        //分别对枢轴左边和右边的序列进行递归划分
        quickSort(R,low,i-1);
        quickSort(R,i+1,high);
    }
}

堆排序

算法思路：将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列。

void sift(int R[],int low,int high)//节点调整
{
    int i=low,j=2*i;
    int temp=R[i];
    while(j<=high)
    {
        if(j<high&&R[j]<R[j+1])
            ++j;
        if(temp<R[j])
        {
            R[i]=R[j];
            i=j;
            j=2*i;
        }
        else
            break;
    }
    R[i]=temp;
}
void heapSort(int R[],int n)
{
    int i,temp;
    for(i=n/2;i>=1;--i)
        sift(R,i,n);
    for(i=n;i>=2;--i)
    {
        //换出根节点的关键字，将其放入最终位置
        temp=R[1];
        R[1]=R[i];
        R[i]=temp;
        sift(R,1,i-1);
    }
}

归并排序

算法思路：先将序列分为两半，对两个序列进行归并排序，得到两个有序序列，然后将这两个有序序列合并成为一个有序序列。

void merge(int arr[],int low,int mid,int high)
{
    int i,j,k;
    int n1=mid-low+1;
    int n2=high-mid;
    int L[n1],R[n2];
    for(i=0;i<n1;i++)
        L[i]=arr[low+i];
    for(j=0;j<n2;j++)
        R[j]=arr[mid+1+j];
    i=0;
    j=0;
    k=low;
    while(i<n1&&j<n2)
    {
        if(L[i]<=R[j])
            arr[k]=L[i++];
        else
            arr[k]=R[j++];
        k++;
    }
    while(i<n1)
        arr[k++]=L[i++];
    while(j<n2)
        arr[k++]=R[j++];
}
void mergeSort(int R[],int low,int high)
{
    if(low<high)
    {
        int mid=(low+high)/2;
        mergeSort(R,low,mid);
        mergeSort(R,mid+1,high);
        merge(R,low,mid,high);//把R数组中low到mid和mid+1到high范围内的两段有序序列归并成一段有序序列
    }
}