C ++快速排序算法 [英] C++ quick sort algorithm

问题描述

我不打算复制qsort算法。我正在练习写qsort，这是我想出来的，我对我的代码的哪部分错了感兴趣。请不要告诉我这是家庭作业，因为我可以只使用下面的链接中的代码。

I'm not looking to copy a qsort algorithm. I'm practicing writing qsort and this is what I've come up with and I'm interested in what part of my code is wrong. Please don't tell me that this is homework cause I could just use the code in the link below.

参考： http：// xoax.net/comp/sci/algorithms/Lesson4.php

运行时，我在控制台中看到：

When this runs I get this in the console:

Program loaded.
run
[Switching to process 10738]
Running…
Current language:  auto; currently c++
Program received signal:  "EXC_ARITHMETIC".


void myQSort(int min, int max, int* myArray)
    {
        // Initially find a random pivot
        int pivotIndex = rand() % max;
            int pivot = myArray[pivotIndex];

        int i = 0 , j = max-1;

        // Pointer to begining of array and one to the end

        int* begin = myArray;
        int* end = &myArray[max-1];

        // While begin < end 
        while( begin < end )
        {
        // Find the lowest bound number to swap
            while( *begin < pivot )
            {
                begin++;
            }
            while( *end > pivot ) 
            {
                // Find the highest bound number to swap
                end--;
            }

        // Do the swap
            swap(begin,end);
        }
        // Partition left
        myQSort(0, pivotIndex-1, myArray);
        // Partiion right
        myQSort(pivotIndex+1,max, myArray);

    }

EDIT--
Swap代码： / p>

EDIT-- Code for Swap:

void swap(int* num, int* num2)
{
    int temp = *num;
    *num = *num2;
    *num2 = temp;
}

推荐答案

// sort interval [begin, end)
void myQSort(int* begin, int* end)
{
    if(end - begin < 2)
        return;
    int* l = begin;
    int* r = end - 1;

    // Initially find a random pivot
    int* pivot = l + rand() % (r - l + 1);
    while(l != r)
    {
        // Find the lowest bound number to swap
        while(*l < *pivot) ++l;
        while(*r >= *pivot && l < r) --r;

        // Do the swap
        if(pivot == l) { pivot = r; }
        std::swap(*l, *r);
    }

    // Here l == r and numbers in the interval [begin, r) are lower and in the interval [l, end) are greater or equal than the pivot
    // Move pivot to the position
    std::swap(*pivot, *l);

    // Sort left
    myQSort(begin, l);
    // Sort right
    myQSort(l + 1, end);
}

这篇关于C ++快速排序算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！