泡泡排序不起作用

Question

i正在使用气泡排序算法并在代码上实现它。目的是使用气泡排序对N大小为n的整数数组进行排序，计算数据比较的数量和数据移动的数量，其中数据比较是比较整数的次数，并且数据移动是整数交换的数量地方。最后，我们只计算执行排序所花费的时间。现在，问题是n的值是大数字，即1000/10000/20000等。要记住的另一件事是，我将数组元素的值分配给了随机数。

import java.util.Random;
import java.util.Scanner;
public class Bubblesort {
public static long DC;
public static long DM;
public static int[] BBSort(int arr[],int n) {
    int K,t,tmp;
    long Data_comp=0,Data_move=0;
    K = n;
    while(K!=0)
    {
        t = 0;
        for (int i = 0; i < K-1; i++) {
            if(arr[i]>arr[i+1])
            {
               tmp = arr[i];
               arr[i] = arr[i+1];
               arr[i+1] = tmp;
               t = i;
               Data_move++;
            }
            Data_comp++;
        }
        K = t;
    }
    DC = Data_comp;
    DM = Data_move;
  return arr;
}
public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    Random r = new Random();
    int N;
    N = sc.nextInt();
    int a[];
    a = new int[N];
    for (int i = 0; i < N; i++) {
          a[i]=r.nextInt(10000);
    }
    long StartTime,EndTime;
    long Totaltime;
    StartTime = System.currentTimeMillis();
    BBSort(a, N);
    EndTime = System.currentTimeMillis();
    Totaltime = EndTime - StartTime;
    for (int j = 0; j < N; j++) {
        System.out.println(a[j]);
    }
    System.out.println("Time taken for sorting = "+Totaltime);
    System.out.println("Number of data comparisons = "+DC );
    System.out.println("Number of data movement = "+3*DM);

}
}

Answer 1

您的问题在于使用变量t的方式。只需将其删除并在每次运行结束时使用K-可以解决您的问题。

public static int[] BBSort(int arr[],int n) {
    int K,tmp;
    long Data_comp=0,Data_move=0;
    K = n;
    while(K!=0)
    {
        for (int i = 0; i < K-1; i++) {
            if(arr[i]>arr[i+1])
            {
               tmp = arr[i];
               arr[i] = arr[i+1];
               arr[i+1] = tmp;
               Data_move++;
            }
            Data_comp++;
        }
        K--;
    }
    DC = Data_comp;
    DM = Data_move;
  return arr;
}

Answer 2

好吧，我相信我已经找到了您的问题。

因此，在气泡排序中，该程序每次都需要遍历每个数字。如果该程序不这样做，则为数字创造机会，以找到他们进入错误的位置并将其捕获的机会。

在您的函数BBSort中，您的程序正在设置运行循环运行到最后一个索引的次数。在这种情况下，您可能有两个数字在最后，本身可能是正确的。IE。获取此列表：{1、2、9、5、6、10}在此数组上，代码将在正确排序两个数字的任何地方都会识别。这意味着，当达到6和10时，它说："好吧，这两个被分类了"，并且不会再碰到6。这是我制作和工作的气泡排序的一些伪代码：

for i = 0 ; i < number of items in array; i++{
    for j = 0; j < number of items in array; j++{
        if (list[j] < list[j+1])
            swap list[j] with list[j+1];
    }
}

我希望您发现这有帮助，并且一切都可以解决！