Blasensortierung und zwei Optimierungen der Blasensortierung

Die Funktionsweise des Blasensortieralgorithmus ist wie folgt: Vergleichen Sie zwei benachbarte Elemente von vorne nach hinten. Wenn das zweite Element kleiner als das erste Element ist, tauschen Sie die beiden Elemente aus, bis es dem letzten Element entspricht ist abgeschlossen, so dass das größte Element am Ende platziert werden kann; durch Wiederholen des Vergleichs (n-1) kann die Sortierung abgeschlossen werden.

---------------- ------ -------------------------------------------- ------ --------

Quicksort-Algorithmus (eine Optimierung der Blasensortierung):

1) Legen Sie zwei Variablen i und j fest, wenn die Sortierung beginnt: i =0, j=N-1;

2) Verwenden Sie das erste Array-Element als Schlüsseldaten und weisen Sie es dem Schlüssel zu, d. h. key=A[0]; Beginnen Sie mit der Suche nach vorne, d. h. nach vorne (j--), finden Sie den ersten Wert A[j], der kleiner als der Schlüssel ist, und tauschen Sie A[j] und A[i] aus

4) Von i aus rückwärts suchen, also von vorne nach hinten suchen (i++), das erste A[i] finden, das größer als der Schlüssel ist, und A[i] und A[j] austauschen; >5) Wiederholen Sie die Schritte 3 und 4, bis i=j; (In den Schritten 3 und 4 wird kein Wert gefunden, der die Bedingungen erfüllt, d. h. A[j] in 3 ist nicht kleiner als der Schlüssel und A[i] in 4 ist nicht größer als der Schlüssel Wenn Sie die Werte von j und i ändern, sodass j = j-1, i = i + 1 ist, bleiben die Zeigerpositionen von i und j unverändert, bis ein Wert gefunden wird, der die Bedingungen erfüllt Der Austausch muss stattfinden, wenn i+ oder j- abgeschlossen ist; an diesem Punkt endet die Schleife.

                                                                  Überprüfen Sie, ob die Elemente ausgetauscht wurden. Wenn ja, fahren Sie mit dem nächsten Zyklus fort nicht, beenden Sie die Schleife.

Diese Methode zum „Setzen von Flag-Bits“ ist nicht so effizient wie der „Schnellsortierungsalgorithmus“.

---------------- ------ -------------------------------------------- ------ --------

Der C-Sprachcode lautet wie folgt:

Wann n ist groß, Zeitkomplexität sollte verwendet werden. Sortiermethoden mit Grad O(nlog2n): schnelle Sortierung, Heap-Sortierung oder Zusammenführungssortierung.

Schnellsortierung: Sie gilt derzeit als die beste interne Sortiermethode, die auf Vergleich basiert. Wenn die zu sortierenden Schlüsselwörter zufällig verteilt sind, ist die durchschnittliche Zeit der Schnellsortierung am kürzesten 🎜>

/*
** bubble sort
*/ 
void bubble_sort(int *str, int size)
{
     int i = 0, j = 0;
     int tmp = 0;
      
     /*
     ** 进行size-1趟排序；
     */
     for (i = 0; i < size - 1; i++)
     {
         /*
         ** 每排序一趟，将最大的元素沉底。下一趟少比较i次；
         */
 
          for (j = 0; j < size - 1 - i; j++)       
          {
               if (str[j] > str[j + 1])
               {
                    tmp = str[j];
                    str[j] = str[j + 1];
                    str[j + 1] = tmp;
               }
          }
 
     }
}
 
/*
** 优化一：设置一个标志位sign的bubble sort；
*/
 void bubble_sort(int *str, int size)
{
     int i = 0, j = 0;
     int tmp = 0, sign = 0;
      
     for (i = 0; i < size - 1; i++)
     {
          /*
          ** 每趟排序前将sign置为0，如果相邻元素进行了交换则sign>1;
          ** 否则，sign==0，没有进行交换，排序完成，跳出循环；
          */
          flag = 0;
          for (j = 0; j < size - 1 - i; j++)
          {
               if (str[j] > str[j + 1])
               {
                    tmp = str[j];
                    str[j] = str[j + 1];
                    str[j + 1] = tmp;
                    sign++;
               }
          }
          if (0 == sign)
          break;
     }
}
 
 
/*
** 优化二：quick sort；
*/
void quicksort(int *str, int left, int right)
{
     assert(str);
      
     /*
     **如果左边大于或等于右边，则该数组已经排序完成；
     */
     if (left >= right)
     {
          return;
     }
      
     int i = left;
     int j = right;
     int key = str[left];
      
     /*
     **当i=j时，一趟排序完成，将所有数分为一大一小两组；
     */
     while (i < j)
     {
          /*
          **第一次从后向前遍历，遇到第一个比key小的交换两数位置；
          */
          while ((i < j) && (key <= str[j]))
          {
               j--;
          }
          str[i] = str[j];
           
          /*
          **第二次从前向后遍历，遇到第一个比key大的交换两数位置；
          */
          while ((i < j) && (key >= str[i]))
          {
               i++;
          }
          str[j] = str[i];
     }
      
     str[i] = key;
     /*
     **递归调用，完成左、右子序列的排序；
     */
     quicksort(str, left, i - 1);
     quicksort(str, i + 1, right);
}

Weitere Artikel zum Thema Blasensortierung und den beiden Optimierungen der Blasensortierung finden Sie auf der chinesischen PHP-Website!