Tag: 基数排序

如何改进基数排序的这种实现？

我正在实现一个2字节的基数排序。 概念是使用Counting Sort，对整数的低16位进行排序，然后对高16位进行排序。 这允许我在2次迭代中运行排序。 我的第一个概念是试图找出如何处理否定。 由于符号位将被翻转为负数，然后以hexforms，这将使负数大于正数。 为了解决这个问题，我在符号位为正时将其翻转，以使[0,2 bil] = [128 000 000 000，255 255 …）。 当它是负数时，我将所有位翻转，使其范围为（000 000 ..，127 255 ..）。 这个网站帮助我了解这些信息。 为了完成它，我会根据传递将整数分成顶部或底部16位。 以下是允许我这样做的代码。 static uint32_t position(int number, int pass) { int mask; if (number > 31) | 0x80000000; uint32_t out = number ^ mask; return pass == 0 ? out & 0xffff : (out >> […]

基数排序优化

我试图优化Radix排序代码，因为我觉得它有空间，因为书籍和网络上的传统代码似乎是彼此的直接副本，而且它们的工作速度很慢，因为它们采用任意数字，例如10为模数操作。 我尽可能地优化了代码，也许我可能错过了一些优化技术。 在那种情况下请赐教。 优化动机： http://codercorner.com/RadixSortRevisited.htm http://stereopsis.com/radix.html 我无法在文章中实现所有优化，主要是超出我的技能和理解，缺乏足够的时间，如果你可以随意实现它们。 编辑4 这个Java版本的Radix Sort在1次读取中计算所有直方图，并且不需要在每次LSB排序后用零填充数组Z以及通常的跳过排序和跳转到下一个LSB​​排序的能力（如果所有先前的LSB都相同）。 像往常一样，这仅适用于32位整数，但可以从中创建64位版本。 protected static int[] DSC(int A[])// Sorts in descending order { int tmp[] = new int[A.length] ; int Z[] = new int[1024] ; int i, Jump, Jump2, Jump3, Jump4, swap[] ; Jump = A[0] & 255 ; Z[Jump] = 1 ; Jump2 = ((A[0] >> […]