欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

C++归并排序

程序员文章站 2022-05-31 08:17:30
...

时间复杂度O(n log n)
算法思想将一个无序数据无限切割,切割成每一个小的元素,然后相邻的小元素再进行比较,可以理解为将复杂的问题拆分成一个个小的问题,然后每一个小的问题一一解决,这里就相当于每一组小的元素,重新进行排序比较。最终将所有小的有序再重新合并。代码如下:

#include <iostream>
#include <vector>
#include <string>

using namespace std;

void merge(int * left_buffer, int * right_buffer, int left_len, int right_len)
{
	int i = 0;
	int j = 0;
	int k = 0;
	int tmp[256] = { 0 };

	while(i < left_len && j < right_len)
	{
		if(left_buffer[i] < right_buffer[j])
		{
			tmp[k++] = left_buffer[i++];
		}
		else
		{
			tmp[k++] = right_buffer[j++];
		}
	}

	while(i < left_len)
	{
		tmp[k++] = left_buffer[i++];		
	}
	
	while(j < right_len)
	{
		tmp[k++] = right_buffer[j++];
	}

	for(auto z = 0; z < k; z++ )
	{
		left_buffer[z] = tmp[z];
	}
}

void merge_sort(int buffer[], int len)
{
	if(len > 1)
	{
		int mid = len  / 2;
		int left_len = len / 2;
		int right_len = len - left_len;
		
		int *left_buffer = buffer;
		int *right_buffer = buffer + left_len;
		
		merge_sort(left_buffer, left_len);
		merge_sort(right_buffer, right_len);
		
		merge(left_buffer, right_buffer, left_len, right_len);
	}
}

int main()
{
	int buffer[10] = { 1,2,9,8,5,6,3,4,7,0};
	
	merge_sort(buffer, 10);

	for(auto  i = 0; i < 10; i++)
	{
		cout<<"iterm = "<<buffer[i]<<endl;
	}
	
	return 1;
}

编译 g++ -o merge_sort mergesort.cpp --std=c++11
运行 ./merge_sort