使用随机枢轴C实现qsort
realization of qsort using random pivot C
我的 qsort 使用 random pivot 太慢了，所以它无法通过所有测试。以中间元素为基准的Qsort也太慢了（因为特殊测试）。我怎样才能改进我的qsort？我真的不知道它有什么问题。
这里有一些建议：
只在main()函数中调用一次srand(time(NULL));，不在randompartition函数中调用。
对数组和 input/output 方法使用相同的类型 int32_t。这将允许您使用对 fread 和 fwrite 的单个调用来加载和存储数据。但是请注意，这种方法是不可移植的：如果文件是用不同的字节序生成的，它将失败。
随机枢轴不是完全随机的：永远不会选择最后一个元素，因为 right 是最后一个元素的偏移量，而不是超过元素末尾的元素的偏移量大批。这种约定很容易出错，并且会导致令人困惑的 +1/-1 调整，并且会因一个错误（例如这个错误）而关闭。
这种方法的病态案例是一个包含所有相同元素的数组。您可能希望通过计算 p 周围相同元素的切片来处理这种情况，并且仅递归这些元素左侧和右侧的较小切片。
我的 qsort 使用 random pivot 太慢了，所以它无法通过所有测试。以中间元素为基准的Qsort也太慢了（因为特殊测试）。我怎样才能改进我的qsort？我真的不知道它有什么问题。
这里有一些建议：
只在
main()函数中调用一次srand(time(NULL));，不在randompartition函数中调用。对数组和 input/output 方法使用相同的类型
int32_t。这将允许您使用对fread和fwrite的单个调用来加载和存储数据。但是请注意，这种方法是不可移植的：如果文件是用不同的字节序生成的，它将失败。随机枢轴不是完全随机的：永远不会选择最后一个元素，因为
right是最后一个元素的偏移量，而不是超过元素末尾的元素的偏移量大批。这种约定很容易出错，并且会导致令人困惑的 +1/-1 调整，并且会因一个错误（例如这个错误）而关闭。这种方法的病态案例是一个包含所有相同元素的数组。您可能希望通过计算
p周围相同元素的切片来处理这种情况，并且仅递归这些元素左侧和右侧的较小切片。