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