归并非递归、快排递归及非递归的C++实现及时间效率对比。。

今天看剑指offer突然发现下学期都要去面试了，还没自己实现过快排非递归和归并非递归，这怎么能行呢，于是就写了一下。

（虽然有点卡壳，又回去翻了下算导，还是顺利写出来了）

先放图： 一亿数据量：

#pragma warning(disable:4996)

#include <iostream>

#include <string>

#include <cctype>

#include<vector>

#include<list>

#include<cstring>

#include<typeinfo>

#include<set>

#include<map>

#include<deque>

#include<regex>

#include<sstream>

#include<cstdlib>

#include<queue>

#include<stdlib.h>

#include<stdio.h>

#include<stack>

#include<algorithm>

#include<thread>

#include<mutex>

#include<assert.h>

using namespace std;

void MergeSort(vector<int>& nums)

{

	if (nums.empty())

	{

		return;

	}

	int len = nums.size();

	vector<int> temp(len, 0);    //临时数组，下面会用

	for (int merge_step = 1; merge_step < len; merge_step <<= 1)//当merge_step为k，表示merge两个长度k的有序序列成一个长度2k的序列

	{

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

		{

			int le = begin, ri = begin + merge_step;   //左右区间起点

			int le_end = ri, ri_end = min(ri + merge_step, len);    //左右区间终点（半闭半开区间）

			int i = 0;

			while (le < le_end and ri < ri_end)

			{

				if (nums[le] < nums[ri])

				{

					temp[i] = nums[le];

					++le;

				}

				else

				{

					temp[i] = nums[ri];

					++ri;

				}

				++i;

			}

			while (le < le_end)

			{

				temp[i] = nums[le];

				++i;

				++le;

			}

			while (ri < ri_end)

			{

				temp[i] = nums[ri];

				++i;

				++ri;

			}

			for (int j = 0; j < i; ++j)    //写回原数组

			{

				nums[begin + j] = temp[j];

			}

		}

	}

}

void InitiateRandomVector(vector<int>& nums)

{

	srand(0);

	for (auto& num : nums)

	{

		num = rand();

	}

}

int partition(vector<int>&nums,int le,int ri)  //划分区间函数

{

    srand(0);

    int rand_num=le+rand()%(ri-le);     //随机生成一个索引

    swap(nums[ri],nums[rand_num]);      //换到结尾

    int stable=nums[ri];

    int i=le-1,j=le;

    while(j<ri)

    {

        if(nums[j]<stable)

        {

            int temp=nums[j];

            nums[j]=nums[++i];

            nums[i]=temp;   //i存的都是小于基准数的值

        }

        ++j;

    }

    swap(nums[i+1],nums[ri]);

    return i+1; //返回基准数的索引

}

void quick_sort(vector<int>& nums,int le,int ri)    //[le,ri]闭区间

{

    if(le>=ri)

    {

        return;

    }

    int mi=partition(nums,le,ri);

    quick_sort(nums,le,mi-1);

    quick_sort(nums,mi+1,ri);

}

void QuickSort_Recursion(vector<int>& nums)   //递归版

{

    quick_sort(nums,0,nums.size()-1);

}

void QuickSort_Iteration(vector<int>&nums)     //迭代版

{

    if(nums.empty())

    {

        return;

    }

    stack<int> sta;

    sta.push(0);

    sta.push(nums.size()-1);

    int le,ri,mi;

    while(!sta.empty())

    {

        ri=sta.top();   //后push的右边界故先pop

        sta.pop();

        le=sta.top();

        sta.pop();

        mi=partition(nums,le,ri);

        if(mi-1>le)

        {

            sta.push(le);

            sta.push(mi-1);

        }

        if(mi+1<ri)

        {

            sta.push(mi+1);

            sta.push(ri);

        }

    }

}

int main(int argc, char** argv)

{

    cout<<"Input data size:";

    int siz;

    cin>>siz;

	vector<int>nums(siz);

    cout<<"Data size:"<<siz<<endl;

	InitiateRandomVector(nums);

    int t1=time(0);

	MergeSort(nums);

    cout<<"My merge sort time:"<<time(0)-t1<<"s"<<endl;

	InitiateRandomVector(nums);

	t1=time(0);

    QuickSort_Recursion(nums);

    cout<<"My quick sort(recursion) time:"<<time(0)-t1<<"s"<<endl;

    InitiateRandomVector(nums);

	t1=time(0);

    sort(nums.begin(),nums.end());

    cout<<"STL sort time:"<<time(0)-t1<<"s"<<endl;

    InitiateRandomVector(nums);

    t1=time(0);

    QuickSort_Iteration(nums);

    cout<<"My quick sort(iteration) time:"<<time(0)-t1<<"s"<<endl;

    getchar();

	return 0;

}

巴特西

归并非递归、快排递归及非递归的C++实现及时间效率对比。。

最新文章

热门文章