快速排序是一种非常优秀的排序算法,应用的也非常广泛,面试时面试官也经常让你手写一个快排,所以说学习快速排序是非常有必要的。
同归并排序一样,快速排序也是一种分治的排序算法。在归并排序中,通过将数组分成两个子数组进行排序,然后对两个有序的子数组进行归并以将整个数组排序。而快速排序则是选定一个基准值,然后将大于该值的元素放在该元素后面,小于该值的元素放在该值前面。通过不断的递归调用来完成排序。
public static void main(String[] args) {
int[] a = {9, 45, 10, 35, 64, 99, 103, 56, 47, 12, 79, 0};
sort(a, 0, a.length - 1);
}
public static void sort(int[] arr, int left, int right) {
if (right <= left)
return;
}
int t = partition(arr, left, right);
sort(arr, left, t - 1);
sort(arr, t + 1, right);
}
public static int partition(int[] arr, int left, int right) {
int i = left;
int j = right + 1;
int t = arr[left];
while (true) {
while (arr[++i] < t) {
if (i == right) {
break;
}
}
while (arr[--j] > t) {
if (j == left) {
break;
}
}
if (i >= j) {
break;
}
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
int temp = arr[left];
arr[left] = arr[j];
arr[j] = temp;
return j;
}
代码也是很容易就能够看懂,通过使用双指针,不断地与基准值进行比较,将大于基准值的元素放在基准值后面,将小于基准值的元素放在基准值前面,当两个指针相遇时则说明已经摆放完毕,然后将基准值与j所对应的元素交换,通过这样不管的递归调用,即可完成排序。
所谓三向切分,就是维护三个指针,维护一个指针使得某块元素小于基准值,维护一个指针使得某块元素等于基准值,维护一个指针使得某块元素大于基准值。
public static void main(String[] args) {
int[] a = {4, 1, 90, 14, 50, 64, 70, 7, 12, 36, 97, 43, 21, 12};
sort(a, 0, a.length - 1);
System.out.println(Arrays.toString(a));
}
public static void sort(int[] arr, int left, int right) {
if (right <= left) {
return;
}
int i = left, j = right, k = left + 1;
int M = arr[left];
while (k <= j) {
if (arr[k] < M) {
int temp = arr[i];
arr[i] = arr[k];
arr[k] = temp;
i++;
k++;
} else if (arr[k] > M) {
int temp = arr[k];
arr[k] = arr[j];
arr[j] = temp;
j--;
} else {
k++;
}
sort(arr, left, i- 1);
sort(arr, j + 1, right);
}
}
和上面的双指针方法基本一样,只是多维护了一个指针。
在快排的过程中,我们需要取一个枢纽值,一般都是取left所对应元素的值,但那样容易出现数组一边倒的情况,所以我们使用三数取中法,也就是取左端、右端、中间三个数,然后对这些数进行排序,将中间值作为枢纽值。
public static void main(String[] args) {
int[] a = {9, 45, 10, 35, 64, 99, 103, 56, 47, 12, 79, 0};
sort(a, 0, a.length - 1);
for (int tt : a) {
System.out.print(tt+" ");
}
}
public static void sort(int[] arr, int left, int right) {
if(right<=left) {
return;
}
threeSplit(arr, left, right);
int i = left, j = right - 1, t = right - 1;
while (true) {
while (arr[++i] < arr[t]) {
if (i == right) {
break;
}
}
while (j>left&&arr[--j] > arr[t]) {
if (j == left) {
break;
}
}
if (i >= j) {
break;
}
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
if (i < right) {
int temp = arr[i];
arr[i] = arr[right - 1];
arr[right - 1] = temp;
}
sort(arr, left, i - 1);
sort(arr, i + 1, right);
}
public static void threeSplit(int[] arr, int left, int right) {
int mid = (left + right)>>>1;
if (arr[left] > arr[mid]) {
int temp = arr[left];
arr[left] = arr[mid];
arr[mid] = temp;
}
if (arr[left] > arr[right]) {
int temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
}
if (arr[mid] > arr[right]) {
int temp = arr[mid];
arr[mid] = arr[right];
arr[right] = temp;
}
int temp = arr[right-1];
arr[right - 1] = arr[mid];
arr[mid] = temp;
}
图解如下:
通过对快速排序的不断改进,我们发现一个细小的改动就可以提升很多性能,快速排序应用非常广泛,一定要掌握的很熟练。