递归分治法在快速排序中的应用
分治法的基本思想
- §分治法的基本思想是将一个规模为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); } }}