C++ Timsort 实现

2024年8月28日 | 阅读 4 分钟

Timsort 算法是使用两种著名的排序技术实现的：插入排序和归并排序。

Timsort 的实现非常简单，我们将整个输入数组（作为输入提供给我们）分成多个我们称之为“run”的块。创建这些 run 是为了让两种排序技术的实现变得更容易。这些 run 使用插入排序算法进行排序。排序后，它们会使用归并排序中的合并函数进行合并。

C++ 代码

//Here, we are writing down the C++ programming language code to demonstrate
//the concept of Timsort Implementation Using C++ with its output
#include<bits/stdc++.h>
using namespace std;
const int RUN = 32;

// This function sorts the array from the left index to
// to the right index, which is of size almost RUN
void insertionSort(int arr[], int left, int right)
{
	for (int i = left + 1; i <= right; i++)
	{
		int temp = arr[i];
		int j = i - 1;
		while (j >= left && arr[j] > temp)
		{
			arr[j+1] = arr[j];
			j--;
		}
		arr[j+1] = temp;
	}
}


// this is the function we are writing to merge the sorted RUNS
void merge(int arr[], int l, int m, int r)
{
	
	
	// the original array, which is like the input to our code
// is broken into left and right arrays (two parts easy for comparison)
	int len1 = m - l + 1, len2 = r - m;
	int left[len1], right[len2];
	for (int i = 0; i < len1; i++)
		left[i] = arr[l + i];
	for (int i = 0; i < len2; i++)
		right[i] = arr[m + 1 + i];

	int i = 0;
	int j = 0;
	int k = l;

	
	
	// once the comparison part is done, we have to merge the two arrays
	// into a single large sub-array
	while (i < len1 && j < len2)
	{
		if (left[i] <= right[j])
		{
			arr[k] = left[i];
			i++;
		}
		else
		{
			arr[k] = right[j];
			j++;
		}
		k++;
	}

	
	// the below while loop copies the elements which are present to the 
	// left (if any)
	while (i < len1)
	{
		arr[k] = left[i];
		k++;
		i++;
	}

	// the below while loop copies the elements which are present to the 
	// right (if any)
	while (j < len2)
	{
		arr[k] = right[j];
		k++;
		j++;
	}
}


// below function code snippet implements the timsort algorithm
//, a combination of both insertion and merge sort algos.
void tim_Sort_(int arr[], int n)
{
	
	// Sort individual subarrays of size RUN
	// below for loop which we have created sorts the sub-arrays which are
	// made individually of the size RUN
	for (int i = 0; i < n; i+=RUN)
		insertionSort(arr, i, min((i+RUN-1),
									(n-1)));


	
	// the runs which we have created from size 32 will merge to form
	// the size of nearly 64 to 128 and 256, and it goes on ...
	for (int size = RUN; size < n;
							size = 2*size)
	{
		
		// picking the starting of the left sub-array
		// then it will be increased by two (*2)
		for (int left = 0; left < n;
							left += 2*size)
		{
			
			
			// below are small code snippets to help us with 
			// rearrangement of the left and right sub-array indices from 
			// starting and ending
			int mid = left + size - 1;
			int right = min((left + 2*size - 1),
											(n-1));

			
			// below code helps us with the recombining of the runs using
			// the merge sort functionality
			if(mid < right)
				merge(arr, left, mid, right);
		}
	}
}

// below function prints the array created
void print_Array_(int arr[], int n)
{
	for (int i = 0; i < n; i++)
		printf("%d ", arr[i]);
	printf("\n");
}

// below, we are writing down the drive code for timsort
int main()
{
	int arr[] = {-12, 17, 15, -14, 0, 15, 0, 17, -17,
					-14, -13, 15, 18, -14, 12};
	int n = sizeof(arr)/sizeof(arr[0]);
	printf("the given array as input is : \n");
	print_Array_(arr, n);

	// calling the timsort function to perform its task
	tim_Sort_(arr, n);

	printf("Array after implementing the sorting : \n");
	print_Array_(arr, n);
	return 0;
}

输出

the given array as input is : 
-12 17 15 -14 0 15 0 17 -17 -14 -13 15 18 -14 12 
Array after implementing the sorting : 
-17 -14 -14 -14 -13 -12 0 0 12 15 15 15 17 17 18

下一主题在 C++ 中超出内置数据类型的有效范围会发生什么

C++ Timsort 实现

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

C++ 教程

C++ 控制语句

C++ 函数

C++ 数组

C++ 类和对象

C++ 构造函数

C++ 继承

C++ 多态

C++ 抽象

C++ 命名空间

C++ 模板

C++ 字符串

C++ 指针

信号处理

C++ 异常

C++ 文件与流

C++ STL 教程

面试题

选择题

C++ 程序

C++ STL Stack

C++ STL Bitset

C++ STL Deque

C++ STL List

C++ STL Map

C++ STL Math

C++ STL priority_queue

C++ STL Queue

C++ STL Multiset

C++ STL Multimap

C++ STL Set

C++ STD Strings

C++ STL Vector

C++ 操纵符

C++ STL Algorithms

C++ Algorithm

C++ Iterators

C++ 杂项

C++ Timsort 实现

相关帖子

C++ 程序通过矩阵乘法进行消息编码

C++ Tellg() 函数

C++ 数字转字符程序

C++ 中 std::set 和 std::vector 的区别

使用 Kruskal 算法的最小生成树（C++）

C++ 阶乘程序

C++ 裸函数调用

C++ 命令行参数

C++ 密码算术谜题

C++ 单链表上的快速排序

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器