用指針快速排序

我需要在C中編寫一個快速排序算法作爲作業。這是我被賦予了原型：用指針快速排序

static inline 
int* choose_pivot(int *left, int *right) { 
    /* FIX ME */ 
} 

/* 
* partition(left, right, pivot): push value less than *pivot on the left 
* return the new pivot. 
*/ 
int* partition(int *left, int *right, int *pivot) { 
/* FIX ME */ 
} 

/* 
* quick_sort(left, right) 
*/ 
void quick_sort(int *left, int *right) { 
/* FIX ME */ 
}

其中left是指向數組和right的第一元件，所述指針的最後一個元素（除外）。我寫了下面的代碼：

static inline 
int* choose_pivot(int *left, int *right) { 
    return &left[(right - left)/2]; 
} 

void swap(int *a, int *b) 
{ 
    int c = *a; 
    *a = *b; 
    *b = c; 
} 
int* partition(int *left, int *right, int *pivot) { 
    int *i, *q; 
    q = right; 
    i = left ; 
    while (q > pivot) 
    { 
     while (pivot < i) 
      pivot++; 
     while (q > i) 
     q--; 
     if (*q > *pivot) 
     { 
      swap(pivot,q); 
     } 
    } 
    swap(left, q); 
    return q ; 
} 
void quick_sort(int *left, int *right) { 
    if(left >= right) 
     return; 

    int *pivot = partition(left, right, choose_pivot(left, right)); 
    quick_sort(left, pivot-1); 
    quick_sort(pivot + 1, right); 
}

我運行3種測試：一個排序的陣列上，一個在反向排序之一，一個逆向排序之一。第一次測試運行良好，但第二次測試失敗。基本上這些功能不起作用。我無法找到任何我應該做的文檔，因爲所有快速排序算法都使用它的長度而不是最後一個元素上的指針，而且我無法將我找到的那些適應於我的表示。這裏出了什麼問題？

編輯：

我的新的分區功能，現在看起來是這樣的意見後：

int* partition(int *left, int *right, int *pivot) { 
    int *i, *q; 
    q = right; 
    i = left ; 
    int p = *pivot; 

    while (q > pivot) 
    { 
     while (p < *i) 
      pivot++; 
     while (*q > *i) 
      q--; 
     if (q > pivot) 
     { 
      swap(pivot,q); 
     } 
    } 
    swap(left, q); 
    return q ; 
}

來源

2014-10-31 user26830

你爲什麼增加支點？ – 2501 2014-10-31 23:24:41

對不起，我試着修改代碼[here]（http://www.dailyfreecode.com/code/quick-sort-2852.aspx）。 – user26830 2014-10-31 23:30:48

通常情況下，您將使用最左側的元素作爲主鍵。如果您選擇使用中間元素作爲數據透視表（更好地處理預排序列表），則在分區之前將其與最左側的元素進行交換。看起來你在某個時候學到了這一點，因爲我在分區函數的末尾看到了'swap（left，q）;'，這隻有在樞軸是最左邊的元素時纔有意義。編輯：在您鏈接的代碼中，透視圖是最左邊的元素（'i = a [lower]'）。 – JS1 2014-10-31 23:32:09

這裏是快速排序使用指針的簡單功能..的

quicksort(void *a, int low, int high) 
    { 
    int pivot; 
    /* Termination condition! */ 
    if (high > low) 
    { 
    pivot = partition(a, low, high); 
    quicksort(a, low, pivot-1); 
    quicksort(a, pivot+1, high); 
    } 
    }

功能分區

int partition(void *a, int low, int high) 
    { 
    int left, right; 
    void *pivot_item; 
    pivot_item = a[low]; 
    pivot = left = low; 
    right = high; 
    while (left < right) { 
    /* Move left while item < pivot */ 
    while(a[left] <= pivot_item) left++; 
    /* Move right while item > pivot */ 
    while(a[right] > pivot_item) right--; 
    if (left < right) SWAP(a,left,right); 
    } 
    /* right is final position for the pivot */ 
    a[low] = a[right]; 
    a[right] = pivot_item; 
    return right; 
    }

希望這有助於！

來源

2014-11-01 00:39:04 Blackhat002

感謝您的回答，但這不是我應該這樣做的。快速排序函數必須帶一個指向數組的第一個元素和最後一個元素（排除）的指針。它明確地寫在問題中。 – user26830 2014-11-01 00:53:23

void quick_sort (int *a, int n) { 
    if (n < 2) 
     return; 
    int p = a[n/2]; 
    int *l = a; 
    int *r = a + n - 1; 
    while (l <= r) { 
     if (*l < p) { 
      l++; 
     } 
     else if (*r > p) { 
      r--; 
     } 
     else { 
      int t = *l; 
      *l = *r; 
      *r = t; 
      l++; 
      r--; 
     } 
    } 
    quick_sort(a, r - a + 1); 
    quick_sort(l, a + n - l); 
} 

int main() { 
    int a[] = {4, 65, 2, -31, 0, 99, 2, 83, 782, 1}; 
    int n = sizeof a/sizeof a[0]; 
    quick_sort(a, n); 
    printf("%d", a[]); 
    return 0; 
} 


// [1]: https://www.cse.ust.hk/~dekai/271/notes/L01a/quickSort.pdf 
// [2]: http://www.cprogramming.com/tutorial/computersciencetheory/quicksort.html 
// [3]: http://rosettacode.org/wiki/Sorting_algorithms/Quicksort

來源

2014-11-03 06:59:06

用指針快速排序

回答

相關問題