快速排序算法

2015-08-14 21:23 评论 0 条

一.摘要

什么是快速排序算法?在Java或Android中如何使用?基本思路:从数组中选择一个基准元素key,通常选择第一个元素或最后一个元素,然后将数组前后分别标记i和j,最后通过基准元素key从后往前遍历(即j--),直到找到小于key的那个数,然后交换这两个值;之后,再拿这个key从前往后遍历(即i++),如果找到大于key的那个数,则交换彼此的值,直到循环i==j,结束遍历。

二.封装

知识点;

1.判断当前数组是否支持快速排序,即数组不为null而且长度大于1

  1. private boolean isArray(int array[]){  
  2.         if(null!=array&&array.length>1){  
  3.     return true;  
  4.     }  
  5.     return false;  
  6. }  

2.选定一个基准数key,第一遍排序:基准元素key大于左边的所有值,同时key小于右边所有值

  1. public int getMiddle(int[] list, int low, int high) {       
  2.             int tmp = list[low];    //数组的第一个作为中轴       
  3.             while (low < high) {       
  4.                   while (low < high && list[high] >= tmp) {       
  5.                       high--;       
  6.                   }       
  7.                   list[low] = list[high];   //比中轴小的记录移到低端       
  8.                   while (low < high && list[low] <= tmp) {       
  9.                       low++;       
  10.                   }       
  11.                   list[high] = list[low];   //比中轴大的记录移到高端       
  12.               }       
  13.              list[low] = tmp;              //中轴记录到尾       
  14.              return low;                   //返回中轴的位置       
  15.   }   

3.快速排序的原理:保证基准元素key大于左边所有值,小于右边所有值,最后递归完成排序。

  1. public void quickSort(int[] list, int low, int high) {       
  2.     
  3.             if (low < high) {      
  4.     
  5.                int middle = getMiddle(list, low, high);  //将list数组进行一分为二       
  6.     
  7.                 quickSort(list, low, middle - 1);        //对低字表进行递归排序       
  8.     
  9.                 quickSort(list, middle + 1, high);       //对高字表进行递归排序       
  10.     
  11.             }       
  12.     
  13.         }   

4.测试。

  1. public static void main(String args[]) {  
  2.            
  3.          int a[]={49,38,65,97,76,13,27,49}  
  4.   
  5.      if(!isArray(a)){  
  6.          return;  
  7.      }  
  8.      quickSort(a,0,a.length-1);  
  9.            
  10.      }  

当前文章价值2.61元,扫一扫支付后添加微信提供帮助!(如不能解决您的问题,可以申请退款)

你可能感兴趣的文章

来源:每日教程每日一例,深入学习实用技术教程,关注公众号TeachCourse
转载请注明出处: https://www.teachcourse.cn/329.html ,谢谢支持!

资源分享

分类:数据结构 标签:,
调试最快的Android模拟器-Genymotion常见问题 调试最快的Android模拟器-Geny
windows系统自动化批处理命令 windows系统自动化批处理命令
一个例子让我理解WebViewClient各方法重写的作用 一个例子让我理解WebViewClie
Android Studio “Live Templates”如何提升编程效率? Android Studio “Live Temp