Алгоритм сортировки пузырьков

Question

Я изучаю алгоритм сортировки пузырьков, и я натолкнулся на два способа его реализации, поэтому мой вопрос в том, что лучше и почему?

первый

for(k=0;k<array.length-1;k++){ 
      if(array[k] > array[k+1]){ 
       int temp = array[k]; 
       array[k] = array[k+1]; 
       array[k+1] = temp; 
      } 
     } 

---

второй

for(i=array.length-1;i>=0;i--){ 
     for(k=0;k<i;k++){ 
      if(array[k] > array[k+1]){ 
       int temp = array[k]; 
       array[k] = array[k+1]; 
       array[k+1] = temp; 
      } 
     } 
     } 

Answer 1

Более о которых один лучше - в первую очередь его, о котором один сортирует массив и ответ второй один

check this чтобы получить дополнительную информацию

Answer 2

1-я из вашей реализации не правильно сортирует, потому что алгоритм может переключать только 2 смежных элемента.

Ex.

входные данные {6,5,4,3,2}

первой итерации сделать это -> {5,6,4,3,2} и теперь 5 находится на 1-ой позиции, и не имеет никаких шансов изменить это положение, becouse индекс цикла (К) 1. И далее итерации увеличивается ..

Bubble рода нужно 2 петли всегда

public static void bubbleSort(int[] array){ 
    for (int i = 0; i < array.length - 1; i++) { 
     for (int j = 0; j < array.length - i - 1; j++) { 
      if(array[j] < array[j+1]){ 
       int tmp = array[j]; 
       array[j] = array[j+1]; 
       array[j+1] = tmp; 
      } 
     } 
    } 
} 

Answer 3

не используйте BubbleSort (вставка использования сортируемую).

EDIT:

Поскольку люди держат вниз голосование, пожалуйста, прочтите http://warp.povusers.org/grrr/bubblesort_misconceptions.html

BubbleSort Парето-неэффективен, так как она медленнее и труднее понять, чем, например, и сортировку вставок сортировки выбора. Просто не используйте (не преподавайте) Bubblesort.

Answer 4

Я нашел более эффективные в Википедии (http://en.wikipedia.org/wiki/Bubble_sort)

procedure bubbleSort(A : list of sortable items) 
    n = length(A) 
    repeat 
     newn = 0 
     for i = 1 to n-1 inclusive do 
      if A[i-1] > A[i] then 
      swap(A[i-1], A[i]) 
      newn = i 
      end if 
     end for 
     n = newn 
    until n = 0 
end procedure 

Answer 5

Второй сортирует массив. Но вы можете уменьшить сравнение во втором цикле, запустив его только тогда, когда на последней итерации есть хотя бы один своп.

Answer 6

Ваше первое решение не будет работать, оно не будет сортировать массив. Но второй, будет работать, и он будет сортировать данные, начиная с самых маленьких и самых больших. Для получения дополнительных пояснений см. Ниже:

Ну, идея алгоритма сортировки пузырьков заключается в том, чтобы пройти через массив/коллекцию данных, сравнивая каждую пару соседних элементов и заменяя их, если они находятся в неправильном порядке. Проход через массив/список повторяется до тех пор, пока не потребуются свопы, что указывает на сортировку списка/массива. Сложность времени: O (n^2). и пространство мы будем использовать исходный массив. Позвольте использовать следующий массив, чтобы проиллюстрировать разговор в приведенном выше абзаце:

//array of integer to be sorted 
    int[] arrayToSort=new int[]{1,7,81,2,-2,9,9,6,-6}; 
    //repeat until we're done sorting 
    while (true){ 
     //flag to check if we did swap number(s) 
     boolean didSort=false; 
     /* 
     * this inner loop is being used to find numbers that need to be  
     * swapped and then help in swapping them 
     */ 
     for(int count=0;count<arrayToSort.length-1;count++){ 
      //check if we need to swap 
      if(arrayToSort[count]>arrayToSort[count+1]){ 
       int temp=arrayToSort[count+1]; 
       arrayToSort[count+1]=arrayToSort[count]; 
       arrayToSort[count]=temp; 
       //set our swap flag so that we will know that we did swap 
       didSort=true; 
      } 

     } 

     //check we did a swap in our last inner loop iteration if not will 
     //be done sorting, then break the outer loop 
     if(!didSort){ 
      break; 
     } 
    } 

    //let's print the sorted array. 
    for(int i=0;i<arrayToSort.length;i++){ 
     System.out.print(arrayToSort[i]+", "); 
    }