首页 > 试题广场 >

请填充下面的快速排序算法的空缺处的代码： inline vo

[问答题]

请填充下面的快速排序算法的空缺处的代码：

inline void swap(int &a, int &b) {
    int t = a; 
    a = b; 
    b = t;} int partition(int *a, int p, int r) {
    int x = a[_____];
    int i = p - 1;
    for(int j = p; j < r - 1; ++j) {
        if (a[j] <= x) {
        ___;
        swap(___,a[j]);
        }
    }
    swap(a[i+1],___);
    return ___;} void quicksort(int *a, int p, int r) {
    if (p < r - 1) {
        int q = partition(a, p, r);
        quicksort(a, p, q);
        quicksort(a, q+1, r);
    }
}
int main( ) {
    const int N = 100;
    int a[N]; // Initialized
    quicksort(a, 0, N);
    return 0; }

查看答案及解析

LaunCH_Aooooo

参考链接 https://www.cnblogs.com/banyu/p/6660276.html

int partition(int *a, int p, int r)

{
int x = a[r-1];
int i = p - 1;
for (int j = p; j < r - 1; ++j)
{
if (a[j] <= x) {
i++;
swap(a[i], a[j]);
}
}
swap(a[i + 1], a[r-1]);
return i+1;

}

其他partiton方法

int partition2(int*a, int p, int r)
{
int pivotkey = a[p];

int low = p, high = r - 1;
while (low < high)
{
while (low<high &&a[high]>=pivotkey) high--;
while (low < high && a[low] <= pivotkey) low++;

if (low < high)
swap(a[low], a[high]);
}
swap(a[p], a[high]);
return low;
}

void quicksort(int *a, int p, int r)
{
if (p < r - 1) {
int q = partition2(a, p, r);
quicksort(a, p, q);
quicksort(a, q + 1, r);
}
}

测试Main函数
int main() {
const int N = 10;
int a[N] = {10,9,8,7,6,5,4,3,2,1}; // Initialized

quicksort(a, 0, 10);

for (int i = 0; i < 10; i++)
cout << a[i] << ' ';

return 0;
}

编辑于 2019-06-10 22:31:11 回复(0)