雙向泡沫排序在Java？

我需要在我的代碼中實現雙向氣泡排序。雙向泡沫排序在Java？

換句話說in會從左至右第一攜帶最大值。

但是當它到達out時，它應該反轉並從右到左攜帶的最小值。

我建議除了當前的另外out索引。

這就是我到目前爲止 - 只有2個循環。我猜我必須以某種方式將它們結合起來？

public void bubbleSort() { 
    int out, in; // nElems in my case is 4, because I have 4 elements in my array 

    for(out=nElems-1; out>1; out--) // outer loop backward 
     for(in=out; in>1; in--) // inner loop backward 
      if(a[in] < a[in-1]) 
       swap(in, in-1); 

    for(out=0; out<nElems; out++) // outer loop forward 
     for(in=0; in<out; in++) // inner loop forward 
      if(a[in] > a[in+1]) 
       swap(in, in+1);

來源

2010-09-30 Sahat Yalkabov

雙向冒泡排序是本次作業？只問，因爲我很少在練習中發現泡泡排序 – 2010-09-30 15:52:19

是的，它是SB。泡沫排序糟透了 - 真實的故事，但我必須完成這個項目。 – 2010-09-30 16:02:48

我猜我不會得到太多的幫助，如果這是一項家庭作業？甚至沒有線索？ – 2010-09-30 16:07:14

public void bidirectionalBubbleSort() 
    { 
     int left = 0, right = a.length-1; 
     while (left < right) 
     { 
      for (int pos = left; pos < right; pos++) 
      { 
      if (a[pos] > a[pos+1]) 
       swap(pos, pos+1); 
      } 
      right--; 


      for (int pos = right; pos > left; pos--) 
      { 
      if (a[pos] < a[pos-1]) 
       swap(pos, pos-1); 
      } 
      left++; 
     } 
    }

來源

2010-09-30 16:15:50 jlewis42

這一行導致數組越界異常：if（a [pos]> a [pos + 1]） – 2010-09-30 16:50:28

我的不好，我正在遞減，而不是增加它 – jlewis42 2010-09-30 17:06:38

我建議你分割方法彌補，你可以理解，像大塊：

public static boolean swap(int[] numbers, int i, int j) { 
    int temp = numbers[i]; 
    numbers[i] = numbers[j]; 
    numbers[j] = temp; 
    return true; 
} 

static boolean leftSide(int[] numbers, int i, int j) { 
    boolean swapped = false; 
    for (int k = i; k < j; k++) 
     if (numbers[k] > numbers[k + 1]) 
      swapped = swap(numbers, k, k + 1); 
    return swapped; 
} 

static boolean rightSide(int[] numbers, int i, int j) { 
    boolean swapped = false; 
    for (int k = j; k > i; k--) 
     if (numbers[k] < numbers[k - 1]) 
      swapped = swap(numbers, k, k - 1); 
    return swapped; 
} 

public static void cocktailSort(int[] numbers) { 
    boolean swapped = true; 
    int i = -1; 
    int j = numbers.length - 1; 

    while (i++ < j && swapped) 
     if (swapped = leftSide(numbers, i, j)) 
      swapped = rightSide(numbers, i, j--); 
}

，並測試它：

public static void main(String[] args) { 
    int x[] = new int[] { 2, 6, 3, 7, 8, 3, 7, 5, 4 }; 
    cocktailSort(x); 
    System.out.println(java.util.Arrays.toString(x)); 
}

輸出：

[2, 3, 3, 4, 5, 6, 7, 7, 8]

來源

2010-09-30 16:54:46 Margus

如果你要返回排序列表，那麼原始列表應該保持不變。克隆它或者其他東西，或者讓排序方法返回其他東西，甚至什麼也不返回。（例如，如果它是無效的，那麼修改原始列表對任何有線索的人都應該是顯而易見的。） – cHao 2010-09-30 18:22:54

這是一個很好的觀點。現在更新代碼以適應這種變化。 – Margus 2010-09-30 19:54:34

boolean f1 = false, f2 = false; 
    outer: 
    for (int i=0; i < arr.length-1; i++) 
      for (int j=i; j< arr.length - i -1; j++) { 

       if(arr[j] >= arr[j+1]){ 
        f1 = true; 
        int t = arr[j]; 
        arr[j] = arr[j+1]; 
        arr[j+1] = t; 
       } 

       if(arr[arr.length - j -1] <= arr[arr.length - j - 2]){ 

        f2 = true; 
        int t = arr[arr.length - j -2]; 
        arr[arr.length - j -2] = arr[arr.length - j -1]; 
        arr[arr.length -j -1] = t; 
       } 

       /** 
       * @param k: iterator variable thats prints each pass..(optional) 
       */ 
       for (int k:arr) 
        System.out.print(" "+k); 
       System.out.println(" "+i); 

       //Ultimate break condition 
       if(j == arr.length - j -2 && (!f1 && !f2)) 
        break outer; 


      }

來源

2013-12-23 19:25:59

雙向冒泡排序只使用2路 & 2指數變量。

public void bubbleSort(){ 
    for(int out=0;out<nElems/2;out++){ 
     boolean forward = true; 
     for (int in = out;in !=(forward ? out-1 : out) 
         ;in = forward ? in + 1 : in - 1) 
     { 
      if (in == nElems - (out + 1)) 
       forward = false; 
      if (a[forward ? in + 1 : in] < a[forward?in:in-1]) 
       swap(forward ? in + 1 : in - 1, in); 
     } 
    } 
}

來源

2015-01-12 20:49:03

雙向冒泡排序，排序變量：數組[]

//-------------------------------------------// 
//biderctioanal bubble sort - coctail sort 
public void bidirBubbleSort(){ 
    for(int i=1; i<length/2; i++){ 
     for(int j=0; j<length-i; j++) 
      if(array[j]>array[j+1]) 
       swap(j, j+1); 
     for(int j=length-i; j>=i; j--) 
      if(array[j]<array[j-1]) 
       swap(j, j-1); 
    } 
} 
//-------------------------------------------// 
//swap 2 elements 
public void swap(int index1, int index2){ 
    int temp=array[index1]; 
    array[index1]=array[index2]; 
    array[index2]=temp; 
} 
//-------------------------------------------//

在10_000隨機選擇的元素，標準泡沫排序完成在410ms和319ms中

來源

2016-09-21 21:39:38 Shone

雙向泡沫排序在Java？

回答

相關問題