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

问题描述

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

参考： http://xoax.net/comp/sci/algorithms/Lesson4。 PHP

在此运行我得到这个在控制台：

 程序加载。
跑
[切换到处理10738]
正在运行...
当前语言：汽车;目前C ++
程序接收到的信号：EXC_ARITHMETIC。


无效myQSort（INT分钟，INT最大，为int * myArray的）
    {
        //首先找到一个随机的支点
        INT pivotIndex =兰特（）％以下;
            INT支点= myArray的[pivotIndex]

        INT I = 0，J =最大-1;

        //指针数组的起始和一个结束

        INT *开始= myArray的;
        INT *结束=＆放大器; myArray的[MAX-1];

        //虽然开始＆LT;结束
        同时（开始与LT端）
        {
        //找到最低数量的约束来交换
            而（*开始＆LT;枢）
            {
                开始++;
            }
            而（*结束＆GT;枢）
            {
                //找到最高势必数交换
                结束 - ;
            }

        //做交换
            掉期（开始，结束）;
        }
        //分区左
        myQSort（0，pivotIndex-1，myArray的）;
        // Partiion权
        myQSort（pivotIndex + 1，最多，myArray的）;

    }
 

EDIT-- $ C $下交换：

 无效掉期（INT * NUM，为int * NUM2）
{
    INT TEMP = * NUM;
    * NUM = * NUM2;
    * NUM2 =温度;
}
 

解决方案

  //排序区间开始，结束）
无效myQSort（INT *开始，为int *完）
{
    如果（结束 - 开始2）
        返回;
    INT * L =开始;
    INT * R =结束 -  1;

    //首先找到一个随机的支点
    INT *支点= L +兰特（）％（R  -  L + 1）;
    而（L！= R）
    {
        //找到最低数量的约束来交换
        而（* L＆LT; *支点）++升;
        而（* R＆GT; = *枢纽和放大器;＆安培; L＆LT; R）--r;

        //做交换
        如果（支点== L）{支点= R; }
        的std ::交换（* L，* R）;
    }

    //这里升== r和号码在区间[开始，r）的较低，在区间[升，端）比枢轴大于或等于
    //将枢轴到位置
    的std ::交换（*支点，* L）;

    //按行排序
    myQSort（开始，L）;
    //排序权
    myQSort（L + 1，结束）;
}
 

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.

Reference: 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-- 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屋！