ch7_4.c

本内容为清华大学严蔚敏版数据结构部分算法实现代码

#include<stdio.h>
#include<stdlib.h>
void quick(int, int *);
void q_sort(int *, int, int);
void ShowData(int, int *);
void main( )
{                                                   
  int Data[11]={ 10, 26, 5, 37, 1, 61, 11, 59, 15, 48, 19 };  /* 原始数据 */   
   /* 第一条数据Data[0]表示数据的个数 */  
  printf("原始数据: ");
  ShowData(Data[0], Data);     /* 把原始数据输出来 */
  quick(Data[0], Data);         /* 调用快速排序法，有10条数据 */
  printf("\n");
  printf("排序结果: ");
  ShowData(Data[0], Data);      /* 把排序后的数据输出来 */
}

void quick(int n, int *data)
{
  q_sort(data, 1, n);
}

void q_sort(int *data, int m, int n)
{
  int k;                 /* 分割元素 */
  int temp;
  int i, j;
  if(m < n)          /* 是否继续分割 */
  {
    i=m;              /* 分割的最左 */
    j=n+1;            /* 分割的最右 */
    k=data[m];       /* 取第一个元素 */
    do 
    {
      do
      {               /* 由左往右找 */
        i++;
      }while(data[i] < k);
      do 
      {               /* 由右往左找 */
        j--;
      }while(data[j] > k);
      if (i < j)
      {
        temp=data[i];     /* 交换数据 */
        data[i]=data[j];
        data[j]=temp;
     }
    }while(i < j);
    temp=data[m];        /* 交换数据 */
    data[m]=data[j];
    data[j]=temp;
    printf("过程输出: ");
    for (i=m; i<=n; i++)         /* 输出过程 */
      printf("%3d", data[i]);
    printf("\n");
    q_sort(data, m, j-1);     /* 快速排序递归调用 */
    q_sort(data, j+1, n);     /* 快速排序递归调用 */
  }
}

void ShowData(int n, int *Data)
{
  int i;
  for(i=1; i<=n; i++)
  {
    printf("%3d", Data[i]);
  }
  printf("\n");
}