C++中怎么实现非递归排序-创新互联

本篇文章给大家分享的是有关C++中怎么实现非递归排序，小编觉得挺实用的，因此分享给大家学习，希望大家阅读完这篇文章后可以有所收获，话不多说，跟着小编一起来看看吧。

创新互联专注于定安网站建设服务及定制，我们拥有丰富的企业做网站经验。 热诚为您提供定安营销型网站建设，定安网站制作、定安网页设计、定安网站官网定制、成都微信小程序服务，打造定安网络公司原创品牌,更为您提供定安网站排名全网营销落地服务。

void bubble_sort(int array[], int length)  
{  
    int inner = 0, outer = 0;  
    int median = 0;  

    if(NULL == array || 0 == length)  
        return;  

    for(outer = length-1; outer >= 1; outer --){  
        for(inner = 0; inner < outer; inner ++){  
            if(array[inner] > array[inner + 1]){  
                median = array[inner];  
                array[inner] = array[inner + 1];  
                array[inner + 1] = median;  
            }  
        }  
    }  
}  

那么这个程序有没有什么改进的地方呢？当然存在，如果发现在一次遍历循环之中，如果没有发生移位的现象，那么是不是可以判断这个排序可以结束了呢？朋友们可以好好思考一下这个问题？

void bubble_sort(int array[], int length)  
{  
    int inner = 0, outer = 0;  
    int median = 0;  
    int flag = 1;  

    if(NULL == array || 0 == length)  
        return;  

    for(outer = length-1; outer >= 1 && flag; outer --){  
        flag = 0;  

        for(inner = 0; inner < outer; inner ++){  
            if(array[inner] > array[inner + 1]){  
                median = array[inner];  
                array[inner] = array[inner + 1];  
                array[inner + 1] = median;  

                if(flag == 0)  
                    flag = 1;  
            }  
        }  
    }  
}  

（2）插入排序插入排序的意思就是说，我们把数据分成两个部分，一部分是已经排好序的数据，一部分是当前还没有完成排序的数据。那么这么说来的话，排序的过程是不是就是把没有排序的数据逐个插入到已经排好序的队列中的过程呢。大家可以自己先试一下，然后再看看我的代码对不对？

void insert_sort(int array[], int length)  
{  
    int inner = 0;  
    int outer = 0;  
    int median = 0;  
    if(NULL == array || 0 == length)  
        return;  

    for(outer = 1; outer = 1; inner --){  
            if(array[inner] < array[inner -1]){  
                median = array[inner];  
                array[inner] = array[inner -1];  
                array[inner -1] = median;  
            }else{  
                break;  
            }  
        }  
    }  
}  

那么插入排序有没有像冒泡排序那样的改进方法呢？其实没有。因为每一次插入排序的位置都是局部比较的结果，而冒泡排序每一次的内容都是全局最优的。这从数据比较的次数就可以看出来。（3）希尔排序希尔排序，我个人认为可以看成是冒泡排序的变种。它的基本思想是：首先按照一个序列递减的方法逐渐进行排序。比如说有10个数据，我们按照序列5、3、1的顺序进行排序。首先是5，那么我们对1和6、2和7、3和8、4和9、5和10进行排列；第二轮是3，那么对数据1、4、7、10排列，再对2、5、8进行排列，以及3、6、9排列；第三轮就和冒泡排序一样了，以此对每个数据进行排列。它的优势就是让整个队列基本有序，减少数据移动的次数，从而降低算法的计算复杂度。

void shell_sort(int array[], int length, int step)  
{  
    int inner = 0;  
    int outer = 0;  
    int median = 0;  

    if(NULL == array || 0 == length)  
        return;  

    for(; step >= 1; step -=2){  
        for(int index = 0; index < step; index ++){  
            if((length -1) < (index + step))  
                continue;  
            else{  
                outer = index + step;  
                while( (outer + step) <= (length - 1))  
                    outer += step;  
            }  

            for(;  outer >= (index + step);  outer -= step){  
                for(inner = index; inner <= outer - step; inner += step){  
                    if(array[inner] >= array[inner + step]){  
                        median = array[inner];  
                        array[inner] = array[inner + step];  
                        array[inner + step] = median;  
                    }  
                }  
            }  
        }  
    }  
}  

总结：（1）上面的排序都是非递归程序，理解上不难，但是细节问题需要注意，特别是长度的问题（2）代码编写的时候务必注意测试用例的设计（3）如果可能的情况下，多使用已经验证的代码和函数

以上就是C++中怎么实现非递归排序，小编相信有部分知识点可能是我们日常工作会见到或用到的。希望你能通过这篇文章学到更多知识。更多详情敬请关注创新互联行业资讯频道。

另外有需要云服务器可以了解下创新互联scvps.cn，海内外云服务器15元起步，三天无理由+7*72小时售后在线，公司持有idc许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。

网站栏目：C++中怎么实现非递归排序-创新互联
分享路径：http://mswzjz.cn/article/dscdee.html