注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

装甲步兵

迎春故早发,独自不疑寒。 畏落众花后,无人别意看。

 
 
 

日志

 
 
关于我

欢迎各位朋友加好友,共同交流进步!欢迎讨论编程技术(c/c++,java) 搜索引擎技术 互联网舆情监测技术 历史

网易考拉推荐

常见排序算法的C语言实现以及算法复杂度分析  

2014-03-12 22:25:32|  分类: 数据结构与算法 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

一、插入排序

基本思想:

每一趟将一个待排序的节点,按其关键值的大小插入到已经排序的序列中的适当位置上,知道全部插完为止。

完整代码

#include <iostream>


using namespace std;

 

int main(int argc, char* argv[])

{

    int a[] = {3,5,6,7,3,5,7,8,9};

    int len = sizeof(a)/sizeof(int);

    int *ptr = a;

    int temp = 0;

    for (int i = 0; i < len - 1; i++)

    {

        for (int j = i + 1; j >= 0; j--)

        {

            if (*(ptr+j) < *(ptr+j-1))

            {

                temp = *(ptr+j);

                *(ptr+j) = *(ptr+j-1);

                *(ptr+j-1) = temp;

            }

        }

    }

 

    for (int i = 0; i < len; i++)

        cout<<*(ptr+i)<<" ";

    cout<<endl;

    return 0;

}


 二、快速排序

基本思想:快速排序是利用分治法进行排序的,分治法主要有三步:分(divide)、治(conquer)、合(combine)。

  1. 从数列中挑出一个元素,通常初始化时,我们选择数组第一个元素作为基准(pivot),
  2. 重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆放在基准的后面(相同的數可以到任一邊)。在这个分割结束之后,该基准就处于数列的中间位置。
  3. 递归地(recursive)把小于基准和大于基准的两边分别进行第二步。
  4. combine的步骤对于快拍来说,可以省略。

程序说明:

基准pivot初始化为数组的首元素,定义两个变量i, j。初始化i = 0, j = i + 1,按照j开始遍历,若该位置处的元素比基准小,则i++,同时i处和j处的元素互换。i的用处是记录了比基准小的个数,也就是说记录了基准在数组中的位置。当循环结束后,我们只需将i处的元素和基准互换,那么一趟快排就完成了。

完整代码

#include "stdlib.h"

#include <iostream>

 

using namespace std;

 

int Partion(int *ptr, int low, int high);

int * QuickSort(int *ptr, int low, int high);

 

int main(void)

{

    int a[] = {3,4,5,1,4,6,7,9};

    int len = sizeof(a)/sizeof(int);

    int *p = QuickSort(a, 0, len-1);

    for (int i = 0; i < len; i++)

        cout<<*(p+i)<<" ";

    cout<<endl;

    return 0;

}

 

int * QuickSort(int *ptr, int low, int high)

{

    int r = 0;

    if (low < high)

    {

        r = Partion(ptr, low, high);    

        QuickSort(ptr, low, r-1);

        QuickSort(ptr, r+1, high);

    }

    return ptr;

}

 

int Partion(int *ptr, int low, int high)        //divide

{

    int x = *(ptr+low);                         //initialize

    int i = low;

    int temp = 0;

    int j = 0;

    for (j = i+1; j <= high; j++)

    {

        if (*(ptr+j) < x)

        {

            i++;

            temp = *(ptr+i);

            *(ptr+i) = *(ptr+j);

            *(ptr+j) = temp;

        }

    }

    temp = *(ptr+low);

    *(ptr+low) = *(ptr+i);

    *(ptr+i) = temp;

    return i;

}

 三、归并排序

基本思想:归并排序也是一种利用分治法来排序的一种算法。

1、分(divide):递归地按照数组长度的一半(mid),分为两部分(low/high);

2、治(conquer):当按照1步骤分的不能再分的时候,也就是当low=mid的时候,我们只需要比较a[high]和a[mid]即可;

