1.1 算法思路——

该算法在数组中选定一个元素作为主元（一般选第一个），然后以这个主元为參考对象将数组分为两个部分，第一部分都是小于或者等于主元，第二部分都是大于或者等于主元。

然后对第一和第二部分递归地使用高速排序算法，直到分到最小的小组为止。

1.2 时间复杂度——

在最差的情况下，要把n个元素的数组划分，须要n次比較和n次移动。如果用T(n) 来表示使用高速排序算法来排序n个元素的数组所耗费的时间。那么

 T（n） = T(n/2)+ T(n/2) +2n

所以，高速排序的时间复杂度应该是  T（n） =O(nlogn) 。

1.3 程序流程图

1.4 实现代码

package lin.algo;public class QuickSort {	int[] list;	public QuickSort(int[] list){		this.list = list;	}		public int[] quickSort(){		quick(list,0,list.length-1);		return list;	}		private void quick(int[] list,int first , int last){		if (last>first) {			int pivoxIndex = partition(list, first, last);			quick(list, first, pivoxIndex-1);			quick(list, pivoxIndex+1, last);		}	}		/**	 * 依据第一个元素来划分数组	 * 输入的是要划分的原始数组。第一个元素下标和最后一个元素下标	 * @param list	 * @param first	 * @param last	 * @return 分组后的主元下标	 */	private int partition(int[] list,int first , int last){		//主元		int privot = list[first];		int secondIndex = first+1;		int lastIndex = last;				//遍历查询，大于主元的在右边。小于的在左边		//实现方法：两边查起，将左边大于主元的与右边小于主元的交换，		//最后把主元放在两个分好组的中间位置		while(lastIndex>secondIndex){			//寻找左边第一个比主元大的			while(secondIndex<= lastIndex  &&list[secondIndex]<=privot ){				secondIndex++;			}						//寻找右边第一个比主元小的			while( secondIndex<= lastIndex  && list[lastIndex]> privot){				lastIndex--;			}						//至此。假设还没检查完序列，就证明分别找到了。交换			if (secondIndex< lastIndex) {				int temp = list[secondIndex];				list[secondIndex] = list[lastIndex];				list[lastIndex] = temp;			}		}				while(list[lastIndex] >= privot && lastIndex> first){			lastIndex --;		}				//返回主元新下标		if (privot > list[lastIndex]) {			list[first] = list[lastIndex];			list[lastIndex] = privot;			return lastIndex;		}else {			return first;		}			}}