成都网站设计费用,十堰电商网站建设,建模培训,网站开发招标方案范本文章目录 1. 快速排序#xff08;Quick Sort#xff09;1.1、 简介1.2、 快速排序的步骤 2. Hoare 版本2.1、 基本思路1. 分区#xff08;Partition#xff09;2. 基准选择#xff08;Pivot Selection#xff09;3. 递归排序#xff08;Recursive Sorting#xff09; 2… 文章目录 1. 快速排序Quick Sort1.1、 简介1.2、 快速排序的步骤 2. Hoare 版本2.1、 基本思路1. 分区Partition2. 基准选择Pivot Selection3. 递归排序Recursive Sorting 2.2 、代码实现2.3、 代码解释1. GetMid 函数三数取中作用逻辑 2. HoreQuickSort 函数Hoare 分区法的快速排序主要步骤代码整体总结 2.4 、动画展示 3. 挖坑版3.1、基本思路3.2、挖坑法步骤3.3、代码实现3.4、动画展示 4. 前后指针4.1、基本思路4. 2、步骤4.3 、代码中的实现解释 4. 4 、动画展示 1. 快速排序Quick Sort
1.1、 简介
快速排序Quick Sort是一种高效的排序算法通常用于大数据集的排序。它由英国计算机科学家 Tony Hoare 在 1960 年提出并基于分治法Divide and Conquer的思想来排序数组或列表。
1.2、 快速排序的步骤 选择基准Pivot 从数组中选择一个元素作为基准。基准的选择方法会影响算法的性能常用的基准选择策略包括 选择第一个元素选择最后一个元素选择中间元素随机选择三数取中法选择第一个、最后一个和中间位置的元素中位数作为基准 划分Partition 将数组分为两部分使得 一部分的元素都小于等于基准另一部分的元素都大于基准。 此时基准元素已经在排序后的正确位置上。 递归排序 对基准左侧的子数组和右侧的子数组递归地进行快速排序。当子数组长度为 1 或 0 时递归结束此时该部分已经有序。
2. Hoare 版本
2.1、 基本思路
这个代码的基本思路是实现快速排序QuickSort算法的一个优化版本主要包含 分区、递归 和 基准选择 三个关键步骤。以下是简化后的基本思路
1. 分区Partition
快速排序的核心是“分区”操作。它通过选择一个基准值将数组分成左右两部分使得左侧的元素都小于等于基准右侧的元素都大于等于基准。完成分区后基准元素会处于它排序后的最终位置。
2. 基准选择Pivot Selection
在分区过程中基准的选择直接影响算法的效率。理想情况下基准会将数组分成大小相近的两部分避免极端情况的出现。这里使用 三数取中法 来选择基准即取数组左端、中间、右端的三个值中间的那个作为基准值。这样能够减少最坏情况的出现例如数组本身有序时的情况提高算法的平均性能。
3. 递归排序Recursive Sorting
完成分区后基准两侧的子数组还未有序需要对每个子数组继续进行快速排序。通过递归调用将每个子数组逐步分成更小的部分最终达到完全有序。递归的终止条件是数组长度为 1 或 0这种情况直接返回无需再排序。
2.2 、代码实现
#include stdio.h// 交换函数
void Swap(int *a, int *b) {int temp *a;*a *b;*b temp;
}// 三数取中函数返回左、中、右三者的中间值索引
int GetMid(int *a, int left, int right) {int mid left (right - left) / 2;if (a[left] a[right]) {Swap(a[left], a[right]);}if (a[mid] a[right]) {Swap(a[mid], a[right]);}if (a[left] a[mid]) {Swap(a[left], a[mid]);}return left; // 返回基准元素的索引
}// Hoare 分区法的快速排序
void HoreQuickSort(int *a, int left, int right) {if (left right) {return;}int begin left, end right;int key GetMid(a, left, right); // 三数取中并将基准值放到left位置Swap(a[left], a[key]); // 将基准交换到左端作为参考while (begin end) {// 从右往左找到第一个小于基准的元素while (begin end a[end] a[left]) {--end;}// 从左往右找到第一个大于基准的元素while (begin end a[begin] a[left]) {begin;}// 交换左右不符合顺序的元素if (begin end) {Swap(a[begin], a[end]);}}// 最后将基准元素放到分区点Swap(a[left], a[begin]);// 递归排序左右两部分HoreQuickSort(a, left, begin - 1);HoreQuickSort(a, begin 1, right);
}// 打印数组
void print_array(int *a, int size) {for (int i 0; i size; i) {printf(%d , a[i]);}printf(\n);
}// 主函数
int main() {int arr[] {10, 7, 8, 9, 1, 5};int n sizeof(arr) / sizeof(arr[0]);printf(原始数组: );print_array(arr, n);HoreQuickSort(arr, 0, n - 1);printf(排序后数组: );print_array(arr, n);return 0;
}2.3、 代码解释
1. GetMid 函数三数取中
int GetMid(int *a, int left, int right) {int mid left (right - left) / 2; // 计算中间索引if (a[left] a[right]) {Swap(a[left], a[right]); // 保证a[left] a[right]}if (a[mid] a[right]) {Swap(a[mid], a[right]); // 保证a[mid] a[right]}if (a[left] a[mid]) {Swap(a[left], a[mid]); // 保证a[left] a[mid]}return left; // 返回左索引位置作为基准索引
}作用
GetMid 函数的目的是在 左端、中间、右端 三个元素中选出中间值作为基准避免在近乎有序的数组中使用一个极值作为基准从而减少分区的不平衡问题。
逻辑
a[left] a[right] 时交换确保 a[left] 比 a[right] 小。a[mid] a[right] 时交换确保 a[mid] 也比 a[right] 小。a[left] a[mid] 时交换这样 a[left] 成为了中间值。最后返回 left将三数取中的结果放到 a[left]作为基准值。
2. HoreQuickSort 函数Hoare 分区法的快速排序
void HoreQuickSort(int *a, int left, int right) {if (left right) {return; // 基本情况如果只有一个元素或无元素直接返回}int begin left, end right; // 初始化分区指针int key GetMid(a, left, right); // 选择基准并取三数中值Swap(a[left], a[key]); // 将基准交换到左端while (begin end) {// 从右向左找到第一个小于基准的元素while (begin end a[end] a[left]) {--end;}// 从左向右找到第一个大于基准的元素while (begin end a[begin] a[left]) {begin;}// 交换找到的元素if (begin end) {Swap(a[begin], a[end]);}}// 最后将基准元素放到最终位置Swap(a[left], a[begin]);// 递归排序左右两部分HoreQuickSort(a, left, begin - 1);HoreQuickSort(a, begin 1, right);
}主要步骤 基准选择与初始化 使用 GetMid 进行三数取中法选择基准减少最坏情况下的不平衡。将基准交换到 left 位置方便分区操作。 分区过程 begin 和 end 分别从左、右两端向中间移动。从右向左找到第一个小于基准的元素将 end 移动到该位置。从左向右找到第一个大于基准的元素将 begin 移动到该位置。如果 begin end交换 a[begin] 和 a[end]确保小于基准的值在左侧大于基准的值在右侧。循环直到 begin end此时 begin 指向的元素是分区的正确位置。 基准位置调整 将 a[left]即基准值和 a[begin] 交换使基准值放置在分区中间的正确位置。 递归调用 对基准左侧left 到 begin - 1和右侧begin 1 到 right的子数组分别递归调用 HoreQuickSort 进行排序直到整个数组有序。
代码整体总结
Hoare 分区法通过双指针从两端向中间扫描交换不符合条件的元素提高分区效率。三数取中法选基准时用三数取中法减少极端情况的出现。递归快速排序分区后对左右两部分递归排序直到每个子数组有序。
2.4 、动画展示 3. 挖坑版
快速排序挖坑法是一种直观且高效的排序算法实现方式它基于分治策略通过递归地将数组分成较小的子数组来排序。以下是关于快速排序挖坑法的详细解释
3.1、基本思路
快速排序的基本思想是选择一个基准值pivot然后将数组分成两部分一部分包含所有小于基准值的元素另一部分包含所有大于基准值的元素。接着递归地对这两部分进行同样的操作直到整个数组有序。
3.2、挖坑法步骤 选择基准值 通常选择数组的第一个元素、最后一个元素或中间元素作为基准值。为了简单起见这里以第一个元素为例。记住基准值的位置这个位置相当于一个“坑”。 初始化指针 设置两个指针left和right分别指向数组的最左和最右两个元素。 从右向左遍历 从right指针开始将指针所指向的元素与基准值进行比较。如果元素大于基准值则right指针向左移动。如果元素小于基准值则将该元素填入坑中即基准值原本的位置并将该元素原本的位置视为新的坑。同时left指针向右移动一位。 从左向右遍历 从left指针开始将指针所指向的元素与基准值进行比较注意此时基准值已被某个元素替换因此实际上是与该元素进行比较。如果元素小于基准值实际上是小于刚才被填入坑中的那个元素因为基准值已被替换则left指针向右移动。如果元素大于基准值则将该元素填入坑中并将该元素原本的位置视为新的坑。同时right指针向左移动一位。 重复步骤3和4 继续按照上述步骤进行遍历直到left和right指针重合。 放入基准值 当left和right指针重合时将基准值或最初被选出的那个基准值的值如果它在遍历过程中被替换了的话放入重合的位置。此时基准值左边的所有元素都小于它右边的所有元素都大于它。 递归排序 对基准值左边和右边的子数组递归地进行上述操作直到整个数组有序。
3.3、代码实现
// 挖坑法快速排序
void HoleQuickSort(int* arr, int left, int right)
{if (left right)return;// 使用第一个元素作为基准值也可以选择其他方式如三数取中int pivotValue arr[left];int holeIndex left; // 挖坑的位置初始化为基准值的位置int scanLeft left, scanRight right; // 左右扫描指针// 从右向左扫描找到第一个小于基准值的元素while (scanRight scanLeft){// 从右向左找到第一个小于基准值的元素while (scanRight scanLeft arr[scanRight] pivotValue)scanRight--;// 如果找到将该元素放到坑里holeIndex位置if (scanRight scanLeft){arr[holeIndex] arr[scanRight];holeIndex scanRight; // 更新坑的位置到当前元素的位置}// 从左向右扫描找到第一个大于基准值的元素while (scanRight scanLeft arr[scanLeft] pivotValue)scanLeft;// 如果找到将该元素放到坑里此时坑的位置可能已经被更新if (scanRight scanLeft){arr[holeIndex] arr[scanLeft];holeIndex scanLeft; // 再次更新坑的位置}}// 当左右扫描指针相遇时将基准值放到坑里arr[holeIndex] pivotValue;// 递归排序基准值左右两侧的子数组HoleQuickSort(arr, left, holeIndex - 1);HoleQuickSort(arr, holeIndex 1, right);
}// 辅助函数交换两个整数的值此函数在您的原始代码中已提供但为完整性而保留
void swap(int* a, int* b)
{int temp *a;*a *b;*b temp;
}
3.4、动画展示 4. 前后指针
4.1、基本思路
快速排序的前后指针法也叫“双指针法”是快速排序中的一种常见分区方法。这个方法通过两个指针分别从数组的左右两端开始来逐步划分数组使得数组中的元素相对于一个基准元素通常是数组的第一个元素进行排序。
4. 2、步骤 选择基准元素选择数组中的一个元素作为基准pivot。在你给出的代码中基准是数组的第一个元素 key。 设置两个指针 前指针pre从左边开始指向当前已经被正确分区的区域的末尾。初始时pre 指向基准元素。后指针cur从左边的第二个元素开始遍历整个数组用来扫描比基准小的元素。 扫描并交换 前指针会不断向右移动找到一个比基准小的元素。后指针会遍历数组直到找到一个比基准大的元素。如果后指针找到一个大于基准的元素同时前指针找到了一个小于基准的元素则交换这两个元素。这保证了所有小于基准的元素都在基准的左边所有大于基准的元素都在基准的右边。 完成分区 当两个指针相遇时或者后指针扫描到数组的右边界时前后指针停止。这时将基准元素和 pre 指针所指向的元素交换。这样基准元素就放置在了正确的位置上左边是比基准小的元素右边是比基准大的元素。 递归排序对基准元素左边和右边的子数组继续使用相同的分区方法递归进行排序直到子数组的大小为 1 或 0。
4.3 、代码中的实现
void FbQuickSort(int* a, int left, int right)
{if (left right)return;int pre left; // 前指针初始化为 leftint cur left 1; // 后指针初始化为 left 1int key a[left]; // 选择基准元素为 leftwhile (cur right){if (a[cur] key) // 如果当前元素小于基准元素{pre; // 前指针右移Swap(a[cur], a[pre]); // 交换当前元素与前指针指向的元素}cur; // 后指针继续右移}// 最后将基准元素与前指针指向的元素交换Swap(a[left], a[pre]);// 递归对左边和右边的子数组进行快速排序FbQuickSort(a, left, pre - 1);FbQuickSort(a, pre 1, right);
}解释
基准元素key a[left]我们选择数组的第一个元素作为基准。前后指针初始化pre leftcur left 1。pre 记录当前已经排序好的区域的边界cur 用来遍历剩余的部分。主循环while (cur right) 让后指针 cur 遍历整个数组。在每次扫描中检查当前元素是否小于基准元素如果是则将其与前指针 pre 所指向的元素交换同时 pre 自增。基准交换Swap(a[left], a[pre]) 将基准元素交换到其最终位置这时 pre 的位置已经确定了基准元素应该放置的位置。左边是比基准小的元素右边是比基准大的元素。递归调用对基准元素左右两侧的子数组递归进行快速排序。
4. 4 、动画展示
