冒泡排序使用冒泡向上

Question

给定冒泡排序的算法：

Algorithm BubbleSort(A[0...n]):
  for i <- 0 to n-2 do
    for j <- 0 to n-2-i do
      if(A[j+1] < A[j] then swap(A[j], A[j+1]))

我不得不重写冒泡排序算法，其中我们通过列表将最小的元素“冒泡”到第i个位置。

有人能帮我吗？

Answer 1

当前您正在从头开始遍历数组，因此如果您遇到最大的元素，它将被“冒泡”到数组的末尾。如果你想做相反的事情，将最小的元素“冒泡”到开始，你需要以相反的方向遍历数组，从结束到开始。希望它能帮你找到路。

Answer 2

#include<stdio.h>
void bubbleSort(int *x,int size)
{
  int e,f,m,g;
  m=size-2;
  while(m>0)
  {
    e=0;
    f=1;
    while(e<=m)
    {
      if(x[f]<x[e])  
      {
        g=x[e];       //swaping
        x[e]=x[f];
        x[f]=g;
      }
    e++;
    f++;   
    }
   m--; 
  } 
}
void main()
{
  int x[10],y;
  for(y=0;y<=9;y++)      //loop to insert 10 numbers into an array
  {
    printf("Enter a number: ");
    scanf("%d",&x[y]);
  }
  bubbleSort(x,10);      //pass number entered by user and size of array to bubbleSort 
  for(y=0;y<=9;y++)     //loop to print sorted numbers
  {
    printf("%d\n",x[y]);
  }
}

Answer 3

看起来这个问题的答案还没有被接受。因此，尝试检查这是否仍然是一个问题。

下面是我认为可能的Java实现。正如@Warlord提到的，该算法是为了确保所关注的排序数组被想象为垂直数组。对于每一次遍历，我们所做的就是检查下面是否有更大的元素，如果找到了，则将该元素向上冒泡到顶部。

    static void bubbleUpSort(int[] arr){
    final int N = arr.length;
    int tmp = 0;
    for (int i=0; i < N; i++){
        for (int j=N-1; j >= i+1; j--){
            if (arr[j] < arr[j-1]){
                tmp = arr[j];
                arr[j] = arr[j-1];
                arr[j-1] = tmp;
            }
        }
    }

    for (int k =0; k < arr.length; k++){
        System.out.print(arr[k] + " ");
    }
}

从main调用为：

public static void main(String[] args) {
    System.out.println("Bubble Up Sort");
    int[] bUp = {19, 2, 9, 4, 7, 12, 13, 3, 6};
    bubbleUpSort(bUp);
}