快速排序问题

Question

这可能不是做quicksort.my的常规做法，首先尝试一下，it.the数没有按它们应有的方式排序，我尝试过对随机的numbers.However列表进行排序，即使经过严格的检查，也无法识别逻辑错误。

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int n;
int *expivot;
int *arr;
void quicksort();
void display();
int check();

main()
{
    int i;
    printf("to continue press 'a' always\n");
    while(getch()=='a')
    {
        printf("Enter the length of list\n");
        scanf("%d",&n);
        time_t start,end;
        double t;
        start=clock();
        arr=(int *)calloc(n,sizeof(int));
        expivot=(int *)calloc(n,sizeof(int));
        srand(time(NULL));
        for(i=0;i<n;i++)
            arr[i]=rand()%RAND_MAX + 1;
        printf("\nelements inputted are:");
        display();
        quicksort();
        end=clock();
        t=(double)(end-start)/CLOCKS_PER_SEC;
        printf("\n\nelements sorted are:");
        display();
        printf("\ntime take is %.15lf",t);
        free(arr);
        free(expivot);
    }
}
void quicksort()
{
    int low,high,temp;
    int pivot=rand()%n;//generate random pivot
    int store=pivot;
    /*location of pivot might change due to swapping,so using store to store pivot      location so as to add this to expivot list after running quickort once*/
    int flag=1;
    if(expivot[pivot]==1)   // checks if it's an already used pivot
        flag=0;
    if(flag==1) //if the pivot is unused
    {
        low=pivot;
        high=pivot;
        while(low>0 && expivot[low]==0)
            low--;
        if(expivot[low]==1)//i
            low++;
        /*decrements low to a location where a value has been set permanently and then    increase by 1,if nothing is set then decrements low to zero*/
        /*increments high to a location where a value has been set permanently and then decrease by 1,if nothing is set then increments high to last index*/
        while(high<n-1 && expivot[high]==0)
            high++;
        if(expivot[high]==1)
            high--;
        while(low<high)
        {
            if(arr[low]>=arr[pivot] && arr[high]<=arr[pivot])//checks swap  possibilty
            {
                if(low==pivot)   //if pivot is to be swapped store new location of pivot
                    store=high;
                else if(high==pivot)
                    store=low;
                temp=arr[low];
                arr[low]=arr[high];
                arr[high]=temp;
                low++;
                high--;
            }
            else
            {
                if(arr[low]<arr[pivot])
                    low++;
                else if(arr[high]>arr[pivot])
                    high--;
            }
        }
        expivot[store]=1;
        /*final location of pivot,stores info that this location has a permanent value now
         and cannot be used as a pivot*/
    }
    if(check()==1)
        quicksort();
}


int check() //checks if there are any unused pivots
{
    int i;
    for(i=0;i<n;i++)
    {
        if(expivot[i]==0)
            return 1;
    }
    return 0;
}

void display()
{
    int i;
    for(i=0;i<n;i++)
        printf("%d ",arr[i]);
}

Answer 1

快速排序是一种分治和征服算法。如果不使用堆栈或递归，则无法执行此操作。

编辑:函数确实使用递归(oops!)。但这不是速战速决。如果您正在更改标准排序算法的方法，则不再是该算法。