赞
踩
快速排序是所有内部排序算法中平均性能最优的排序算法
快速排序是对冒泡排序算法的一种改进
快速排序由C. A. R. Hoare在1960年提出。
它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列
快速排序的基本思想是基于分治法的
在待排序表L[1…n]中任取一个元素pivot作为枢轴(或基准,通常取首元素)
也就是常见的 固定位置选取基准
通过一趟排序将待排序表划分为独立的两部分L[1…k-1]和L[k+1…n]
使得L[1…k-1]中的所有元素小于pivot
L[k+1.n]中的所有元素大于等于pivot
则pivot放在了其最终位置L(k)上
这个过程称为一趟快速排序(或一次划分)
然后分别递归地对两个子表重复上述过程,直至每部分内只有一个元素或空为止,即所有元素放在了其最终位置上。
一趟快速排序的过程是一个交替搜索和交换的过程
常见方法就是 挖坑法
不过需要注意:
如果选择 第一个数组元素为基准时,必须先 从后向前进行
如果选择 最后一个数组元素为基准时,必须先 从前向后进行
挖坑法的流程:
首先写好划分操作算法,然后递归调用~
// 每一次的 划分操作 int Partition(int *arr, int left, int right) { int i = left; int j = right; // 固定位置选取基准 选第一个 int k = arr[left]; while (i < j) { while(i < j && arr[j] >= k) {j--;} arr[i] = arr[j]; while(i < j && arr[i] <= k) {i++;} arr[j] = arr[i]; } arr[i] = k; return i; } // 递归调用 实现快速排序 void QuickSort(int *arr,int low,int high) { int k = Partition(arr,low,high); if(low < k-1) { QuickSort(arr,low,k-1); } if(high > k+1) { QuickSort(arr,k+1,high); } }
示例:
int arr[] = {3,44,38,5,47,15,36,26,27,2,46,4,19,50,48};
① 空间复杂度
由于快速排序是递归的,需要借助一个递归工作栈来保存每层递归调用的必要信息,其容量应与递归调用的最大深度一致。
最好情况下为 O(log2n)
最坏情况下 O(n) ;因为要进行n-1 次递归调用
平均情况下,栈的深度为 O(log2n)
② 时间复杂度
快速排序的运行时间与划分是否对称有关
最坏情况发生在初始排序表基本有序或基本逆序时,时间复杂度为 O(n)
最好的情况,每一次划分都很均衡,时间复杂度为 O(nlog2n)
③ 优化:提高算法效率
一种方法是尽量选取一个可以将数据中分的枢轴元素
三分取中法选取基准:从序列的头尾及中间选取三个元素,再取这三个元素的中间值作为最终的枢轴元素;
随机选择基准:随机地从当前表中选取枢轴元素
这样做可使得最坏情况在实际排序中几乎不会发生。
④ 稳定性
一种情况是,右端区间有两个关键字相同,且均小于基准值,则交换到左端区间后,它们的相对位置(不是绝对位置)会发生变化
所以快速排序是一种不稳定的排序方法
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。