对于少量整数，最快的排序算法是什么？

本文介绍了对于少量整数，最快的排序算法是什么？的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

我想知道什么是最快的算法。我有0到3000之间的8个整数，我需要对它们进行排序。虽然只有8个整数，这个操作将执行数百万次。

I am wondering what the fastest algorithm would be for this. I have 8 integers between 0 and 3000 and I need to sort them. Although there are only 8 integers, this operation will be performed millions of times.

推荐答案

在C99中合并排序网络（对于错误语言的遗憾）：

Here is an implementation of an odd-even merge sort network in C99 (sorry for the "wrong" language):

#define CMP_SWAP(i, j) if (a[i] > a[j]) \ { int tmp = a[i]; a[i] = a[j]; a[j] = tmp; } void sort8_network(int *a) { CMP_SWAP(0, 1); CMP_SWAP(2, 3); CMP_SWAP(4, 5); CMP_SWAP(6, 7); CMP_SWAP(0, 2); CMP_SWAP(1, 3); CMP_SWAP(4, 6); CMP_SWAP(5, 7); CMP_SWAP(1, 2); CMP_SWAP(5, 6); CMP_SWAP(0, 4); CMP_SWAP(1, 5); CMP_SWAP(2, 6); CMP_SWAP(3, 7); CMP_SWAP(2, 4); CMP_SWAP(3, 5); CMP_SWAP(1, 2); CMP_SWAP(3, 4); CMP_SWAP(5, 6); }

我在我的机器上插入排序

I timed it on my machine against insertion sort

void sort8_insertion(int *a) { for (int i = 1; i < 8; i++) { int tmp = a[i]; int j = i; for (; j && tmp < a[j - 1]; --j) a[j] = a[j - 1]; a[j] = tmp; } }

对于大约1000万种40320可能的排列），排序网络花费0.39秒，而插入排序花费0.88秒。看来我两个都够快。 （用于产生置换的数字大约为0.04秒。）

For about 10 million sorts (exactly 250 times all the 40320 possible permutations), the sort network took 0.39 seconds while insertion sort took 0.88 seconds. Seems to me both are fast enough. (The figures inlcude about 0.04 seconds for generating the permutations.)