欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

快速排序算法,二分思想

程序员文章站 2022-06-28 17:28:24
package QuickSortAlgorithm;public class QuickSort {//快速排序算法,原地操作public static void quickSort(int[] arr, int start, int end) {//交换辅助变量int t;int i = start;int j = end;//结束条件if(start >= end) return;//快排的基元int temp = arr[start]...
package QuickSortAlgorithm;

public class QuickSort {
	//快速排序算法,原地操作
	public static void quickSort(int[] arr, int start, int end) {
		//交换辅助变量
		int t;
		int i = start;
		int j = end;
		//结束条件
		if(start >= end) return;
		//快排的基元
		int temp = arr[start];
		//快排算法,就是借用了二分法的思路
		while(true) {
			//从右边开始侦查
			while(temp <= arr[j] && i != j) {
				j --;
			}
			//左边也开始侦查,注意这里必须是>=号,不然的话,这里的第一步执行起来就有问题了
			while(temp >= arr[i] && i != j) {
				i ++;
			}
			//交换
			if(i < j) {
				t = arr[i];
				arr[i] = arr[j];
				arr[j] = t;
			}
			
			//跳出循环的条件
			if(i == j) {
				//交换基元和i元素
				t = arr[i];
				arr[i] = arr[start];
				arr[start] = t;
				//调用递归
				quickSort(arr, start, i - 1);
				quickSort(arr, i + 1, end);
				break;
			}
		}
	}
	
	public static void main(String[] args) {
		int[] arr = {3,5,6,2,12,0,5,3,46,74,15,4,8};
		quickSort(arr, 0, arr.length - 1);
		System.out.println("快速排序后的结果为:");
		for(int obj : arr) {
			System.out.print(obj + "\t");
		}
	}
}

运行截图:

快速排序后的结果为:
0	2	3	3	4	5	5	6	8	12	15	46	74	

小结:快速排序之所以快,是因为他排序的时候是跳跃的,像传统的冒泡排序法,是在相邻的两个变量之间进行交换,而快速排序通过选择一个基变量,可以很好的实现排序,其实就是二分法思想,分而治之,虽然和冒泡排序最差的情况一致,都是O(n^2),但是在实际情况中,却比冒泡排序来的要快,平均时间是O(nlogn)

本文地址:https://blog.csdn.net/qq_44652489/article/details/110873091