c++排序算法

前言

我相信再看这篇文章的童鞋已经学完语言部分了吧。

学完语言后就应该学习算法，而最先应该学的算法就是排序

虽然排序函数（sort）可以解决一切问题，但是这种（好）东西并不是万能的，在某些题目中，不仅需要记录排序后的答案，还需要记录排序过程（例如排序的次数）

所以要想学到排序思想就只有一个办法：

乖乖的写几遍代码理解、背过

下面正式开启文章内容

一、算法概述

十大常见算法基本上就可以分成两类了

非线性时间比较类排序：通过比较来决定元素间的相对次序，称为非线性时间比较类排序。

线性时间非比较类排序：不通过比较来决定元素间的相对次序，以线性时间运行，称为线性时间非比较类排序。

下面这个图就可以清楚地分类：

思维导图好

下面就是各种排序算法的复杂度和是否稳定的表格。

Excel好

下面是注释：

稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面。（会交换）

不稳定：如果a原本在b的前面，而a=b，排序之后 a 可能会出现在 b 的后面。（不会交换）

时间复杂度：对排序数据的总的操作次数。反映当n变化时，操作次数呈现什么规律。

空间复杂度：是指算法在计算机内执行时所需存储空间的度量，它也是数据规模n的函数。

在这里我就不一一给大家讲解各种算法了，我会挑5个给大家简单讲解。

二、算法讲解

1.冒泡排序

我偷偷和大家说一下，本蒟蒻第一个学习的排序算法就是冒泡排序。

**********************************************************

　　它重复地走访过要排序的元素列，依次比较两个相邻的元素，如果顺序（如从大到小、首字母从Z到A）错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素列已经排序完成。

　　这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。

**********************************************************

使用方法：

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

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

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

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

**********************************************************

冒泡排序最坏的时间复杂度是O（n^2）

也就是说在数据不多的时候可以使用。

这种方法是比较简单好理解的！

上代码！

//整数或浮点数皆可使用
void Sort(a[], int len)
{
    int i, j,temp;
    for (i = 0; i < len - 1; i++)
        for (j = 0; j < len - 1 - i; j++)
        if (a[j] > a[j + 1])
        {
            temp = a[j];
            arr[j] = a[j + 1];
            a[j + 1] = temp;
        }
}

代码已经给您找来了，其中的Sort函数即为排序过程。

2.桶排序

为什么第二个就要学习桶排序嘞？

因为简单

**********************************************************

桶排序或所谓的箱排序，是一个排序算法，工作的原理是将数组分到有限数量的桶子里，每个桶子再个别排序。

**********************************************************

使用方法：

把每一个数字放在对应下标的“桶”中。

从头输出“桶”的下标。

**********************************************************

这是一种牺牲空间保空间的做法，数字有多大，就要开多大的数组。

并且不支持浮点数。

时间复杂度是O（n+c）

上代码！

void Sort(int a[],int len)
{
    int x=0;
    for(int i=1;i<=len;i++)
    { 
        b[a[i]]++;
        x=max(x,a[i])
    }
    for(int i=0;i<=x;i++)
    {
        if(b[i]>=0)
        {
            while(b[i]!=0)
            {
                b[i]--;
                cout<<i;
            }
        }
    }
}

代码已经给您找来了，其中的Sort函数即为排序过程。

3.归并排序

**********************************************************

归并排序是将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。

**********************************************************

使用方法：

申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列

设定两个指针，最初位置分别为两个已经排序序列的起始位置

比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置

重复步骤3直到某一指针超出序列尾

将另一序列剩下的所有元素直接复制到合并序列尾

**********************************************************

这是一种比较不错的方法，这个方法也会分为几种：二路归并和多路归并。

这种方法也是利用了分治的方法，也就是分而治之。

大家可以看一看下面的这个图：（来源：百度百科）

上代码！

void　Merge(int*　data,int　a,int　b,int　length,int　n)
{
　    int right;
　    if(b+length-1 >= n-1)　right=n-b;
　    else　right=length;
　    int*　temp=new　int[length+right];
　    int　i=0,j=0;
　    while(i<=length-1&&j<=right-1)
    {
    　    if(data[a+i]<=data[b+j])
        {
    　        temp[i+j]=data[a+i];i++;
          }
    　    else
        {
            temp[i+j]=data[b+j];
            j++;
          }
　    }
　    if(j == right)
    {//a中还有元素，且全都比b中的大,a[i]还未使用
　      memcpy(temp + i + j, data + a + i, (length - i) * sizeof(int));
　    }
      else 
          if(i == length)
          {
              memcpy(temp + i + j, data + b + j, (right - j)*sizeof(int));
          }
　    memcpy(data+a, temp, (right + length) * sizeof(int));
　    delete [] temp;
}
void　MergeSort(int*　data, int　n)
{
　    int step = 1;
　    while(step<n)
    {
    　for(int　i=0;i<=n-step-1;i+=2*step)
    　    Merge(data,i,i+step,step,n);
    //将i和i+step这两个有序序列进行合并
    //序列长度为step
    //当i以后的长度小于或者等于step时，退出
    　step*=2;//在按某一步长归并序列之后，步长加倍
　    }
}
//由于比较懒，所以这个也是百度百科的，我给稍加了调整。

懒癌发作……

4.选择排序

这就是我们常说的“打擂台”的方法。

**********************************************************

选择排序的工作原理是：第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。以此类推，直到全部待排序的数据元素的个数为零。

**********************************************************

这个跟冒泡排序很像，但也有区别：

选择排序与冒泡排序的区别：冒泡排序通过依次交换相邻两个顺序不合法的元素位置，从而将当前最小（大）元素放到合适的位置；而选择排序每遍历一次都记住了当前最小（大）元素的位置，最后仅需一次交换操作即可将其放到合适的位置。

上代码！

void Sort(int* h, size_t len)
{
    if(h==NULL) return;
    if(len<=1) return;
    int minindex,i,j;
    //i是次数，也即排好的个数;j是继续排
    for(i=0;i<len-1;++i)
    {
        minindex=i;
        for(j=i+1;j<len;++j)
        {
            if(h[j]<h[minindex]) minindex=j;
        }
        Swap(h[i],h[minindex]); 
    }
    return; 
}

代码已经给您找来了，其中的Sort函数即为排序过程。

5.插入排序

关于我的话……这个我真的没什么可说的了……直接介绍吧

**********************************************************

插入排序是一种简单直观且稳定的排序算法。如果有一个已经有序的数据序列，要求在这个已经排好的数据序列中插入一个数，但要求插入后此数据序列仍然有序，这个时候就要用到一种新的排序方法——插入排序法,算法适用于少量数据的排序，时间复杂度O(n^2)。

**********************************************************

插入算法把要排序的数组分成两部分：第一部分包含了这个数组的所有元素，但将最后一个元素除外（让数组多一个空间才有插入的位置），而第二部分就只包含这一个元素（即待插入元素）。在第一部分排序完成后，再将这个最后元素插入到已排好序的第一部分中。

**********************************************************

如果过不理解的话看看这个图片吧：（来源：百度百科）

百度百科好

上代码！

void Sort(int* h, size_t len)
{
    if(h==NULL) return;
    if(len<=1) return;
    int i,j;
    //i是次数，也即排好的个数;j是继续排
    for(i=1;i<len;++i)
        for(j=i;j>0;--j)
            if(h[j]<h[j-1]) Swap(h[j],h[j-1]);
            else break;
    return;
}