1 //数组中两个数的交换

 2     static void swap(int[] nums, int pos1, int pos2){

 3         int temp = nums[pos1];

 4         nums[pos1] = nums[pos2];

 5         nums[pos2] = temp;

 6     }

 7     /**

 8      * 快速排序中，在数组中选择一个数字，将数组中的数字分为两部分

 9      * start, end 介于 0 与 nums.length之间

10      */

11     static int partition(int[] nums, int start, int end){

12

13         int index = new Random().nextInt(end + 1 - start) + start;//范围是[start end]闭区间

14         swap(nums, index, end);

15

16         int small = start - 1;

17         for (index = start; index < end; ++index) {

18

19             if (nums[index] < nums[end]) {

20                 ++small;

21                 if (small != index) {

22                     swap(nums, index, small);

23                 }

24             }

25

26         }

27

28         ++ small;

29         swap(nums, small, end);

30         return small;

31     }