泡泡排序使用冒泡

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个位置的第i个位置。

谁能帮我这个？

Answer 1

#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 2

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

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