快排之所以快,是因为采用了分治法,在每一轮挑选一个基准元素,并让其他比它大的元素移到数动到数列一边,比它小的元素移动到数列的另一边,从而把数列拆解成两个部分。
快排的平均时间复杂度是O(nlogn),但在极端情况下(数列的第一个元素为最小值或最大值),时间复杂度为O( n 2 n^2 n2)。
快排有两种方法:双边循环法、单边循环法。
双边循环法是选定基准元素pivot,并设置两个指针left、right,指向数列的最左和最右两个元素。
先从 right 指针开始,让指针指向的元素与基准元素比较,如果大于或等于pivot,则指针向左移动,如果小于pivot,则right指针停止移动,切换到left指针;让left指针所指向的元素与pivot比较,如果小于或等于pivot,则指针右移,如果大于pivot,则left指针停止移动。一轮循环结束让left和right指针指向的元素交换。
所有循环结束,pivot和指针重合点交换。
public class QuickSort {
public static void quickSort(int[] arr,int startIndex,int endIndex){
// 递归结束条件:startIndex大于或等于endIndex时
if(startIndex >= endIndex){
return;
}
// 得到基准元素位置
int pivotIndex = partition(arr,startIndex,endIndex);
// 根据基准元素,分成两部分进行递归排序
quickSort(arr,startIndex,pivotIndex - 1);
quickSort(arr,pivotIndex + 1, endIndex);
}
/**
* 分治法(双边循环法)
* @param arr
* @param startIndex
* @param endIndex
* @return
*/
private static int partition(int[] arr, int startIndex, int endIndex) {
// 取第1个位置(也可以选择随机位置)元素为基准元素
int pivot = arr[startIndex];
int left = startIndex;
int right = endIndex;
while (left != right){
// 控制right指针比较并左移
while (left < right && arr[right] > pivot){
right--;
}
// 控制left指针比较并右移
while (left < right && arr[left] <= pivot){
left++;
}
// 交换left和right指针所指向的元素
if(left < right){
int p = arr[left];
arr[left] = arr[right];
arr[right] = p;
}
}
// pivot和指针所指向的元素
arr[startIndex] = arr[left];
arr[left] = pivot;
return left;
}
public static void main(String[] args) {
int[] arr = new int[]{4,4,6,5,3,10,2,8,1,9};
quickSort(arr,0,arr.length-1);
System.out.println(Arrays.toString(arr));
}
}
双边循环法从数组两边交替遍历元素,虽然更加直观,但代码实现相对繁琐。单边循环法则简单的多,只从数组的一边对元素进行遍历和交换。与双边循环法类似,先选定基准元素pivot,再设置一个mark指针指向数列起始位置,这个mark指针代表小于基准元素的区域边界。
从基准元素的下一个元素开始遍历数组,如果遍历到的元素大于基准元素,就继续遍历;如果小于基准元素,则做两件事:把mark指针右移1位、让最新遍历到的元素和mark指针所在位置的元素交换位置。
public class QuickSort_single {
public static void QuickSort(int[] arr,int startIndex,int endIndex){
// 递归结束条件:starkIndex大于或等于endIndex
if(startIndex >= endIndex){
return;
}
// 得到基准元素位置
int pivotIndex = partition(arr,startIndex,endIndex);
// 根据基准元素,分成两部分进行递归排序
QuickSort(arr,startIndex,pivotIndex - 1);
QuickSort(arr,pivotIndex + 1, endIndex);
}
/**
* 分治(单边循环法)
* @param arr
* @param startIndex
* @param endIndex
* @return
*/
private static int partition(int[] arr, int startIndex, int endIndex) {
//取第1个位置(也可以选择随机位置)元素为基准元素
int pivot = arr[startIndex];
int mark = startIndex;
for(int i = startIndex + 1; i <= endIndex; i++){
if(arr[i] < pivot){
mark++;
int p = arr[mark];
arr[mark] = arr[i];
arr[i] = p;
}
}
arr[startIndex] = arr[mark];
arr[mark] = pivot;
return mark;
}
public static void main(String[] args) {
int[] arr = new int[]{8,7,9,2,6,4,5,1,3};
QuickSort(arr,0,arr.length-1);
System.out.println(Arrays.toString(arr));
}
}