3、合(combine):归并排序和快排的一个显著差别就在于这一步。快排是一种原地排序,合的步骤都可以省略,不需要额外的内存区完成合的功能。而归并排序,在完成1、2步后,我们只能得到有序的前半部分和有序的后半部分。并不能保证整个数组是有序的。所以就需要额外的内存去完成合的功能。如:

i                  4              1               j

5              2

6              3

low             high

我们需要声明一个数组,和两个循环索引i,j,比较low[i]和high[j],若low[i]<high[j],则先放入low[i],此时i++,指向下一个元素。再比较low[i]和high[j],依次类推。。。。当有一方(如low)提前走到头时,则不再需要比较,只需要将另外一方(high)按照顺序依次复制到声明的数组中。

所以,快排相当于归并来说更节省空间。

完整代码

#include "stdafx.h"

#include <stdlib.h>

#include <iostream>

 

using namespace std;

 

void MergeSort(int *ptr, int low, int high);               //divide & conquer

void Merge(int *ptr, int low1, int low2,int high2);                                            //combine

int main(void)

{

    int a[] = {16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1};

    int len = sizeof(a)/sizeof(int);

    int *p = a;

    MergeSort(a, 1, len);

    for (int i = 0; i < len; i++)

        cout<<*(p+i)<<" ";

    cout<<endl;

    return 0;

}

 

void MergeSort(int *ptr, int low, int high)

{

    int temp = 0;                              //divide & conquer

    int mid = (low+high)/2;

    int low2 = low;

    if (low == mid)

    {

        if(*(ptr+low-1) > *(ptr+high-1))

        {

            temp = *(ptr+low-1);

            *(ptr+low-1) = *(ptr+high-1);

            *(ptr+high-1) = temp;

        }

    }

    else

    {

        MergeSort(ptr,low,mid);

        MergeSort(ptr,mid+1,high);          //divide & conquer

        Merge(ptr,low,mid+1,high);             //combine

    }

}

 

void Merge(int *ptr, int low1, int low2, int high2)

{

    int temp = 0;

    int i, j;

    int count = 0;

    int *array = (int *)malloc(sizeof(int)*(high2-low1+1));          //声明一个临时数组用于归并结果,可见归并排序不是原地排序,需要额外的空间

    for (i = low1, j = low2; i < low2 && j <= high2;count++)

    {

        if (*(ptr+j-1) < *(ptr+i-1))

        {

            *(array+count) = *(ptr+j-1);                  //j组元素比j组小,则将j组的元素放入array中

            j++;

        }

        else

        {

            *(array+count) = *(ptr+i-1);

            i++;

        }

    }

    if (j == high2+1)          //说明j到头了

        for(; i < low2; i++,count++)       //则需要把多余的i组的元素复制到array里面

            *(array+count) = *(ptr+i-1);

    else if(i == low2)                   //说明i到头了,也是一样,需要把多余的j组的元素复制到array里面

        for(; i < low2; i++,count++)

            *(array+count) = *(ptr+j-1);

 

    for (int k = 0; k < high2-low1+1; k++)         //将array数组重新复制ptr数组里面

        *(ptr+k+low1-1) = *(array+k);

}


 四、希尔排序

基本思想:

先将整个待排元素序列分割成若干个子序列(由相隔某个“增量”的元素组成的)分别进行直接插入排序,然后依次缩减增量再进行排序,待整个序列中的元素基本有序(增量足够小)时,再对全体元素进行一次直接插入排序。因为直接插入排序在元素基本有序的情况下(接近最好情况),效率是很高的,因此希尔排序在时间效率上比前两种方法有较大提高。

例如:

49, 38, 65, 97, 26, 13, 27, 49, 55, 4     len=10;

1、10/2=5,以5为步长,分为两组:

49, 38, 65, 97, 26

13, 27, 49, 55, 4

按照纵向将五列数据进行直接插入排序,如49和13为一组,38和27为一组等等。。。,得到结果

13, 27,49, 55, 4

49, 38, 65, 97, 26

并将结果写成1排:13, 27,49, 55, 4, 49, 38, 65, 97, 26

