快速排序似乎改变值

Question

我坚持了以下问题：

int sort_compare(const void *x, const void *y) { 
    const int *xi = *(const int **) x; 
    const int *yi = *(const int **) y; 

    for (int i = 0; i < block_size; i++) { 
     comp_x[i] = block[(*xi + i) % block_size]; 
     comp_y[i] = block[(*yi + i) % block_size]; 
    } 

    return memcmp(comp_x, comp_y, block_size); 
} 

void sort() { 
    for (int i = 0; i < block_size; i++) { 
     printf("%d,", to_sort[i]); 
    } 
    puts(""); 
    qsort(to_sort, block_size, sizeof (int), sort_compare); 
    for (int i = 0; i < block_size; i++) { 
     printf("%d,", to_sort[i]); 
    } 
    puts(""); 
} 

values: 
    block_size = 5; 
    block = "jkldj"; 
    comp_x, compy_y and to_sort are well allocated 

output: 
    0,1,2,3,4, 
    3,0,1785357420,1,1684826986, 

to_sort包含从（圆形）字符串例如第一个字母

qwer 
werq 
erqw 
rqwe 

，表示为（0,1,2,3）需要进行排序，以

erqw 
rqwe 
qwer 
werq 

，表示为（2,3,0,1）。我似乎得到了非常大的数字，为什么呢？

在此先感谢！

Answer 1

的x和y传递到你的比较是指向你的数组元素。您的数组元素为int s，因此要获取int值，您需要将void指针转换为int指针和取消引用。你有间接的在你的代码的额外的层，它应该是这样的：

int xi = *(const int *) x; 
int yi = *(const int *) y; 

然后，只需使用xi和yi，而不是直接*xi和*yi做数据对比时。

作为一种优化，就没有必要将数据复制到单独的数组，然后memcmp他们 - 你可以自己比他们在循环：

for (int i = 0; i < block_size; i++) { 
    char data_x = block[(xi + i) % block_size]; 
    char data_y = block[(yi + i) % block_size]; 
    if (data_x != data_y) 
     return data_x - data_y; 
} 

return 0; 

以及进一步的优化，如果你加倍在block阵列中的数据（例如，使其具有"qwerqwer"，而不是仅仅"qwer"），你可以在一个单一的通话比较memcmp，因为你不再需要对付环绕。 memcmp经过大量优化，因此如果您有大量数据，则可以使用memcmp，然后使用手写for循环更快。

Answer 2

当你初始化

const int *xi = *(const int **) x; 
const int *yi = *(const int **) y; 

的to_sort元素的地址被解释为const int**，即取消引用然后给予值xi和yi。这将解释to_sort（可能超出，如果int* s大于int s）中的值作为指针。

你应该只投了void* S：

const int *xi = (const int *) x; 
const int *yi = (const int *) y; 

Answer 3

的qsort（）通过给它一个N个项，其中任何给定项目（n）的地址是可计算使用每个“项目”的基础地址+大小的线性列表唱歌。因此，简单的东西开始，通过简单的我的意思是指针的列表。首先，可以通过将拷贝简单地拼接到原始文件（理想情况下少于一个字符，但我不打算约一个字节）来模拟缓冲区的循环性。即

"qwer" ==> "qwerqwer" 

这可以这样做：

char *buff = malloc(2 * blocksize); 
memcpy(buff, to_sort, blocksize); 
memcpy(buff+blocksize, to_sort, blocksize); 

现在你有偏移0 ..（块大小-1），其每一个为字符的块大小，即可以相对于彼此进行比较，而不任何特殊的指针数学。

其次，建立指针列表实际上排序，在这种情况下，

char** ptrs = malloc(sizeof(char*) * blocksize); 
for (i=0;i<blocksize;i++) 
    ptrs[i] = buff+i; 

接下来，是比较两个“项目”的功能。我们通过地址传递给我们的项目是指向字符串的指针。再次，地址过去作为左侧和右侧的内存位置我们会发现两个char *。地址本身不字符*：

int block_compare(const void *left, const void *right) 
{ 
    // memcmp would work for most platforms, but not all, so... 
    return strncmp(*(char **)left, *(char **)right, blocksize); 
} 

最后，发送这对的qsort（）作为这样的：

qsort(ptrs, blocksize, sizeof(char*), block_compare); 

的最终输出将是指针的块大小长度列表插入到制造循环缓冲区，每个缓冲区都引用一个块大小的块。上述一切的全文如下：

#include <stdio.h> 
#include <stdlib.h> 
#include <memory.h> 
#include <string.h> 

size_t blocksize = 0; 

int block_compare(const void *left, const void *right) 
{ 
    // memcmp would work for most platforms, but not all, so... 
    return strncmp(*(char **)left, *(char **)right, blocksize); 
} 


int main(int argc, char* argv[]) 
{ 
    char to_sort[] = "qwer"; 
    size_t i = 0; 

    // set blockize 
    blocksize = strlen(to_sort); 

    char *buff = malloc(2 * blocksize); 
    memcpy(buff, to_sort, blocksize); 
    memcpy(buff+blocksize, to_sort, blocksize); 

    char ** ptrs = malloc(blocksize * sizeof(char*)); 
    for (i=0;i<blocksize;++i) 
     ptrs[i] = buff+i; 

    // now send the pointer list to qsort() 
    qsort(ptrs, blocksize, sizeof(*ptrs), block_compare); 

    // ptrs is sorted. do with it what you will. 
    for (i=0;i<blocksize;i++) 
    { 
     fwrite(ptrs[i], sizeof(char), blocksize, stdout); 
     fwrite("\n", sizeof(char), 1, stdout); 
    } 
    fflush(stdout); 

    free(ptrs); 
    free(buff); 

    return EXIT_SUCCESS; 
} 

使用 “QWER” 生产：

erqw 
qwer 
rqwe 
werq 

另一个样本，采用 “asubstantiallylongerstringtest”

allylongerstringtestasubstanti 
antiallylongerstringtestasubst 
asubstantiallylongerstringtest 
bstantiallylongerstringtestasu 
erstringtestasubstantiallylong 
estasubstantiallylongerstringt 
gerstringtestasubstantiallylon 
gtestasubstantiallylongerstrin 
iallylongerstringtestasubstant 
ingtestasubstantiallylongerstr 
llylongerstringtestasubstantia 
longerstringtestasubstantially 
lylongerstringtestasubstantial 
ngerstringtestasubstantiallylo 
ngtestasubstantiallylongerstri 
ntiallylongerstringtestasubsta 
ongerstringtestasubstantiallyl 
ringtestasubstantiallylongerst 
rstringtestasubstantiallylonge 
stantiallylongerstringtestasub 
stasubstantiallylongerstringte 
stringtestasubstantiallylonger 
substantiallylongerstringtesta 
tantiallylongerstringtestasubs 
tasubstantiallylongerstringtes 
testasubstantiallylongerstring 
tiallylongerstringtestasubstan 
tringtestasubstantiallylongers 
ubstantiallylongerstringtestas 
ylongerstringtestasubstantiall 

男人，我希望这是你正在寻找。 （噢）。