优化冒泡排序（Java） [英] Optimized Bubble Sort (Java)

问题描述

我想知道如何优化冒泡排序，以便忽略已排序的元素，即使在第一次传递后也是如此。

I would like to know how else I can optimize bubble sort so that it overlooks elements that have already been sorted, even after the first pass.

Eg. [4, 2, 3, 1, 5, 6] --> [2, 3, 1, **4, 5, 6**]

我们观察到[ 4,5,6]已按排序顺序排列，如何修改我的代码以便在下一遍中忽略这3个元素？ （这意味着排序会更有效吗？）
你建议使用递归方法吗？

We observe that [4,5,6] are already in sorted order, how can modify my code so that it overlooks this 3 elements in the next pass? (which means the sort would be more efficient?) Do you suggest a recursive method?

public static void bubblesort(int[] a) {
  for(int i=1; i<a.length; i++) {
    boolean is_sorted = true;

    for(int j=0; j<a.length; j++) {
      if(a[j] > a[j+1]) {
         int temp = a[j];
         a[j] = a[j+1];
         a[j+1] = temp;
         is_sorted = false;
      }
    }

    if(is_sorted) return;
  }
}

感谢您的时间！

推荐答案

首先，你有一个越界访问权限：

First of all, you have an out-of-bounds access:

    for(int j=0; j<a.length; j++) {
      if(a[j] > a[j+1]) {

j == a.length-1 ，所以循环条件应该是而是 j< a.length-1 。

for j == a.length-1, so the loop condition should rather be j < a.length-1.

但是，在冒泡排序中，你知道在 k pass，最大的 k 元素在 k 数组的最后条目中排序，因此传统的Bubble排序使用

But, in Bubble sort, you know that after k passes, the largest k elements are sorted at the k last entries of the array, so the conventional Bubble sort uses

public static void bubblesort(int[] a) {
  for(int i=1; i<a.length; i++) {
    boolean is_sorted = true;

    for(int j=0; j < a.length - i; j++) { // skip the already sorted largest elements
      if(a[j] > a[j+1]) {
         int temp = a[j];
         a[j] = a[j+1];
         a[j+1] = temp;
         is_sorted = false;
      }
    }

    if(is_sorted) return;
  }
}

现在，这仍然会做很多不必要的迭代当数组有一个较长的最大元素尾部时，假设你有 k，k-1，...，1 作为第一个 k 元素和 k + 1 到 100000000 之后依次排序。标准冒泡排序将通过（差不多）整个数组传递 k 次。

Now, that would still do a lot of unnecessary iterations when the array has a long sorted tail of largest elements, say you have k,k-1,...,1 as the first k elements and k+1 to 100000000 in order after that. The standard Bubble sort will pass k times through (almost) the entire array.

但如果你还记得你在哪里做了你的最后一次交换，你知道在那个索引之后，顺序中有最大的元素，所以

But if you remember where you made your last swap, you know that after that index, there are the largest elements in order, so

public static void bubblesort(int[] a) {
  int lastSwap = a.length-1;
  for(int i=1; i<a.length; i++) {
    boolean is_sorted = true;
    int currentSwap = -1;

    for(int j=0; j < lastSwap; j++) {
      if(a[j] > a[j+1]) {
         int temp = a[j];
         a[j] = a[j+1];
         a[j+1] = temp;
         is_sorted = false;
         currentSwap = j;
      }
    }

    if(is_sorted) return;
    lastSwap = currentSwap;
  }
}

将上述示例排序，只需一次通过整个数组，其余的传递只通过一个（短）前缀。

would sort the above example with only one pass through the entire array, and the remaining passes only through a (short) prefix.

当然，一般情况下，这不会给你带来太多，但随后优化冒泡排序无论如何，这是徒劳的。

Of course, in general, that won't buy you much, but then optimising a Bubble sort is a rather futile exercise anyway.

这篇关于优化冒泡排序（Java）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！