疯狂java


您现在的位置: 疯狂软件 >> 新闻资讯 >> 正文

快速排序——Java递归实现


 

   

  Java代码

  package com.bjsxt.test;

  import org.junit.Test;

  /**

  * 递归实现快速排序算法

  * @author jsqiu

  *

  */

  public class FastSort {

  @Test

  public void quick_sortTest() {

  int[] a = new int[] { 72, 6, 57, 88, 60, 42, 83, 73, 48, 85 };

  quick_sort(a, 0, a.length-1);

  }

  void quick_sort(int s[], int begin, int end) {

  if (begin < end) {

  // Swap(s[l], s[(l + r) / 2]); //将中间的这个数和第一个数交换 参见注1

  int i = begin, j = end, x = s[begin];

  while (i < j) {

  while (i < j && s[j] >= x)

  // 从右向左找第一个小于x的数

  j--;

  // 很多人认为既然前面判断了i

  要。

  // 例如此时进while时i=4,j=5,前面while的判断把j减1了,如果不加这个判断

  // s[i++] = s[j]会把i加1,最终变成i=6,j=5,后面就乱套了,不信你可以试试。

  if (i < j)

  s[i++] = s[j];

  while (i < j && s[i] < x)

  // 从左向右找第一个大于等于x的数

  i++;

  if (i < j)

  s[j--] = s[i];

  }

  s[i] = x;

  for (int index = 0; index < s.length; index++) {

  System.out.print(s[index] + " ");

  }

  System.out.println();

  quick_sort(s, begin, i - 1); // 递归调用

  quick_sort(s, i + 1, end);

  } else {

  return; // 这句加不加都没关系,方便理解加了这个else

  }

  }

  }