手写快速排序(java实现)

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了手写快速排序(java实现)，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1426字，纯文字阅读大概需要3分钟。

内容图文

手写快速排序(java实现)

时间复杂度:

　　O(nlogn)

快速排序原理:

1. 定义一个基准元素base(我这里定义的是最左面的元素定位基准元素)
2. 定义两个变量i和j
3. j先从右向左遍历,找到第一个比base小的数就停止
4. i再从左向右便利找到第一个比base大的数停止
5. 交换i和j指向的元素
6. 直到i和j指向同一个元素,将这个元素与基准元素交换
7. 递归求解即可

图解:(排序过程)

　

注意:

　　上图为第一次快速排序的过程,递归过程和上图一致(没有给出)

 

每一次的排序结果:

　　现在在火车上没有给出具体每次排序结果,回学校补上.

 

Java代码实现:

package cn.csuft.poorguy.struct;

public class quickSortText {
	public static void main(String[] args) {
		int[] arr = { 3, 4, 1, 2, 6, 9, 8, 5, 7 };
		quickSort(arr, 0, arr.length - 1);
		for (int i = 0; i < arr.length; i++) {
			System.out.print(arr[i] + " ");
		}
	}

	public static void quickSort(int[] arr, int left, int right) {
		
		//数组最左边小于最右边不合法,直接退出
		if (left > right) {
			return;
		}
		
		//定义变量i指向最左边
		int i = left;
		
		//定义变量j指向最右边
		int j = right;
		
		//定义左边为基准元素base
		int base = arr[left];

		//只要i和j没有指向同一个元素,就继续交换
		while (i != j) {

			//从右向左寻找第一个小于基准元素的数
			while (arr[j] >= base && i < j) {
				j--;
			}

			//从左向右寻找第一个大于基准元素的数
			while (arr[i] <= base && i < j) {
				i++;
			}

			//执行到这里证明找到了i和j指向的元素
			//交换i和j指向的元素
			int temp = arr[i];
			arr[i] = arr[j];
			arr[j] = temp;
		}

		//将i和j共同指向的元素与基准元素交换
		arr[left] = arr[i];
		arr[i] = base;

		//对左边进行快速排序
		quickSort(arr, left, i - 1);
		
		//对右边进行快速排序
		quickSort(arr, i + 1, right);
	}
}

　　

内容总结

以上是互联网集市为您收集整理的手写快速排序(java实现)全部内容，希望文章能够帮你解决手写快速排序(java实现)所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---