0

我试图实现冒泡排序，但我不确定它是否正确。如果您可以看一下，并且如果它是冒泡排序并且可以以更好的方式完成，请不要害羞。这是代码：

package Exercises;

import java.util.*;

public class BubbleSort_6_18 
{
    public static void main(String[] args) 
    {
        Random generator = new Random();

        int[] list = new int[11];
        for(int i=0; i<list.length; i++)
        {
            list[i] = generator.nextInt(10);
        }

        System.out.println("Original Random array: ");
        printArray(list);

        bubbleSort(list);

        System.out.println("\nAfter bubble sort: ");
        printArray(list);
    }

    public static void bubbleSort(int[] list)
    {
        for(int i=0; i<list.length; i++)
        {
            for(int j=i + 1; j<list.length; j++)
            {
                if(list[i] > list[j])
                {
                    int temp = list[i];
                    list[i] = list[j];
                    list[j] = temp;
                }
            }

        }
    }

    public static void printArray(int[] list)
    {
        for(int i=0; i<list.length; i++)
        {
            System.out.print(list[i] + ", ");
        }
    }
}
4

17 回答 17

9 
private static int [] bublesort (int[] list , int length) {

    boolean swap = true;
    int temp;

    while(swap){

        swap = false;

        for(int i = 0;i < list.length-1; i++){              
            if(list[i] > list[i+1]){
                temp = list[i];
                list[i] = list[i+1];
                list[i+1] = temp;                   
                swap = true;
            }
        }
    }
    return list;
}
于 2012-07-25T08:22:24.750 回答
5

Mohammod Hossain 的实现非常好，但他做了很多不必要的迭代，遗憾的是他没有接受我的编辑，由于声誉点，我无法发表评论，所以它应该是这样的：

public void sort(int[] array) {
        int temp = 0;
        boolean swap = true;
        int range = array.length - 1;
        while (swap) {
            swap = false;
            for (int i = 0; i < range; i++) {
                if (array[i] > array[i + 1]) {
                    temp = array[i];
                    array[i] = array[i + 1];
                    array[i + 1] = temp;
                    swap = true;
                }
            }
            range--;
        }
    }
于 2016-06-23T16:55:22.173 回答
2

这是冒泡排序的经典实现，它似乎没问题。有几种优化可以做，但总体思路是一样的。这里有一些想法：

  • 如果内循环没有swap的时候有外循环的迭代，那么break，没用继续
  • 在外部循环的每次迭代中，交换内部循环的方向 - 从左到右执行一次，然后从右到左执行一次（这有助于避免元素缓慢地向右端移动）。
于 2012-07-25T07:43:29.153 回答
2 
{
    System.out.println("The Elments Before Sorting:");
    for(i=0;i<a.length;i++)
    {
        System.out.print(a[i]+"\t");
    }
    for(i=1;i<=a.length-1;i++)
    {
      for(j=0;j<=a.length-i-1;j++)
      {
          if((a[j])>(a[j+1]))
          {
              temp=a[j];
              a[j]=a[j+1];
              a[j+1]=temp;
            }
       }
      System.out.println("The Elements After Sorting:");
      for(i=0;i<a.length;i++)
      {
            System.out.println(a[i]+"\t");
      }
    }
}
于 2014-09-21T09:08:28.483 回答
2

简短的回答：这绝对不是冒泡排序。它是选择排序的一种变体（一种效率低于众所周知的变体）。

查看他们如何在VisuAlgo上工作的可视化可能会有所帮助

为什么这不是冒泡排序？

因为您循环遍历数组并将每个元素与其右侧的其他元素进行比较。如果正确的元素较小，则交换。因此，在第一次外循环迭代结束时，您将在最左边的位置拥有最小的元素，并且在最坏的情况下您已经完成了 N 次交换（想想一个反向排序的数组）。

如果您考虑一下，您实际上并不需要进行所有这些交换，您可以在右侧搜索最小值，然后在找到它之后进行交换。这只是选择排序的想法，您选择剩余未排序元素的最小值并将其放在正确的位置。

那么冒泡排序是什么样子的呢？

在冒泡排序中，您总是比较两个相邻的元素并将较大的元素冒泡到右侧。在外部循环的第一次迭代结束时，您将在最右边的位置拥有最大的元素。swap当数组已经排序时，该标志停止外循环。

void bubbleSort(int[] arr) {
    boolean swap = true;       
    for(int i = arr.length - 1; i > 0 && swap; i--) {
        swap = false;
        // for the unsorted part of the array, bubble the largest element to the right.
        for (int j = 0; j < i; j++) {
            if (arr[j] > arr[j+1]) {
                // swap
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
                swap = true;
            }
        }
    }
}
于 2016-04-26T11:56:30.903 回答
1

