各种排序方法的c++实现

  数据结构这本书里的许多知识点可谓面试的常客，其中排序算法更是频繁出现。为了加深理解和牢记这些排序算法，我们有必要对这些算法自己实现一遍，并作相应的总结。

  pre:许多排序算法都会用到swap函数，作用很简单，交换a[i]与a[j]的值。

  

void swap(int a[],int i,int j)
{
    int temp = a[i];
    a[i] = a[j];
    a[j] = temp;
}

      测试代码：

 

 

int main()
{
    int a[8] = {5,3,7,2,9,10,8,6};
    InsertSort(a,8);
    for(int i=0;i<8;i++){
        cout<<a[i]<<" ";
    }
    return 0;
}

 

 

 

 

 

1.      冒泡排序

         冒泡排序基本思想：从数组末尾开始，每次将最小的数调整至数组开头，正所谓冒泡。

  

void BubbleSort(int a[],int n)
{
    int i,j;
    for(i=0;i<n-1;i++){
        for(j=n-1;j>i;j--){
            if(a[j]<a[j-1])
                swap(a,j,j-1);
        }
    }
}

 

 

 

2.      简单选择排序

         感觉这个排序和冒泡有点像啊，每次选择一个最小值放到i位，然后i++。

 

void SelectSort(int a[],int n)
{
    int i,j,m;
    for(i=0;i<n-1;i++){
        m=i;
        for(j=i+1;j<n;j++){
            if(a[j]<a[m])
                m=j;
        }
        if(i!=m)
            swap(a,i,m);
    }
}

 

 

 

 

 

3.      直接插入排序

         插入排序类似于玩扑克牌时的排序方法，从i=1开始，当前数比后数大时开始外循环，然后内循环把a[i]插入到之前比a[i]大的数之前，注意两个限制条件不能少，保证前数较小时不再插入。

 

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

 

 

 

 

 

4.      希尔排序

         希尔排序实际就是插入排序的改进版，引如一个increment增量，使得序列通过几次操作变得“基本有序”，这样后续的插入操作会大大减少，这样直接排序的优势也就显现出来了。

 

void ShellSort(int a[],int n)
{
    int i,j,tmp;
    int increment=n;
    do
    {
        increment=increment/3+1;
        for(i=increment;i<n;i++)
        {
            if(a[i]<a[i-increment])
            {
              tmp=a[i];
              for(j=i-increment;j>=0&&tmp<a[j];j-=increment)
                    a[j+increment]=a[j];
              a[j+increment]=tmp;
            }
        }
    }while(increment>1);
}

 

 

 

 

 

5.      堆排序

         堆排序的思想是利用大顶堆的性质，即k[i]>=k[2i]，每次把顶上的最大值取走，再重新调整为大顶堆，然后再取，再调整......直至完成有序排列。

         代码分为两部分，首先是主码HeapSort。

 

void HeapSort(int a[],int n)
{
    int i;
    for(i=n/2-1;i>=0;i--)
        HeapAdjust(a,i,n-1);
 
    for(i=n-1;i>0;i--){
        swap(a,0,i);
        HeapAdjust(a,0,i-1);
    }
}

      然后是最为关键的HeapAdjust函数，将交换后的序列重新调整为大顶堆。

 

 

void HeapAdjust(int a[],int s,int m)
{
    int i,j;
    int temp=a[s];
    for(j=2*s+1;j<=m;j=2*j+1){
        if(j<m && a[j]<a[j+1])
            ++j;
        if(temp>=a[j])
            break;
        a[s]=a[j];
        s=j;
    }
    a[s]=temp;
}

https://baike.baidu.com/item/%E5%A0%86%E6%8E%92%E5%BA%8F/2840151?fr=kg_qa 关于堆排序，百度百科里的代码实现和注释非常详尽，遂转于此。

 

 

 

 

 

 

6.      归并排序

归并排序的Merge函数实现这样一个功能：将两个有序序列合并为一个有序序列。

 

void Merge(int a[],int b[],int i,int m,int n)
{
    int j,k,l;
    for(j=m+1,k=i;i<=m && j<=n;k++)
    {
        if(a[i]<a[j])
            b[k]=a[i++];
        else
            b[k]=a[j++];
    }
    if(i<=m)
    {
        for(l=0;l<=m-i;l++)
            b[k+l]=a[i+l];
    }
    if(j<=n)
    {
        for(l=0;l<=n-j;l++)
            b[k+l]=a[j+l];
    }
}

这里就是把序列a的i到m当做一个序列，m+1到n当做另一个序列，然后合并成b序列。

void MergeSort(int a[],int b[],int s,int t)
{
    int m;
    int tmp[8];
    if(s==t)
        b[s]=a[s];
    else
    {
        m=(s+t)/2;
        MergeSort(a,tmp,s,m);
        MergeSort(a,tmp,m+1,t);
        Merge(tmp,b,s,m,t);
    }
}

 

 

 

 

 

7.      快速排序

快排的Partion函数返回一个povit所在的位置，使得povit位置左边的数全都比povit位置的数小，右边全都比它大。

 

int Partion(int a[],int low,int high)
{
    int povitkey=a[low];
    while(low<high)
    {
        while(low<high && povitkey<=a[high])
            high--;
        swap(a,low,high);
        while(low<high && povitkey>=a[low])
            low++;
        swap(a,low,high);
    }
    return low;
}

快排的主函数，对povit左边和右边递归调用QuickSort以达到排序效果。

 

 

void QuickSort(int a[],int low,int high)
{
    int povit;
    if(low<high)
    {
        povit=Partion(a,low,high);
        QuickSort(a,low,povit-1);
        QuickSort(a,povit+1,high);
    }
}

未完待续，欢迎补充，代码都是测试通过的，有不足之处（本人新手，肯定很多）欢迎指正！