C语言中的一趟快速排序问题

发布网友发布时间：2023-05-05 08:48

共3个回答

热心网友时间：2023-11-09 04:25

第一，你main里面，把一个没有分配内容的指针L拿来直接用就错了。

第二，quicksort是分而治之，是逐层分。每次partition之后，分成两部分，一边比哨兵小，一边比哨兵大。应该对于这两部分分别继续quicksort。递归的做。你只partition了一次，所以，这一次能不能正好排对就靠运气了。

我给你改了一下，你看看对不对。

#include<stdio.h>
#define MAXSIZE 1000

typedef struct
{
int r[MAXSIZE+1];
int length;
}SqList;

void swap(SqList *L,int i,int j)
{
int temp=L->r[i];
L->r[i]=L->r[j];
L->r[j]=temp;
}

int Partition(SqList *L,int low,int high)
{
int pivotkey;
pivotkey=L->r[low];
while(low<high)
{
while(low<high&&L->r[high]>=pivotkey)
    high--;
swap(L,low,high);
while(low<high&&L->r[low]<=pivotkey)
    low++;
swap(L,low,high);
    }
return low;
}

void QuickSort(SqList *L, int low, int high){
    int key = Partition(L, low, high);
    if(key > low+1)
        QuickSort(L, low, key-1);
    if(key < high-1)
        QuickSort(L, key+1, high);
}

int main()
{
    SqList L;
    int i,j;
    int low=0,high;
    printf("请输入排序个数：");
    scanf("%d",&i);
    high=i-1;
    printf("请输入元素：");
    for(j=0;j<i;j++)
    {
    scanf("%d",&L.r[j]);
   }
    QuickSort(&L,low,high);
    for(j=0;j<i;j++)
    {
    printf("%d   ",L.r[j]);
    }

}

追问不好意思，再问一个问题
我在main里面只定义了一个SqList L，为什么int Partition(SqList *L,int low,int high)能出现SqList *L呢？？L又不是指针,加不加*为什么有区别呢

追答在main里面，我改过之后，是通过QuickSort(&L,low,high)调用，&L就是求地址，即指针。
Partition和QuickSort都是使用指针传参，按址传递。

热心网友时间：2023-11-09 04:25

SqList *L;//这里只是一个指针，没有保存元素的内存空间，只要运行都会出错的。

热心网友时间：2023-11-09 04:26

#include<stdio.h>
#define MAXSIZE 1000
typedef struct{
int r[MAXSIZE+1];
int length;
}SqList;
void swap(SqList *L,int i,int j){
int temp=L->r[i];
L->r[i]=L->r[j];
L->r[j]=temp;
}
void Partition(SqList *L,int low,int high){
int pivotkey;
int l=low,h=high;
if(low<high){
pivotkey=L->r[low];
while(low<high){
while(low<high&&L->r[high]>=pivotkey)
high--;
swap(L,low,high);
while(low<high&&L->r[low]<=pivotkey)
low++;
swap(L,low,high);
}
Partition(L,l,low-1);
Partition(L,low+1,h);
}
}
int main(){
SqList L;
int i,j;
int low=0,high;
printf("请输入排序个数：");
scanf("%d",&i);
high=i-1;
printf("请输入元素：");
for(j=0;j<i;j++){
scanf("%d",&L.r[j]);
}
Partition(&L,low,high);
for(j=0;j<i;j++){
printf("%d ",L.r[j]);
}
}

热心网友时间：2023-11-09 04:25

第一，你main里面，把一个没有分配内容的指针L拿来直接用就错了。

我给你改了一下，你看看对不对。

追答在main里面，我改过之后，是通过QuickSort(&L,low,high)调用，&L就是求地址，即指针。
Partition和QuickSort都是使用指针传参，按址传递。

热心网友时间：2023-11-09 04:25

SqList *L;//这里只是一个指针，没有保存元素的内存空间，只要运行都会出错的。

热心网友时间：2023-11-09 04:26

#include<stdio.h>
#define MAXSIZE 1000
typedef struct{
int r[MAXSIZE+1];
int length;
}SqList;
void swap(SqList *L,int i,int j){
int temp=L->r[i];
L->r[i]=L->r[j];
L->r[j]=temp;
}
void Partition(SqList *L,int low,int high){
int pivotkey;
int l=low,h=high;
if(low<high){
pivotkey=L->r[low];
while(low<high){
while(low<high&&L->r[high]>=pivotkey)
high--;
swap(L,low,high);
while(low<high&&L->r[low]<=pivotkey)
low++;
swap(L,low,high);
}
Partition(L,l,low-1);
Partition(L,low+1,h);
}
}
int main(){
SqList L;
int i,j;
int low=0,high;
printf("请输入排序个数：");
scanf("%d",&i);
high=i-1;
printf("请输入元素：");
for(j=0;j<i;j++){
scanf("%d",&L.r[j]);
}
Partition(&L,low,high);
for(j=0;j<i;j++){
printf("%d ",L.r[j]);
}
}