快速排序"/>
Java,快速排序
写了好久的注释,将就着看吧,>_<
下面只是方法部分
public class Kspx
{//快速排序的实现/*** 通过数次根据大小的过滤,完成数组的排序* 以基准数为过滤的条件,将大于基准数的数和小于基准数的元素分开到基准数两边* 每一边都是继续找一个基准值进行过滤,直到边界重合,不能继续过滤* @param arr 需要排序的数组* @param left l哨兵的起点* @param right r哨兵的起点*/public void quickSort(int[] arr,int left,int right){int l = left;//左边的哨兵int r = right;//右边的哨兵int pivot = arr[(left + right) / 2];//基准数取中间的数while(l < r){while(arr[l] < pivot)//l哨兵没找到比基准数小的数就继续往后找{l++;}while(arr[r] > pivot)//r哨兵没找到比基准数大的数就继续往前找{r--;}if(l >= r)//如果l哨兵超过r哨兵就停止寻找{break;}int temp = arr[l];//交换l哨兵和r哨兵找到的元素arr[l] = arr[r];arr[r] = temp;if(arr[l] == pivot)//如果l哨兵找到的元素和r哨兵找到的元素都是基准数,就会进入死循环{r--;}if(arr[r] == pivot)//如果有一方因为找到的元素是基准数而停止寻找,则让另一方继续寻找{l++;}}if(l == r)//如果l哨兵和r哨兵处于同一个位置,则让l哨兵往右一步,让r哨兵往左一步,用以参与后面的递归。{l++;r--;}//只要还没排序完到边界,就会把被基准值分开的部分继续进行排序if(left < r){quickSort(arr,left,r);//以最终的r哨兵所在的元素的位置作为右边界,也就是下次调用时r哨兵的起点}if(l < right){quickSort(arr,l,right);//以最终的l哨兵所在的元素的位置作为左边界,也就是下次调用时l哨兵的起点}}
}
更多推荐
Java,快速排序
发布评论