论坛 › C\C++交流 › C++ 快速排序 的问题！！！！求助求助。

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

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

本帖最后由 十二月的萧邦 于 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到a的数组，找到a的位置，并返回l的值
{

        while (l < r)
        {


               
        }

        return l;
}



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

}
       


int main()
{
        int a = { 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;

        }

}

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

顶一下{:10_257:}

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

再顶一下{:10_285:}

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

感觉swap函数有点多余

#include <stdio.h>

int partition(int k[], int low, int high) {
    int key = k;
    while(low < high) {
      while(low < high && key <= k)
            --high;
      k = k;
      while(low < high && key >= k)
            ++low;
      k = k;
    }
    k = 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 = {4, 2, 5, 0, 3, 9, 1, 7, 6, 8};
    qsort(a, 0, 9);
    for(int i = 0; i < 10; ++i) {
      printf("%d ", a);
    }
    printf("\n");
    return 0;
}

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

参考 https://baike.baidu.com/item/快速排序算法/369842?fromtitle=快速排序&fromid=2084344&fr=aladdin

查看完整版本: C++ 快速排序 的问题！！！！求助求助。