Java 数组的快速排序
快速排序思想
快速排序的思想通过先选择一个基准点,然后通过左右两个指针先后遍历,并且依次比较数值与基准点的大小,比基准点大的数据放到右边,比基本点小的数据放到左右。在循环遍历左右两边依次进行,每次移到一个数据过后,都会更换遍历方向。
快速排序的核心思想是分治思想。
package com.cyj.demo;
/**
*
* Function:
* Author:@author chenyongjia
* Date:2019-11-04 22:59
* Desc:无
*/
public class QuickSort {
public static void main(String[] args) {
int[] array = new int[]{2, 3, 1, 4, 7, 8, 3, 5, 2, 6, 8, 9, 1};
quickSort(array, 0, array.length - 1);
for (int i = 0; i < array.length; i++) {
System.out.println(array[i]);
}
}
private static void quickSort(int[] array, int left, int right) {
if (left < right) {
int middle = middle(array, left, right);
quickSort(array, left, middle - 1);
quickSort(array, middle + 1, right);
}
}
/**
* 找到中间
*
* @param array
* @param left
* @param right
* @return
*/
private static int middle(int[] array, int left, int right) {
int base = array[left];
while (left < right) { while (right > left && array[right] >= base) {
right--;
}
array[left] = array[right];
while (left < right && array[left] <= base) {
left++;
}
array[right] = array[left];
}
array[left] = base;
return left;
}
}
总结
快速排序几个关键点
递归调用
找到中间点
从右递减
从左递增
注意:middle 函数找到的中间点,此时 left 和 right 两者是一样的,我们这里的基准点采用的是数组的最左边的数据。
最后
-
更多参考精彩博文请看这里:《陈永佳的博客》
-
喜欢博主的小伙伴可以加个关注、点个赞哦,持续更新嘿嘿!
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
文章由极客之音整理,本文链接:https://www.bmabk.com/index.php/post/97663.html