高速ソートアルゴリズム-C言語


高速ソートは、実際には最も速い既知のソートアルゴリズムであり、その平均時間はO(Nlogn)であり、最悪の場合はO(N*N)である.
プログラムの重要な点は、中枢要素pivotを見つけることです.
C言語プログラムは以下の通りである.
typedef int ElementType;

void QuickSort(ElementType A[],int left,int right)
{
    int i,j;
    ElementType pivot;
    i=left;
    j=right;
    pivot=A[left];
    if(left>=right) return ;
    while(i!=j)
    {      while(A[j]>=pivot && j>i)
            j--;
        if(j>i)
            A[i++]=A[j];
        while(A[j]<=pivot && j>i)
            i++;
        if(j>i)
            A[j--]=A[i];
    }
    A[i]=pivot;
    QuickSort(A,left,i-1);
    QuickSort(A,i+1,right);
}