如何修改此快速排序算法的數據透視選擇？

Question

我想修改列出的快速排序算法來選擇樞軸選擇爲1）數組中的隨機元素。 2）數組中第一個中間元素和最後一個元素的中位數。 ====更新==== 另外我怎樣才能實現一個計時機制，以計算每個算法的運行時間？

void QuickSort1(long *L, int first, int last) 
{ 
    int SplitPoint; /* Value to Split list around */ 

    if(first < last) 
    { 
     /* Use first element as pivot (for splitting) */ 
     SplitPoint = first;     /* assign SplitPoint to 1st index */ 
     Split(L, first, last, &SplitPoint); /* Split List around SplitPoint */ 
     QuickSort1(L, first, SplitPoint-1); /* Sort 1st section of list */ 
     QuickSort1(L, SplitPoint+1, last); /* Sort 2nd section of list */ 
    } 
} 

void Split(long *L, int first, int last, int *SplitPoint) 
/* Splits a list around SplitPoint such that all values to the left of 
    SplitPoint are < than SplitPoint and all values to the right of 
    SplitPoint are >= SplitPoint */ 
{ 
    int x;   /* Key */ 
    int unknown;  /* index of unknown value */ 

    x = L[*SplitPoint]; /* assign x to value at SplitPoint */ 
    Swap(&L[*SplitPoint], &L[first]); 
    *SplitPoint = first; 

    /* Loop walks through unknown portion of list */ 
    for (unknown = first+1; unknown <= last; ++unknown) 
    { 
     /* If unknown value is < SplitPoint Value, then: */ 
#ifdef TAKE_COUNT 
     comparison_count++; 
#endif 
     if(L[unknown] < x) { 
     ++ (*SplitPoint);      /* SplitPoint is incremented */ 
     Swap(&L[*SplitPoint], &L[unknown]); /* values are swapped*/ 
     } 
    } 
    /* Original value which was being split upon is swapped with the current 
     SplitPoint to put it in correct position */ 
    Swap(&L[first], &L[*SplitPoint]); 
} 

int FindMedian(long *L, int A, int B, int C) 
/* Receives array and three respective indices in the array. */ 
/* Returns the index of the median. */ 
{ 
    if (L[A] < L[B]) 
    if (L[B] < L[C])  /* A < B < C */ 
     return (B); 
    else 
     if (L[A] < L[C])   /* A < C < B */ 
    return (C); 
     else 
    return (A);   /* C < A < B */ 
    else 
    if (L[A] < L[C])   /* B < A < C */ 
     return (A); 
    else 
     if (L[B] < L[C])  /* B < C < A */ 
    return (C); 
     else 
    return (B);   /* C < B < A */ 
} 

void Swap(long *a, long *b) 
/* This function uses call by reference to switch two elements.*/ 
{ 
    long temp; /* temporary variable used to switch. */ 

    temp = *a; /* temp = 1st # */ 
    *a = *b;  /* 1st # = 2nd # */ 
    *b = temp; /* 2nd # = temp */ 
} 

我該如何修改列出的數據透視選項？它們還必須作爲程序的附加菜單選項添加。

Answer 1

祕訣是你總是選擇數組中的第一個元素作爲支點。如果你想使用另一個元素，如果輸入已經排序或者（通常情況下）大部分被附加了幾個新元素排序，這是一個非常好的主意，將它與第一個元素交換。現在樞軸是第一個元素。

有了這種見解，任務應該變得非常簡單。要選擇一個隨機數據透視表，生成一個隨機數字）到N-1，並與第一個元素交換。要取平均值3，寫一個如果...... else語句那麼容易混淆但直截了當的集合。