快速排序分析和递归实现(java)

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了快速排序分析和递归实现(java)，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1751字，纯文字阅读大概需要3分钟。

内容图文

目录

• 分析
• 一.快速排序的思想
• 二.partition函数如何实现
• 递归实现

分析

一.快速排序的思想

• 取数组中的第一个元素作为标准值，把小于标准值的元素放在其左侧smaller区域，把大于标准值的元素放在其右侧larger区域。那么标准值的位置就移动到了排序完成以后他应该在的位置。
• 把smaller,larger两部分分别通过这种方式进行排序。
  
  数组5 4 2 7 3 6 为例,[ ]括起来的是此次比较的标准值：
  第一轮后：4 2 3 [5] 7 6
  第二轮后：2 3 [4] 5 6 [7]
  第三轮后：2 [3] 4 5 [6] 7
  第四轮后：[2] 3 4 5 6 7
  第五轮后：2 3 4 5 6 7

二.partition函数如何实现

partition函数的功能：实现将数组的值分为<v和>v区域

我们从数组的中间状态开始讨论。
如图L指向标准值v，J指向<v区的最后一个元素，i指向待分类元素。那么arr[L+1…J]是<v区，arr[J+1…i-1]是>v区。

• 若e>v，将i向右移动一位，那么e就被归入了>v的区域。i也指向了下一个待分类数据的位置。
  
• 若e<=v
  1.将e与>v区域的第一个值交换
  
  2.J++将元素e归入<v的部分，i++进行对下个数据的分类。

递归实现

     public static void quickSort(int[] arr){
         quickSort(arr,0,arr.length-1);
     }
     
     public static void quickSort(int[] arr,int l,int r){
         if(l>=r){
             return;
         }
         int p=partition(arr,l,r);
         quickSort(arr,l,p-1);
         quickSort(arr,p+1,r);
     }

     //返回的p使得arr[l..p-1]<arr[p],arr[p+1...r]>arr[p]
     public static int partition(int[] arr,int left,int right){
         //数组结构：|v|smallerPart|largerPart|unPaitition
         //arr[left+1...j]<v     arr[j+1...i)>v
         
         int j=left;//smaller部分的最后一个数据的下标
         int i=left+1;//待分类的数值的下标
         
         //依次把每个值分类
         while(i<=right){
             if(arr[i]<=arr[left]){
                 //若当前数据小于等于判别值，当前值与larger区域的最小值交换
                 //最终smaller部分扩大1，待判别指针向前移动
                 int temp=arr[i];
                 arr[i]=arr[j+1];
                 arr[j+1]=temp;
                 j++;
             }
             i++;
             //若当前数据大于判别值，将待判别数据向前移动一个即可，当前数据将自动归入larger区域
         }
         //分类完成，交换v和smaller区的最后一个值
         int temp=arr[left];
         arr[left]=arr[j];
         arr[j]=temp;
         //最后返回判别值的位置
         return j;
     }

内容总结

以上是互联网集市为您收集整理的快速排序分析和递归实现(java)全部内容，希望文章能够帮你解决快速排序分析和递归实现(java)所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---