高级排序算法之快速排序 _排序算法

前言今天继续算法学习，本次学习的是高级排序之快速排序。本文代码部分存在调用公共方法，可在文章：简单排序算法之冒泡、插入和选择排序-Java实现版，高级排序之归并排序、希尔排序。中查找相关方法，另外，本文也提供测试时使用的完整代码，对其他算法不感兴趣，可在文末找到完整源代码。
快速排序快速排序的本质就是把一个数组划分为两个子数组，然后递归地调用自身为每一个数组进行“快速排序”来实现的。这里就涉及一个问题：如何划分？
在快速排序中，为了划分数组，提出了“枢纽”这个词，它代表待排序序列中的一个数据项。快速排序利用枢纽将数组划分成两部分，一部分（枢纽左侧）是所有小于该枢纽表示的数据项，另一部分（枢纽右侧）则都大于该枢纽表示的数据项（注意，此时左右两侧的数据项是无序的），枢纽放置在左右两侧的中间，此时该枢纽已经处在排序的正确位置上了（枢纽是快速排序所排序的对象，实现“排序”的关键点就是调整枢纽的位置）。通过递归的这样划分，最终出现左侧只有一个数据项（该数据项既是左侧子数组又是枢纽），则结束左侧递归，开始划分右侧数组。。。以此类推。这里又产生了一个问题，如何选择枢纽？
选择枢纽的算法：最简单的选择枢纽算法就是每次递归都选择数组的最后一个数据项做为枢纽（或者选择最左侧的数据项作枢纽）。

文章插图
上图演示了以子数组最右侧数据项做枢纽的排序过程
代码演示（枢纽始终使用子数组的最右侧数据项）

private static int partitionIt(int left,int right,int pivot,int[] array){int leftPtr = left-1;int rightPtr = right;while(true){// 查找左侧子数组大于枢纽的位置while(compare(array[++leftPtr],pivot)<0){}// 查询右侧子数组小于枢纽的位置while(rightPtr>0&&compare(array[--rightPtr],pivot)>0){}if(leftPtr>=rightPtr){break;}// 交换需要调整位置的两个数据项swap(leftPtr,rightPtr,array);}// 将枢纽挪到两侧中间swap(leftPtr,right,array);return leftPtr;}private static void recQuickSort(int left,int right,int[] array){if(right-left<=0){return;}// 选择的枢纽int pivot = array[right];int partition = partitionIt(left,right,pivot,array);recQuickSort(left,partition-1,array);recQuickSort(partition+1,right,array);}public static void quickSort(int[] array){compareCount=0;swapCount=0;long start = new Date().getTime();recQuickSort(0,array.length-1,array);long end = new Date().getTime();printResult("快速排序","交换次数",start,end);}

运行结果【高级排序算法之快速排序】