快排解决思路

快排
#include <iostream>
int Partition(int array[],int low,int high)
{
int temp=array[0];
int pivot=array[0];
while(low<high)
{
if(low<high && pivot<=array[high])
--high;
array[low]=array[high];
if(low<high && array[low]<=pivot)
++low;
array[high]=array[low];
}
array[low]=temp;
return low;
}
void QuickSort(int array[],int low,int high)
{
int pivot=0;
if(low<high)
{
pivot=Partition(array,low,high);
QuickSort(array,low,pivot-1);
QuickSort(array,pivot+1,high);
}
}
int main()
{
int i;
int a[]={49,38,65,97,76,13,27};
QuickSort(a,0,6);
for(i=0;i<7;i++)
{
printf("%d,",a[i]);
}
system("pause");
}
哪位大虾能告诉我一下，为什么我这个快排的结果不对呢？

------解决方案--------------------
你的Partition函数有问题吧，下面是我改的，才疏学浅如有错误请见谅。

int Partition( int array[],int low,int high )
{
int temp = array[high] ;
while( low<high ){
while( low<high && array[low]<=temp )
low++;
if( low<high )
{
array[high] = array[low] ;
high-- ;
}
while( low<high && array[high]>=temp )
high-- ;
if( low<high )
{
array[low] = array[high] ;
low++ ;
}
}
array[low] = temp ;
return low ;
}
------解决方案--------------------
你这里的错误有两个，是在Partition函数中。
首先是pivot这个区分值的问题，注释中有说明明。
另一个就是在与区分值进行比较时应该当是循环进行的。你使用的是if，你可以自己手工实现一下这个排序，你可以发现为什么要用while而不是if。

顺便，你是使用C++来写代码的。可是，你使用C++写出了C的代码。。。这个是很不幸的。
因为C++中的面向对象思想完全没有体现。
并且，你使用了<iostream>标准头文件，但却中代码中使用了printf这种。。。。
建议要再了解一下C++相关概念。

然后，看在打了这么多字的面子上，给个分呗~~~

C/C++ code


#include <iostream>

using namespace std;

int Partition(int array[], int low, int high)
{
    int pivot = array[low];    // 这里，你是让pivot每次都等于array[0]，这导致后半段的快排出错
    // pivot应该就是区分值，你这里选择的区分值是每段序列的第一个数字。
    // 所以每段序列的第一个数字应该就是array[low]

    while(low < high)
    {
        while(low < high && pivot <= array[high]) // 这里你的程序中是if。
            --high;
        array[low]=array[high];

        while(low < high && array[low] <= pivot)
            ++low;
        array[high]=array[low];
    }
    array[low]=pivot;

    return low;
}

void QuickSort(int array[], int low, int high)
{
    int pivot=0;
    
    if(low < high)
    {
        pivot = Partition(array, low, high);

        QuickSort(array, low, pivot-1);
        QuickSort(array, pivot+1, high);
    }
}

int main(void)
{
    int i;
    int a[]={49, 38, 65, 97, 76, 13, 27};

    QuickSort(a, 0, 6);
    
    printf("结果为：\n");
    for(i=0; i<7; i++)
    {
        printf("%d ", a[i]);
    }
    system("pause");
}

快排解决思路

相关推荐