这篇文章运用简单易懂的例子给大家介绍java如何实现快速排序,代码非常详细,感兴趣的小伙伴们可以参考借鉴,希望对大家能有所帮助。
快速排序又称分区交换排序(partition-exchange sort),简称快排,一种排序算法。
在平均状况下,排序n个项目要O(nlog n)(大O符号)次比较。在最坏状况下则需要 O(n^2)次比较,但这种状况并不常见。事实上,快速排序O(nlog n)通常明显比其他算法更快,因为它的内部循环(inner loop)可以在大部分的架构上很有效率地达成。
快速排序使用分治法(Divide and conquer)策略来把一个序列(list)分为较小和较大的2个子序列,然后递归地排序两个子序列。
步骤为:
挑选基准值:从数列中挑出一个元素,称为“基准”(pivot)。
分割:重新排序数列,所有比基准值小的元素摆放在基准前面,所有比基准值大的元素摆在基准后面(与基准值相等的数可以到任何一边)。在这个分割结束之后,对基准值的排序就已经完成。
递归排序子序列:递归地将小于基准值元素的子序列和大于基准值元素的子序列排序。
递归到最底部的判断条件是数列的大小是零或一,此时该数列显然已经有序。
选取基准值有数种具体方法,此选取方法对排序的时间性能有决定性影响。
代码实现:
public class QuickSort { public static void main(String[] args) { int[] arr = SortUtil.randomArr(6); SortUtil.printArr(arr); // sort(arr,0,arr.length-1); sort1(arr,0,arr.length-1); // int[] arr1= netherlands(arr,0,arr.length-1); // SortUtil.printArr(arr1); SortUtil.printArr(arr); } /** * 快排1.0,时间复杂度O(n²),找出以arr[right]为界的中间位置,小于等于的放左边,大于等于的放右边 * 分为左右2个区域,每个区域重复上面的步骤,直到最后left=right * @param arr * @param left * @param right */ public static void sort(int[] arr,int left,int right){ if(left>=right){return;} int mid = partition(arr,left,right); sort(arr,left,mid-1); sort(arr,mid+1,right); } /** * 快排2.0 以arr[right]作为中间值,最差情况时间复杂度O(n²),平均时间复杂度为 O(n logn) * @param arr * @param left * @param right */ public static void sort1(int[] arr,int left,int right){ if(left>=right){return;} int[] mid = netherlands(arr,left,right); sort1(arr,left,mid[0]-1); sort1(arr,mid[1]+1,right); } private static int partition(int[] arr, int left, int right) { if (left > right) { return -1; } if (left == right) { return left; } int lessEqual = left - 1; int index = left; while (index < right) { // 情况1,当前位置小于等于标记值,当前位置不动,标记右移 if (arr[index] <= arr[right]) { lessEqual++; // 扩大小于等于区域 SortUtil.swap(arr, index, lessEqual); } index++; } // 右边界位置和大于区域的起始位置交换 SortUtil.swap(arr, ++lessEqual, right); return lessEqual; } /** * 荷兰国旗问题 * @param arr * @param left * @param right * @return */ private static int[] netherlands(int[] arr,int left,int right){ if(left>right){ return new int[]{-1,-1}; } if(left==right){ return new int[]{left,right}; } int lessEqual = left-1; int i = left; int more = right; while (i<more){ // 1.i位置==arr[right],i++ if (arr[i]==arr[right]){ i ++; } // 2.i位置<arr[right],i位置与小于区域右一个位置交换 else if (arr[i]<arr[right]){ SortUtil.swap(arr,++lessEqual,i++); } // 3.i位置>arr[right],i位置与大于区域左一个位置交换,i不动 else if(arr[i]>arr[right]){ SortUtil.swap(arr,i,--more); } } SortUtil.swap(arr,right,more); return new int[]{lessEqual+1,more}; } }
关于java如何实现快速排序就分享到这里了,希望以上内容可以对大家有一定的帮助,可以学到更多知识。如果觉得文章不错,可以把它分享出去让更多的人看到。
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。