对整数数组进行快速排序的方法？

Question

我来提供一种解决方案，但我肯定找不到比这更快速地对数组进行排序的方法。

实际上，我需要算法在包含10万个整数的数组中在不到1秒的时间内给出答案。

以下是代码：

read N
for (( i=0; i<N; i++ )); do
    read arr[i]
done

sorted=($(printf '%s\n' "${arr[@]}"|sort -n))

min=$(( sorted[1]-sorted[0] ))

for (( i=1; i<N-1; i++ )); do
    diff=$(( sorted[i+1] - sorted[i] ))
    if [ "$diff" -lt "$min" ]; then
        min=$diff
    fi
done

echo $min

N是元素的数量，本例中为10万。 问题是，在我的数组排序后，我需要遍历它并计算两个整数之间的最小距离： 例如，对于（3,5,8,9），最小距离为1（在8和9之间）。 由于我是Bash的新手，因此甚至不知道这是否是一种有效的方法； 实际上，速度的提高可能来自代码的第二部分，而不是排序的一部分...... 有什么建议吗？ 先行致谢，

- Eldoïr

---

第二部分以线性时间找到最小距离。我认为你无法获得更好的（渐近）性能。 - fferri

是的，我也试过了，但我不知道它是如何工作的，我该如何让排序后的数组在后面进行循环呢？我尝试了sorted=($(sortnumbers "${arr[@]}"))，但它并没有对数组进行排序。 - Eldoïr

如果您的整数已知为固定集合，则桶排序将更快，时间复杂度为O(N)。 - Steve

一定要用 bash 吗？对于这种类型的任务，bash 是你能选择的最糟糕的语言之一，因为它需要进行大量不必要的字符串解析。我敢打赌，如果使用编译型语言重新编写代码，你可以轻松获得 10 倍的加速。 - j_random_hacker

@BrentWashburne 这个问题可能是Code Review上的一个好问题，但首先要问这个问题：它是否超出了Stack Overflow的范围？这是移植最重要的要求。 Code Review不是Stack Overflow的迁移目标，因此只有自定义标志才能将问题移动到那里，如果您认为应该将其移动。 - Simon Forsberg

Answer 1

我最终提出了一个简单而优雅的解决方案：

read N

for (( i=0; i<N; i++ )); do
    read tab[i]
done

printf "%i\n" ${tab[@]} | sort -n | awk 'BEGIN{dmin=1000000;} (NR>1){d=$1-prec; if (d<dmin) dmin=d;} {prec=$1;} END{print dmin;}'

就是这样了。 :) 感谢大家抽出时间来帮助我！;)

- Eldoïr

---

好像是在 Codingame 上的马题解决方案 ;) - Tryum

Answer 2

数字范围<0,1000000)足够小

• 因为你的数字不重复（最小距离是>=40）
• 那么每个值只需要一个比特（存在或不存在）
• 因此，您最多需要1MB的字节/值或128KB的位/值
• （由于K、M基于1024，因此您有足够的储备空间）

因此桶排序是一种可能性：

1. 创建每个可能值的标志数组

   • bool flag[1000000];

2. 清除标志O(M)

   • for (int i=0;i<1000000;i++) flag[i]=0;

3. 通过处理数组arr[N]计算标志...O(N)

   • for (int i=0;i<N;i++) flag[arr[i]]=1;
   • 对于重复项，只需递增标志[]，除非它太大以避免溢出
   • 如果flag[arr[i]]已经是1，则返回distance = 0

4. 重构数组O(M)

   • for (int i=0,j=0;i<1000000;i++) if (flag[i]) { arr[j]=i; j++; } N=j;

5. 现在计算距离O(N)

   • 您可以将这些步骤混合在一起，因此不需要在内存中使用arr[N]
   • 而是只需计算flag[]中的连续零...

[备注]

• M = 1000000
• N <= M
• 如果N比M小得多，则可能不是最快的方法...

- Spektre

---

这似乎是一个很好的解决方案，你解释得非常清楚，谢谢你！我会尽快检查这个bash语法，并发布我的结果 :) - Eldoïr

Answer 3

鉴于这篇关于排序算法复杂度的精彩文章，我会使用基数排序（这里有Python实现，虽然我还没有找到Bash实现，但我正在寻找）：

#python2.6 <
from math import log

def getDigit(num, base, digit_num):
    # pulls the selected digit
    return (num // base ** digit_num) % base  

def makeBlanks(size):
    # create a list of empty lists to hold the split by digit
    return [ [] for i in range(size) ]  

def split(a_list, base, digit_num):
    buckets = makeBlanks(base)
    for num in a_list:
        # append the number to the list selected by the digit
        buckets[getDigit(num, base, digit_num)].append(num)  
    return buckets

# concatenate the lists back in order for the next step
def merge(a_list):
    new_list = []
    for sublist in a_list:
       new_list.extend(sublist)
    return new_list

def maxAbs(a_list):
    # largest abs value element of a list
    return max(abs(num) for num in a_list)

def split_by_sign(a_list):
    # splits values by sign - negative values go to the first bucket,
    # non-negative ones into the second
    buckets = [[], []]
    for num in a_list:
        if num < 0:
            buckets[0].append(num)
        else:
            buckets[1].append(num)
    return buckets

def radixSort(a_list, base):
    # there are as many passes as there are digits in the longest number
    passes = int(round(log(maxAbs(a_list), base)) + 1) 
    new_list = list(a_list)
    for digit_num in range(passes):
        new_list = merge(split(new_list, base, digit_num))
    return merge(split_by_sign(new_list))

- Thomas Ayoub