C#-Schnellsortierung

C#-Schnellsortierung

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace Sort
{
    class QuickSorter
    {
        private static int[] myArray;
        private static int arraySize;
        public static int[] Sort(int[] a)
        {
            arraySize = a.Length;
            QuickSort(a, 0,arraySize- 1);
	    return a;
        }
        private static void QuickSort(int[] myArray, int left, int right)
        {
            int i, j, s;
            if (left < right)
            {
                i = left - 1;
                j = right + 1;
                s = myArray[(i + j) / 2];
                while (true)
                {
                    while (myArray[++i] < s) ;
                    while (myArray[--j] > s) ;
                    if (i >= j)
                        break;
                    Swap(ref myArray[i], ref myArray[j]);
                }
                QuickSort(myArray, left, i - 1);
                QuickSort(myArray, j + 1, right);
            }
        }
        private static void Swap(ref int left, ref int right)
        {
            int temp;
            temp = left;
            left = right;
            right = temp;
        }
    }
}

Die Idee der Schnellsortierung:

Angenommen, das zu sortierende Array ist A[0]...A[N-1], Wählen Sie zuerst beliebige Daten (normalerweise wird die erste Zahl des Arrays ausgewählt) als Schlüsseldaten aus, und platzieren Sie dann alle Zahlen, die kleiner als diese sind, und alle Zahlen, die größer als diese sind, danach. Dieser Vorgang wird als Eins bezeichnet -Pass-Schnellsortierung. Es ist zu beachten, dass die schnelle Sortierung kein stabiler Sortieralgorithmus ist, d. h. die relativen Positionen mehrerer identischer Werte können sich am Ende des Algorithmus ändern.

Der Algorithmus der Schnellsortierung in einem Durchgang ist:

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];

3) Suchen Sie vorwärts, beginnend mit j, d (j- -), finden Sie den ersten Wert A[j], der kleiner als der Schlüssel ist, und tauschen Sie das Element mit dem Wert Schlüssel mit A[j] aus

4) Suchen Sie rückwärts, beginnend bei i , beginnend mit der Suche von vorne nach hinten (i++), finden Sie das erste A[i] größer als Schlüssel und tauschen Sie das Element mit dem Wert Schlüssel mit A[i] aus

5) Wiederholen Sie Schritt 3

6) Wiederholen Sie die Schritte 3, 4 und 5, bis i=j; (In den Schritten 3 und 4 wird kein Wert gefunden, der die Bedingungen erfüllt, d. h. wenn A[j] in 3 nicht kleiner ist als key und A[j] in 4 ist nicht größer als key Ändern Sie die Werte von j und i so, dass j=j-1 und i=i+1, bis ein Wert gefunden wird, der die Bedingungen erfüllt i- und j-Zeigerpositionen bleiben unverändert. Außerdem gilt: i==j. Der Vorgang muss genau dann erfolgen, wenn i+ oder j- abgeschlossen ist. An diesem Punkt endet die Schleife.

Beispiel:

Nehmen Sie ein Array als Beispiel und nehmen Sie die erste Zahl im Bereich als Basiszahl.

i = 3; j = 7 .

Beginnen Sie bei j und suchen Sie vorwärts, wenn die Bedingungen erfüllt sind, graben Sie a[5] aus und füllen Sie es in das vorherige Loch, a[3] = a[5];

Beginnen Sie bei i und suchen Sie rückwärts. Wenn i=5, wird es beendet, weil i==j.

Zu diesem Zeitpunkt ist i = j = 5 und a[5] ist zufällig das letzte Mal gegrabene Loch, also fülle X in a[5] ein. Das Array

wird zu:

Das Obige ist der Inhalt der C#-Schnellsortierung. Weitere verwandte Inhalte finden Sie auf der chinesischen PHP-Website (www .php.cn)!