递归分治法在快速排序中的应用
分治法的基本思想
- §分治法的基本思想是将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相独立且与原问题相同。
- k个子问题分别求解。如果子问题的规模仍然不够小，则再划分为k个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止。
- §将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。
- §分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。
Ø 由分治法产生的子问题往往是原问题的较小模 式，这就为使用递归技术提供了方便。在这种 情况下，反复应用分治手段，可以使子问题与 原问题类型一致而其规模却不断缩小，最终使 子问题缩小到很容易直接求出其解。这自然导 致递归过程的产生。
Ø 分治与递归像一对孪生兄弟，经常同时应用在 算法设计之中，并由此产生许多高效算法。
分治法的适用条件
§ 分治法所能解决的问题一般具有以下几个特征：
• 该问题的 规模缩小到一定的程度 就可以容易地解决；
• 该问题可以分解为若干个规模较小的相同问题，即该问题具 有 最优子结构性质
• 利用该问题分解出的子问题的解可以 合并 为该问题的解；
• 该问题所分解出的各个子问题是相互 独立 的，即子问题之间 不包含公共的子问题。
§ 这条特征涉及到分治法的效率，如果各子问题是不独立 的，则分治法要做许多不必要的工作，重复地解公共的子 问题，此时虽然也可用分治法，但一般用 动态规划 较好。
public class mainRecursion {
/**
* @param 主类
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
new recursionFrame();
}
}
import java.util.*;
public class numberTaxis {
public boolean isNumber(String number) {// 检验数字是否合理
StringTokenizer tokenizer = new StringTokenizer(number, ",");
boolean bool = true;
while (tokenizer.hasMoreTokens()) {
try {
Double.valueOf(tokenizer.nextToken());
} catch (Exception e) {
bool = false;
}
}
return bool;
}
double sumNumber[];
public String uptaxis(String number, boolean updown) {// 排序
int i = 0;
String s = "";
StringTokenizer tokenizer = new StringTokenizer(number, ",");
sumNumber = new double[tokenizer.countTokens()];//字符串的解析
while (tokenizer.hasMoreTokens()) {
String d = tokenizer.nextToken();
sumNumber[i] = Double.valueOf(d);//将字符串转换为双字节类型
i++;
}
QSort(sumNumber, 0, sumNumber.length - 1);// 快速排序（升序）
// 如果选择降序
if (!updown) {
double num;
int low = 0, high = sumNumber.length - 1;
for (; low < high; low++, high--) {
num = sumNumber[low];//数组交换位子
sumNumber[low] = sumNumber[high];
sumNumber[high] = num;
}
}
for (i = 0; i < sumNumber.length - 1; i++) {
s += String.valueOf(sumNumber[i]) + "，";
}
return s + String.valueOf(sumNumber[sumNumber.length - 1]);
}
//搜索字符串
public String search(String s, boolean updown) {
String str = "";
int a = searchNumber(Double.valueOf(s), updown);// 调用折半查找
if (a != -1)
str = "查找成功，位序为：" + String.valueOf(a + 1);
else
str = "没有找到该元素！";
return str;
}
public int searchNumber(double num, boolean updown) {// 折半查找算法
int left = 0, right = sumNumber.length - 1, middle = -1;
while (left <= right) {
middle = (left + right) / 2;
if (num == sumNumber[middle])
return middle;
if (updown) {//如果数组是升序
if (num > sumNumber[middle])
left = middle + 1;
else
right = middle - 1;
} else {//数组是降序
if (num > sumNumber[middle])
right = middle - 1;
else
left = middle + 1;
}
}
return -1;
}
// 快速排序算法
public int partition(double num[], int low, int high) {
double m = num[low];// 记录关键字
while (low < high) {
while (low < high && num[high] >= m)
--high;// 将比记录小的记录移到低端
num[low] = num[high];
while (low < high && num[low] <= m)
++low;// 将比记录大的记录移到高端
num[high] = num[low];
}
num[low] = m;// 返回记录轴的位置
return low;
}
//快速排序递归 的实现
public void QSort(double num[], int low, int high) {
if (low < high) {// 长度大于一
int pivotloc = partition(num, low, high);// 将数据一分为二
QSort(num, low, pivotloc - 1);// 递归排序
QSort(num, pivotloc + 1, high);
}
}
public void Quick(double num[], boolean updown) {
// 选择排序算法
int i = 0, j, k;
double n;
for (i = 0; i < sumNumber.length; i++) {
k = i;
for (j = i + 1; j < sumNumber.length; j++) {
if (updown) {//如果数组是升序
if (sumNumber[j] < sumNumber[k])
k = j;
} else {
if (sumNumber[j] > sumNumber[k])
k = j;
}
}
n = sumNumber[k];
sumNumber[k] = sumNumber[i];
sumNumber[i] = n;
}
}
}
import java.awt.Dimension;
import java.awt.Toolkit;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;
import java.awt.event.WindowAdapter;
import java.awt.event.WindowEvent;
import javax.swing.*;
public class recursionFrame extends JFrame implements ActionListener {
private JLabel firstNumberLabel, secondNumberLabel, searchLabel,
resultLabel, result;
private JButton upButton, downButton;
private JTextField firstNumber, secondNumber, searchNumber;
numberTaxis numbertaxis;
recursionFrame() {
super("递归分治法应用");
numbertaxis = new numberTaxis();
mainFrame();
}
boolean updown = true;
public void actionPerformed(ActionEvent e) {
// TODO 事件的处理
if (e.getSource() == firstNumber) {
action(true);
} else if (e.getSource() == downButton) {
action(false);
updown = false;
} else if (e.getSource() == upButton) {
action(true);
updown = true;
} else if (e.getSource() == searchNumber) {
String str1 = searchNumber.getText();
String str2 = secondNumber.getText();
boolean isnumber = numbertaxis.isNumber(searchNumber.getText());
if (!str2.equals("") && !str1.equals("") && isnumber) {
result.setText(numbertaxis.search(str1, updown));
} else {
JOptionPane.showMessageDialog(this, "您输入的搜索数据有错误请从新输入！",
"警告对话框", JOptionPane.WARNING_MESSAGE);
searchNumber.setText("");
}
}
}
public void mainFrame() {
firstNumberLabel = new JLabel("请输入一组数据，以逗号隔开(默认为升序排列)：");
secondNumberLabel = new JLabel("排序结果：");
searchLabel = new JLabel("请输入要查询的数据，以回车键确定:");
resultLabel = new JLabel("查询结果是：");
result = new JLabel(" ");
upButton = new JButton("升序排列");
downButton = new JButton("降序排列");
firstNumber = new JTextField(50);
secondNumber = new JTextField(50);
searchNumber = new JTextField(10);
upButton.addActionListener(this);
downButton.addActionListener(this);
firstNumber.addActionListener(this);
searchNumber.addActionListener(this);
this.add(firstNumberLabel);
firstNumberLabel.setBounds(10, 10, 290, 25);
this.add(firstNumber);
firstNumber.setBounds(10, 35, 270, 25);
this.add(upButton);
upButton.setBounds(20, 65, 100, 25);
this.add(downButton);
downButton.setBounds(150, 65, 100, 25);
this.add(secondNumberLabel);
secondNumberLabel.setBounds(10, 95, 70, 25);
this.add(secondNumber);
secondNumber.setBounds(10, 120, 270, 25);
this.add(searchLabel);
searchLabel.setBounds(10, 150, 230, 25);
this.add(searchNumber);
searchNumber.setBounds(230, 150, 50, 25);
this.add(resultLabel);
resultLabel.setBounds(10, 180, 100, 30);
this.add(result);
result.setBounds(10, 205, 200, 30);
Toolkit tool = getToolkit();// 获取屏幕的大小
Dimension dim = tool.getScreenSize();
this.setBounds(dim.width / 2 - 150, dim.height / 2 - 100, 300, 300);
this.setLayout(null);
this.setResizable(false);
this.setVisible(true);
this.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
// this.addWindowListener(new WindowAdapter()
// {
// public void windowClosing(WindowEvent e){
// System.exit(0);
// }
// }
// );
}
public void action(boolean updown) {// 对输入的数据验证和排序
if (numbertaxis.isNumber(firstNumber.getText())
&& !firstNumber.getText().equals("")) {
secondNumber.setText(numbertaxis.uptaxis(firstNumber.getText(),
updown));
} else {
JOptionPane.showMessageDialog(this, "您输入的数据有错误请从新输入！", "警告对话框",
JOptionPane.WARNING_MESSAGE);
}
}
}