为什么这个算法稳定，我怎么能使它不稳定？

我在问，因为兴趣，需要以某种方式了解如何知道算法是否稳定或不。为什么这个算法稳定，我怎么能使它不稳定？

什么意思是稳定的？ 如果两个具有相同键的对象在排序后的输出中以相同的顺序出现在排序输入数组中时，排序算法被认为是稳定的。

如果我正确理解算法，数组的相同元素不能分配给同一个数组，所以它是一个稳定的算法。

我怎么能使这个不稳定？我不想做很大的改变，那么将for i = n down to 1 do更改为for i = 1 to n do呢？我想这应该是打破它的一个方式，但我不是很确定：d

Input: Array arr with n integers, from 1 to m 
Output: Array arr sorted upwards 

Initialize Array B with length m which is set to 0 everywhere 
n <-- |arr| 
Initialize Array C with length n 
for i = 1 to n do 
    B[arr[i] <-- B[arr[i]] + 1 
end for 
for j = 2 to m do 
    B[j] <-- B[j] + B[j-1] 
end for 
for i = n down to 1 do 
    C[B[arr[i]]] <-- arr[i] 
    B[arr[i]] <-- B[arr[i]] - 1 
end for 
return C

这应该是与上面相同的代码：

countingsort(A, k) 
{ 
    C = array(0, k) 
    for (m=0; m<=k; m=m+1) 
    C[m] = 0 
    // end for 
    for (j=1; j<=A.size; j=j+1) 
    C[A[j]] = C[A[j]] + 1 
    // end for 
    i=0 
    B = array(1, A.size) 
    for (m=0; m<=k; m=m+1) 
    while (C[m]>0) 
    { 
     B[i] = m 
     i = i+1 
     C[m]=C[m]-1 
    } // end while 
    // end for 
    return B 
}

来源

2016-06-12 itaminul

嗨，你没有排序......所以没有必要说稳定或没有... – Thomas

有现有的编程语言显示算法比这个假设的语言更清晰。只是说......实际上我想说的是：为什么让我们猜测这个“代码”实际上做了什么，而不是给出你想到的排序算法的名称？或者给我们代码，我们可以执行，看看它是否甚至排序？ – BitTickler

我不知道自己是怎么称呼的，但我们称之为“Linearsort”，可能是因为它按线性时间排序......？我认为这个算法的更一般的名字是计数排序。 – itaminul

这是一个计数/基数排序与一个将数组从n分类到1的单个字段。将最后一个for循环切换为1到n会使其不稳定，因为相同的元素将以相反的顺序存储。

来源

2016-06-12 20:10:55 rcgldr

为什么这个算法稳定，我怎么能使它不稳定？

回答

相关问题