[ VB2010 ] - 快速氣泡排序法

[ VB2010 ] - 快速氣泡排序法

快速排序(Quick sorting)

快速排序之觀念，找資料之中間值，將小於中間值放右邊，大於中間值放左邊，再以相同方法分左右兩邊序列，直到排序完成。

【分析】

1.        時間複製度，最差O(n²)與平均時間O(nlog₂n)。

2.        需要額外堆疊空間。

3.        為不穩定排序。

4.        快速排序是平均時間最快之內部排序法。

【原理】

1.        取第一個記錄為鍵值K_0，當中間值。

2.        由左而右找第一個K_i，使得K_i≧K₀。由右而左找第一個K_j，使得K_j≦K₀。也就是說，從左邊找比K₀大，從右邊找比K₀小。

3.        若i<j則K_i與K_j對調位置繼續步驟2；否則K₀與K_j對調位置，並以j為基準，分為兩個未排序之序列。以遞迴呼叫方式對左右兩邊進行排序，直道完成排序。

4.        由最大(最小)逐回合比較至最小(最大)。

【演算法】

QuickSort(int A[], int left, int right)

{

    int i, j, s , Temp;

    if(left < right) {

        s = A[(left+right)/2];

        i = left - 1;

        j = right + 1;

        while(1) {

            while(A[++i] < s) ;  // 向右找

            while(A[--j] > s) ;  // 向左找

            if(i >= j) break;

               Temp = A[i];

               A[i] = A[j];

               A[j] = Temp;

        }

        QuickSort(A, left, i-1);   // 對左邊進行遞迴

        QuickSort(A, j+1, right);  // 對右邊進行遞迴

    }

}

Public Class Form1

    Private Sub Button1_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Button1.Click

        Dim SortResult As String = ""

        Dim Data(7) As Integer

        Dim I, J, K As Integer, Buffer As Integer

        Data(0) = Val(TextBox1.Text)

        Data(1) = Val(TextBox2.Text)

        Data(2) = Val(TextBox3.Text)

        Data(3) = Val(TextBox4.Text)

        Data(4) = Val(TextBox5.Text)

        Data(5) = Val(TextBox6.Text)

        Data(6) = Val(TextBox7.Text)

        Data(7) = Val(TextBox8.Text)

        For I = 0 To UBound(Data) - 1

            For K = 0 To UBound(Data)

                TextBox9.Text &= (I + 1).ToString & ". Data" & (K + 1).ToString & "=" & CStr(Data(K)) & "__"

            Next

            For J = 0 To UBound(Data) - 1 - I

                If Data(J) < Data(J + 1) Then

                    Buffer = Data(J)

                    Data(J) = Data(J + 1)

                    Data(J + 1) = Buffer

                End If

            Next

            TextBox9.Text &= vbCrLf

        Next

        For I = 0 To UBound(Data)

            SortResult &= CStr(Data(I)) & ","

        Next

        TextBox9.Text &= vbCrLf & "最後排序結果" & vbCrLf & (SortResult)

    End Sub

End Class