Datenstruktur: Binäre Suche, schnelle Sortierideen und Implementierung

In letzter Zeit habe ich darüber nachgedacht, wie man besser entwirft, codiert und das objektorientierte Denken besser versteht, und ich beschäftige mich auch bewusst mit diesem Aspekt. Nachdem ich mehrere Jahre lang Code geschrieben hatte, habe ich ihn auch zusammengefasst und festgestellt, dass es am wichtigsten ist, darüber nachzudenken. Ich habe das Buch „Programming Practice“ rezensiert und den Stil, die Qualität, die Leistung, die Portabilität usw. des von mir geschriebenen Codes weiter standardisiert und darüber nachgedacht. Die Kenntnisse und Algorithmen der Datenstruktur werden weiter gefestigt. Schreiben wir über Algorithmen, die in schriftlichen Prüfungen häufig vorkommen: binäre Suche, schneller Sortieralgorithmus. Der Schlüssel zur Implementierung eines Algorithmus liegt in der Idee der Implementierung.

(1) Binäre Suche
Die binäre Suche ist eigentlich eine halbe Suche, eine effizientere Suchmethode. Suchen Sie nach erforderlichen Arrays.
Die Hauptidee ist: (Angenommen, die gesuchte Array-Periode ist array[low, high])
(1) Bestimmen Sie die Mittelposition K der Periode
(2) Vergleichen Sie den gesuchten Wert T mit array[ k] Vergleiche. Wenn sie gleich sind, ist die Suche erfolgreich und kehrt zu dieser Position zurück. Andernfalls wird der neue Suchbereich bestimmt und die binäre Suche fortgesetzt. Die Fläche wird wie folgt bestimmt:
a.array[k]>T Aus der Reihenfolge des Arrays ergibt sich array[k,k+1,…,high]>T; das neue Intervall lautet also array[low ,… …, K-1]
b.array[k]

Zeitliche Komplexität: O(log2n);

Code-Implementierung:
                                                                                                               ;
                                                                                                                                                                                                       Die Zahl
                                                                                                                                                  ,                                                                        ,,,, ,,,,,,,,,,,,,,, , , high, mid;
low = 0;
high = array.Length - 1;
while (low <= high)
{
mid = (low + high) / 2 ;
if (array[mid] < T)
{
low = mid + 1;
}
               else if. (array[mid]>T)
                                                                                           🎜>                                                                  ​return mid;
}
}
return -1;
}

(2) Schnellsortierungsalgorithmus
Die Schnellsortierung ist ein hervorragendes Beispiel dafür, wie man zusätzliche Berechnungen so weit wie möglich vermeidet. Die Funktionsweise besteht darin, kleine und große Elemente im Array zu unterteilen.
Die Grundidee ist:
Aus dem Array ein Element als Basiswert
Andere Elemente in zwei Gruppen einteilen:
„Klein“ sind diejenigen Elemente, die kleiner als der Basiswert sind.
„Groß“ sind die Elemente, die größer als der Basiswert sind.
Sortieren Sie diese beiden Gruppen rekursiv.
Der Grund, warum die schnelle Sortierung schnell ist, liegt darin, dass sie, sobald sie weiß, dass ein Element kleiner als der Basiswert ist, keinen Vergleich mit diesen größeren Elementen durchführen muss. Große Elemente müssen nicht mit kleinen Elementen verglichen werden. Diese Eigenschaft macht die schnelle Sortierung viel schneller als die einfache Sortierung und Blasensortierung.

时间复杂度：O（nlogn）
代码实现：
        ///

        /// 快速排序
        ///
        / //
        ///
        ///
        public void QuickSort(int[] array,int left,int right)
        {
            int last;
            if (left>=right)
return;
            int rand = (left+right)/2;
            Swap(array, left, rand);
            last = left;
            for (int i = left + 1; i < = right; i++)
            {
               if (array[i] < array[left])
                  Swap(array, ++last, i);
            }
            Swap(array, left, last);
            QuickSort(array, left, last - 1);
            QuickSort(array, last + 1, right);
        }

        ///

        /// 交换两个值
        ///

        ///
        /// < param name="i">
        ///
        private void Swap(int[] a,int i,int j)
        {
            int temp;
            temp = a[i];
            a[i] = a[j];
            a[j] =. temp;
        }

更多数据结构之二分法查找、快速排序思想与实现相关文章请关注PHP中文网！