排序算法——快速排序

算法思想

1. 从数列中挑选一个元素，一般情况下我们是取的数列第一个元素。这个取到的元素成为“基准数”(pivot)；
2. 从数列尾部开始往头部找比基准数小的数，将小的数与基准数做位置调换；
3. 从数列头部开始往尾部找比基准数大的数，将大的数与基准数做位置调换；
4. 当步骤2与步骤3执行完毕之后，基准数就处于了数列的中间位置，这时基准数左边的子数列中所有元素都是小于基准数；基准数右边的子数列中的所有元素都是大于基准数；这个过程称为分区操作；
5. 递归地把基准数左边数列和基准数右边数列排序；

图解过程

现有如下数列：data={3,44,38,5,47,15,36,26,27,2,46,4,19,50,48}，我们对这个数列使用快排。

定义一个基数：pivot = 3
一个查询左边的元素的指针: leftPointer，起初 leftPointer = 0
一个查询右边的元素指针: rightPointer , 起初rightPointer = data.length - 1

动态图演示

代码实现

import java.util.*;
import java.lang.*;

class Rextester
{  
    public static void main(String args[])
    {
		  int[] data = {6,1,2,7,9,3,4,5,10,8};
		  qSort(data,0,data.length - 1);
		  System.out.println(Arrays.toString(data));
    }
	
	public static void qSort(int[] data, int left,int right) {
		// 基准数
		int base = data[left];
		// 向后移动的指针
		int leftPointer = left;
		// 向前移动的指针
		int rightPointer = right;
		// 如果left和right不想等，说明没有循环完毕,继续循环
		while(leftPointer < rightPointer) {
			// 从后往前找比基准数小的数
			while(leftPointer < rightPointer && data[rightPointer] >= base) {
				rightPointer--;
			}
			// 说明找到了
			if(leftPointer < rightPointer) {
				int temp = data[rightPointer];
				data[rightPointer] = data[leftPointer];
				data[leftPointer] = temp;
				leftPointer++;
			}
			// 从前往后找比基准数大的数
			while(leftPointer < rightPointer && data[leftPointer] <= base) {
				leftPointer++;
			}
			// 如果找到了就交换位置
			if(leftPointer < rightPointer) {
				int temp = data[leftPointer];
				data[leftPointer] = data[rightPointer];
				data[rightPointer] = temp;
				rightPointer--;
			}
		}
		// 将数组分成三部分，左，基准数，右，
		if(left < leftPointer) {
			qSort(data,left,leftPointer - 1);
		}
		if(rightPointer < right) {
			qSort(data,rightPointer + 1,right);
		}
	}
}

复杂度

当基准数选择的是数列中做小或者做大的数时，快速排序的运行情况最坏是O(n²)，如果说基准数取得比较好，或者数列中有很多已经是排好序的数列了，这时快速排序的平均复杂度降为了O(nlogn)；

优化

这里可以中间放在优化基准数，怎么取基准数可以合适。比如：

1. 三数据中取基准数