排序算法——关于快速排序的详解
目录
1.基本思想
????????快速排序（Quick Sort）是一种常用的排序算法，它采用分治法的思想，通过递归地将数据分解成小于基准值和大于基准值的两部分，然后对这两部分进行排序，最终将它们合并起来。
2.基本原理
??????2.1划分思想
????????在待排序表L[l...n]中任取一个元素pivot作为枢轴(或称基准，通常取首元素)，通过一趟排序将待排序表划分为独立的两部分L[l...k-1]和L[k+l...n]，使得L[l...k-l]中的所有元素小于pivot；L[k+l...n]中的所有元素大于或等于pivot，则pivot放在了其最终位置L(k)上，这个过程称为一次划分。
??????2.2排序过程
? ? ?（1）选择基准值
????????从待排序数组中选择一个元素作为基准值。通常选择第一个元素，但也可以选择随机元素或数组中间的元素。
? ? ?（2）分割过程（Partition）
????????将数组按照基准值进行分割，将小于等于基准值的元素放在基准值的左侧，大于基准值的元素放在右侧。同时，基准值所在的位置被确定，这个位置之前的元素都小于等于基准值，之后的元素都大于基准值。这一过程可以使用双指针法来实现。
? ? ?（3）递归排序
????????对基准值左侧和右侧的子数组分别进行递归排序。即对左侧子数组和右侧子数组分别重复步骤1和步骤2。
? ? ?（4）合并过程
????????递归排序完成后，整个数组已经被拆分成若干有序的子数组，只需简单地将这些子数组合并即可得到最终的有序数组。
??????2.3具体实例
????????一趟快速排序的过程是一个交替搜索和交换的过程，下面通过实例来介绍
*来自2024版王道数据结构考研复习指导
????????设两个指针i和j，初值分别为low和high，取第一个元素49为枢轴赋值到变量pivot。
????????对算法的最好理解方式是手动地模拟一遍这些算法。
??????2.4实现代码
void Quicksort(ElemType A[], int low, int high) {
if (low < high) {
//递归跳出的条件
//Partition()就是划分操作，将表A [low…high]划分为满足上述条件的两个子表
int pivotpos = Partition(A, low, high);
//划分
Quicksort(A, low, pivotpos - 1);
//依次对两个子表进行递归排序
Quicksort(A, pivotpos + 1, high);
}
}int Partition(ElemType A[], int low, int high) {
//一趟划分
ElemType pivot = A[low]; //将当前表中第一个元素设为枢轴，对表进行划分
while (low < high) {
//循环跳出条件
while (low < high && A[high] >= pivot)
--high;
A[low] = A[high];
//将比枢轴小的元素移动到左端
while (low < high && A[low] < pivot)
++low;
A[high] = A[low];
//将比枢轴大的元素移动到右端
}
A[low] = pivot;
//枢轴元素存放到最终位置
return low;
//返回存放枢轴的最终位置
}??????2.5关键要点
????????(1)基准值的选择：选择待排序数组中的一个元素作为基准值。通常情况下选择第一个元素，但也可以采用其他策略，如随机选择。
????????(2)分割过程：将数组分割成两个子数组，一个包含小于等于基准值的元素，另一个包含大于基准值的元素。这个过程通常被称为分区（partition）。
????????(3)递归排序：对分割得到的两个子数组递归地应用快速排序算法。这是分治策略的关键，通过不断递归排序，最终实现整个数组的排序。
????????(4)合并过程：将排好序的子数组与基准值合并起来，形成最终的有序数组。
????????(5)终止条件：当子数组的长度为1或0时，不再进行递归，因为长度为1或0的数组被认为是有序的。
????????(6)不稳定性：快速排序是一种不稳定的排序算法，即相等元素的相对位置可能在排序前后发生变化。
????????(7)空间复杂度：快速排序是原地排序算法，不需要额外的存储空间，只需要在递归调用时保持一些辅助变量。
????????(8)平均时间复杂度：快速排序的平均时间复杂度为O(n log n)，其中n是数组的长度。最坏情况下为O(n^2)，但在实际应用中，快速排序通常表现良好。
3.性能分析
??????3.1空间效率
????????由于快速排序是递归的，需要借助一个递归工作栈来保存每层递归调用的必要信息，其容量与递归调用的最大深度一致。最好情况下为O(log2n)；最坏情况下，因为要进行n-1次递归调用，所以栈的深度为O(n)；平均情况下，栈的深度为O(log2n)。
??????3.2时间效率
????????快速排序的运行时间与划分是否对称有关，快速排序的最坏情况发生在两个区域分别包含n-1个元素和0个元素时，这种最大限度的不对称性若发生在每层递归上，即对应于初始排序表基本有序或基本逆序时，就得到最坏情况下的时间复杂度为0(n^2)。
????????快速排序是所有内部排序算法中平均性能最优的排序算法
??????3.3稳定性
????????在划分算法中，若右端区间有两个关键字相同，且均小于基准值的记录，则在交换到左端区间后，它们的相对位置会发生变化，即快速排序是一种不稳定的排序方法。例如，表L={3,2,2}，经过一趟排序后L={2,2,3}，最终排序序列也是L={2,2,3)，显然，2与2的相对次序己发生了变化。
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符，请联系我的编程经验分享网邮箱：veading@qq.com进行投诉反馈，一经查实，立即删除！