安徽网站排名优化公司,wordpress分类不显示图片,免费国外ddos网站,软件开发是吃青春饭的吗快速排序是一种高效的排序算法#xff0c;由C. A. R. Hoare在1960年提出#xff0c;基本思想是分治法#xff08;Divide and Conquer#xff09;策略#xff0c;通过递归将一个大问题分解为若干个较小的子问题#xff0c;然后合并这些子问题的解来解决原始问题
快速排序…快速排序是一种高效的排序算法由C. A. R. Hoare在1960年提出基本思想是分治法Divide and Conquer策略通过递归将一个大问题分解为若干个较小的子问题然后合并这些子问题的解来解决原始问题
快速排序的基本步骤如下
1 选择基准元素Pivot 从数组中选择一个元素作为基准元素pivot
通常有三种选择方法
1. 选择第一个元素作为基准
2. 选择最后一个元素作为基准
3.选择中间位置的元素作为基准
2分区Partitioning操作 重新排列数组所有比基准元素小的元素摆放在基准前面所有比基准元素大的元素摆在基准的后面这个分区操作后基准元素处于数组的中间位置
分区操作 使用两个指针通常称为i和j从数组的两端开始向中间移动 当i指针找到比基准大的元素j指针找到比基准小的元素时交换这两个元素 重复上述过程直到两个指针相遇
#include iostream using namespace std; void Quicksort(int array[], int L, int R) { if (L R) // 如果左边索引 L 大于等于右边索引 R则说明子数组的大小为 1 或更小不需要进一步排序。此时函数直接返回结束当前递归 return; int left L, right R; int pivot array[left]; while (left right) { while (left right array[right] pivot) { right--; } if (left right) { array[left] array[right]; left; } while (left right array[left] pivot) { left; } if (left right) { array[right] array[left]; right--; } } array[left] pivot; Quicksort(array, L, left - 1); Quicksort(array, left 1, R); }
int main() { int array[] {6, 4, 8, 2, 1, 0}; int n sizeof(array) / sizeof(array[0]); cout Original array: ; for (int i 0; i n; i) cout array[i] ; cout endl; Quicksort(array, 0, n - 1); cout Sorted array: ; for (int i 0; i n; i) cout array[i] ; cout endl; return 0; } 参数说明
array[]待排序的整数数组
L当前子数组的左边界索引
R当前子数组的右边界索引
函数逻辑
递归终止条件如果 L R说明子数组的大小为 1 或更小不需要排序直接返回
初始化将 left 和 right 分别初始化为 L 和 R选择 array[left] 作为基准元素 pivot
分区操作
从右向左扫描找到第一个小于 pivot 的元素将其放到 left 位置并将 left 指针右移一位
从左向右扫描找到第一个大于 pivot 的元素将其放到 right 位置并将 right 指针左移一位
重复上述两个步骤直到 left 和 right 指针相遇
放置基准元素将基准元素 pivot 放到 left 位置
递归排序分别对基准元素左边和右边的子数组进行递归排序