2、5/2 = 2,以2为步长,将上述数据分成五列:

13, 27

49, 55

4, 49

38, 65

97, 26

按照纵向将两列列数据进行直接插入排序,得到结果:

4, 26

13, 27

49, 49

38, 55

97, 65

并将结果写成一排:

4, 26,13,27,49,49,38,55,97,65

4、2/2 = 1,此时列数就等于数组的长度,再对齐进行直接插入排序。

希尔排序这样做的目的是,当长度小的时候,直接插入排序性能还是比较优越的。而当长度大的时候,基于前面的步骤,此时数组已经基本接近有序。而直接插入排序在数组基本接近有序的时候,性能很高。所以希尔排序是直接插入排序的改良版。

完整代码

using namespace std;

 

void InsertSort(int *ptr, int index, int len);

void ShellSort(int *ptr, int len, int Length);

 

int main(int argc, char* argv[])

{

    int a[] = {1,2,3,4,5,6,7,8,9,11,1,2,12,12,13,13};

    int len = sizeof(a)/sizeof(int);

    ShellSort(a,len,len);

    for (int i = 0; i < len; i++)

        cout<<*(a+i)<<" ";

    cout<<endl;

    return 0;

}

 

void ShellSort(int *ptr, int len, int Length)

{

    int index = len/2;

    if (0 == index)

        return;

    for (int i = 0; i < index; i++)

        InsertSort(ptr+i, index, Length+1+i-2*index);

    ShellSort(ptr,len/2,Length);

}

 

void InsertSort(int *ptr, int index, int len)

{

    int temp = 0;

    for (int i = 0; i < len ; i = i + index)

    {

        int flag = 0;

        for (int j = i + index; j > 0; j = j - index)

        {

            if (*(ptr+j) < *(ptr+j-index))

            {

                temp = *(ptr+j);

                *(ptr+j) = *(ptr+j-index);

                *(ptr+j-index) = temp;

                flag = 1;

            }

            if (0 == flag)

                break;

        }

    }

}

 五、冒泡排序

基本思想:将待排序的结点顺次两两比较,若为逆序则
进行交换,使关键字最小的结点如气泡一般逐渐往上“漂浮
”直至“水面”,而将关键字最大的结点“沉入水底”。

其他的不解释.

完整代码

六、直接选择排序

基本思想:在当前无序序列中选择一个关键字最小的记录,
并将它与最前端的记录交换。不解释。

完整代码

七、计数排序

基本思想:

计数排序(Counting sort)是一种稳定的排序算法。计数排序使用一个额外的数组C,其中第i个元素是待排序数组A中值等于i的元素的个数。然后根据数组C来将A中的元素排到正确的位置。

例如:{1,2,3,4,4}

1、首先统计出每个数组出现的次数,并存入数组pCount中,pCount[i]表示元素等于i的出现的次数,如pCount[4]=2;

2、求出不大于i的元素的个数,pCount[i] += pCount[i-1],如pCount[2]=2,pCount[4]=5。

3、对于只出现1次的元素,非常好办,若pCount[i]=x,则i就存放在最终数组的x位置处。如pCount[3]=3,说明比它小的有2个,那3肯定排第三;

4    对于出现多次的元素来说,则只需要每次循环将pCount[i]–就可以了。如pCount[4]=5,从数组末尾开始循环,因为pCount[4]=5,所以数组末尾4元素排在第五的位置,此时pCount[4]–=4。继续遍历,再次遇到元素4,查询pCount[4],此时pCount[4]=4,那么这个4就排在第四位了。

说明:从数组末尾开始排列,为了保证计数排序是个稳定排序。程序中因为数组下标从0开始,会和上面的有点点出入。

完整代码

八、基数排序

基本思想:

将所有待比较数值统一为同样的数位长度,数位较短的数前面补零. 然后, 从最低位开始, 依次进行一次计数排序(因为每一位的可能取值范围是固定的0-9,计数排序比较适合.这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列.


 九、堆排序

堆排序内容太多了,下次再实现。

  评论这张
 
阅读(95)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017