#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");
}
问题的原因出在这段上：
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都可
不知道你这个问题是否已经解决, 如果还没有解决的话: