基本排序算法

排序算法是最基本的算法，本文使用语言为C/C++

详细了解参考以下链接：

十大排序算法

个人认为应该牢记的是归并排序，快速排序，基本的冒泡排序以及sort()函数的使用方法，这些是在比赛和做题时经常遇到的。

各排序算法分析

归并排序

是稳定的排序算法，适用于大规模的基本有序的数据

原理

不断地划分区间，一分二，二分四，直到最后一个小数组只有一个元素，然后开始逐层向上合并，合并时要按想要的顺序(从小到大，或是从大到小)进行选择然后合并，因此要用到递归

原理动图如下：

算法采用C++实现：

#include<iostream>
using namespace std;
//合并函数
void Merge(int a[],int L,int mid,int R)
{
    int len=R-L+1;
    int *t=new int [len+1];
    int i=L,j=mid+1,k=1;
    //比较，选择小的一个
    while(i<=mid&&j<=R)
    {
        t[k++]=a[i]<a[j]?a[i++]:a[j++];
    }
    //比较完后如果有剩余元素，都添加进数组中
    while(i<=mid)
    {
        t[k++]=a[i++];
    }
    while(j<=R)
    {
        t[k++]=a[j++];
    }
    for(int m=L;m<=R;m++)
    {
        a[m]=t[m-L+1];
    }
    delete [] t;
}
//用来递归成小区间进行排序
void MergeSort(int a[],int L,int R)
{
    if(L>=R)//这个条件不能忘记，否则会死循环
    return;
    else
    {
        int mid=(L+R+0.5)/2;
        MergeSort(a,L,mid);
        MergeSort(a,mid+1,R);
        Merge(a,L,mid,R);
    }
    
}
int main()
{
    int n;
    cout<<"input num of items:";
    cin>>n;
    int *a=new int[n+1];
    for(int i=1;i<=n;i++)
    cin>>a[i];
    MergeSort(a,1,n);
    for(int i=1;i<=n;i++)
    cout<<a[i]<<" ";
    cout<<endl;
    delete [] a;
}

快速排序

对完全无序的数据执行结果最优

原理

在一组数据中选择一个基准数，一个左标记，一个右标记，将所有比这个数小的数放在左边，比这个数大的数放在其右侧，不断重复此过程，直至左标记与右标记重合，最后让基准数归位。
原理的动图如下：

用C++实现：

#include<iostream>
using namespace std;
void swap(int *x,int *y)
{
    int temp=*x;
    *x=*y;
    *y=temp;
}
int sort(int a[],int L,int R)
{
    int base=a[L];
    while(L<R)  
    { 
        //从右标记开始先找，之后左标记找，然后交换
        while(R>L&&a[R]>base)
        R--;
        while(L<R&&a[L]<base)
        L++;
        swap(a[R],a[L]);
    }
    a[L]=base;//基准数归位
    return L;//返回这个基准数的位置，之后排序它左右的两个小区间
}
void QuickSort(int a[],int L,int R)
{
    if(L>=R) //这个条件不能忘记，否则会死循环
    return;
    int mid=sort(a,L,R);
    QuickSort(a,L,mid-1);//排序左区间
    QuickSort(a,mid+1,R);//排序右区间
}
int main()
{
    int N;
    cin>>N;
    int *a=new int[N+1];
    for(int i=1;i<=N;i++)
    cin>>a[i];
    QuickSort(a,1,N);
    for(int i=1;i<=N;i++)
    cout<<a[i]<<" ";
    cout<<endl;
    return 0;
    delete [] a;
}

sort的基础用法

包含在头文件

<algorithm>

中

有三个参数

• 第一个是要排序的数组的起始地址。
• 第二个是结束的地址（最后一位要排序的地址的下一地址）
• 第三个参数是排序的方法，可以是从大到小也可是从小到大，还可以不写第三个参数，此时默认的排序方法是从小到大排序。

第一种用法：直接比较

第二种：传入一个返回值为布尔类型的比较函数，用来进行比较

冒泡排序

原理：前后两个元素进行比较

原理动图：

采用C++实现情况如下：

#include <iostream>
using namespace std;
void swap(int *x, int *y)
{
    int t = *x;
    *x = *y;
    *y = t;
}
int main()
{
    int n;
    cin >> n;
    int *a = new int[n + 1];
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    //最外面代表一共要进行n-1趟排序，第n趟时实际已经排好了
    //j<=n-i是因为每一趟排序最后都会累积一个排好的数，可见图
    for (int i = 1; i < n; i++)
    {
        for (int j = 1; j <= n - i; j++)
        {
            if (a[j] > a[j + 1])
                swap(a[j], a[j+1]);
        }
    }
    for (int i = 1; i <= n; i++)
        cout << a[i] << " ";
    cout << endl;
    delete[] a;
    return 0;
}