1、快速排序是一种比较高效的排序算法,采用“分而治之”的思想,通过多次比较和交换来实现排序,在一趟排序中把将要排序的数据分成两个独立的部分,对这两部分进行排序使得其中一部分所有数据比另一部分都要小,然后继续递归排序这两部分,最终实现所有数据有序。
2、快速排序图
3、Java 代码实现快速排序
public static void main(String[] args) {
int[] arry = {9,8,7,6,5,4,3,2,1};
quickSort(arry,0, arry.length-1);
System.out.println(Arrays.toString(arry));
}
public static void quickSort(int[] arry,int left,int right){
//运行判断,如果左边索引大于右边是不合法的,直接return结束次方法
if(left>right){
return;
}
//定义变量保存基准数
int base = arry[left];
//定义变量i,指向最左边
int i = left;
//定义j ,指向最右边
int j = right;
//当i和j不相遇的时候,再循环中进行检索
while(i!=j){
//先由j从右往左检索比基准数小的,如果检索到比基准数小的就停下。
//如果检索到比基准数大的或者相等的就停下
while(arry[j]>=base && i<j){
j--; //j从右往左检索
}
while(arry[i]<=base && i<j){
i++; //i从左往右检索
}
//代码走到这里i停下,j也停下,然后交换i和j位置的元素
int tem = arry[i];
arry[i] = arry[j];
arry[j] = tem;
}
//如果上面while条件不成立就会跳出这个循环,往下执行
//如果这个条件不成立就说明 i和j相遇了
//如果i和j相遇了,就交换基准数这个元素和相遇位置的元素
//把相遇元素的值赋给基准数这个位置的元素
arry[left] = arry[i];
//把基准数赋给相遇位置的元素
arry[i] = base;
//基准数在这里递归就为了左边的数比它小,右边的数比它大
//排序基准数的左边
quickSort(arry,left,i-1);
//排右边
quickSort(arry,j+1,right);
}
4、这个是面试常考的算法之一,后续将继续更新剩下的几种。
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)