江苏龙网

  1. 主页 > 生活百科 > >

java快速排序

排序

快速排序是一种非常高效的排序算法 ， 它的实现 ， 增大了记录和比较和移动的距离 ， 从而减少总的比较此时和移动次数 。采用分而治之的思想 ， 将一个大的问题拆成一个小的问题 ， 小的问题拆成更小的问题 。
public static void quickSort(int []array,int low,int high) {
if(low>=high){
return;
}
int left=low;
int right=high;
int base = array[low];
while (left!=right) {//从后面开始检索 遇到比基准数小的就停下 ， 遇到比基准数大于等于的就继续检索
while (array[right]>=base&&left<right) {//left小于right 防止越界 比如数组内所有元素都比base小就会一路走下去
right--;
}
while (array[left] <= base&&left<right) {
left++;
}
 
int temp=array[left];
array[left]=array[right];
array[right]=temp;
}
//交换基准值和相遇位置的值
【java快速排序】array[low]=array[left];//相遇的值一定小于基准值
array[left]=base;
quickSort(array,low,left-1);
quickSort(array,left+1,high);
}
快速排序
时间复杂度最好情况是都能分割成较完美的两部分 O（nlog(n)）,最坏情况是数组是有序的每次分割只有一边 O（n^2）
空间复杂度为O（nlog(n)） 稳定性：不稳定
快速排序再最坏的情况下可以优化 ， 即优化基准值
三数取中法即low mid high 取中间大小的数字为基准值




    推荐阅读


    上一篇：Spring boot的logback配置

    下一篇：Chosen One掀起Web 3.0时代内容新革命