问题描述

为什么这个快速排序总是不行

 #include<stdio.h>
int FindPos(int *a,int low,int high);
void QuickSort(int *a,int low,int high);
int main()
{
    int a[6]={2,1,0,5,4,3};
    int i;
    QuickSort(a,0,5);//0为将要排序元素的第一个下标，5为想要排序的第六个元素的下标
    for(i=0;i<6;i++)
    {
        printf("%d ",a[i]);
    }
    return 0;
}
void QuickSort(int *a,int low,int high)
{
    int pos=FindPos(a,low,high);
    pos=FindPos(a,low,high);
    if(low<high)
    {
        QuickSort(a,low,pos-1);
        QuickSort(a,pos+1,high);
    }

}
int FindPos(int *a,int low,int high)
{
    int val=a[low];
    while(low!=high)
    {
        while(low<high&&a[high]>=val)
            --high;
        a[low]=a[high];
        while(low<high&&a[low]<=val)
            ++low;
        a[high]=a[low];
    }
    a[low]=val;
    return high;
}

总是不行，也没报错

解决方案

分区函数有问题，程序死循环了。

解决方案二：

 // app1.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"

#include<stdio.h>

int FindPos(int *a,int low,int high);
void QuickSort(int *a,int low,int high);
int main()
{
    int a[6]={2,1,0,5,4,3};
    int i;
    QuickSort(a,0,5);//0为将要排序元素的第一个下标，5为想要排序的第六个元素的下标
    for(i=0;i<6;i++)
    {
        printf("%d ",a[i]);
    }
    return 0;
}
void swap(int *x,int *y)
{
   int temp;
   temp = *x;
   *x = *y;
   *y = temp;
}
void QuickSort(int *list,int m,int n)
{
   int key,i,j,k;
   if( m < n)
   {
      k = (m+n) /2;
      swap(&list[m],&list[k]);
      key = list[m];
      i = m+1;
      j = n;
      while(i <= j)
      {
         while((i <= n) && (list[i] <= key))
                i++;
         while((j >= m) && (list[j] > key))
                j--;
         if( i < j)
                swap(&list[i],&list[j]);
      }
      swap(&list[m],&list[j]);
      QuickSort(list,m,j-1);
      QuickSort(list,j+1,n);
    }
}

解决方案三：

你程序问题太多，连交换都没有，怎么排序。给你重写了一个，自己看

解决方案四：

这是我java写的http://blog.csdn.net/strutce/article/details/47784735

  a[low]=val;
    return high;
  在这里应该还有开始标志位数值与low的最后一位的交换****

解决方案五：

 void QuickSort(int *a,int low,int high)
{
    int pos=FindPos(a,low,high);
    // pos=FindPos(a,low,high);这里不知道你为什么调用两次
    if(low<high)
    {
        QuickSort(a,low,pos-1);
        QuickSort(a,pos+1,high);
    }

}
int FindPos(int *a,int low,int high)
{
    int val=a[low];
    while(low < high)//这里不能使！=，因为low和high不一定最后正好相等，所以会导致死循环
    {
        while(low<high&&a[high]>val)
            --high;
        a[low]=a[high];
        while(low<high&&a[low]<val)
            ++low;
        a[high]=a[low];
    }
    a[low]=val;
    return low;
}