三、排序算法总结（C++版本）

一、引言

对于各种排序算法也算是有了一定的了解，所以这里做一个总结。

二、冒泡排序法。

       这是比较经典的排序算法，主要是通过内外两层的循环比较，使得乱序变为顺序。

下面是一个测试代码

#include <iostream>
#include <vector>
using namespace std;
int main()
{
    vector<int> L(10);
    for(int i=0;i<L.size();i++)
    {
        L[i] = 10 - i;
    }
    int temp = 0;
    for (int i = 0; i < L.size(); i++)
        for (int j = L.size()-1; j >= (i+1); j--)
        {
            if (L[j-1] > L[j ])
            {
                temp = L[j];
                L[j] = L[j - 1];
                L[j - 1] = temp;
            }
        }
    for (int j = 0; j < L.size(); j++)
    {
        cout << "the number is " << L[j] << endl;
    }
}

初始化为10-1，最后冒泡排序法的的结果为升序排列。

下面是算法的运行过程。

在第一次循环里面（即i=0的时候）：

每一次比较之后数据变化如下：

 随着 i 的增大，蓝色区域扩展如下：

 　　最后达到有序状态。

从上面的分析可以看出来：

其时间复杂度：O(n ²) (这里的时间，主要花费在了比较运算上面，所以计算的是循环里面的比较次数)

空间复杂度： O(n)  （即所有的变量占用的空间）

算法稳定性上来说，属于稳定算法（即两个相同的元素经过排序之后的 先后顺序不变）。

二直接插入排序

插入排序的算法思想是，将待排序的数据看做两个部分，一部分是有序数据A,一部分是无序数据B, 最开始的时候A的规模是0， B是整个的待排序数据。

之后对于B中的每一个数据，按照顺序插入到A中，直至整个过程完成。

例如，对于一个待排序数组来说，过程如下：

#include <iostream>
using namespace std;
void Sorted(int* x, int length);
int main(void)
{
    int a[5]={2,1,3,6,4};
    Sorted(a,5);
    for(int i=0;i<5;i++)
        cout<<"-----------"<<a[i]<<endl;
    return 0;
}

void Sorted(int* x, int length)
{
    for(int i=1; i<length;i++ )
    {
        int temp=x[i];
        int j=i-1;
        while( j>=0 && temp<x[j])
        {
            x[j+1]=x[j];
            x[j]=temp;
            j--;
        }
     } 
}

在上面的例子里面：

1 a[5]={2,1,3,6,4};

在每一步的运算过程中，其数据的变化如下：

上述描述了比较的过程。

柱状图表表示了每一个位置的数字大小，蓝色区域为无序部分，黄色部分为经过一次运算之后的有序部分。

其主要步骤是，选择无序部分的第一个元素，将其插入到黄色的有序部分里面去，这样黄色区域扩展，而蓝色区域则是不断地减小，直至所有的区域变为有序状态。

复杂度分析：

　　可以看到，上述过程，主要操作是比较操作，然后是赋值操作,其中赋值操作的所花费的时间更长

　　在最好的情况下，整个数据正好是升序排列的，这个时候比较操作是（n-1），赋值操作 复杂度为0

　　在最坏的情况下，整个数据是降序排列的，这个时候比较次数是  n*(n-1)/2 次，赋值操作是4*n*(n-1)/2, 主要的时间花在了赋值的操作上，时间复杂度为O(n²)

　　稳定性来说，这个算法是不稳定的，即相同的两个元素，在排序前和排序之后，先后次序可能发生了改变。

三、选择排序

　　选择排序的思想与上面的插入排序相同，将数据分为有序部分和无序部分。

　　在无序部分里面选择出最值（比如说是最大值，放到有序部分），这样经过不断的选择无序部分的最大值，使得有序部分不断的扩展，无序部分不断地缩小，最后得到整个有序数据序列。

　　具体代码如下：

#include <iostream>
using namespace std;
void Sorted(int* x, int length);
int main(void)
{
    int a[5] = { 4,1,3,2,6};
    Sorted(a, 5);
    for (int i = 0; i < 5; i++)
        cout << "-----------" << a[i] << endl;
    return 0;
}

void Sorted(int* x, int length)
{
    int max = 0;
    int len = length - 1;
    
    for (int i = 0; i <= length-1; i=i+1)
    {
        max = x[0];
        int j = 0;
        int number = 0;
        for (j = 1; j <= len; j++)
        {
            if (max < x[j])
            {
                max = x[j];
                number = j;
            }
        }
        int temp = x[len];
        x[len] = max;
        x[number] = temp;
        len--;
    }
}

其每一次的比较过程如下：

如图可以看到，有序的黄色区域在不断的扩展，无序部分在逐渐减少。

复杂度：

最好情况：全是升序排列，这个时候只需要(n-1)次比较

最坏情况：全是降序排列，这个时候需要（n-1)*n/2次比较，（n-1）次互换操作，时间复杂度在O(n) （这里只是考虑了互换操作）, 比冒泡排序法快

　　稳定性：不稳定