排序算法之快速排序
快速排序
快速排序是一种非常优秀的排序算法，应用的也非常广泛，面试时面试官也经常让你手写一个快排，所以说学习快速排序是非常有必要的。
快速排序原理
同归并排序一样，快速排序也是一种分治的排序算法。在归并排序中，通过将数组分成两个子数组进行排序，然后对两个有序的子数组进行归并以将整个数组排序。而快速排序则是选定一个基准值，然后将大于该值的元素放在该元素后面，小于该值的元素放在该值前面。通过不断的递归调用来完成排序。
动图演示
快速排序动图演示
代码实现
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;
}图解如下：
图片演示
图片演示
总结
通过对快速排序的不断改进，我们发现一个细小的改动就可以提升很多性能，快速排序应用非常广泛，一定要掌握的很熟练。
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2019-12-12 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录