package com.algorithm.sort.quick;

import java.util.Arrays;

/**
 * 快速排序
 * Created by yulinfeng on 2017/6/26.
 */
public class Quick {
  public static void main(String[] args) {
    int[] nums = {6, 5, 3, 1, 7, 2, 4};
    nums = quickSort(nums, 0, nums.length - 1);
    System.out.println(Arrays.toString(nums));
  }
  
  /**
   * 快速排序
   * @param nums 待排序数组序列
   * @param left 数组第一个元素索引
   * @param right 数组最后一个元素索引
   * @return 排好序的数组序列
   */
  private static int[] quickSort(int[] nums, int left, int right) {
    if (left < right) {
      int temp = nums[left];  //基数
      int i = left;  //哨兵i
      int j = right;  //哨兵j
      while (i < j) {
        while (i < j && nums[j] >= temp) {
          j--;
        }
        if (i < j) {
          nums[i] = nums[j];
          i++;
        }
        while (i < j && nums[i] < temp) {
          i++;
        }
        while (i < j) {
          nums[j] = nums[i];
          j--;
        }
      }
      nums[i] = temp;
      quickSort(nums, left, i - 1);
      quickSort(nums, i + 1, right);
    }
    return nums;
  }
}

#快速排序
def quick_sort(nums, left, right):
  if left < right:
    temp = nums[left]  #基数
    i = left  #哨兵i
    j = right  #哨兵j
    while i < j:
      while i < j and nums[j] >= temp:
        j -= 1
      if i < j:
        nums[i] = nums[j]
        i += 1
      while i < j and nums[i] < temp:
        i += 1
      if i < j:
        nums[j] = nums[i]
        j -= 1
    nums[i] = temp
    quick_sort(nums, left, i - 1)
    quick_sort(nums, i + 1, right)
  
  return nums

nums = [6, 5, 3, 1, 7, 2, 4]
nums = quick_sort(nums, 0, len(nums) - 1)
print(nums)