用Java实现快速排序

快速排序（Quick Sort）是一种分治的排序算法。

它的基本思想是：

1. 选择一个基准元素（本文选择第一个元素）。
2. 将数组中比基准小的元素放在基准的左边，比基准大的元素放在基准的右边。
3. 对基准左边和右边的子数组分别进行快速排序。

快速排序的优点包括：

1. 高效性：平均时间复杂度为O(nlogn)。
2. 适用于各种数据类型。
3. 空间复杂度相对较低。

然而，它也有一些缺点：

1. 在最坏情况下，时间复杂度可能退化为。
2. 对于小型数组，可能不太划算。

实现快速排序的步骤如下：

1. 选择基准元素：本文选择数组中的第一个元素作为基准。则”指针“要从右侧向左侧移动
2. 分割数组：当右侧向左扫描时，遇到比基准大的元素时，则继续向左扫描，当遇到比基准小的元素时，交换两”指针的元素“，然后从左侧开始向右侧扫描，重复如此。
3. 最后，比基准小的元素将放在左边，比基准大的元素将放在右边。
4. 递归地对左右子数组进行快速排序。

 代码演示如下：

public class Test2 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int []ints=new int [] {23,-9,78,3,34,3,0,34,23};
		quickSort(ints,0,ints.length-1);
		System.out.println(Arrays.toString(ints));
	
		
	}
	//快速排序
	public static void quickSort(int[]arr,int left,int right) {
		
		//递归结束条件
		if(left>=right) {
		return;
		}
		//确定最左最右指针
		int l=left;
		int r=right;
		//与基准进行判断：这里选择左边第一个为基准即arr[left]
		while(l<r) {
			//选择了左边第一个为基准，则要从最右侧向左开始判断，如果满足，则指针继续向左移动
			while(l<r&&arr[r]>=arr[left])r--;
			//
			while(l<r&&arr[l]<=arr[left])l++;
			//移到最后，指针重合，则将重合的位置的元素与基准进行交换
			if(l==r) {
				int temp=arr[left];
				arr[left]=arr[l];
				arr[l]=temp;
			
			}
			//当出现比基准大的元素在基准的左边，或者比基准小的元素出现在基准的右边时，两个指针的元素进行交换
			else {
				int temp=arr[r];
				arr[r]=arr[l];
				arr[l]=temp;
				
			}
			
		}
		//递归调用
		quickSort(arr,left,l-1);
		quickSort(arr,r+1,right);
	}

}

快速排序是一种常用的排序算法，在许多情况下都能提供较好的性能。