Java 快速排序与冒泡排序_JAVA_编程开发_程序员俱乐部

一、
  /*
   * 快速排序
   */
  public void _quickSort(int[] list, int low, int high) {
    if (low < high) {
      int middle = getMiddle(list, low, high);  //将数组进行一分为二
      _quickSort(list, low, middle - 1);        //对低位进行递归排序
      _quickSort(list, middle + 1, high);       //对高位进行递归排序
    }
  }

  public int getMiddle(int[] list, int low, int high) {
    int tmp = list[low];    //数组的第一个作为中轴
    while (low < high) {
      while (low < high && list[high] >= tmp) {
        high--;
      }
      list[low] = list[high]; //比中轴小的记录移到低端
      while (low < high && list[low] <= tmp) {
        low++;
      }
      list[high] = list[low]; //比中轴大的记录移到高端
    }
    list[low] = tmp; //中轴记录到尾
    return low;     //返回中轴的位置
  }


二、
  /*
   * 快速排序(改进版)
   */
  private void quickSort(int[] arr, int start, int end) {
    int base = arr[start];
    int i = start;
    int j = end + 1;
    // 如果end <= start,则结束递归
    if (start < end) {
      while (true) {
        // 当i指向的数字大于或等于基准数时，停止递增
        while (i < end) {
          if (base <= arr[++i]) //小于等于
            break;
        }
        // 当j指向的数字小于基准数时，停止递减
        while (start < j) {
          if (arr[--j] < base)
            break;
        }
        // 如果i<j,则将两个数字对换；否则跳出循环
        if (i < j) {
          int temp = arr[i];
          arr[i] = arr[j];
          arr[j] = temp;
        } else {
          break;
        }
      }
      // 将基准数与j指向的数字进行对换
      arr[start] = arr[j];
      arr[j] = base;
      // 对基准数两侧的区域分别进行递归
      quickSort(arr, start, j - 1);
      quickSort(arr, j + 1, end);
    }
  }


三、
  /*
   * 冒泡排序(改进版)
   */
  private void BubbleSort(int[] arr) {
    boolean flag;
    for (int i = 0; i < arr.length; i++) {
      flag = false;
      for (int j = 0; j < (arr.length - i - 1); j++) {
        if (arr[j] > arr[j + 1]) {
          int temp = arr[j + 1];
          arr[j + 1] = arr[j];
          arr[j] = temp;
          flag = true;
        }
      }
      // 如果没有发生交换，说明排序正确，退出循环
      if (!flag) {
        break;
      }
    }
  }