Java常见排序算法详解——快速排序
Java常见排序算法详解——快速排序
Demo_Yang
发布于 2019-04-22 10:35:35
发布于 2019-04-22 10:35:35
概念:
通过一趟排序将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分小，则可分别对这两部分记录继续进行排序，直到整个序列有序。
原理:
- 在数据集之中，选择一个元素作为”基准”（pivot）。
- 所有小于”基准”的元素，都移到”基准”的左边；所有大于”基准”的元素，都移到”基准”的右边。这个操作称为分区 (partition) 操作，分区操作结束后，基准元素所处的位置就是最终排序后它的位置。
- 对”基准”左边和右边的两个子集，不断重复第一步和第二步，直到所有子集只剩下一个元素为止。
图解: 例如我们有个一个数组[29 4 10 11 7] 1.首先我们先选定一个基准元素，这里我们选择10作为基准元素，然后把基准元素放在最后一个，如果选择最后一个元素作为基准元素，那么可以省略
快速排序
↓
29 4 11 7 102.从左到右（除了最后的元素），循环移动小于基准元素到数据开头，留下大于等于基准元素的接在后面。 循环i = 1的时候，找到一个小于基准元素的元素4 这个时候storeIndex = 1
快速排序
↓
4 29 11 7 10之后循环到i=3时7小于10和storeIndex = 1换位置
4 7 11 29 10这个时候storeIndex = 2 3.再然后，我们把基准元素放到storeIndex的位置，其他元素位置依次+1得到了我们想要的数组
4 7 10 11 29代码:
public static void qSort(int[] arr, int head, int tail) {
if (head >= tail || arr == null || arr.length <= 1) {
return;
}
int i = head, j = tail, pivot = arr[(head + tail) / 2];
while (i <= j) {
while (arr[i] < pivot) {
++i;
}
while (arr[j] > pivot) {
--j;
}
if (i < j) {
int t = arr[i];
arr[i] = arr[j];
arr[j] = t;
++i;
--j;
} else if (i == j) {
++i;
}
}
qSort(arr, head, j);
qSort(arr, i, tail);
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2019.04.14 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录