数据结构例程—— 交换排序之快速排序

简介: 本文是[数据结构基础系列(9):排序]中第5课时[ 交换排序之快速排序]的例程。1.以第1个元素作为基准#include <stdio.h>#define MaxSize 20typedef int KeyType; //定义关键字类型typedef char InfoType[10];typedef struct //记录

本文是[数据结构基础系列(9):排序]中第5课时[ 交换排序之快速排序]的例程。

1.以第1个元素作为基准

#include <stdio.h>
#define MaxSize 20
typedef int KeyType;    //定义关键字类型
typedef char InfoType[10];
typedef struct          //记录类型
{
    KeyType key;        //关键字项
    InfoType data;      //其他数据项,类型为InfoType
} RecType;              //排序的记录类型定义
void QuickSort(RecType R[],int s,int t) //对R[s]至R[t]的元素进行快速排序
{
    int i=s,j=t;
    RecType tmp;
    if (s<t)                //区间内至少存在两个元素的情况
    {
        tmp=R[s];           //用区间的第1个记录作为基准
        while (i!=j)        //从区间两端交替向中间扫描,直至i=j为止
        {
            while (j>i && R[j].key>=tmp.key)
                j--;        //从右向左扫描,找第1个小于tmp.key的R[j]
            R[i]=R[j];      //找到这样的R[j],R[i]"R[j]交换
            while (i<j && R[i].key<=tmp.key)
                i++;        //从左向右扫描,找第1个大于tmp.key的记录R[i]
            R[j]=R[i];      //找到这样的R[i],R[i]"R[j]交换
        }
        R[i]=tmp;
        QuickSort(R,s,i-1);     //对左区间递归排序
        QuickSort(R,i+1,t);     //对右区间递归排序
    }
}
int main()
{
    int i,n=10;
    RecType R[MaxSize];
    KeyType a[]= {6,8,7,9,0,1,3,2,4,5};
    for (i=0; i<n; i++)
        R[i].key=a[i];
    printf("排序前:");
    for (i=0; i<n; i++)
        printf("%d ",R[i].key);
    printf("\n");
    QuickSort(R,0,n-1);
    printf("排序后:");
    for (i=0; i<n; i++)
        printf("%d ",R[i].key);
    printf("\n");
    return 0;
}
AI 代码解读

2.以中间位置的元素作为基准

