关于各种排序（插入，冒泡，选择，希尔）

插入排序：

能快速处理相对有序的数据，最优情况下复杂度仅仅为O（n）（即原本就是有序的数列）；

#include<bits/stdc++.h>
using namespace std;
const int maxn = 100;
int num[maxn];

void InsertionSort(int n)
{
    for(int i=1;i<n;i++)
    {
        int j = i-1;
        int v = num[i];
        while(j>=0 && num[j] > v)
        {
            num[j+1] = num[j];
            j--;
        }
        num[j+1] = v;
    }

}

int main()
{
    int t;
    scanf("%d",&t);
    memset(num,0,sizeof(num));
    for(int i=0;i<t;i++)
        scanf("%d",&num[i]);
    InsertionSort(t);
    for(int i=0;i<t;i++)
        printf("%d ",num[i]);
}

---

冒泡排序：

冒泡排序是稳定排序。

首先，排序算法的稳定性大家应该都知道，通俗地讲就是能保证排序前2个相等的数其在序列的前后位置顺序和排序后它们两个的前后位置顺序相同。在简单形式化一下，如果Ai = Aj，Ai原来在位置前，排序后Ai还是要在Aj位置前。
其次，说一下稳定性的好处。排序算法如果是稳定的，那么从一个键上排序，然后再从另一个键上排序，第一个键排序的结果可以为第二个键排序所用。基数排序就是这样，先按低位排序，逐次按高位排序，低位相同的元素其顺序再高位也相同时是不会改变的。另外，如果排序算法稳定，对基于比较的排序算法而言，元素交换的次数可能会少一些（个人感觉，没有证实）。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 100;
int num[maxn];

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

int main()
{
    int t;
    scanf("%d",&t);
    memset(num,0,sizeof(num));
    for(int i=0;i<t;i++)
        scanf("%d",&num[i]);
    BubbleSort(num,t);

    for(int i=0;i<t;i++)
        printf("%d ",num[i]);
}

---

选择排序：

每次选择最小的一个数依次从头放

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

int SelectionSort(int n)
{
    int times = 0;
    for(int i=0;i<n;i++)
    {
        int mini = i;
        for(int j=i;j<n;j++)
            if(ve[j] < ve[mini])
                mini = j;
        swap(ve[i],ve[mini]);
        if(i != mini)
            times++;
    }
    return times;
}

int main()
{
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        int now;
        scanf("%d",&now);
        ve.push_back(now);
    }

    int times = SelectionSort(n);

    for(int i=0;i<n;i++)
    {
        if(i == n-1)
            printf("%d",ve[i]);
        else
            printf("%d ",ve[i]);
    }
    printf("
%d
",times);
}

---

希尔排序：

主要运用了分治法的思想，还用了插入排序在有序的数列中的高效的性质

#include<bits/stdc++.h>
using namespace std;
vector <int> ve;
const int maxn = 1000010;
long long cnt = 0;
int num[maxn];

void InsertionSort(int n,int g)
{
    for(int i=g;i<n;i++)
    {
        int v = num[i];
        int j = i-g;
        while(j>=0 && num[j] > v)
        {
            num[j+g] = num[j];
            j -= g;
            cnt++;
        }
        num[j+g] = v;
    }
}

void ShellSort(int n)
{
    int h = 1;
    while(h <= n)
    {
        ve.push_back(h);
        h = h*3 + 1;
    }

    for(int i=ve.size()-1;i>=0;i--)
        InsertionSort(n,ve[i]);
}

int main()
{
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++)
        scanf("%d",&num[i]);
    ShellSort(n);
    printf("%d
",ve.size());
    for(int i=ve.size()-1;i>=0;i--)
    {
        printf("%d",ve[i]);
        if(i != 0)
            printf(" ");
    }
    printf("
");
    printf("%lld
",cnt);
    for(int i=0;i<n;i++)
    {
        printf("%d",num[i]);
        if(i != n-1)
            printf("
");
    }
    return 0;
}