快速排序+一道练习题
快速排序
先引入几个问题;
既然它叫快速排序,那么它的时间复杂度?
为什么它是''不稳定''的?
思路
1.从数列中挑出一个元素，称为 "基准"（pivot）
2.重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区操作；
3.递归地把小于基准值元素的子数列和大于基准值元素的子数列排序；
光说不练假把戏,上题:
描述给定一个数组，请你编写一个函数，返回该数组排序后的形式。示例1输入：[5,2,3,1,4]返回值：[1,2,3,4,5]示例2输入：[5,1,6,2,5]返回值：[1,2,5,5,6]
import java.util.*;public class Solution {public int[] MySort (int[] arr) {// write code herequicksort(arr,0,arr.length-1);return arr;}private void quicksort(int[] arr,int left,int right){if(left>=right){return;}int L = left;int R = right;int pivot = arr[left];while(left<right){while(left<right&&arr[right]>=pivot){right--;}arr[left] = arr[right];while(left<right&&arr[left]<=pivot){left++;}arr[right] = arr[left];}arr[left] = pivot;quicksort(arr,L,left);quicksort(arr,left+1,R);}}