快速排序算法

2015-08-14 21:23 阅读 2,994 次 评论 0 条
版权声明:本文著作权归TeachCourse所有,未经许可禁止转载,谢谢支持!
转载请注明出处:http://teachcourse.cn/329.html

一.摘要

什么是快速排序算法?在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.      }  
关注公众号 扫一扫二维码,加我QQ

如果文章对你有帮助,欢迎点击上方按钮关注作者

来源:TeachCourse每周一次,深入学习Android教程,关注(QQ1589359239或公众号TeachCourse)
转载请注明出处:http://teachcourse.cn/329.html
分类:数据结构 标签:,
关于如何解决“NoClassDefFoundError”错误的问题? 关于如何解决“NoClassDefFo
HashMap方法解析 HashMap方法解析
浅谈OptionMenu选项菜单 浅谈OptionMenu选项菜单
Android开发之Genymotion安装第三方软件的“APP not installed”问题 Android开发之Genymotion安装第

发表评论

呲牙 憨笑 坏笑 偷笑 色 微笑 抓狂 睡觉 酷 流汗 鼓掌 大哭 可怜 疑问 晕 惊讶 得意 尴尬 发怒 奋斗 衰 骷髅 啤酒 吃饭 礼物 强 弱 握手 OK NO 勾引 拳头 差劲 爱你

表情