深圳营销网站建设,定制衣服的厂家,旅游网站开发设计报告书,上网导航下载大家好#xff0c;我是烤鸭#xff1a; 今天分享一下基础排序算法之快速排序。快速排序是内部排序#xff08;基于比较排序#xff09;中最好的比较算法。 1. 快速排序#xff1a; 原理#xff1a;在要排的数#xff08;比如数组A#xff09;中选择一个中心值k…大家好我是烤鸭 今天分享一下基础排序算法之快速排序。快速排序是内部排序基于比较排序中最好的比较算法。 1. 快速排序 原理在要排的数比如数组A中选择一个中心值key比如A[0]通过一趟排序将数组A分成两部分其中以key为中心key右边都比key大key左边的都key小然后对这两部分分别重复这个过程直到整个有序。 整个快排的过程就简化为了一趟排序的过程然后递归调用就行了。
思路
1定义i0jA.lenght-1i为第一个数的下标j为最后一个数下标 2从数组的最后一个数Aj从右往左找找到第一小于key的数记为Aj 3从数组的第一个数Ai 从左往右找找到第一个大于key的数记为Ai 4交换Ai 和Aj 5重复这个过程直到 ij 6调整key的位置把A[i] 和key交换 例如 6 9 8 5 4 7(i0,j0)first time: 4 9 8 5 6 7 从左向右取6的第一个为6从右向左取比6小的第一个为4交换位置(i0,j1)second time: 4 5 8 9 6 7 比6大的第二个元素9比6小的第二个元素5交换位置(i1,j2)third time: 4 5 8 9 6 7 再继续i j了,递归原方法45基准变成48967基准变成8(i2,j1)forth time: 4 5 7 9 6 8 同上8和7交换(i2,j5)fifth time: 4 5 7 6 9 8 同上9和6交换(i3,j4)再同上 , 7和6交换。9和8交换。代码实现
public void quickSort(int[] numbers, int start, int end) {if (start end) {int base numbers[start]; // 选定的基准值第一个数值作为基准值int temp; // 记录临时中间值int i start, j end;do {while ((numbers[i] base) (i end)) {i;}while ((numbers[j] base) (j start)) {j--;}if (i j) {temp numbers[i];numbers[i] numbers[j];numbers[j] temp;i;j--;}} while (i j);if (start j) {quickSort(numbers, start, j);}if (end i) {quickSort(numbers, i, end);}}}
耗时对比
10W 条随机 数据 运行如图 分别对比了冒泡排序直插排序希尔排序和快速排序。差距很明显。
50W 条随机 数据 运行如图 分别对比了冒泡排序直插排序希尔排序和快速排序。差距很明显。
100W 条随机 数据 运行如图 分别对比了冒泡排序直插排序希尔排序和快速排序。差距很明显。
总结
快速排序Quicksort是对冒泡排序的一种改进。
最坏时间复杂度和插入排序相同O(n^2)。
冒泡排序总的平均时间复杂度为O(nlog2n) 。
各种排序方法比较 更多排序算法
冒泡排序 https://blog.csdn.net/Angry_Mills/article/details/81057900
插入排序 https://blog.csdn.net/Angry_Mills/article/details/81208700
