快速排序，不知道哪里有问题，请高手指点！！！！！ - 编程论坛

#2

寒风中的细雨2010-11-18 22:18

原始的问题是数组越界  和代码copy遗漏
//.cpp文件
#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>

#define OK 1
#define NULL 0
#define LIST_INTT_SIZE 100000
#define LISTINCREMENT 10
#define OVERFLOW 0

typedef int Status;
typedef int ElemType;
typedef struct
{
    ElemType *elem;
    int Length;
    int MaxSize;
}SqList;

Status InitList_Sq(SqList &L)
{
    L.elem=(ElemType*)malloc(1000*sizeof(ElemType));
    if(!L.elem)
        exit(OVERFLOW);
    L.Length=0;
    L.MaxSize = LIST_INTT_SIZE;
    return OK;
}

void DataIn_Sq(SqList &L)
{
    int x;
    int i;
    for(i=1;i<=5;i++)
    {
        scanf("%d",&x);
        L.elem[i-1]=x;
        L.Length++;
    }
}

void DataOut_Sq(SqList &L)
{
    int i;
    for(i=0;i<L.Length;i++)
        printf("%d ",L.elem[i]);
    printf("\n");
}

Status Partition(SqList &L, int low, int high)
{
    int temp;
    int pivotkey;
    pivotkey = L.elem[low];
    while(low<high)
    {
        while(low<high && L.elem[high]>=pivotkey)
            --high;
        temp=L.elem[low];
        L.elem[low]=L.elem[high];
        L.elem[high]=temp;
        while(low<high && L.elem[low]<=pivotkey)
            ++low;
        temp=L.elem[low];
        L.elem[low]=L.elem[high];
        L.elem[high]=temp;
    }
    return low;
}

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

void DestroyList(SqList &L)
{
   free(L.elem);
   L.elem = NULL;
   L.Length = 0;
   L.MaxSize = 0;
}

void main()
{
    SqList MyList;
    InitList_Sq(MyList);
    DataIn_Sq(MyList);
    DataOut_Sq(MyList);
    QuickSort(MyList,0,MyList.Length-1);
    DataOut_Sq(MyList);
    DestroyList(MyList);
}

#3

ice_callous2010-11-18 22:26

回复 2楼寒风中的细雨

多谢指点

#4

寒风中的细雨2010-11-19 12:20

#include <stdio.h>

int a[] = {0, 49, 78, 12, 13, 90, 21, 56, 23, 9, 10 };/*零下标作为哨兵*/

int partion( int low, int high )
{
    a[0] = a[low];
    while( low < high )
    {
        while( low<high && a[0]<=a[high] )
            --high;
        a[low] = a[high];
        while( low<high && a[0]>=a[low] )
            ++low;
        a[high] = a[low];
    }
    a[low] = a[0];
    return low;
}
void sort(int low, int high)
{
    int i;
    if( low < high )
    {
        i = partion(low, high);
        sort(low, i-1);
        sort(i+1, high);
    }
}

void show()
{
    for( int i=1; i<=10 ; ++i )
        printf(" %d", a[i]);
}

int main()
{
    sort(1, 10);
    show();
    printf("\n");
    return 0;
}

#5

h23637522802012-12-24 13:43

#include <stdio.h>
#define MAX 99900
#include <time.h>

void creat1(int *p,int n)  //随机生成
{ int temp,i;   //定义两个整型变量
  srand((unsigned)time(NULL));
   for(i=0;i<n;i++)          //用随机函数生成一个顺序表
     {    temp=(int)rand()%MAX+100;  p[i]=temp;}

}
void creat2(int *p,int n)//输出
{    int i;
    for(i=0;i<n;i++)
   printf("%d\t",p[i]);

}
int partion(int low, int high)
{int a[MAX];
    a[0] = a[low];
    while( low < high )
    {
        while( low<high && a[0]<=a[high] )
            --high;
        a[low] = a[high];
        while( low<high && a[0]>=a[low] )
            ++low;
        a[high] = a[low];
    }
    a[low] = a[0];
    return low;
}
void sort(int a[],int low, int high)
{
    int i;
    if( low < high )
    {
        i = partion(low, high);
        sort(a,low, i-1);
        sort(a,i+1, high);
    }
}

void show(int n)
{int i,a[MAX];
    for(i=1; i<=n ; ++i )
        printf(" %d", a[i]);
}

int main()                  //主函数
{
int a[MAX],n;
int i,j=0;

while(1)
{
printf("\n 1随机生成顺序表       \n");
printf(" 2输出生成元素           \n");
printf(" 3paixu          \n");

scanf("%d",&i);

while(j==0&&i<0&&i>3)           //确认数组建立与否
{
printf("数组还没有建立！请重新选择功能号：");
scanf("%d",&i);}
switch(i)                    //功能选择
{

case 1:
    printf("键盘输入元素个数n\n");
    scanf("%d",&n);
    creat1(a,n);
    printf("随机生成数组元素成功！！\n\n");
    break;

case 2: creat2(a,n);break;

case 3: sort(a,1,n);
    show(n);
      break;


}}}
可以帮忙修改一下吗，快速排序排不了，不知道为什么，急急急急急