- 快速排序的单趟排序
快速排序的单趟排序:是以一个数作为基准值，实现将数组中比基准数小的数放在基准值的左侧，比基准值大的数放在基准值的右侧。
方法一：霍尔法
霍尔法的由来：霍尔是一个人的名字，他是最初发现快速排序的人，所以，它使用的单趟排序算法被称为霍尔法。
1.基本思路：
用key标记基准值的下标(数组下标0的元素)，使用两个指针left和right分别指向待排数组的最左侧和最右侧，right指针找比key基准值小的数，left指针找比key基准值大的数，找到后将两个数交换位置，同时实现大数右移和小数左移，直到left与right相遇则排序完成，最后将key基准值的下标返回，就完成了单趟排序。
package LiKou;
public class QuickSort {
public static void main(String[] args) {
int[] arr = {10,7,2,4,7,62,3,4,2,1,8,9,19};
quickSort(arr,0,arr.length-1);
for (int i = 0; i < arr.length; i++) {
System.out.println(arr[i]);
}
}
public static void quickSort(int[] arr,int low,int high){
int i,j,temp,t;
if(low>high){
return;
}
i=low;
j=high;
//temp就是基准位 temp = arr[low];
while (i<j) {
//先看右边，依次往左递减
while (temp<=arr[j]&&i<j) {
j--;
}
//再看左边，依次往右递增
while (temp>=arr[i]&&i<j) {
i++;
}
//如果满足条件则交换
if (i<j) {
t = arr[j];
arr[j] = arr[i];
arr[i] = t;
}
}
//最后将基准为与i和j相等位置的数字交换
arr[low] = arr[i];
arr[i] = temp;
//递归调用左半数组
quickSort(arr, low, j-1);
//递归调用右半数组
quickSort(arr, j+1, high);
}
}
方法二：挖坑法1.基本思路：挖坑法是将key基准值用变量单独保存，然后将key的位置空出来形成一个坑，left和right指针分别从左右两端向中心遍历，此时left先指向这个坑，从右边先开始，right找比key小的数，找到后将该数直接放进坑里，并将自己空出来的位置设置为坑，left找比key大的数，找到后将该数放进坑里，并将现在空出来的位置设置为坑，一直遍历，直到left与right相遇，相遇位置一定为坑(left和right必定有一个指向坑)，此时将key基准值放进坑内，并返回基准值下标完成单趟排序。
package LiKou;
public class QuickSort2 {
public static void main(String[] args) {
int[] arr = {10,7,2,4,7,62,3,4,2,1,8,9,19};
Quick3(arr,0,arr.length-1);
for (int i = 0; i < arr.length; i++) {
System.out.println(arr[i]);
}
}
public static void Quick2(int[] arr,int left,int right){
if(left>right){
return;
}
int key=arr[left];
int pre=left;
int cur=left+1;
while(cur<=right){
if(arr[cur]<=key && ++pre!=cur){
int temp=arr[cur];
arr[cur]=arr[pre];
arr[pre]=temp;
}
cur++;
}
int temp=arr[left];
arr[left]=arr[pre];
arr[pre]=temp;
Quick2(arr,pre+1,right);
Quick2(arr,left,pre-1);
}
public static void Quick3(int[] arr,int left,int right){
if(left>=right){
return;
}
int key=arr[left];
int i=left;
int j=right;
while(i<j){
while(j>i && arr[j]>=key){
j--;
}
if(j>i){
arr[i]=arr[j];
}
while(i<j && arr[i]<=key){
i++;
}
if(j>i){
arr[j]=arr[i];
}
}
arr[i]=key;
Quick3(arr,left,i-1);
Quick3(arr,i+1,right);
}
}方法三：前后指针法
1.基本思路：
（1） 用key保存数组第一个元素作为基准值，定义前指针prev指向第一个数，后指针cur指向前指针的后一个位置。
（2） 由cur挨个遍历数组中的数据，如果cur寻找比key基准值小的数，则prev后移一个位置，并且交换cur和prev所对应的元素值，cur和prev位置不变。
（3） 依次类推直到cur完全遍历完数组，停止。
prev之前的值一定小于key基准值，而prev与cur之间的一定大于基准值文章来源：https://www.toymoban.com/news/detail-823606.html
最后将prev处与key位置的元素交换，将基准值下标返回（此时基准值下标已经交换到prev位置）。则完成单趟排序。文章来源地址https://www.toymoban.com/news/detail-823606.html
package LiKou;
public class QuickSort2 {
public static void main(String[] args) {
int[] arr = {10,7,2,4,7,62,3,4,2,1,8,9,19};
Quick2(arr,0,arr.length-1);
for (int i = 0; i < arr.length; i++) {
System.out.println(arr[i]);
}
}
public static void Quick2(int[] arr,int left,int right){
if(left>right){
return;
}
int key=arr[left];
int pre=left;
int cur=left+1;
while(cur<=right){
if(arr[cur]<=key && ++pre!=cur){
int temp=arr[cur];
arr[cur]=arr[pre];
arr[pre]=temp;
}
cur++;
}
int temp=arr[left];
arr[left]=arr[pre];
arr[pre]=temp;
Quick2(arr,pre+1,right);
Quick2(arr,left,pre-1);
}
}到了这里，关于快速排序的三种实现方法的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
