排序算法-快速排序 蔚落 2022-06-01 06:17 233阅读 0赞 快速排序 是最高效、不占用空间的一种排序算法 快排的精髓 是在于 找到 中间基数。 比中间基数小的放在左边 ,比中间基数大的放在右边 然后 左右各自进行快排。 参考博客:[http://developer.51cto.com/art/201403/430986.htm][http_developer.51cto.com_art_201403_430986.htm] ![这里写图片描述][SouthEast] 首先 以数组第一个数字作为基数 数组从最左是低位,最右是高位 刚开始 低位 就是基数 比较基数 和 高位 如果基数比高位小 高位减减 直到 基数大于 高位 交换位置 然后比较低位 和 基数 低位 小于基数 低位加加 直到低位大于基数 交换位置 又开始比较高位 …… 直到 低位下标和高位下标重合 (低位下标不小于高位) 然后将基数赋值给 低位(或高位) 第一次比较 结束 比基数小的 在左边 比基数大的在右边 将 基数 下标返回 迭代 继续对左右两边 进行排序 实现代码: package quicksort; import java.util.Arrays; public class QuickSort { public static void main(String[] args) { int[] arr = { 34,45,12,89,25,76,44,90,1,62,59}; quickSort(arr,0,arr.length-1); System.out.println(Arrays.toString(arr)); } public static int getMiddle(int[] arr,int low,int high){ int tmp =arr[low]; while(low<high){ while (low<high && arr[high]>tmp){ high--; } arr[low]=arr[high]; while (low<high && arr[low]<tmp){ low++; } arr[high]=arr[low]; } arr[low] =tmp; return low; } public static void quickSort(int[] arr,int low,int high){ if(low<high){ int i = getMiddle(arr,low,high); //将数组一分为二 quickSort(arr,low,i-1); quickSort(arr,i+1,high); } } } [http_developer.51cto.com_art_201403_430986.htm]: http://developer.51cto.com/art/201403/430986.htm [SouthEast]: /images/20220601/e2a0617be7ea4d70be213d509be4286c.png
还没有评论,来说两句吧...