C++ 快速排序的问题！！！！求助求助。

十二月的萧邦 · 发表于 2020-3-29 00:13:19

马上注册，结交更多好友，享用更多功能^_^

您需要登录才可以下载或查看，没有账号？立即注册

x

本帖最后由十二月的萧邦于 2020-3-30 13:13 编辑

和甲鱼哥那个快速排序好像有点区别？？？

要求用到三个函数：

void quicksort( int * const, int, int );
int partition( int * const, int, int );
void swap( int * const, int * const );

quicksort是递归函数，调用partition函数进行分区。

没太理解用三个函数这样怎么做，写了一半不会了，不知道思路对不对。
求解答。

我写的如下：

#include<iostream>
using namespace std;

void quickSort(int* const, int, int);
int partition(int* const, int, int);
void swap(int&,int&);

void quickSort(int* const a, int left, int right)
{
if (left >= right)return;
int pivot = partition(a, left, right);

quickSort(a, left, pivot - 1);
quickSort(a, pivot + 1, right);

}

int partition(int* const a, int l, int r)//对从a[l]到a[r]的数组，找到a[l]的位置，并返回l的值
{

while (l < r)
{

}

return l;
}

void swap(int &x,int &y)
{
int temp = x;
x = y;
y = temp;

}

int main()
{
int a[10] = { 6,5,8,9,10,1,4,3,2,7 };
void printarray(int[]);

cout << "Before:\n";
printarray(a);

quickSort(a, 0, 9);

cout << "\nAfter:\n";
printarray(a);

return 0;
}

void printarray(int a[])
{

for (int i = 0; i < 10; ++i)
{
cout.width(4);
cout << a[i];

}

}

十二月的萧邦 · 发表于 2020-3-29 14:24:14

顶一下

十二月的萧邦 · 发表于 2020-3-30 13:10:26

再顶一下

人造人 · 发表于 2020-3-30 16:09:53

感觉swap函数有点多余

#include <stdio.h>

int partition(int k[], int low, int high) {
    int key = k[low];
    while(low < high) {
        while(low < high && key <= k[high])
            --high;
        k[low] = k[high];
        while(low < high && key >= k[low])
            ++low;
        k[high] = k[low];
    }
    k[low] = key;
    return low;
}

void qsort(int k[], int low, int high) {
    if(low >= high) return;
    int point = partition(k, low, high);
    qsort(k, low, point - 1);
    qsort(k, point + 1, high);
}

int main(void) {
    int a[10] = {4, 2, 5, 0, 3, 9, 1, 7, 6, 8};
    qsort(a, 0, 9);
    for(int i = 0; i < 10; ++i) {
        printf("%d ", a[i]);
    }
    printf("\n");
    return 0;
}

人造人 · 发表于 2020-3-30 16:10:30

参考 https://baike.baidu.com/item/快� ... 4344&fr=aladdin

账号		自动登录	找回密码
密码			立即注册

C++ 快速排序 的问题！！！！求助求助。

马上注册，结交更多好友，享用更多功能^_^

回帖奖励 +2 鱼币

C++ 快速排序的问题！！！！求助求助。