C++ 实现 Java Tim 排序算法 - 详细代码解析

{///'#include///' ///', ///'#include///' ///', ///'#include///' ///', ///'//n///', ///'const int RUN = 32;///', ///'//n///', ///'void insertionSort(std::vector& arr, int left, int right) {///', ///' for (int i = left + 1; i <= right; i++) {///', ///' int key = arr[i];///', ///' int j = i - 1;///', ///'//n///', ///' while (j >= left && arr[j] > key) {///', ///' arr[j + 1] = arr[j];///', ///' j--;///', ///' }///', ///'//n///', ///' arr[j + 1] = key;///', ///' }///', ///'}///', ///'//n///', ///'void merge(std::vector& arr, int left, int mid, int right) {///', ///' int len1 = mid - left + 1;///', ///' int len2 = right - mid;///', ///' //n///', ///' std::vector leftArr(len1);///', ///' std::vector rightArr(len2);///', ///'//n///', ///' for (int i = 0; i < len1; i++) {///', ///' leftArr[i] = arr[left + i];///', ///' }///', ///'//n///', ///' for (int i = 0; i < len2; i++) {///', ///' rightArr[i] = arr[mid + 1 + i];///', ///' }///', ///'//n///', ///' int i = 0;///', ///' int j = 0;///', ///' int k = left;///', ///'//n///', ///' while (i < len1 && j < len2) {///', ///' if (leftArr[i] <= rightArr[j]) {///', ///' arr[k] = leftArr[i];///', ///' i++;///', ///' }///', ///' else {///', ///' arr[k] = rightArr[j];///', ///' j++;///', ///' }///', ///' k++;///', ///' }///', ///'//n///', ///' while (i < len1) {///', ///' arr[k] = leftArr[i];///', ///' i++;///', ///' k++;///', ///' }///', ///'//n///', ///' while (j < len2) {///', ///' arr[k] = rightArr[j];///', ///' j++;///', ///' k++;///', ///' }///', ///'}///', ///'//n///', ///'void timSort(std::vector& arr, int n) {///', ///' for (int i = 0; i < n; i += RUN) {///', ///' insertionSort(arr, i, std::min((i + RUN - 1), (n - 1)));///', ///' }///', ///'//n///', ///' for (int size = RUN; size < n; size *= 2) {///', ///' for (int left = 0; left < n; left += 2 * size) {///', ///' int mid = left + size - 1;///', ///' int right = std::min((left + 2 * size - 1), (n - 1));///', ///' merge(arr, left, mid, right);///', ///' }///', ///' }///', ///'}///', ///'//n///', ///'int main() {///', ///' std::vector arr = {5, 2, 8, 9, 1, 3, 7, 4, 6};///', ///' int n = arr.size();///', ///'//n///', ///' std::cout << ///'Original Array: ///' << std::endl;///', ///' for (int i = 0; i < n; i++) {///', ///' std::cout << arr[i] << ///' ///' << std::endl;///', ///' }///', ///'//n///', ///' timSort(arr, n);///', ///'//n///', ///' std::cout << ///'Sorted Array: ///' << std::endl;///', ///' for (int i = 0; i < n; i++) {///', ///' std::cout << arr[i] << ///' ///' << std::endl;///', ///' }///', ///'//n///', ///' return 0;///', ///'}///', ///'//n///', ///'这段代码使用了插入排序（insertion sort）和归并排序（merge sort）来实现Tim排序（Timsort）。Tim排序是一种混合了插入排序和归并排序的稳定排序算法，它的特点是在处理小规模数据时具有较高的效率，同时也能处理大规模数据。在代码中，我们通过设置RUN的大小来确定何时使用插入排序。然后，我们使用归并排序将排好序的子数组合并为较大的子数组，直到整个数组排序完成。///