排序(插入排序、折半插入排序、希尔排序、冒泡排序、快速排序、简单选择排序、堆排、归并排序、基数排序)...

86 阅读 0 评论 57 点赞

我是靠谱客的博主虚拟心情，最近开发中收集的这篇文章主要介绍排序(插入排序、折半插入排序、希尔排序、冒泡排序、快速排序、简单选择排序、堆排、归并排序、基数排序)...，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

插入排序

1、直接插入排序

　　思想：①、查找出a[i]在a[0.....i-1]中的插入位置k

　　　　　②、将a[k...i-1]中所有的元素全部后移一个位置

　　　　　③、a[i]=a[k]

#include <bits/stdc++.h>

using namespace std;

void InsertSort(int *a,int index)
{
    int temp=a[index];//插入的数据
    int i=0;
    for(;i<index;i++)//找到第一个比插入数据大的
    {
        if(a[index]<a[i]) break;
    }
    for(int j=index;j>i;j--)//后移比插入数据大的数据
    {
        a[j]=a[j-1];
    }
    a[i]=temp;
}

int main()
{
    int n;
    cin>>n;
    int a[n];
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }

    for(int i=1;i<n;i++)
    {
        InsertSort(a,i);
    }

    for(auto i:a)//输出
    {
        cout<<i<<endl;
    }
    return 0;
}

View Code

直接插入排序，时间复杂度为O(n²)，空间复杂度为O(1)，稳定的排序算法。

2、折半插入排序

　　思想：在查找a[i]在a[0...i-1]中的插入位置k时，使用折半查找

#include <bits/stdc++.h>

using namespace std;

void InsertSort(int *a,int index)
{
    int temp=a[index];//插入的数据
    int left=0,right=index-1,i;
    while(left<=right)//找到第一个比插入数据大的
    {
        i=(left+right)/2;
        if(a[index]<a[i]) right=i-1;
        else left=i+1;
    }
    for(int j=index;j>left;j--)//后移比插入数据大的数据
    {
        a[j]=a[j-1];
    }
    a[left]=temp;
}

int main()
{
    int n;
    cin>>n;
    int a[n];
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }

    for(int i=1;i<n;i++)
    {
        InsertSort(a,i);
    }

    for(auto i:a)//输出
    {
        cout<<i<<endl;
    }
    return 0;
}

View Code

折半插入排序，仅仅减小了比较次数，但时间复杂度仍为O(n²)，空间复杂度仍为O(1)，稳定的排序算法。

3、希尔排序　

　　思想：希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。

#include <bits/stdc++.h>

using namespace std;

void InsertSort(int *a,int n,int i,int d)
{
    for(int j=i+d;j<n;j+=d)//以d为间隔的数组进行插入排序
    {
        int temp=a[j];
        int k=i;
        for(;k<j;k+=d)
        {
            if(temp<a[k]) break;
        }
        for(int l=j;l>k;l-=d)
        {
            a[l]=a[l-d];
        }
        a[k]=temp;
    }
}

int main()
{
    int n;
    cin>>n;
    int a[n];
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
//    int n=10;
//    int a[10]={49,38,65,97,76,13,27,48,55,4};

    for(int d=n/2;d>=1;d=d/2)//d取n/2 n/4.....
    {
        for(int i=0;i<d;i++)
        {
            InsertSort(a,n,i,d);
        }
        cout<<"d:"<<d<<endl;//输出
        for(auto i:a)
        {
            cout<<i<<' ';
        }
        cout<<endl;
    }

    return 0;
}

View Code

希尔排序的时间复杂度很难分析，它的空间复杂度为O(1)，该排序为不是稳定排序。

交换排序

1、冒泡排序

　　思想：①、比较相邻的元素。如果第一个比第二个大，就交换他们两个。

　　　　　②、对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。

　　　　　③、针对所有的元素重复以上的步骤，除了最后一个。

　　　　　④、持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int n;
    cin>>n;
    int a[n];
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }

    bool flag;//用一个标记来表示是否存在交换
    int temp;
    for(int i=0;i<n;i++)
    {
        flag=false;
        for(int j=i+1;j<n;j++)
        {
            if(a[i]>a[j])
            {
                temp=a[i];
                a[i]=a[j];
                a[j]=temp;
                flag=true;
            }
            if(!flag) break;
        }
    }


    for(auto i:a)//输出
    {
        cout<<i<<' ';
    }
    cout<<endl;
    return 0;
}

View Code

冒泡排序时间复杂度为O(n2)，空间复杂度O(1)，该排序也是一个稳定排序。

2、快速排序

　　思想：①、设置两个变量i、j，排序开始的时候：i=0，j=N-1；

　　　　　②、以第一个数组元素作为关键数据，赋值给key，即key=A[0]；

　　　　　③、从j开始向前搜索，即由后开始向前搜索(j--)，找到第一个小于key的值A[j]，将A[j]和A[i]互换；

　　　　　④、从i开始向后搜索，即由前开始向后搜索(i++)，找到第一个大于key的A[i]，将A[i]和A[j]互换；

　　　　　⑤、重复第3、4步，直到i=j；

递归、非递归实现：

#include <bits/stdc++.h>
using namespace std;