我认为您通过查看代码了解了冒泡排序的概念：

冒泡排序通常如下工作：假设aNumber是一些随机数：

for (int i = 0; i < aNumber; i++)
{
     for(int j = 0; j < aNumber; j++)

      //Doing something with i and j, usually running it as a loop for 2D array
      //array[i][j] will give you a complete sort.
}

冒泡排序的工作原理是遍历数组的每一个可能点。i x jtimes 不利的一面是，排序的次数是平方数。效率不是很高，但它确实以最简单的方式完成了工作。

于 2012-07-25T07:52:44.387 回答
1

是的，它似乎是冒泡排序交换元素

冒泡排序

void bubbleSort(int arr[])
{
    int n = arr.length;
    for (int i = 0; i < n-1; i++)
        for (int j = 0; j < n-i-1; j++)
            if (arr[j] > arr[j+1])
            {
                // swap temp and arr[i]
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
}

即使数组已排序，它也会在最坏的情况下给出 O(n^2) 。

于 2016-11-20T04:14:14.510 回答
0

A bubblesort version with while loops from my first undergraduate year ("the BlueJ era").

public static void bubbleSort()
    {
        int[] r = randomArrayDisplayer();
        int i = r.length;
        while(i!=0){
            int j = 0;
            while(j!=i-1){
                if(r[j+1]<r[j]){
                    swap(r,j,j+1);
                }
                j++;
            }
            i--;
        }
    }

private static void swap(int[] r, int u, int v)
    {
       int value = r[u];
       r[u] = r[v];
       r[v] = value;
       arrayDisplayer(r);
    }

My advice is to display every step in order to be sure of the correct behaviour.

于 2014-09-21T09:16:25.603 回答
0
  • 您可以遍历数组，直到没有更多元素被交换
  • 当您将元素放在最后一个位置时，您知道它是最大的，因此您可以将内部循环减少 1
于 2012-07-25T07:47:18.303 回答
0

上面的代码看起来像实现选择排序，它不是冒泡排序。

请在下面找到冒泡排序的代码。

Class BubbleSort {
public static void main(String []args) {
int n, c, d, swap;
Scanner in = new Scanner(System.in); 
System.out.println("Input number of integers to sort");
n = in.nextInt();

int array[] = new int[n]; 
System.out.println("Enter " + n + " integers");

for (c = 0; c < n; c++) 
  array[c] = in.nextInt();

for (c = 0; c < ( n - 1 ); c++) {
  for (d = 0; d < n - c - 1; d++) {
    if (array[d] > array[d+1]) /* For descending order use < */
    {
      swap       = array[d];
      array[d]   = array[d+1];
      array[d+1] = swap;
    }
  }
}

System.out.println("Sorted list of numbers");

for (c = 0; c < n; c++) 
  System.out.println(array[c]);
}
}
于 2015-04-27T11:30:09.620 回答
0 
public class BubbleSort {
    public static void main(String[] args) {
        int arr[] = {64, 34, 25, 12, 22, 11, 90};
        BubbleSort client=new BubbleSort();
        int[] result=client.bubbleSort(arr);
        for(int i:result)
        {
            System.out.println(i);
        }
    }
    public int[] bubbleSort(int[] arr)
    {
        int n=arr.length;
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<n-i-1;j++) 
                if(arr[j]>arr[j+1])
             swap(arr,j,j+1);   
        }
        return arr;
    }
    private int[] swap(int[] arr, int i, int j) {
        int temp=arr[i];
        arr[i]=arr[j];
        arr[j]=temp;
        return arr;
    }


}
于 2015-02-17T17:46:02.413 回答
0 
/*
Implementation of Bubble sort using Java
*/

import java.util.Arrays;
import java.util.Scanner;


public class BubbleSort {

    /**
     * @param args
     */
    public static void main(String[] args) {
        // TODO Auto-generated method stub
            Scanner in = new Scanner(System.in);
            System.out.println("Enter the number of elements of array");
            int n = in.nextInt();
            int []a = new int[n];
            System.out.println("Enter the integer array");
            for(int i=0; i<a.length; i++)
            {
                a[i]=in.nextInt();
            }
            System.out.println("UnSorted array: "+ Arrays.toString(a));         
            for(int i=0; i<n; i++)
            {
                for(int j=1; j<n; j++)
                {
                    if(a[j-1]>a[j])
                    {
                        int temp = a[j-1];
                        a[j-1]=a[j];
                        a[j]=temp;
                    }
                }
            }
            System.out.println("Sorted array: "+ Arrays.toString(a));           
    }
}