#include <stdio.h>
#define MaxSize 20
typedef int KeyType;    //定义关键字类型
typedef char InfoType[10];
typedef struct          //记录类型
{
    KeyType key;        //关键字项
    InfoType data;      //其他数据项,类型为InfoType
} RecType;              //排序的记录类型定义
void QuickSort1(RecType R[],int s,int t) //对R[s]至R[t]的元素进行快速排序
{
    int i=s,j=t;
    KeyType pivot;
    RecType tmp;
    pivot = R[(s+t)/2].key; //用区间的中间位置的元素作为关键字
    if (s<t)                //区间内至少存在两个元素的情况
    {
        while (i!=j)        //从区间两端交替向中间扫描,直至i=j为止
        {
            while (j>i && R[j].key>pivot)
                j--;        //从右向左扫描,找第1个小于基准的R[j]
            while (i<j && R[i].key<pivot)
                i++;        //从左向右扫描,找第1个大于基准记录R[i]
            if(i<j)        //将前后的两个失序元素进行交换
            {
                tmp=R[i];
                R[i]=R[j];
                R[j]=tmp;
            }
        }
        QuickSort1(R,s,i-1);        //对左区间递归排序
        QuickSort1(R,j+1,t);        //对右区间递归排序
    }
}
int main()
{
    int i,n=10;
    RecType R[MaxSize];
    KeyType a[]= {6,8,7,9,0,1,3,2,4,5};
    for (i=0; i<n; i++)
        R[i].key=a[i];
    printf("排序前:");
    for (i=0; i<n; i++)
        printf("%d ",R[i].key);
    printf("\n");
    QuickSort1(R,0,n-1);
    printf("排序后:");
    for (i=0; i<n; i++)
        printf("%d ",R[i].key);
    printf("\n");
    return 0;
}
AI 代码解读
目录
打赏
0
0
0
0
67
分享
相关文章
C 408—《数据结构》图、查找、排序专题考点(含解析)
408考研——《数据结构》图,查找和排序专题考点选择题汇总(含解析)。
122 29
【C++数据结构——内排序】二路归并排序(头歌实践教学平台习题)【合集】
本关任务是实现二路归并算法,即将两个有序数组合并为一个有序数组。主要内容包括: - **任务描述**:实现二路归并算法。 - **相关知识**: - 二路归并算法的基本概念。 - 算法步骤:通过比较两个有序数组的元素,依次将较小的元素放入新数组中。 - 代码示例(以 C++ 为例)。 - 时间复杂度为 O(m+n),空间复杂度为 O(m+n)。 - **测试说明**:平台会对你编写的代码进行测试,提供输入和输出示例。 - **通关代码**:提供了完整的 C++ 实现代码。 - **测试结果**:展示代码运行后的排序结果。 开始你的任务吧,祝你成功!
105 10
【C++数据结构——内排序】希尔排序(头歌实践教学平台习题)【合集】
本文介绍了希尔排序算法的实现及相关知识。主要内容包括: - **任务描述**:实现希尔排序算法。 - **相关知识**: - 排序算法基础概念,如稳定性。 - 插入排序的基本思想和步骤。 - 间隔序列(增量序列)的概念及其在希尔排序中的应用。 - 算法的时间复杂度和空间复杂度分析。 - 代码实现技巧,如循环嵌套和索引计算。 - **测试说明**:提供了测试输入和输出示例,帮助验证代码正确性。 - **我的通关代码**:给出了完整的C++代码实现。 - **测试结果**:展示了代码运行的测试结果。 通过这些内容,读者可以全面了解希尔排序的原理和实现方法。
93 10
|
3月前
|
【C++数据结构——内排序】快速排序(头歌实践教学平台习题)【合集】
快速排序是一种高效的排序算法,基于分治策略。它的主要思想是通过选择一个基准元素(pivot),将数组划分成两部分。一部分的元素都小于等于基准元素,另一部分的元素都大于等于基准元素。然后对这两部分分别进行排序,最终使整个数组有序。(第一行是元素个数,第二行是待排序的原始关键字数据。本关任务:实现快速排序算法。开始你的任务吧,祝你成功!
81 7
数据结构与算法学习十二:希尔排序、快速排序(递归、好理解)、归并排序(递归、难理解)
这篇文章介绍了希尔排序、快速排序和归并排序三种排序算法的基本概念、实现思路、代码实现及其测试结果。
134 1
数据结构与算法学习十三:基数排序,以空间换时间的稳定式排序,速度很快。
基数排序是一种稳定的排序算法,通过将数字按位数切割并分配到不同的桶中,以空间换时间的方式实现快速排序,但占用内存较大,不适合含有负数的数组。
80 0
数据结构与算法学习十三:基数排序,以空间换时间的稳定式排序,速度很快。
【用Java学习数据结构系列】七大排序要悄咪咪的学(直接插入,希尔,归并,选择,堆排,冒泡,快排)以及计数排序(非比较排序)
【用Java学习数据结构系列】七大排序要悄咪咪的学(直接插入,希尔,归并,选择,堆排,冒泡,快排)以及计数排序(非比较排序)
59 1
|
6月前
|
蓝桥杯宝藏排序 | 数据结构 | 快速排序 归并排序
蓝桥杯宝藏排序 | 数据结构 | 快速排序 归并排序
|
5月前
|
非递归实现后序遍历时,如何避免栈溢出?
后序遍历的递归实现和非递归实现各有优缺点,在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
146 58
|
3月前
|
【C++数据结构——栈与队列】顺序栈的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现顺序栈的基本运算。开始你的任务吧,祝你成功!​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 1.初始化栈 概念:初始化栈是为栈的使用做准备,包括分配内存空间(如果是动态分配)和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈,通常需要定义一个数组来存储栈元素,并设置一个变量来记录栈顶位置;对于链式栈,需要定义节点结构,包含数据域和指针域,同时初始化栈顶指针。 示例(顺序栈): 以下是一个简单的顺序栈初始化示例,假设用C语言实现,栈中存储
242 77
下一篇
oss创建bucket