冒泡排序不排序最后一个数字与此算法

Question

我有问题，这个代码中的最后一个数字没有被排序。

   // This is the more advanced optimzed version of bubble sort
        int modifiedBubbleSortArray(int array[])
        {
        int swapped = 0;
         do {
            swapped = false;
            // We specify a loop here for the sorting
            for(int i=0;i<NUM_ARRAYS;i++)
            {
                // We specify aother loop here for the sorting
                for(int j=0;j< i - 1 /* <<< here we make less comparisns on each pass each time */ ;j++)
                {
                    // If the array i is better than j we enter this swap
                    if (array[j]<array[j+1])  
                    {
                        // We swap here for the functions
                        swap(array[j], array[j+1]);
                        // We measure the amount of times we swap
                        amountOfSwaps += 1;
                        // If we swapped we break out of the loop
                        swapped = true;
                    }
                }
            }
             } while (swapped);
        printArray(array);
        return amountOfSwaps;
        }
        // Here we swap values to sort them
        void swap(int & value1, int & value2)
        {
            // We specify a temp and use it to swap
            int temp=value1; 
            value1=value2;
            value2=temp;
        }

Answer 1

内循环应为:

if (array[j]>array[j+1]) 
{ 
  // We swap here for the functions 
  swap(array[j], array[j+1]); 
  // We measure the amount of times we swap 
  amountOfSwaps += 1; 
} 

试一试，看看你的冒泡排序变体是否正确排序。

要按降序排序，只需更改if条件:

if (array[j]<array[j+1]) 

还有一个bug是内部for循环。将其更改为:

for(int j=0;j<=i-1;++j)

更新(基于添加交换测试的最后更改):

bool swapped = false; 
// We specify a loop here for the sorting 
for(int i=0;i<NUM_ARRAYS;i++) 
{ 
    // We specify aother loop here for the sorting 
    for(int j=0;j<=i-1;++j)
    { 
        // If the array i is better than j we enter this swap 
        if (array[j]<array[j+1])   
        { 
            // We swap here for the functions 
            swap(array[j], array[j+1]); 
            // We measure the amount of times we swap 
            amountOfSwaps += 1; 
            // If we swapped we break out of the loop 
            swapped = true; 
        } 
    } 
    // If no swaps this iteration, break out
    if (!swapped)
        break;
} 

如果你真的想要一个好的排序，看看内省排序——快速排序的一种变体。该算法更复杂，但排序效率也更高，为O(N log N)而不是O(N^2)，后者是冒泡排序的复杂度。

Answer 2

亲爱的朋友

下面的

代码是用Java编写的，但这是一个完美的例子。

    int[] nums = { 12 , 5 , 16 , 9 , 25 , 3 , 45 , 11 , 14 };
    int temp;
    for(int y = 1 ; y < nums.length - 1 ; y++) {
        for(int x = 0 ; x < nums.length - y ; x++) {
            if(nums[x] > nums[x+1]) {
                temp = nums[x];
                nums[x] = nums[x+1];
                nums[x+1] = temp;
            }
        }
    }