【数据结构——内排序】快速排序（头歌实践教学平台习题）【合集】

目录😋

任务描述

测试说明

我的通关代码:

测试结果：

任务描述

本关任务：实现快速排序算法。

测试说明

平台会对你编写的代码进行测试：

测试输入示例：
10
6 8 7 9 0 1 3 2 4 5 
(说明：第一行是元素个数，第二行是待排序的原始关键字数据。）

输出示例：
排序前:6 8 7 9 0 1 3 2 4 5 
第1次划分:  5  4  2  3  0  1  6  9  7  8
第2次划分:  1  4  2  3  0  5
第3次划分:  0  1  2  3  4
第4次划分:        2  3  4
第5次划分:           3  4
第6次划分:                       8  7  9
第7次划分:                       7  8
排序后:0 1 2 3 4 5 6 7 8 9 

开始你的任务吧，祝你成功！

我的通关代码:

#include <malloc.h>
#include <stdio.h>

#define MAXL 100     //最大长度
typedef int KeyType; //定义关键字类型为int
typedef char InfoType;

typedef struct {
  KeyType key;   //关键字项
  InfoType data; //其他数据项，类型为InfoType
} RecType;       //查找元素的类型

void CreateList(RecType R[], KeyType keys[], int n) //创建顺序表
{
  for (int i = 0; i < n; i++) // R[0..n-1]存放排序记录
    R[i].key = keys[i];
}
void DispList(RecType R[], int n) //输出顺序表
{
  for (int i = 0; i < n; i++)
    printf("%d ", R[i].key);
  printf("\n");
}

//显示一趟划分后的结果
void disppart(RecType R[], int s, int t) {
  /********** Begin *********/
  for (int i = 0; i < s; i++)
    printf("    ");
  for (int i = s; i <= t; i++)
    printf("%3d ", R[i].key);
  printf("\n");
  /********** End **********/
}

//一趟划分
int partition(RecType R[], int s, int t) {
  /********** Begin *********/
  KeyType pivot = R[s].key; // 从 RecType 中提取 key 字段
  while (s < t) {
    while (s < t && R[t].key >= pivot)
      t--;
    R[s] = R[t];
    while (s < t && R[s].key <= pivot)
      s++;
    R[t] = R[s];
  }
  R[s].key = pivot; // 将 pivot 的值赋回 R[s].key
  return s;
  /********** End **********/
}

//对R[s..t]的元素进行递增快速排序
void QuickSort(RecType R[], int s, int t, int *count) {
  /********** Begin *********/
  int pivotpos;
  if (s < t) {
    (*count)++;                      // 增加划分次数
    printf("第%d次划分:", *count); // 输出划分次数提示信息

    pivotpos = partition(R, s, t);
    disppart(R, s, t);
    QuickSort(R, s, pivotpos - 1, count);
    QuickSort(R, pivotpos + 1, t, count);
  }
  /********** End **********/
}

int main() {
  /********** Begin *********/
  int n;
  scanf("%d", &n);
  KeyType keys[MAXL];
  RecType R[MAXL];
  for (int i = 0; i < n; i++)
    scanf("%d", &keys[i]);
  CreateList(R, keys, n);
  printf("排序前:");
  DispList(R, n);

  int count = 0; // 初始化划分次数
  QuickSort(R, 0, n - 1, &count);

  printf("排序后:");
  DispList(R, n);
  /********** End **********/
  return 0;
}

测试结果：