数组实现
枢纽值的选取用的是三数选一法，即在首、尾、中间位置的三个数中选择数值位于中间的那一个数。
public class QuickSort {
public static int partition(int []num,int left,int right){
//三数取中
int mid = left + (right-left)/2;//
if(num[mid] > num[right]){
swap(num[mid], num[right]);
}
if(num[left] > num[right]){
swap(num[left], num[right]);
}
if(num[mid] > num[left]){
swap(num[mid], num[left]);
}
int base = num[left];//此处保证在left处存储的是三个数中处于中间的数
while(left < right){
while(num[right] >= base && right > left){//找到从右起下一个比base小的值
right--;
}
num[left] = num[right];
while(num[left] <= base && right > left){//找到从左起下一个比base大的值
left++;
}
num[right] = num[left];
}
num[right] = base;//定下base值应在的位置
return right;
}
//递归实现快排
public void quickSort(int num[],int left,int right){
if(left < right) {
int index=partition(num,left,right); //将数组分区，获得base值所在的位置
quickSort(num,left,index-1); //搜索左边的子数组
quickSort(num,index+1,right); //搜索右边的子数组
}
}
public static void swap(int a,int b){
int temp=a;
a=b;
b=temp;
}
}
单链表实现
用三个指针来控制，pBase指针指向枢纽值结点，pleft指针指向当前最后一个比枢纽值小的结点，pright结点用于遍历，将遇到的比pBase小的结点跟pleft交换，将其放到前面一段去。
- 可以理解为：链表的快排就是在left 和 right 指针之间维护比枢纽值大的数据
- 其最终效果大致为：[pBase, 小值, pleft，大值，pright，未处理值]
-
最终将 pleft 和 pBase 交换，就可以得到一轮排好序的值。
public class QuickSortList {
public void quickSort(LNode head, LNode tail) {
if(head == null || head == tail)
return ;
LNode pBase = head;//作为枢纽值的结点
LNode pleft = pBase;//指向当前最后一个比枢纽值小的结点,pBase与pleft之间的结点值始终都比枢纽值小，
LNode pright = pBase.next;//指向比枢纽值大的结点
int temp;
while(pright != tail) {
//作为遍历的pright指针，此时当pright找到了下一个比基准值小的结点，就把pleft右移，将pright的值与pleft交换
if(pright.val < pBase.val) {
pleft = pleft.next;//移向下一个存储小值的位置
if(pright != pleft) {
temp = pleft.val;
pleft.val = pright.val;
pright.val = temp;
}
}
pright = pright.next;
}
temp = pBase.val;
pBase.val = pleft.val;
pleft.val = temp;//原pleft的下一个结点就比枢纽值大
quickSort(pBase, pleft);
quickSort(pleft.next, tail);
}
}
