快速排序基于分治思想，期望时间复杂度可以达到O(nlgn)，并且是一种稳定的排序算法。
/** * 快速排序，选取最后一个元素作为参考，输出数组的非递减序列 * @param array 待排序的数组 * @param start 要排序数组的开始位置 * @param end 要排序数组的结束位置 */ public void quickSort(int array[] , int start , int end) { if(array == null || array.length < 2 || start >= end) { return; } //选取最后一个元素作为参考 int flag = array[end]; //记录大于flag的第一个元素位置 int i = start-1; //标识当前遍历的位置 int j = start ; while(j < end) { //当元素小于flag时，与++i进行交换 if( array[j] < flag) { i++; swap(array,i,j); } j++; } //将flag交换到合适的位置 int mid = i + 1; swap(array,mid,end); //对左右子数组进行递归排序 quickSort(array,start,mid -1); quickSort(array,mid + 1,end); } /** * 快速排序，选取最后一个元素作为关键值，输出数组的非递减序列 * @param array 待排序的数组 * @param start 要排序数组的开始位置 * @param end 要排序数组的结束位置 */ public void quickSort2(int array[] , int start , int end) { if(array == null || array.length < 2 || start >= end) { return; } int flag = array[end]; //1.从左向右遍历，寻找比flag大的元素left //2.从右向左遍历，寻找比flag小的元素right //3.交换元素位置，直到left >= right ， 将参考值交换到合适的位置 int left = start; int right = end; while(left < right) { if(array[left] <= flag) { left++; }else if(array[right] >= flag) { right--; }else { swap(array,left,right); } } //将flag交换到合适的位置 swap(array,left,end); //对左右子数组进行递归排序 quickSort2(array,start,left -1); quickSort2(array,left + 1,end); } /** * 交换数组中两元素的位置 * @param array * @param x * @param y */ private void swap(int array[] , int x , int y) { int temp = array[x]; array[x] = array[y]; array[y] = temp; }
