Java中的双向冒泡排序?

发布于 2024-09-25 17:39:39 字数 767 浏览 11 评论 0原文

我需要在我的代码中实现双向冒泡排序。

换句话说,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); 

I need to implement the bidirectional bubble sort in my code.

In other words in will go from left to right first carrying the largest value.

But when it reaches out, it should reverse and go from right to left carrying the smallest value.

I am advised to to implement another out index in addition the current one.

This is what I have so far - just 2 loops. I am guessing I have to combine them somehow?

    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); 

如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

评论(5

我很OK 2024-10-02 17:39:39
    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++;
       }
   }  
    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++;
       }
   }  
人事已非 2024-10-02 17:39:39

我建议您将该方法拆分为您可以理解的块,例如:

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]

I recommend you split the method up for chunks that you can comprehend, like:

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--);
}

And to test it:

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));
}

Output:

[2, 3, 3, 4, 5, 6, 7, 7, 8]
尘世孤行 2024-10-02 17:39:39
    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;


           }
    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;


           }
鲸落 2024-10-02 17:39:39

仅使用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);
        }
    }
}

Bidirectional Bubble Sort using only 2 loops & 2 index variables.

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);
        }
    }
}
旧人 2024-10-02 17:39:39

双向冒泡排序,排序变量:array[]

//-------------------------------------------//
//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 内完成

Bidirectional bubble sort, sorting variable: array[]

//-------------------------------------------//
//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;
}
//-------------------------------------------//

On 10_000 randomly selected elements, standard bubble sorts completes in 410ms and bidirectional bubble sort in 319ms

~没有更多了~
我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
原文