内容简介:排序这个序列:6 1 2 7 9 3 4 5 10 8
举个例子
排序这个序列:6 1 2 7 9 3 4 5 10 8
- 步骤1:选择一个基准数作为对比的开始值,这里选择第一个数6:
- 步骤2、先从右往左找一个小于 6 的数,再从左往右找一个大于 6 的数。
- 步骤3、然后交换他们
变成这样子:
继续执行步骤2和3,直到两个哨兵相遇,:
左右两个哨兵都走到3:
- 步骤4:将开始选择基准数字6换到中间,测试6左边的数都小于6,右边的数都大于6。完成第一次循环:
第一次完成之后,再按照此方法分别对6左右两边的数列进行递归排序即可。是不是很简单。
看下代码就更清晰了:
void quicksort(int a[], int left,int right) { int i,j,t,temp; if(left>right) return; temp=a[left]; //temp中存的就是基准数 i=left; j=right; while(i!=j) { //顺序很重要,要先从右边开始找 while(a[j]>=temp && i<j) j--; //再找右边的 while(a[i]<=temp && i<j) i++; //交换两个数在数组中的位置 if(i<j) { t=a[i]; a[i]=a[j]; a[j]=t; } } //最终将基准数归位 a[left]=a[i]; a[i]=temp; quicksort(a, left,i-1);//继续处理左边的,这里是一个递归的过程 quicksort(a, i+1,right);//继续处理右边的 ,这里是一个递归的过程 }
也可以这么写:
/** * 快排 * @param arr * @param low * @param high * @return */ public static int[] quit(int arr[], int low, int high) { int l = low; int h = high; int key = arr[l]; //先找出一个数作为基准数(这里取数组最中间的一位) while (l < h) { while (l < h && arr[h] >= key) h --; //从后向前:寻找比基准数小的数据,如果找到,停下来 if (l < h) { //“探测”到了符合要求的数据,则交换数据,继续顺着方向寻找 arr[l] = arr[h]; l ++; } while (l < h && arr[l] <= key) l ++; //从前向后:寻找比基准数大的数据,如果找到,停下来 if (l < h) { ////“探测”到了符合要求的数据,则交换数据,继续顺着方向寻找 arr[h] = arr[l]; h --; } } arr[l] = key; if (l > low) quit(arr, low, l - 1); if (h < high) quit(arr, h + 1, high); return arr; }
热度: 1
以上所述就是小编给大家介绍的《教你学习快速排序算法-程序员必备哦》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!
猜你喜欢:- 程序员如何提升算法思维?
- 程序员必知必会的十大排序算法
- 程序员笔试面试最爱考察的算法,到底怎么搞定?
- 程序员 520 表白:我写算法只为找到你!
- 程序员需要了解的硬核知识之压缩算法
- 深入浅出排序学习:写给程序员的算法系统开发实践
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。