快速排序算法

一、快速排序算法基本思想

快速排序通过一趟排序将待排元素分割成独立的两个部分，其中一部分元素均比另外一部分元素小，则可以对这两部分元素再继续进行排序，以达到整个元素有序。

二、快速排序图解

三、代码实现

package Sort;

import java.util.Arrays;

public class QucikSort {
	public static void quicksort(int[] arr,int low,int high) {
		if(low<high) {
			int partitionIndex=partition(arr,low,high); //将小于partitionIndex的值放左边，大于partitionIndex的值放右边
			quicksort(arr,low,partitionIndex-1); //对左边部分进行快速排序
			quicksort(arr,partitionIndex+1,high); //对右边部分进行快速排序
		}
	}
 
	public static int partition(int[] arr,int low,int high) {
		int pivot=arr[low];//使用arr[low]作为枢纽元素
		while(low<high) {//从两端交替向内扫描
			while(low<high&&arr[high]>=pivot) {//将比 pivot 小的元素移向低端
				high--;
			}
			arr[low]=arr[high];
			while(low<high&&arr[low]<=pivot) {//将比 pivot 大的元素移向高端
				low++;
			}
			arr[high]=arr[low];
		}
		arr[low]=pivot;//设置枢纽(结束时low=high，即可为arr[high]=pivot)
		return low; //返回枢轴元素位置
	}
	public static void main(String[] args) {
		int[] arr= {2,10,8,22,34,5,12,28,21,11};
		System.out.println("快速排序前：");
		System.out.println(Arrays.toString(arr));
		quicksort(arr,0,arr.length-1);
		System.out.println("快速排序后：");
		System.out.println(Arrays.toString(arr));
	}
}

运行结果：


四、快速排序算法性能测试

package Sort;

import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;

public class QucikSort {
	public static void quicksort(int[] arr,int low,int high) {
		if(low<high) {//升序排序
			int partitionIndex=partition(arr,low,high); //将小于partitionIndex的值放左边，大于partitionIndex的值放右边
			quicksort(arr,low,partitionIndex-1); //对左边部分进行快速排序
			quicksort(arr,partitionIndex+1,high); //对右边部分进行快速排序
		}
	}
 
	public static int partition(int[] arr,int low,int high) {
		int pivot=arr[low];//使用arr[low]作为枢纽元素
		while(low<high) {//从两端交替向内扫描
			while(low<high&&arr[high]>=pivot) {//将比 pivot 小的元素移向低端
				high--;
			}
			arr[low]=arr[high];
			while(low<high&&arr[low]<=pivot) {//将比 pivot 大的元素移向高端
				low++;
			}
			arr[high]=arr[low];
		}
		arr[low]=pivot;//设置枢纽(结束时low=high，即可为arr[high]=pivot)
		return low; //返回枢轴元素位置
	}
	public static void main(String[] args) {
		int[] arr = new int[80000];
		for (int i = 0; i < 80000; i++) {
			arr[i] = (int) (Math.random() * 8000000); // 生成一个[0, 8000000) 数
		}

		Date date1 = new Date();
		SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");//SimpleDateFormat是Java提供的一个格式化和解析日期的工具类
		String date1Str = simpleDateFormat.format(date1);
		System.out.println("快速排序前的时间是：" + date1Str);
		quicksort(arr,0,arr.length-1);
		Date date2 = new Date();
		String date2Str = simpleDateFormat.format(date2);
		System.out.println("快速排序后的时间是：" + date2Str);
	}
}

快速排序前的时间是：2021-01-31 15:27:32
快速排序后的时间是：2021-01-31 15:27:32

快速排序测试80000个数据一共需要1s左右的时间。