数组和单链表的快速排序（JAVA）

数组实现

枢纽值的选取用的是三数选一法，即在首、尾、中间位置的三个数中选择数值位于中间的那一个数。

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);
    }
    
}