Java快速排序

Java快速排序快速排序是基于二分的思想,对冒泡排序的一种改进。主要思想是确立一个基数,将小于基数的数放到基数左边,大于基数的数字放到基数的右边,然后在对这两部分进一步排序,从而实现对数组的排序优点效率高:时间复杂度平均为O(N*logN),顾名思义,最快的排序算法;耗费资源少:最优的情况下空间复杂度为:O(logn),每一次都平分数组的情况;代码较为简单。缺点不稳定,初始序列有序或基本有序时,时间复杂度降为O(n^2)。图解有一个无序数组,首先确认一个基数,一般都以第0个元素为基数,然后定义左右指针,我们

快速排序是基于二分的思想,对冒泡排序的一种改进。主要思想是确立一个基数,将小于基数的数放到基数左边,大于基数的数字放到基数的右边,然后在对这两部分进一步排序,从而实现对数组的排序

优点
效率高:时间复杂度平均为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

(0)
编程小号编程小号

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注