java - 冒泡排序算法实现

Question

我正在学习冒泡排序算法，我遇到了两种实现它的方法，所以我的问题是哪个更好，为什么？

第一

for(k=0;k<array.length-1;k++){ 
            if(array[k] > array[k+1]){
                int temp = array[k];
                array[k] = array[k+1];
                array[k+1] = temp;
            }
        }

第二

for(i=array.length-1;i>=0;i--){
        for(k=0;k<i;k++){ 
            if(array[k] > array[k+1]){
                int temp = array[k];
                array[k] = array[k+1];
                array[k+1] = temp;
            }
        }
        }

score 1 · Accepted Answer

不仅仅是关于哪个更好 - 首先是关于哪个对数组进行排序，答案是第二个

检查这个以获得更多想法

score 0 · Accepted Answer

The second one will sort the array. But you can reduce the comparisons in second loop by running it only when there is at least a single swap in last iteration.

score 0 · Accepted Answer

我在 Wikipedia ( http://en.wikipedia.org/wiki/Bubble_sort )中找到了更有效的方法

procedure bubbleSort( A : list of sortable items )
    n = length(A)
    repeat
       newn = 0
       for i = 1 to n-1 inclusive do
          if A[i-1] > A[i] then
             swap(A[i-1], A[i])
             newn = i
           end if
       end for
       n = newn
    until n = 0
end procedure

score 0 · Accepted Answer

您的第一个实现无法正确排序，因为该算法只能切换 2 个相邻元素。

前任。

输入数据 {6,5,4,3,2}

第一次迭代使这个 -> {5,6,4,3,2} 现在 5 在第一个位置并且没有机会改变这个位置，因为循环索引（k）是 1。进一步迭代它会增加..

冒泡排序总是需要 2 个循环

public static void bubbleSort(int[] array){
    for (int i = 0; i < array.length - 1; i++) {
        for (int j = 0; j < array.length - i - 1; j++) {
            if(array[j] < array[j+1]){
                int tmp = array[j];
                array[j] = array[j+1];
                array[j+1] = tmp;
            }
        }
    }
}

score 0 · Accepted Answer

您的第一个解决方案将不起作用，它不会对数组进行排序。但是第二个会起作用，它将从最小到最大对数据进行排序。有关更多说明，请参见下文：

嗯，冒泡排序算法背后的想法是遍历数据的数组/集合，同时比较每对相邻的项目，如果它们的顺序错误则交换它们。重复遍历数组/列表，直到不需要交换，这表明列表/数组已排序。时间复杂度：O(n^2)。以及我们将使用原始数组的空间。让我们使用以下数组来说明上段中的讨论：

    //array of integer to be sorted
    int[] arrayToSort=new int[]{1,7,81,2,-2,9,9,6,-6};
    //repeat until we're done sorting 
    while (true){
        //flag to check if we did swap number(s)
        boolean didSort=false;
        /*
         *  this inner loop is being used to find numbers that need to be    
         *  swapped and then help in swapping them
         */
        for(int count=0;count<arrayToSort.length-1;count++){
            //check if we need to swap
            if(arrayToSort[count]>arrayToSort[count+1]){
                int temp=arrayToSort[count+1];
                arrayToSort[count+1]=arrayToSort[count];
                arrayToSort[count]=temp;
                //set our swap flag so that we will know that we did swap
                didSort=true;
            }

        }

        //check we did a swap in our last inner loop iteration if not will   
        //be done sorting, then break the outer loop
        if(!didSort){
            break;
        }   
    }

    //let's print the sorted array.
    for(int i=0;i<arrayToSort.length;i++){
        System.out.print(arrayToSort[i]+", ");
    }

score -2 · Accepted Answer

不要使用冒泡排序（改用插入排序）。

编辑：

由于人们一直对此投反对票，请阅读http://warp.povusers.org/grrr/bubblesort_misconceptions.html

冒泡排序是帕累托低效率的，因为它比插入排序和选择排序更慢且更难理解。只是不要使用（也不教）Bubblesort。

java - 冒泡排序算法实现

6 回答 6

Related

Reference