只用单个循环进行冒泡排序

Question

我正在通过冒泡排序对数字进行排序。因为我想看看这个排序是否可以通过使用单循环来完成，因为我们在冒泡排序中使用了2个循环。有人可以告诉我如何做，甚至可能吗？

Answer 1

气泡排序通过移动彼此相邻的值对来工作。因此，举例来说，你有这样的名单：

list = {5, 3, 6, 11, 2}

第一次迭代，会走的，一对一对，转仓如果必要的：

1. 比较5和3 3小，所以切换=>{3, 5, 6, 11, 2}
2. 比较5和6 5较小，所以你什么都不做=>{3, 5, 6, 11, 2}
3. 比较图6和11，图6是更小的，所以你什么都不做=>{3, 5, 6, 11, 2}
4. 比较11和2 2小，所以你这女巫=>{3, 5, 6, 2, 11}

我们已经完成了1次迭代循环的，正如你看到的，列表进行排序。您需要迭代多次以实现排序。

什么可以做，虽然是只使用1循环，不断迭代，直到它的排序，这将通过在原有基础上冒泡排序开关标志改变迭代指数来实现：

bool valuesSwitched = false; 
int list[5] = {5, 3, 6, 11, 2}; 
int len = 5; 
for(int i = 1; i <= len; i++) 
{ 
    if(i == len) 
    { 
     if(!valuesSwitched) break; 

     valuesSwitched = false; 
     i = 1; 
    } 
    if(list[i - 1] > list[i]) 
    { 
     int temp = list[i - 1]; 
     list[i - 1] = list[i]; 
     list[i] = temp; 
     valuesSwitched = true; 
    } 
} 

Answer 2

在最好的情况下，我们可以使用O（n）进行冒泡排序。

Bubble Sort中的最好情况是完整数组排序的时候。在这种情况下，您会比较第一遍中的相邻元素，并记录您做出的交换次数。

由于完整的数组排序，交换次数将为零。因此你会跳出循环。

我们可以通过对传统的气泡排序算法进行小改动来得到答案。

public class BubbleSort { 

    public static void main(String args[]){ 
     int arr[] = {1,2,3,4,5,6}; 
     BubbleSort bubbleSort = new BubbleSort(); 
     bubbleSort.sort(arr); 

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

    public void sort(int arr[]){ 
     boolean flag = true; 
     for(int i=0; i < arr.length -1; i++){ 
      for(int j=0; j<arr.length-i-1; j++){ 
       if(arr[j]>arr[j+1]){ 
        int temp = arr[j]; 
        arr[j] = arr[j+1]; 
        arr[j+1] = temp; 
        flag=false; 
       } 
      } 
      if(flag){ 
       break; 
      } 
     } 
    } 
}