void quicksort(int *a,int left,int right)
{
    if(left>right) return;
    int temp=a[left];
    int i=left;
    int j=right;
    while(i!=j)
    {
        while(a[j]>=temp&&i<j) j--;
        while(a[i]<=temp&&i<j) i++;
        if(i<j)
        {
            int k=a[i];
            a[i]=a[j];
            a[j]=k;
        }
    }
    a[left]=a[i];
    a[i]=temp;
    
    quicksort(a,left,i-1);
    quicksort(a,i+1,right);

}

int fun(int *b,int left,int right)
{
    int temp=b[left];
    int i=left;
    int j=right;
    while(i!=j)
    {
        while(temp<=b[j]&&i<j) j--;
        while(temp>=b[i]&&i<j) i++;
        if(i<j)
        {
            int k=b[j];
            b[j]=b[i];
            b[i]=k;
        }
    }
    b[left]=b[i];
    b[i]=temp;
    return i;
}

int main()
{

    int n=10;

    //1 递归
    cout<<"递归实现："<<endl;
    int a[10]={49,38,65,97,76,13,27,48,55,4};
    quicksort(a,0,n-1);
    for(auto i:a)//输出
    {
        cout<<i<<' ';
    }
    cout<<endl;

    //2 非递归
    cout<<"非递归实现："<<endl;
    int b[10]={49,38,65,97,76,13,27,48,55,4};
    list<int> l={0,n-1};//利用队列存储排序下标
    int left,right,i;
    while(!l.empty())
    {
        left=l.front();l.pop_front();
        right=l.front();l.pop_front();
        i=fun(b,left,right);//返回基数存储的下标
        if(right-i>1)
        {
            l.push_front(right);
            l.push_front(i+1);
        }
        if(i-left>1)
        {
            l.push_front(i-1);
            l.push_front(left);
        }
    }
    for(auto i:b)//输出
    {
        cout<<i<<' ';
    }
    cout<<endl;
    return 0;
}

View Code

快排的时间复杂度为O(nlog₂n)，空间复杂度为O(log₂n)，该排序不是稳定排序。

选择排序

1、简单选择排序

　　思想：排序表为a[1 2 3...]，第i趟排序即从a[1 2 3....]中选择关键字最小的元素与a[i]交换，每一趟排序可以确定一个元素的最终位置，这样经过n-1趟排序就可以使得整个排序表有序。
#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n;
    cin>>n;
    int a[n];
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }

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

    for(auto i:a)
    {
        cout<<i<<' ';
    }
    cout<<endl;
    return 0;
}
View Code
简单选择排序的时间复杂度为O(n2)，空间复杂度为O(1)，该排序不是稳定排序。

2、堆排序

　　堆排序详解

堆排序的时间复杂度为O(nlog2n)，空间复杂度为O(1)，该排序不是稳定排序。

归并排序

2-路归并排序思想如下图：

#include <bits/stdc++.h>
using namespace std;

void fun_sort(int *a,int *b,int low,int mid,int high)
{
    for(int i=low;i<=high;i++)
    {
        b[i]=a[i];//将a复制到辅助数组b
    }
    //比较a[low,mind] b[mind+1,high],合并
    int i,j,k;
    for(i=low,j=mid+1,k=i;i<=mid&&j<=high;k++)
    {
        if(b[i]<=b[j])
            a[k]=b[i++];
        else
            a[k]=b[j++];
    }

    while(i<=mid) a[k++]=b[i++];
    while(j<=high) a[k++]=b[j++];
}

void Merge(int *a,int *b,int low,int high)//二路归并
{
    if(low<high)
    {
        int mid=(low+high)/2;
        Merge(a,b,low,mid);
        Merge(a,b,mid+1,high);
        fun_sort(a,b,low,mid,high);
        for(int i=0;i<7;i++) cout<<a[i]<<' ';
        cout<<endl;
    }
}

int main()
{
    int n=7;
    int a[n]={49,38,65,97,76,13,27},b[n];
    Merge(a,b,0,n-1);
    for(auto i:a) cout<<i<<' ';
    cout<<endl;
    return 0;
}

View Code

二路归并查找的时间复杂度为O(nlog2n)，空间复杂度为O(n)，该排序是一个稳定排序。

基数排序

基数排序（radix sort）属于“分配式排序”（distribution sort），又称“桶子法”（bucket sort）或bin sort，顾名思义，它是透过键值的部份资讯，将要排序的元素分配至某些“桶”中，藉以达到排序的作用，

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n=7;
    int a[n]={329,457,657,839,436,720,355};
    int temp=0,l=0;
    for(int i=0;i<n;i++)
    {
        l=to_string(a[i]).length();
        temp=max(temp,l);
    }
    int b,c,d,e,k=1;
    while(k<=temp)
    {
        for(int i=0;i<n;i++)
        {
            for(int j=i+1;j<n;j++)
            {
                d=pow(10,k);
                e=pow(10,k-1);
                b=(a[i]%d)/e;
                c=(a[j]%d)/e;
                if(b>c) swap(a[i],a[j]);
            }
        }
        for(int i=0;i<n;i++) cout<<a[i]<<' ';
        cout<<endl;
        k++;
    }

    return 0;
}