[数据结构与算法]实验题8.4 实现快速排序算法

?【实验目的】

（1）掌握排序的相关概念；

（2）熟练掌握快速排序的原理及实现方法。

【实验准备】

（1）阅读教材中快速排序算法的相关内容；

（2）熟悉快速排序算法。

【实验要求】

（1）采用函数调用的方式完成；

（2）文件funp8-4.cpp的作用是快速排序的相关运算操作；

（3）实验提交必须有完整正确的程序以及程序运行结果的截图。

【实验内容】

编写一个程序使用快速排序法对以下数据

{7，4，9，2，5，1，3，6，0，8}进行排序并输出结果；

再随机输入一组整数，进行排序并输出结果。

#include <stdio.h>

#define MAX_LEN     (100)                       //  最大长度

typedef int key_type;                           //  定义关键字类型为int
typedef char info_type;
typedef struct
{
    key_type key;                               //  关键字项
    info_type data;                             //  其他数据项,类型为info_type
}rec_type;                                      //  查找元素的类型


void swap_rec(rec_type &x, rec_type &y)         //  引用类型
{
    rec_type tmp = x;
    x = y;
    y = tmp;
}


void create_list(rec_type recs[], key_type keys[], int n)
{
    int i;

    for(i = 0; i < n; i++)                      // recs[0...n-1]存放排序记录
        recs[i].key = keys[i];
}


void disp_list(rec_type recs[], int n)
{
    int i;

    for(i = 0; i < n; i++)
        printf("%d ", recs[i].key);

    printf("\n");
}


void create_list1(rec_type recs[], key_type keys[], int n)
{
    int i;

    for(i = 1; i <= n; i++)                     // recs[1...n]存放排序记录
    {
        recs[i].key = keys[i - 1];
    }
}


void disp_list1(rec_type recs[], int n)
{
    int i;

    for(i = 1; i <= n; i++)
    {
        printf("%d ", recs[i].key);
    }
    printf("\n");
}


static void disp_partition(rec_type recs[], int s, int t)
{
    static int i = 1;                               // 局部静态变量仅被初始化一次
    int j;

    printf("第%d次划分:", i);
    for(j = 0; j < s; j++)
        printf("   ");
    for(j = s; j <= t; j++)
        printf("%3d", recs[j].key);
    printf("\n");
    i++;
}


static int partition_recs(rec_type recs[], int s, int t)
{
    int i = s, j = t;
    rec_type tmp = recs[i];                         //  以recs[i]为基准 [6, 8, 7, 9, 0, 1, 3, 2, 4, 5]

    while(i < j)                                    //  从两端交替向中间扫描,直至i=j为止
    {
        while(i < j && recs[j].key >= tmp.key)
            j--;                                    //  从右向左扫描,找一个小于tmp.key的recs[j]
        recs[i] = recs[j];                          //  找到这样的recs[j],放入recs[i]处
        while(i < j && recs[i].key <= tmp.key)
            i++;                                    //  从左向右扫描,找一个大于tmp.key的recs[i]
        recs[j] = recs[i];                          //  找到这样的recs[i],放入recs[j]处
    }
    recs[i] = tmp;
    disp_partition(recs, s, t);

    return i;
}


static void quick_sort(rec_type recs[], int s, int t)
{
    int i;

    if(s < t)                                       //  区间内至少存在两个元素的情况
    {
        i = partition_recs(recs, s, t);
        quick_sort(recs, s, i - 1);                 //  对左区间递归排序
        quick_sort(recs, i + 1, t);                 //  对右区间递归排序
    }
}

int main(int argc, char *argv[])
{
    int n = 10;
    rec_type recs[MAX_LEN];
    key_type a[] = {7,4,9,2,5,1,3,6,0,8};

    create_list(recs, a, n);
    printf("排序前: ");
    disp_list(recs, n);
    quick_sort(recs, 0, n - 1);// 0 9
    printf("排序后: ");
    disp_list(recs, n);

    return 0;
}