快速排序

首先你得先学会荷兰国旗分组 , 然后再次递归进行排序 , 就是随机快速排序

①快速排序问什么要随机选择一个值来当做划分值呢 ?

答 : 因为只有中间才是复杂度最小的O(nlogn) , 最左最右都是O(n^2) , 因此随机快速排序比经典快速排序好一些 !

②实际工作中用哪一种快速排序 ?

实际工作中我们肯定是要用随机快速排序的 , 因为快速排序的含有常数项的 , 我们在计算时间复杂度的时候是忽略常数项的 , 因此我们实际中是要考虑常数项的 !

③什么是排序的稳定性 ?

就是一堆无序数组中有多个相同的数 , 例如第一个3 , 第二个3 , 拍完序之后 , 仍然是第一个3在前 ,第二个3在后 ,如果符合 , 那么就是稳定的

④一个数组有奇数也有偶数 , 你把他们给分成两组 , 一组是奇数 , 一组是偶数 但是要维持原来的次序 , 也就是实现稳定性 (不能额外开辟新数组)

直接说明 : 这个是做不到的 , 只有论文级别才可以做到 , 当面试官问你这个问题的时候 ,说明他就是想恶心你的 , 不想要你 !

快速排序的代码 :

public class QuickSort {/**快速排序是在荷兰国旗的基础上进行的*还用到了递归* */public int[] qucik (int[]arr,int L,int R){if(L<R){swap(arr,L+(int)(Math.random()*(R-L+1)),R);int[] p = partition(arr, L, R);qucik(arr,L,p[0]-1);qucik(arr,p[1]+1,R);}return arr;}public int[] partition(int[]arr,int L,int R){int less=L-1;int more=R;while(L<more){if(arr[L]<arr[R]){swap(arr,++less,L++);} else if(arr[L]>arr[R]){swap(arr,--more,L);} else {L++;}}swap(arr,more,R);return new int[]{less+1,more};}/*用来交换两个元素位置的方法*/public void swap(int[]arr,int i,int j){int temp;temp=arr[i];arr[i]=arr[j];arr[j]=temp;}
}