一.摘要
什么是快速排序算法?在Java或Android中如何使用?基本思路:从数组中选择一个基准元素key,通常选择第一个元素或最后一个元素,然后将数组前后分别标记i和j,最后通过基准元素key从后往前遍历(即j--),直到找到小于key的那个数,然后交换这两个值;之后,再拿这个key从前往后遍历(即i++),如果找到大于key的那个数,则交换彼此的值,直到循环i==j,结束遍历。
二.封装
知识点;
1.判断当前数组是否支持快速排序,即数组不为null而且长度大于1
- private boolean isArray(int array[]){
- if(null!=array&&array.length>1){
- return true;
- }
- return false;
- }
2.选定一个基准数key,第一遍排序:基准元素key大于左边的所有值,同时key小于右边所有值
- public int getMiddle(int[] list, int low, int high) {
- int tmp = list[low]; //数组的第一个作为中轴
- while (low < high) {
- while (low < high && list[high] >= tmp) {
- high--;
- }
- list[low] = list[high]; //比中轴小的记录移到低端
- while (low < high && list[low] <= tmp) {
- low++;
- }
- list[high] = list[low]; //比中轴大的记录移到高端
- }
- list[low] = tmp; //中轴记录到尾
- return low; //返回中轴的位置
- }
3.快速排序的原理:保证基准元素key大于左边所有值,小于右边所有值,最后递归完成排序。
- public void quickSort(int[] list, int low, int high) {
- if (low < high) {
- int middle = getMiddle(list, low, high); //将list数组进行一分为二
- quickSort(list, low, middle - 1); //对低字表进行递归排序
- quickSort(list, middle + 1, high); //对高字表进行递归排序
- }
- }
4.测试。
- public static void main(String args[]) {
- int a[]={49,38,65,97,76,13,27,49}
- if(!isArray(a)){
- return;
- }
- quickSort(a,0,a.length-1);
- }
你可能感兴趣的文章
来源:TeachCourse,
每周一次,深入学习Android教程,关注(QQ158#9359$239或公众号TeachCourse)
转载请注明出处: https://www.teachcourse.cn/329.html ,谢谢支持!
转载请注明出处: https://www.teachcourse.cn/329.html ,谢谢支持!