发布日期:2016-01-06 10:30 来源: 标签: 编程语言 开发语言 C++入门教程 C++双向冒泡与SHELL法
本章我们主要学习C++中双向冒泡与SHELL排序法,下面我们就做一下具体讲解,希望大家多多支持中国站长网络学院。
双向冒泡
通常的冒泡是单向的,而这里是双向的,也就是说还要进行反向的工作。
代码看起来复杂,仔细理一下就明白了,是一个来回震荡的方式。
写这段代码的作者认为这样可以在冒泡的基础上减少一些交换。
#include <iostream.h>
void Bubble2Sort(int* pData,int Count)
{
     int iTemp;
     int left = 1;
     int right =Count -1;
     int t;
     do
     {
         //正向的部分
         for(int i=right;i>=left;i--)
         {
             if(pData[i]<pData[i-1])
             {
                 iTemp = pData[i];
                 pData[i] = pData[i-1];
                 pData[i-1] = iTemp;
                 t = i;
             }
         }
         left = t+1;


         //反向的部分
         for(i=left;i<right+1;i++)
         {
             if(pData[i]<pData[i-1])
             {
                 iTemp = pData[i];
                 pData[i] = pData[i-1];
                 pData[i-1] = iTemp;
                 t = i;
             }
         }
         right = t-1;
     }while(left<=right);
}
void main()
{
     int data[] = {10,9,8,7,6,5,4};
     Bubble2Sort(data,7);
     for (int i=0;i<7;i++)
         cout<<data[i]<<" ";
     cout<<"\n";
}
SHELL排序
这个排序非常复杂,看了程序就知道了。
首先需要一个递减的步长,这里我们使用的是9、5、3、1(最后的步长必须是1)。
工作原理是首先对相隔9-1个元素的所有内容排序,然后再使用同样的方法对相隔5-1个元素的排序以次类推。
#include <iostream.h>
void ShellSort(int* pData,int Count)
{
     int step[4];
     step[0] = 9;
     step[1] = 5;
     step[2] = 3;
     step[3] = 1;
     int iTemp;
     int k,s,w;
     for(int i=0;i<4;i++)
     {
         k = step[i];
         s = -k;
         for(int j=k;j<Count;j++)
         {
             iTemp = pData[j];
             w = j-k;//求上step个元素的下标
             if(s ==0)
             {
                 s = -k;
                 s++;
                 pData[s] = iTemp;
             }
             while((iTemp<pData[w]) && (w>=0) && (w<=Count))
             {
                 pData[w+k] = pData[w];
                 w = w-k;
             }
             pData[w+k] = iTemp;
         }
     }
}
void main()
{
     int data[] = {10,9,8,7,6,5,4,3,2,1,-10,-1};
     ShellSort(data,12);
     for (int i=0;i<12;i++)
         cout<<data[i]<<" ";
     cout<<"\n";
}
程序看起来有些头疼。不过也不是很难,把s==0的块去掉就轻松多了,这里是避免使用0步长造成程序异常而写的代码。

相关评论

专题信息
    Visual C++是一个功能强大的可视化软件开发工具,是高等院校计算机及相关专业主要核心课程。 本教程对Visual C++ 的应用与开发进行了详细系统的介绍,内容主要包括:Visual C++程序的建立,菜单、工具栏和状态栏的创建,对话框和常用控件,窗口、文档与视图,图形绘制,数据库应用,多媒体技术等。 本教程以案例教学为主,各章节都附有大量的实例,并且操作步骤详细,有利于引导读者更好的消化、理解和实际应用本章节所学的知识内容,希望大家能多多支持中国站长网络学院!