双向泡沫排序在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？

回答

相关问题