一、快速排序的介绍

        快速排序（Quicksort）是对冒泡排序的一种改进。基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列

二、快速排序法示意图

三、快速排序法思路分析

• 从序列中选择一个基准数pivot [可以选择序列中的第一个数为pivot]
• 将序列中所有数依次遍历，同时比基准数pivot大的放在其右侧，比基准数小的放在其左侧
• 分别对左右子序列重复以上两步操作

四、快速排序算法的Java实现

import java.util.Arrays;
//快速排序
public class QuickSortDemo {
	public static void main(String[] args) {
		int[] arr ={5,41,3,7,1,6,9,10,16,32};
		quickSort(arr,0, arr.length-1);
		System.out.println(Arrays.toString(arr));
	}

	public static void  quickSort(int[] arr,int left,int right){
		if (arr == null || arr.length < 2){
			return;
		}
		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);
		}
	}
}

五、快速排序算法的时间复杂度分析

         在最坏的情况下，仍可能是相邻的两个数进行了交换，因此快速排序的最差时间复杂度和冒泡排序是一样的都是O(N^2)，它的平均时间复杂度为O(NlogN)。

总结

        快速排序之所比较快，因为相比冒泡排序，每次交换是跳跃式的。每次排序的时候设置一个基准点，将小于等于基准点的数全部放到基准点的左边，将大于等于基准点的数全部放到基准点的右边。这样在每次交换的时候就不会像冒泡排序一样每次只能在相邻的数之间进行交换，交换的距离就大的多了。因此总的比较和交换次数就少了，速度自然就提高了。