排序系统中使用快速排序时数组有重复数字无法排序 各位大佬帮忙改一下

Question

#include<stdio.h>
#define LENGTH 5
int A[LENGTH];
void bubbleSort();
void quickSort();
void insertSort();
void shellSort();
void main()
{
    int choice,i,j,k=1;
    int O[LENGTH];//保存原始数据的数组
    printf("请输入%d个待排序的整数:",LENGTH);
    for(i=0;i<LENGTH;i++)
    {
        scanf("%d",&O[i]);
    }
    printf("排序数据输入成功。\n");
    while(k)
    {
        printf("\t\t   排序子系统\t\t\n");
        printf("*************************************************\n");
        printf("*\t\t1......起泡排序\t\t\t*\n");
        printf("*\t\t2......快速排序\t\t\t*\n");
        printf("*\t\t3......直接插入排序\t\t*\n");
        printf("*\t\t4......希尔排序\t\t\t*\n");
        printf("*\t\t0......返回\t\t\t*\n");
        printf("*************************************************\n");
        printf("请选择菜单号(0---4):");
        scanf("%d",&choice);//输入菜单号进行排序算法选择

        for(j=0;j<LENGTH;j++)//将原始数组的数据赋值到待排序数组
        {
            A[j]=O[j];
        }
        switch(choice)//选择分支  选择排序算法
        {
        case 1:
            bubbleSort();
            break;
        case 2:
            printf("原始数据为：\n");
            for(i=0;i<LENGTH;i++)
            {
                printf("%5d",A[i]);
            }
            printf("\n");

            quickSort(0,LENGTH-1);

            printf("排序后结果为：\n");
            for(i=0;i<LENGTH;i++)
            {
                printf("%5d",A[i]);
            }
            printf("\n");
            break;
        case 3:
            insertSort();
            break;
        case 4:
            shellSort();
            break;
        case 0:
            k=0;
            break;
        default:
            printf("\n输入错误，请重新输入。\n");
            getchar();
            k=1;
            break;
        }
    }
}
void bubbleSort()//冒泡排序
{
    int i,j,k;
    printf("原始数据为：\n");
    for(i=0;i<LENGTH;i++)
    {
        printf("%5d",A[i]);
    }
    printf("\n");

    for(i=0;i<LENGTH;i++)
    {
        for(j=0;j<LENGTH-1;j++)
        {
            if(A[j]>A[j+1])
            {
                k=A[j];
                A[j]=A[j+1];
                A[j+1]=k;
            }
        }
    }
    printf("排序后结果为：\n");
    for(i=0;i<LENGTH;i++)
    {
        printf("%5d",A[i]);
    }
    printf("\n");
}
void quickSort(int low,int high)//快速排序
{
    int first=low;
    int last=high;
    int key=A[first];
    if(low>=high)
        return;
    while(first<last)
    {
        while(first<last&&A[last]>key)
        {
            last--;
        }
        A[first]=A[last];

        while(first<last&&A[first]<key)
        {
            first++;
        }
        A[last]=A[first];
    }
    A[first]=key;

    quickSort(low,first-1);
    quickSort(first+1,high);

}
void insertSort()//插入排序
{
    int i,j,k;
    printf("原始数据为：\n");
    for(i=0;i<LENGTH;i++)
    {
        printf("%5d",A[i]);
    }
    printf("\n");

    for(i=1;i<LENGTH;i++)
    {
        k=A[i];
        for(j=i-1;j>=0&&A[j]>k;j--)
        {
            A[j+1]=A[j];
        }
        A[j+1]=k;
    }

    printf("排序后结果为：\n");
    for(i=0;i<LENGTH;i++)
    {
        printf("%5d",A[i]);
    }
    printf("\n");
}
void shellSort()//希尔排序
{
    int i,j,k,gap,tmp;
    printf("原始数据为：\n");
    for(i=0;i<LENGTH;i++)
    {
        printf("%5d",A[i]);
    }
    printf("\n");

    for(gap=LENGTH/2;gap>0;gap/=2)// 步长初始化为数组长度的一半
    {
        for (i=0;i<gap;++i)// 变量 i 为每次分组的第一个元素下标
        {
            for (j=i+gap;j<LENGTH;j+=gap)//对步长为gap的元素进行直插排序，当gap为1时，就是直插排序
            {
	            tmp=A[j];  // 备份A[j]的值
	            k=j-gap;  // j初始化为i的前一个元素（与i相差gap长度）
	            while(k>=0&&A[k]>tmp)
	            {
	                A[k+gap]=A[k]; // 将在A[i]前且比tmp的值大的元素向后移动一位
	                k-=gap;
	            }
	            A[k+gap]=tmp;
	        }
	    }
    }

    printf("排序后结果为：\n");
    for(i=0;i<LENGTH;i++)
    {
        printf("%5d",A[i]);
    }
    printf("\n");
}

Answer 1

问题的原因出在这段上：

    while (first < last) {
        while (first < last && A[last] > key) {
            last--;
        }
        A[first] = A[last];
        while (first < last && A[first] < key) {
            first++;
        }
        A[last] = A[first];
    }

如果A[last]恰好等于key,就会导致变成一个死循环。

解决办法很简单，上面的判定或者下面的判定加个等号，不管是A[last] >= key还是用A[first] <= key都可