我想知道如何优化冒泡排序，使其忽略已经排序的元素，即使是在第一次遍历之后也是如此。
Eg. [4, 2, 3, 1, 5, 6] --> [2, 3, 1, **4, 5, 6**]
我们观察到
[4,5,6]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;
}
}
首先，你有一个越界访问权限：
for (int j = 0; j < a.length; j++) {
if (a[j] > a[j + 1]) {
for
j == a.length-1j < a.length-1但是，在冒泡排序中，您知道在经过
kkkpublic static void bubbleSort(int[] a) {
for (int i = 1; i < a.length; i++) {
boolean is_sorted = true;
// skip the already sorted largest elements
for (int j = 0; j < a.length - i; 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;
}
}
现在，当数组具有最大元素的长排序尾部时，仍然会进行大量不必要的迭代，假设您将
k,k-1,...,1kk+1100000000k但是如果您记得上次交换的位置，您就会知道在该索引之后，有按顺序排列的最大元素，所以
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;
}
}
只需一次遍历整个数组即可对上面的示例进行排序，其余的遍历仅通过（短）前缀。
当然，一般来说，这不会给你带来太多好处，但无论如何，优化冒泡排序都是一项相当徒劳的练习。
public static void BubbleSorter(params int[] input) {
int newSize = input.Length - 1, size = 0;
bool swap;
do {
swap = false;
for (int j = 0; j < newSize; j++) {
if (input[j] > input[j + 1]) {
int temp = input[j + 1];
input[j + 1] = input[j];
input[j] = temp;
swap = true;
size = j;
}
}
newSize = size;
} while (swap);
DisplayArrayElements(input);
}
public static Integer[] optimizedBubbleSort(Integer[] input) {
long startTime = System.nanoTime();
boolean swapped = true;
for (int pass = input.length - 1; pass >= 0 && swapped; pass--) {
swapped = false;
for (int i = 0; i < pass; i++) {
if (input[i] > input[i + 1]) {
int temp = input[i];
input[i] = input[i + 1];
input[i + 1] = temp;
swapped = true;
}
}
}
System.out.println("Time taken for OPTIMIZED bubbleSort: "
+ (System.nanoTime() - startTime));
return input;
}
您应该为内部循环使用变量“大小”，并将其更改为每个循环中最新交换的元素。这样，您的内部循环就会上升到最新的“交换”元素，并传递其余未交换的元素（也称为它们的正确的地方）。即
do {
int newsize = 0;
for (int i = 1; i < size; i++) {
if (a[i - 1] > a[i]) {
int temp;
temp = a[i - 1];
a[i - 1] = a[i];
a[i] = temp;
newsize = i;
}
}
size = newsize;
} while (size > 0);
在上面的示例中，数组在第 3 遍后已排序，但我们仍将继续第 4、5 遍。假设如果数组已经排序，那么就不会进行交换（因为相邻元素总是按顺序排列的），但我们仍然会继续传递，并且仍然会有 (n-1) 次传递。
如果我们可以识别出数组已排序，那么我们应该停止执行进一步的传递。这是对原始冒泡排序算法的优化。
如果特定遍中没有交换，则意味着数组已排序，因此我们不应该执行进一步的遍。为此，我们可以有一个标志变量，在每次传递之前将其设置为 true，并在执行交换时将其设置为 false。
void bubbleSort(int *arr, int n) {
for (int i = 0; i < n; i++) {
bool flag = false;
for (int j = 0; j < n - i - 1; j++) {
if (array[j] > array[j + 1]) {
flag = true;
int temp = array[j + 1];
array[j + 1] = array[j];
array[j] = temp;
}
}
// No Swapping happened, array is sorted
if (!flag) {
return;
}
}
}
您可以使用单个 do-while-loop 而不是两个嵌套的 for-loop，并将逻辑移至内部 if-statement 中。后续遍数会根据遍数索引而缩短。
public static void bubbleSort(int[] arr) {
boolean swapped = false;
int i = 0, pass = 0;
do {
if (i < arr.length - 1 - pass) {
if (arr[i] > arr[i + 1]) {
int temp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = temp;
swapped = true;
}
i++;
} else {
i = 0;
pass++;
swapped = false;
}
} while (i < arr.length - 1 - pass || swapped);
}
public static void main(String[] args) {
int[] arr = {6, 1, 5, 8, 4, 3, 9, 2, 0, 7};
System.out.println(Arrays.toString(arr));
bubbleSort(arr);
System.out.println(Arrays.toString(arr));
}
输出：
[6, 1, 5, 8, 4, 3, 9, 2, 0, 7]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
另请参阅：冒泡排序输出不正确
public class Tester {
static boolean bubbleFlag = true;
public static void main(String[] args) {
int array[] = new int[]{1, 9, 2, 3, 4, 5, 6};
bubbleSort(array);
}
private static void bubbleSort(int... array) {
System.out.println("Before Sorting: " + Arrays.toString(array));
for (int i = 0; i < array.length - 1; i++) {
if (i > 0) if (bubbleFlag) break;
for (int j = 0; j < array.length - i - 1; j++) {
if (array[j] > array[j + 1]) array = swap(j, j + 1, array);
System.out.println("Iteration "+j+" :"+Arrays.toString(array));
}
bubbleFlag = true;
}
}
private static int[] swap(int i1, int i2, int... is) {
bubbleFlag = false;
is[i1] = is[i1] + is[i2];
is[i2] = is[i1] - is[i2];
is[i1] = is[i1] - is[i2];
return is;
}
}
输出：
Before Sorting: [1, 9, 2, 3, 4, 5, 6]
Iteration 0 :[1, 9, 2, 3, 4, 5, 6]
Iteration 1 :[1, 2, 9, 3, 4, 5, 6]
Iteration 2 :[1, 2, 3, 9, 4, 5, 6]
Iteration 3 :[1, 2, 3, 4, 9, 5, 6]
Iteration 4 :[1, 2, 3, 4, 5, 9, 6]
Iteration 5 :[1, 2, 3, 4, 5, 6, 9]
我设计了一种方法，通过排除先前循环中已排序的数组开头和结尾的部分来减少迭代次数。
static int[] bubbleSortOptimized(int arr[]) {
int start = 0, stop = arr.length - 1, control = 0;
boolean ordered, nsCaught;
while (true) {
ordered = true;
nsCaught = false;
for (int i = start; i < stop; i++) {
if (i > 1) {
if (!nsCaught && arr[i - 2] > arr[i - 1]) {
ordered = false;
start = i - 2;
nsCaught = true;
}
}
if (arr[i] > arr[i + 1]) {
int hold = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = hold;
control = i;
}
}
System.out.println(Arrays.toString(arr));
if (ordered) return arr;
stop = control;
}
}
但是正如 @Daniel Fischer 在之前的回答中所说，它对较大的数组没有太多作用。
我想这就是你所需要的。关键是要考虑 数组仅直到上次交换发生的索引（newn）。
public static void bubbleSort(int[] a) {
int i, n, newn;
n = a.length;
while (n > 0) {
newn = 0;
for (i = 1; i < n; i++) {
if (a[i - 1] > a[i]) {
temp = a[i];
a[i] = a[i - 1];
a[i - 1] = temp;
newn = i;
}
}
n = newn;
}
return a;
}
这是使用 while 循环的最简单、最好和最优的冒泡排序算法。它将给定数组形式中的数字按升序从左到右排序。它非常简单易懂且易于实现。
private static int[] bubbleSort(int[] array) {
int length = array.length - 1;
int index = 0;
while (index < length) {
if (array[index] > array[index + 1]) {
swap(array, index, index + 1);
}
index++;
if (index == length) {
index = 0;
length--;
}
}
return array;
}
private static void swap(int[] array, int index1, int index2) {
int temp = array[index1];
array[index1] = array[index2];
array[index2] = temp;
}
public static void main(String[] args) {
int[] arr = {4, 2, 3, 1, 5, 6};
System.out.println(Arrays.toString(arr));
bubbleSort(arr);
System.out.println(Arrays.toString(arr));
}
输出：
[4, 2, 3, 1, 5, 6]
[1, 2, 3, 4, 5, 6]
我没有代码，但您可以使用 n 位来跟踪最后一次执行交换的位置。或者，效率较低的方法是使用单个变量来跟踪第一次交换的执行位置。我们不需要重新比较未交换的元素 - 它们是相同顺序的相同元素，因此我们知道比较将是相同的，并且我们可以安全地跳过它们。
直觉上我觉得，即使进行了上述优化，冒泡排序仍然无法击败二进制插入排序的比较，并且会引入更多的分支逻辑（在辅助空间之上）来跟踪交换。所以这可能不值得研究，除非有人好奇。
您可以通过添加一个标志来检查传递过程中交换的任何元素来优化冒泡排序算法。如果没有元素交换，则数组已经排序，您可以退出。
仅使用 1 个 for 循环优化冒泡排序
/*Advanced BUBBLE SORT with ONE PASS*/
/*Authored by :: Brooks Tare AAU*/
public class Bubble {
public int[] bubble(int b[]) {
int temp, temp1;
for (int i = 0; i < b.length - 1; i++) {
if (b[i] > b[i + 1]) {
///swap(b[i],b[i+1]);
temp = b[i];
b[i] = b[i + 1];
b[i + 1] = temp;
// Checking if there is any number(s) greater
// than the current number. If there is swap them.
while (i > 0) {
if (b[i] < b[i - 1]) {
///swap(b[i]<b[i-1])
temp1 = b[i];
b[i] = b[i - 1];
b[i - 1] = temp1;
i--;
} else if (b[i] > b[i - 1]) {
i--;
}
}
} else {
continue;
}
}
return b;
}
///the following is a function to display the Array
public void see(int[] a) {
for (int j = 0; j < a.length; j++) {
System.out.print(a[j] + ",");
}
}
public static void main(String[] args) {
///You can change the Array to your preference..
// u can even make it dynamic
int b[] = {5, 1, 4, 2, 0, 3};
int v[] = new int[100];
Bubble br = new Bubble();
v = br.bubble(b);
br.see(v);
}
}