0

我正在尝试实现 Timsort 算法以将随机有符号整数排序为非递减顺序。当整数的数量相对较小时，该算法可以很好地对有符号整数进行排序，但是当数字变大时，当有符号整数的数量不是 2 的幂时，它似乎无法排序。

例如，它可以很好地对 256 个随机有符号整数进行排序，但无法对 257、258、259、260 或 261 个有符号整数进行排序。但是它对 512、511、510 个有符号整数进行了很好的排序。我找不到导致这种不一致结果的原因，对于某些不是 2 的幂的元素，它可以工作，而对于其他一些不是 2 的幂的元素，它会失败。 

#include <stdio.h>
#include <stdlib.h>
#include <time.h> 
#include <string.h>
#include <limits.h>
#include <bits/stdc++.h>
#include <stdint.h>

const int RUN = 32;

void insertionSort(int* list, int left, int right){
    for(int i = left+1; i <= right; i++){
    int temp = list[i];
    int j = i - 1;
    while(list[j] > temp && j >= left){
        list[j+1] = list[j];
        j--;
    }
    list[j+1] = temp;
    }
}

void merge(int* list, int l, int m, int r){
    if( l == r) return; //
    int len1 = m - l + 1, len2 = r - m;
    int* left = (int*)malloc(sizeof(int)*len1);
    int* right = (int*)malloc(sizeof(int)*len2);

    for(int i = len1; i--;) left[i] = list[l + i];

    for(int i = len2; i--;) right[i] = list[m + 1 + i];
    int i = 0, j = 0, k = l;
    //merging into larger sub array
    while(i < len1 && j < len2){
    if( left[i] <= right[j]){
            list[k] = left[i];
        i++;
    }
    else{
        list[k] = right[j];
        j++;
        }
    k++;
    }
    //copy remaining part
    while(i < len1){
    list[k] = left[i];
    k++; i++;
    }
    while(j < len2){
    list[k] = right[j];
    k++; j++;
    }
}

void algorithm_4(int* list, int input_size) { //tim sort
   int* list2 = (int*)malloc(sizeof(int)*input_size);
   for(int i = 0; i < input_size; i++){
       list2[i] = list[i+1];
   }
   //for(int i = 1; i <= input_size; i+=RUN){
   for(int i = 0 ; i < input_size; i+=RUN){
     insertionSort(list2, i,std::min((i+31), (input_size-1)));
   }
   for(int size = RUN; size < input_size; size = size * 2){
     for(int left = 0; left < input_size; left += size * 2){
    int right;
    if(input_size - 1 < 2*(2*size - 1)){
           right = input_size -1;
    }
    else right = std::min((left+2*size-1), (input_size-1));
    int mid = (left + right) / 2;
    merge(list2, left, mid, right);
          }
   }
   for(int i = 0; i<input_size; i++){
       list[i+1] = list2[i];
   }
}
4

0 回答 0