快速排序（二）最后修改

//2012-07-16
void quickSort(element list[], int left, int right)//快速排序
{
    int i=left;
    int j=right;

    if(i >= j) //判断需要i<j
        return;

    element temp=list[i];

    while(i<j)
    {
        while(i<j && list[j]>temp)//需要i<j
            j--;

        list[i]=list[j];
        i++;

        while(i<j && list[i]<temp)//需要i<j
            i++;

        list[j]=list[i];
        j--;
    }
    
    list[j+1]=temp;// 运行到此处j j+1 i

    quickSort(list,left,j);
    quickSort(list,i,right);
}

void quickSort2(element list[], int left, int right)
{
    int i=left;
    int j=right;

    if(i>=j)
        return;

    element pivot=list[i];
    element temp;
    j++;//以下i++,j--了一次，i是需要首先+1，但j不需要，所以此处需要提前+1，抵消
    
    do{
        do{
            i++;
        }while( list[i]<pivot);//不需要i<j,便于之后的交换操作和子快速排序

        do{
            j--;
        }while(list[j]>pivot);//不需要i<j

        if(i<j)
        {
            temp=list[i];
            list[i]=list[j];
            list[j]=temp;
        }
    }while(i<j);//运行到此处，a[i]>pivot,a[j]<pivot,j=i-1;
                //一般情况结束时left...j,i...right  [j]<pivot,[i]>pivot所以交换left和j，
                //特殊情况结束时left......right，i=j=right+1//1,2,3,4,5,6,7
                //即结束时，i后的都大于pivot，j前的都小于pivot，其中[j]<pivot,[i]>pivot  
    list[left]=list[j];
    list[j]=pivot;

    quickSort(list,left,j-1);
    quickSort(list,j+1,right);
    
}

下面的是对quickSort方法的修改：

删除了quickSort的18、24行，以及27、29、30进行对应修改。修改之后使得如下代码运行到23行时，i=j，这样思维更清晰。

void quickSort3(element list[], int left, int right)//快速排序，修改时间2012-09-18 16:40:40
{
    int i=left;
    int j=right;

    if(i >= j) //判断需要i<j
        return;

    element temp=list[i];

    while(i<j)
    {
        while(i<j && list[j]>temp)//需要i<j
            j--;

        list[i]=list[j];

        while(i<j && list[i]<temp)//需要i<j
            i++;

        list[j]=list[i];
    }
    list[i]=temp;// 运行到此处i=j

    quickSort3(list,left,i-1);
    quickSort3(list,j+1,right);
}