/*
****************************************
Time Complexity: O(n*n)
Space Complexity: O(1)
****************************************
*/
于 2015-06-29T05:06:38.723 回答
0 
package com.examplehub.sorts;

public class BubbleSort implements Sort {

  /**
   * BubbleSort algorithm implements.
   *
   * @param numbers the numbers to be sorted.
   */
  public void sort(int[] numbers) {
    for (int i = 0; i < numbers.length - 1; ++i) {
      boolean swapped = false;
      for (int j = 0; j < numbers.length - 1 - i; ++j) {
        if (numbers[j] > numbers[j + 1]) {
          int temp = numbers[j];
          numbers[j] = numbers[j + 1];
          numbers[j + 1] = temp;
          swapped = true;
        }
      }
      if (!swapped) {
        break;
      }
    }
  }

  /**
   * Generic BubbleSort algorithm implements.
   *
   * @param array the array to be sorted.
   * @param <T> the class of the objects in the array.
   */
  public <T extends Comparable<T>> void sort(T[] array) {
    for (int i = 0; i < array.length - 1; ++i) {
      boolean swapped = false;
      for (int j = 0; j < array.length - 1 - i; ++j) {
        if (array[j].compareTo(array[j + 1]) > 0) {
          T temp = array[j];
          array[j] = array[j + 1];
          array[j + 1] = temp;
          swapped = true;
        }
      }
      if (!swapped) {
        break;
      }
    }
  }
}

来源

于 2020-10-30T07:20:11.873 回答
0

这是冒泡排序算法的实现，使用Stack：

static void bubbleSort(int[] elements) {
    Stack<Integer> primaryStack = new Stack<>();
    Stack<Integer> secondaryStack = new Stack<>();
    int lastIndex = elements.length - 1;

    for (int element : elements) {
        primaryStack.push(element);
    } // Now all the input elements are in primaryStack

    // Do the bubble sorting
    for (int i = 0; i < elements.length; i++) {
        if (i % 2 == 0) sort(elements, i, primaryStack, secondaryStack, lastIndex);
        else sort(elements, i, secondaryStack, primaryStack, lastIndex);
    }
}

private static void sort(int[] elements, int i, Stack<Integer> stackA, Stack<Integer> stackB, int lastIndex) {
    while (!stackA.isEmpty()) { // Move an element from stack A to stack B
        int element = stackA.pop();

        if (stackB.isEmpty() || element >= stackB.peek()) { // Don't swap, just push
            stackB.push(element);
        } else { // Swap, then push
            int temp = stackB.pop();
            stackB.push(element);
            stackB.push(temp);
        }
    }
    elements[lastIndex - i] = stackB.pop();
}
于 2021-11-04T10:43:33.630 回答
0 
class BubbleSort {

public static void main(String[] args) {

    int a[] = {5,4,3,2,1};
    int length = a.length - 1;

    for (int i = 0 ; i < length ; i++) {
        for (int j = 0 ; j < length-i ; j++) {
            if (a[j] > a[j+1]) {
                int swap = a[j];
                a[j] = a[j+1];
                a[j+1] = swap;
            }
        }
    }

    for (int x : a) {
        System.out.println(x);
    }
}

}

于 2015-11-04T10:54:15.623 回答
0 
function bubbleSort(arr,n) {
    if (n == 1)  // Base case
    return; 
    // One pass of bubble sort. After
    // this pass, the largest element
    // is moved (or bubbled) to end. and count++

    for (let i = 0; i <n-1; i++){
        if (arr[i] > arr[i + 1]) 
        { 
            let temp = arr[i]; 
            arr[i] = arr[i + 1]; 
            arr[i + 1] = temp; 
        }
    }
    // Largest element is fixed,
    // recur for remaining array
    console.log("Bubble sort Steps ", arr, "   Bubble sort array length reduce every recusrion ", n);
    bubbleSort(arr, n - 1);
}
let arr1 = [64, 3400, 251, 12, 220, 11, 125]
bubbleSort(arr1, arr1.length); 
console.log("Sorted array : ", arr1);

在此处输入图像描述

在此处输入图像描述

于 2021-05-14T06:36:29.213 回答
0 
    int[] nums = new int[] { 6, 3, 2, 1, 7, 10, 9 };

        for(int i = nums.Length-1; i>=0; i--)
            for(int j = 0; j<i; j++)
            {
                int temp = 0;
                if( nums[j] < nums[j + 1])
                {
                    temp = nums[j];
                    nums[j] = nums[j + 1];
                    nums[j + 1] = temp;
                }
            }
于 2017-03-30T14:28:21.430 回答