快速排序是基于二分的思想,对冒泡排序的一种改进。主要思想是确立一个基数,将小于基数的数放到基数左边,大于基数的数字放到基数的右边,然后在对这两部分进一步排序,从而实现对数组的排序
优点
效率高:时间复杂度平均为O(N*logN),顾名思义,最快的排序算法;耗费资源少:最优的情况下空间复杂度为:O(logn) ,每一次都平分数组的情况;代码较为简单。
缺点
不稳定,初始序列有序或基本有序时,时间复杂度降为O(n^2)。
图解
有一个无序数组,首先确认一个基数,一般都以第0个元素为基数,然后定义左右指针,我们以左指针所在的位置为基数。
将基数从数组中拿出来,基数所在的位置就会产生一个空位
如果基数在左,就先移动右指针,找到一个小于基数的值,将右指针的所指的值放在左指针所在位置
右指针被操作后移动左指针,找到一个大于基数的值,交换到右指针的位置,右指针自减
重复这个步骤
左右指针重合时,将基数插入到重合位置,比基数小的数都在基数左边,大的数都在右边
对左右数据重复上述步骤,直到排序结束。
代码实现
public static void main(String[] args) {
int[] arr = new int[]{
1, 8, 5, 7, 2, 3, 4, 9, 6, 10};
quicksort(arr, 0, arr.length - 1);
}
public static void quicksort(int[] arr, int left, int right) {
if (right >= left) {
//保存基数
int basic = arr[left];
//定义左右指针
int i = left;
int j = right;
while (i < j) {
//左指针小于右指针
while (i < j && arr[j] > basic) {
//操作右指针找到小于基数的下标
j--;
}
if (i < j) {
arr[i] = arr[j]; //将右指针对应小于基数的值放到左指针所指的位置
i++; //左指针自加
}
while (i < j && arr[i] < basic) {
//相反,找到大于基数的下标
i++;
}
if (i < j) {
arr[j] = arr[i]; //大于基数的值赋给右指针所指的位置
j--; //右指针自减
}
}
arr[i] = basic; //将基数放入到指针重合处
quicksort(arr, left, i - 1); //重复调用,对左半部分数组进行排序
quicksort(arr, i + 1, right); //对右半部分数组进行排序
}
}
排序结果
今天的文章Java快速排序分享到此就结束了,感谢您的阅读,如果确实帮到您,您可以动动手指转发给其他人。
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/30722.html