当前位置：首页 > news >正文

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

news 2025/1/7 23:24:02

目录😋

任务描述

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

相关知识

为了完成本关任务，你需要掌握：

快速排序算法的基本原理
快速排序算法步骤
代码示例（以 C++ 为例）
时间复杂度和空间复杂度

1. 快速排序算法的基本原理

快速排序是一种高效的排序算法，基于分治策略。它的主要思想是通过选择一个基准元素（pivot），将数组划分成两部分。一部分的元素都小于等于基准元素，另一部分的元素都大于等于基准元素。然后对这两部分分别进行排序，最终使整个数组有序。

2. 快速排序算法步骤

选择基准元素：可以有多种选择基准元素的方式。常见的有选择数组的第一个元素、最后一个元素或者中间元素等。例如，在简单的实现中，常常选择数组的第一个元素作为基准元素。
划分操作（Partition）：
设定两个指针，一个从数组的左边开始（通常称为左指针），一个从数组的右边开始（称为右指针）。
左指针向右移动，直到找到一个大于基准元素的元素；同时，右指针向左移动，直到找到一个小于基准元素的元素。
当左指针和右指针都停止移动后，如果左指针小于右指针，就交换它们所指向的元素。
持续进行上述操作，直到左指针和右指针相遇或者交叉。此时，将基准元素与左指针（此时左指针和右指针相遇的位置）所指向的元素交换。这样就完成了一次划分，使得基准元素左边的元素都小于等于它，右边的元素都大于等于它。

递归排序：对划分后的两部分子数组（基准元素左边的和右边的）分别进行快速排序。这个过程是递归的，即对每个子数组重复选择基准元素、划分和递归排序的步骤，直到子数组的长度为 1 或者 0（这种情况下子数组已经是有序的）。

3. 代码示例（以 C++ 为例）
#include <iostream>
#include <vector>
using namespace std;// 划分函数
int partition(vector<int>& arr, int low, int high) {int pivot = arr[low];int i = low + 1;int j = high;while (true) {while (i <= j && arr[i] <= pivot) i++;while (i <= j && arr[j] > pivot) j--;if (i > j) break;swap(arr[i], arr[j]);}swap(arr[low], arr[j]);return j;
}// 快速排序函数
void quickSort(vector<int>& arr, int low, int high) {if (low < high) {int pivotIndex = partition(arr, low, high);quickSort(arr, low, pivotIndex - 1);quickSort(arr, pivotIndex + 1, high);}
}
在上述代码中：

partition函数实现了划分操作。它以arr[low]作为基准元素，通过两个while循环和指针i、j的移动来找到需要交换的元素，最后交换基准元素和j所指元素，返回划分后的基准元素位置。
quickSort函数是快速排序的主函数，它首先调用partition函数进行划分，然后递归地对划分后的两部分子数组进行排序。

4. 时间复杂度和空间复杂度

时间复杂度：
在最好情况下，每次划分都能将数组均匀地分成两部分，时间复杂度为 $O(nlogn)$ ，其中 $n$ 是数组中的元素个数。
在最坏情况下，例如数组已经是有序的（选择第一个元素作为基准元素），每次划分得到的两个子数组长度分别为 $n-1$ 和 $0$ ，时间复杂度为 $O(n^{2})$ 。
平均时间复杂度是 $O(nlogn)$ 。

空间复杂度：快速排序是递归实现的，需要栈空间来保存递归调用的信息。在最好情况下，空间复杂度为 $O(logn)$ ，因为递归树的高度为。在最坏情况下，空间复杂度为 $O(n)$ ，例如数组已经是有序的情况。平均空间复杂度是 $O(logn)$ 。

测试说明

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

测试输入：(第一行是元素个数，第二行是待排序的原始关键字数据。）
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].keyreturn 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;
}