气泡排序比较计数始终相同 [英] bubble sort comparison count is always the same
问题描述
我无法理解比较的工作原理以及气泡排序(或与此相关的任何排序)中进行的比较。在我的冒泡排序示例代码中:
I am having trouble understanding how comparisons work and how many are made in bubble sort(or any sort for that matter). In my example code for bubble sort:
public class BS
{
public static void main (String[] args)
{
int[] Array = {5,1,4,2,8};
System.out.println("Array Before Bubble Sort:");
for (int element : Array)
System.out.print(element + " ");
bubbleSort(Array);
System.out.println("Array After Bubble Sort:");
for (int element : Array)
System.out.print(element + " ");
System.out.print("\n");
}
public static void bubbleSort(int[] array)
{
int lastPos;
int index;
int temp;
int comp = 0;
int swap = 0;
for(lastPos = array.length - 1; lastPos >= 0; lastPos--)
{
for(index = 0; index <= lastPos - 1; index++)
{
comp++;
if(array[index] > array[index + 1])
{
swap++;
temp = array[index];
array[index] = array[index + 1];
array[index + 1] = temp;
}
}
}
System.out.println("\nComparisons: " + comp);
System.out.println("Swaps: " +swap;
}
}
输出是这样的:
Array Before Bubble Sort:
5 1 4 2 8
Comparisons: 10
Swaps: 4
Array After Bubble Sort:
1 2 4 5 8
据我所知,交换的数量是正确的,但比较的数量不应该是12吗?的比较结果总是10。对于不同的数组,冒泡排序比较是否有所不同?还是取决于数组的大小?我对此没有任何见解,我感到非常困惑。
As far as I can tell, the number of swaps is correct but shouldn't the number of comparisons be 12? No matter what numbers I put in the array, the number of comparisons is always 10. Aren't bubble sort comparisons different for different arrays? Or it depends on the size of the array? I couldn't find any insight on this and I'm genuinely confused. I'd appreciate some help and I will edit with more information if needed.
推荐答案
如果不检查数组是否已排序,它将始终执行
Without a check to see if your array is sorted, it will always perform a constant number of checks based on the size of the array.
在您的for循环中,如果您可以检查是否使用了整个传递,排除掉任何交换,然后您可以提早退出,这意味着对包含5个元素的已排序数组进行排序仅需要进行4次比较。
In your for loops, if you have a check to see if you did an entire pass without any swaps, then you can exit early which would mean that sorting an already sorted array containing 5 elements would only take 4 comparisons.
在测试算法时,您应始终抛出边缘情况,例如您的算法在
When testing your algorithms you should always throw edge cases at them, for instance what is the outcome of your algorithm on
{}
{1}
{0,0,0,0}
{1,1,3,1,1}
{1,2,3,4,5,6}
{10,9,8,7,6,5,4,3,2,1,}
{1,5,1,5,1,5,1,5,1,5,1}
以及一些真正随机的序列。
As well as a few genuinely random sequences.
这篇关于气泡排序比较计数始终相同的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!