数据结构与算法（JAVA篇）一

Bertha 。 2021-12-13 22:21 262阅读 0赞

1.  递归算法
    
    1.  /\*\* 
    2.   \* 
    3.   \* @author SunnyMoon 
    4.   \*/  
    5.    
    6.    
    7.  /\*\* 
    8.   \* 概念介绍： 
    9.   \* 递归是一种方法（函数）调用自已编程技术。 
    10.  \* 递归就是程序设计中的数学归纳法。 
    11.  \* 例如：tri(n)=1            if n=1 
    12.  \*     tri(n)=n+tri(n-1)    if n>1 
    13.  \* 可能while循环方法执行的速度比递归方法快，但是为什么采用递归呢。 
    14.  \* 采用递归，是因为它从概念上简化了问题，而不是因为它提高效率。 
    15.  \*/  
    16.   
    17. import java.io.BufferedReader;  
    18. import java.io.IOException;  
    19. import java.io.InputStreamReader;  
    20.   
    21.   
    22. public class Recursion \{ //求三角数字的递归算法：1，3，6，10，15，21, ......  
    23.   
    24.     static int theNumber;  
    25.   
    26.     public static void main(String\[\] args) throws IOException \{  
    27.         System.out.print("Enter a number: ");  
    28.         theNumber = getInt();  
    29.         //使用递归时调用，默认  
    30.         int theAnswer = triangle(theNumber);  
    31.         //使用非递归时调用  
    32.         //int theAnswer=triangle2(theNumber);  
    33.         System.out.println("Result: " + theAnswer);  
    34.     \}  
    35.   
    36.     public static int triangle(int n) \{ //递归方法，循环调用  
    37.         if (n == 1) \{  
    38.             return 1;  
    39.         \} else \{  
    40.             return (n + triangle(n - 1));  
    41.         \}  
    42.     \}  
    43.   
    44.     public static int triangle2(int n) \{ //非递归方法  
    45.         int total = 0;  
    46.         while (n > 0) \{  
    47.             total = total + n--;  
    48.         \}  
    49.         return total;  
    50.     \}  
    51.   
    52.     public static String getString() throws IOException \{  
    53.         InputStreamReader isr = new InputStreamReader(System.in);  
    54.         BufferedReader br = new BufferedReader(isr);  
    55.         String s = br.readLine();  
    56.         return s;  
    57.     \}  
    58.   
    59.     public static int getInt() throws IOException \{  
    60.         String s = getString();  
    61.         return Integer.parseInt(s);  
    62.     \}  
    63. \}  
    64.   
    65. /\*\* 
    66.  \* 运行结果： 
    67.  \* Enter a number:  
    68.  \* 3 
    69.  \* Result: 6 
    70.  \*/  
    71.   
    72. /\*\* 
    73.  \* 总结： 
    74.  \* 使用非递归的方式更简洁，更易懂，运行效率更高，为什么还要用递归的算法呢。 
    75.  \* 递归使规模逐渐降低的方式解决问题，以这种统一的方式解决足够复杂的问题。 
    76.  \*/   
        
2.  1.  /\*\* 
    2.   \* 概念介绍： 
    3.   \* 
    4.   \* 树：树由边连接的节点构成。 
    5.   \* 多路树：节点可以多于两个。 
    6.   \* 路径：顺着连接点的边从一个节点到另一个节点，所以过的节点顺序排列就称做路径。 
    7.   \* 根：树的顶端节点称为根。 
    8.   \* 父节点：每个节点都有一条边向上连接到另一个节点，这个节点就称为父节点。 
    9.   \* 子节点：每个节点都可能有一条或多条边向下连接其它节点，下面这些节点就称为子节点。 
    10.  \* 叶节点：没有子节点的节点为叶子节点或叶节点。 
    11.  \* 子树：每个节点都可以作为子树的根，它和它所有的子节点都包含在子树中。 
    12.  \* 访问：当程序控制流程到达某个节点时，就称为“访问”这个节点。 
    13.  \* 遍历：遍历树意味着要遵循某种特定的顺序访问树中所有的节点。 
    14.  \* 层：一个节点的层数是指从根开始到这个节点有多少“代”。一般根为第0层。 
    15.  \* 关键字：对象中通常会有一个数据域被指定为关键字，通常使用这个关键字进行查询等操作。 
    16.  \* 二叉树：如果树中每个节点最多只能有两个子节点，这样的特殊的树就是二叉树。 
    17.  \* 二叉搜索树：二叉树的一个节点的左子节点的关键字值小于这个节点，右子节点的关键字值大 
    18.  \*            于或等于这个父节点。 
    19.  \* 平衡树与非平衡树：左子节点与左子节点对称的树为平衡树，否则就是非平衡树。 
    20.  \* 完全二叉树：二叉树的最后一层都是叶子结点，其它各层都有左右子树，也叫满二叉树。 
    21.  \* 
    22.  \* 为什么用二叉树：1.二叉树结合了另外两种数据结构的优点：一种是有序数组，另一种是链表。 
    23.  \*                在树中查找数据的速度和在有序数组中查找的速度一样快，同时插入的速度 
    24.  \*                和删除的速度和链表的速度一样。 
    25.  \*                2.在有序数组中插入数据项太慢：用二分查找法可以在有序数据中快速的查找 
    26.  \*                特定的值，查找所需时间复杂度为O(logN)。然而插入和删除是非常低效的。 
    27.  \*                3.在链表中查找太慢：链表的插入和删除操作都很快，时间复杂度是O(1)。 
    28.  \*                然而查找数据项是非常低效的。 
    29.  \* 二叉树的效率：时间复杂度为O(logN)。树对所有的数据存储操作都很高效。 
    30.  \* 
    31.  \* 程序介绍：对树的一些常用操作进行了封装，包括查询，插入，删除，遍历二叉树（中序，后序，前序） 
    32.  \*          以及以树的方式显示二对树的各个结点。 
    33.  \* 
    34.  \*/  
    35. /\*\* 
    36.  \* 
    37.  \* @author SunnyMoon 
    38.  \*/  
    39.   
    40. import java.io.BufferedReader;  
    41. import java.io.IOException;  
    42. import java.io.InputStreamReader;  
    43.   
    44. /\*\* 
    45.  \* 定义树的结点类 
    46.  \*/  
    47. class Node \{  
    48.   
    49.     public int iData;//关键字  
    50.     public double dData;//数据项  
    51.     public Node leftChild;//左子树  
    52.     public Node rightChild;//右子树  
    53.   
    54.     public void displayNode() \{ //输出结点内容  
    55.         System.out.print("【");  
    56.         System.out.print("关键字: "\+iData);  
    57.         System.out.print(",");  
    58.         System.out.print("值："\+dData);  
    59.         System.out.print("】");  
    60.     \}  
    61. \}  
    62.   
    63. /\*\* 
    64.  \* 定义二叉树类 
    65.  \*/  
    66. class Tree \{  
    67.   
    68.     private Node root;  
    69.   
    70.     public Tree() \{  
    71.         root = null;  
    72.     \}  
    73.   
    74.     /\*\* 
    75.      \* 查找 
    76.      \* @param key 
    77.      \* @return 
    78.      \*/  
    79.     public Node find(int key) \{  
    80.         Node current = root;  
    81.         while (current.iData != key) \{  
    82.             if (key < current.iData) \{  
    83.                 current = current.leftChild;  
    84.             \} else \{  
    85.                 current = current.rightChild;  
    86.             \}  
    87.             if (current == null) \{  
    88.                 return null;  
    89.             \}  
    90.         \}  
    91.         return current;  
    92.     \}  
    93. /\*\* 
    94.  \* 插入 
    95.  \* @param id 
    96.  \* @param dd 
    97.  \*/  
    98.     public void insert(int id, double dd) \{  
    99.         Node newNode = new Node();  
    100.         newNode.iData = id;  
    101.         newNode.dData = dd;  
    102.         if (root == null) \{  
    103.             root = newNode;  
    104.         \} else \{  
    105.             Node current = root;  
    106.             Node parent;  
    107.             while (true) \{  
    108.                 parent = current;  
    109.                 if (id < current.iData) \{  
    110.                     current = current.leftChild;  
    111.                     if (current == null) \{  
    112.                         parent.leftChild = newNode;  
    113.                         return;  
    114.                     \}  
    115.                 \} else \{  
    116.                     current = current.rightChild;  
    117.                     if (current == null) \{  
    118.                         parent.rightChild = newNode;  
    119.                         return;  
    120.                     \}  
    121.                 \}  
    122.             \}  
    123.         \}  
    124.     \}  
    125.   
    126.     /\*\* 
    127.      \* 删除 
    128.      \* @param key 
    129.      \* @return 
    130.      \*/  
    131.     public boolean delete(int key) \{  
    132.         Node current = root;  
    133.         Node parent = root;  
    134.         boolean isLeftChild = true;  
    135.   
    136.         while (current.iData != key) \{  
    137.             parent = current;  
    138.             if (key < current.iData) \{  
    139.                 isLeftChild = true;  
    140.                 current = current.leftChild;  
    141.             \} else \{  
    142.                 isLeftChild = false;  
    143.                 current = current.rightChild;  
    144.             \}  
    145.             if (current == null) \{  
    146.                 return false;  
    147.             \}  
    148.         \}  
    149.         if (current.leftChild == null && current.rightChild == null) \{  
    150.             if (current == root) \{  
    151.                 root = null;  
    152.             \} else if (isLeftChild) \{  
    153.                 parent.leftChild = null;  
    154.             \} else \{  
    155.                 parent.rightChild = null;  
    156.             \}  
    157.         \} else if (current.rightChild == null) \{  
    158.             if (current == root) \{  
    159.                 root = current.leftChild;  
    160.   
    161.             \} else if (isLeftChild) \{  
    162.                 parent.leftChild = current.leftChild;  
    163.             \} else \{  
    164.                 parent.rightChild = current.leftChild;  
    165.             \}  
    166.         \} else if (current.leftChild == null) \{  
    167.             if (current == root) \{  
    168.                 root = current.rightChild;  
    169.             \} else if (isLeftChild) \{  
    170.                 parent.leftChild = current.rightChild;  
    171.             \} else \{  
    172.                 parent.rightChild = current.rightChild;  
    173.             \}  
    174.         \} else \{  
    175.             Node successor = getSuccessor(current);  
    176.             if (current == root) \{  
    177.                 root = successor;  
    178.             \} else if (isLeftChild) \{  
    179.                 parent.leftChild = successor;  
    180.             \} else \{  
    181.                 parent.rightChild = successor;  
    182.             \}  
    183.             successor.leftChild = current.leftChild;  
    184.         \}  
    185.         return true;  
    186.     \}  
    187. /\*\* 
    188.  \* 遍历二叉树 
    189.  \* @param traverseType 
    190.  \*/  
    191.     public void traverse(int traverseType) \{  
    192.         switch (traverseType) \{  
    193.             case 1:  
    194.                 System.out.print("\\n" + "前序遍历（Preorder traversal）: ");  
    195.                 preOrder(root);  
    196.                 break;  
    197.             case 2:  
    198.                 System.out.print("\\n" + "中序遍历（Inorder traversal）: ");  
    199.                 inOrder(root);  
    200.                 break;  
    201.             case 3:  
    202.                 System.out.print("\\n" + "后序遍历（Postorder traversal）: ");  
    203.                 postOrder(root);  
    204.                 break;  
    205.         \}  
    206.         System.out.println();  
    207.     \}  
    208. /\*\* 
    209.  \* 定义定位到后序结点方法 
    210.  \* @param delNode 
    211.  \* @return 
    212.  \*/  
    213.     private Node getSuccessor(Node delNode) \{  
    214.         Node successorParent = delNode;  
    215.         Node successor = delNode;  
    216.         Node current = delNode.rightChild;  
    217.         while (current != null) \{  
    218.             successorParent = successor;  
    219.             successor = current;  
    220.             current = current.leftChild;  
    221.         \}  
    222.         if (successor != delNode.rightChild) \{  
    223.             successorParent.leftChild = successor.rightChild;  
    224.             successor.rightChild = delNode.rightChild;  
    225.         \}  
    226.         return successor;  
    227.     \}  
    228. /\*\* 
    229.  \* 前序遍历 
    230.  \* @param localRoot 
    231.  \*/  
    232.     private void preOrder(Node localRoot) \{  
    233.         if (localRoot != null) \{  
    234.             System.out.print(localRoot.iData + " ");  
    235.             preOrder(localRoot.leftChild);  
    236.             preOrder(localRoot.rightChild);  
    237.         \}  
    238.     \}  
    239. /\*\* 
    240.  \* 中序遍历 
    241.  \* @param localRoot 
    242.  \*/  
    243.     private void inOrder(Node localRoot) \{  
    244.         if (localRoot != null) \{  
    245.             inOrder(localRoot.leftChild);  
    246.             System.out.print(localRoot.iData + " ");  
    247.             inOrder(localRoot.rightChild);  
    248.         \}  
    249.     \}  
    250. /\*\* 
    251.  \* 后序遍历 
    252.  \* @param localRoot 
    253.  \*/  
    254.     private void postOrder(Node localRoot) \{  
    255.         if (localRoot != null) \{  
    256.             postOrder(localRoot.leftChild);  
    257.             postOrder(localRoot.rightChild);  
    258.             System.out.print(localRoot.iData + " ");  
    259.         \}  
    260.     \}  
    261. /\*\* 
    262.  \* 把关键字按树型输出 
    263.  \* ‘--’表示树中这个位置的结点不存在。 
    264.  \*/  
    265.     public void displayTree() \{  
    266.         Stack globalStack = new Stack(1000);  
    267.         globalStack.push(root);  
    268.         int nBlanks = 32;  
    269.         boolean isRowEmpty = false;  
    270.         System.out.println(  
    271.                 "-----------------------------------------------------------------------");  
    272.         while (isRowEmpty == false) \{  
    273.             Stack localStack = new Stack(1000);  
    274.             isRowEmpty = true;  
    275.   
    276.             for (int j = 0; j < nBlanks; j++) \{  
    277.                 System.out.print(" ");  
    278.             \}  
    279.             while (globalStack.isEmpty() == false) \{  
    280.                 Node temp = (Node) globalStack.pop();  
    281.                 if (temp != null) \{  
    282.                     System.out.print(temp.iData);  
    283.                     localStack.push(temp.leftChild);  
    284.                     localStack.push(temp.rightChild);  
    285.   
    286.                     if (temp.leftChild != null || temp.rightChild != null) \{  
    287.                         isRowEmpty = false;  
    288.                     \}  
    289.                 \} else \{  
    290.                     System.out.print("..");  
    291.                     localStack.push(null);  
    292.                     localStack.push(null);  
    293.                 \}  
    294.                 for (int j = 0; j < nBlanks \* 2 - 2; j++) \{  
    295.                     System.out.print(" ");  
    296.                 \}  
    297.             \}  
    298.             System.out.println();  
    299.             nBlanks /= 2;  
    300.             while (localStack.isEmpty() == false) \{  
    301.                 globalStack.push(localStack.pop());  
    302.             \}  
    303.         \}  
    304.         System.out.println(  
    305.                 "-----------------------------------------------------------------------");  
    306.     \}  
    307. \}  
    308.   
    309. /\*\* 
    310.  \* 使用的栈 
    311.  \* @author Administrator 
    312.  \*/  
    313. class Stack \{  
    314.   
    315.     private int maxSize;  
    316.     private Object\[\] stackArray;  
    317.     private int top;  
    318.   
    319.     public Stack(int s) \{  
    320.         maxSize = s;  
    321.         stackArray = new Object\[maxSize\];  
    322.         top = -1;  
    323.     \}  
    324.   
    325.     public void push(Object p) \{  
    326.         stackArray\[++top\] = p;  
    327.     \}  
    328.   
    329.     public Object pop() \{  
    330.         return stackArray\[top--\];  
    331.     \}  
    332.   
    333.     public Object peek() \{  
    334.         return stackArray\[top\];  
    335.     \}  
    336.   
    337.     boolean isEmpty() \{  
    338.         if (top == -1) \{  
    339.             return true;  
    340.         \} else \{  
    341.             return false;  
    342.         \}  
    343.     \}  
    344. \}  
    345. /\*\* 
    346.  \* 主方法 
    347.  \* @author Administrator 
    348.  \*/  
    349. class TreeAaa \{  
    350.   
    351.     public static void main(String\[\] args) throws IOException \{  
    352.         int value;  
    353.         Tree theTree = new Tree();  
    354.         theTree.insert(12, 1.5);  
    355.         theTree.insert(15, 2.4);  
    356.         theTree.insert(22, 5.6);  
    357.         theTree.insert(33, 7.1);  
    358.         theTree.insert(55, 3.3);  
    359.         theTree.insert(26, 8.7);  
    360.         theTree.insert(17, 2.3);  
    361.         theTree.insert(8, 6.9);  
    362.         theTree.insert(6, 8.4);  
    363.         theTree.insert(14, 7.0);  
    364.         theTree.insert(23, 1.8);  
    365.         theTree.insert(38, 2.9);  
    366.   
    367.         while (true) \{  
    368.             System.out.print("输入想执行的操作的英文首字母：");  
    369.             System.out.print("插入（Insert）, 查找（Find）, 删除（Delete）, 遍历（Traverse）: ");  
    370.             int choice = getChar();  
    371.             switch (choice) \{  
    372.                 case 's':  
    373.                     theTree.displayTree();  
    374.                     break;  
    375.                 case 'i':  
    376.                     System.out.print("输入想要插入的值: ");  
    377.                     value = getInt();  
    378.                     theTree.insert(value, value + 0.9);  
    379.                     break;  
    380.                 case 'f':  
    381.                     System.out.print(("输入想要查找的关键字: "));  
    382.                     value = getInt();  
    383.                     Node found = theTree.find(value);  
    384.                     if (found != null) \{  
    385.                         System.out.print("成功查找: ");  
    386.                         found.displayNode();  
    387.                         System.out.print("\\n");  
    388.                     \} else \{  
    389.                         System.out.print("不存在所查询关键字");  
    390.                     \}  
    391.                     System.out.print("输入的关键字：" + value + "\\n");  
    392.                     break;  
    393.                 case 'd':  
    394.                     System.out.print("输入想要删除的关键字: ");  
    395.                     value = getInt();  
    396.                     boolean didDelete = theTree.delete(value);  
    397.                     if (didDelete) \{  
    398.                         System.out.print("删除的值：" + value + "\\n");  
    399.                     \} else \{  
    400.                         System.out.print("不能执行删除操作");  
    401.                     \}  
    402.                     System.out.println(value);  
    403.                     //System.out.print(value + "\\n");  
    404.                     break;  
    405.                 case 't':  
    406.                     System.out.print("输入遍历类型 1, 2 或 3:");  
    407.                     value = getInt();  
    408.                     theTree.traverse(value);  
    409.                     break;  
    410.                 default:  
    411.                     System.out.println("非法输入");  
    412.             \}  
    413.         \}  
    414.     \}  
    415.   
    416.     public static String getString() throws IOException \{  
    417.         InputStreamReader isr = new InputStreamReader(System.in);  
    418.         BufferedReader br = new BufferedReader(isr);  
    419.         String s = br.readLine();  
    420.         return s;  
    421.     \}  
    422.   
    423.     public static char getChar() throws IOException \{  
    424.         String s = getString();  
    425.         return s.charAt(0);  
    426.     \}  
    427.   
    428.     public static int getInt() throws IOException \{  
    429.         String s = getString();  
    430.         return Integer.parseInt(s);  
    431.     \}  
    432.   /\*\* 
    433.     \* 运行结果： 
    434.     \* 输入想执行的操作的英文首字母：插入（Insert）, 查找（Find）, 删除（Delete）, 遍历（Traverse）: s 
    435.     \*----------------------------------------------------------------------- 
    436.     \*                                12 
    437.     \*                8                              15 
    438.     \*        6              ..              14              22 
    439.     \*    ..      ..      ..      ..      ..      ..      17      33 
    440.     \*  ..  ..  ..  ..  ..  ..  ..  ..  ..  ..  ..  ..  ..  ..  26  55 
    441.     \* ........................................................23..38.. 
    442.     \*----------------------------------------------------------------------- 
    443.     \*输入想执行的操作的英文首字母：插入（Insert）, 查找（Find）, 删除（Delete）, 遍历（Traverse）: i 
    444.     \*输入想要插入的值: 3 
    445.     \*输入想执行的操作的英文首字母：插入（Insert）, 查找（Find）, 删除（Delete）, 遍历（Traverse）: f 
    446.     \*输入想要查找的关键字: 14 
    447.     \*成功查找: \{14,7.0\} 
    448.     \*输入的关键字：14 
    449.     \*输入想执行的操作的英文首字母：插入（Insert）, 查找（Find）, 删除（Delete）, 遍历（Traverse）: 
    450.     \*/  
    451.  /\*\* 
    452.   \* 总结： 
    453.   \* 树结合了数组和链表的优点，是一种非常高效的数据结构。 
    454.   \*/   
        
3.  快速排序/\*\* 
4.  1.  /\*\* 
    2.   \* 
    3.   \* @author SunnyMoon 
    4.   \*/  
    5.    
    6.  /\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\* 
    7.   \* 概念介绍： 
    8.   \* \*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\* 
    9.   \*  
    10.  \* 简单排序： 
    11.  \* 包括冒泡排序，选择排序和插入排序，是一些容易实现的，但速度比较慢的排序算法。 
    12.  \*  
    13.  \* 高级排序： 
    14.  \* 快速排序，希尔排序和快速排序比简单排序快很多。本节主要介绍快速排序。 
    15.  \*  
    16.  \* 归并排序： 
    17.  \* 在递归算法中已经介绍过，它需要的容易是原始空间的两倍，是一个严重的缺点。 
    18.  \*  
    19.  \* 希尔排序： 
    20.  \* 不需要大量的辅助空间，和归并排序一样容易实现。希尔排序是基于插入排序的一种算法， 
    21.  \* 在此算法基础之上增加了一个新的特性，提高了效率。 
    22.  \*  
    23.  \* 快速排序： 
    24.  \* 不需要大量辅助空间，并且是通用排序算法中最快的排序算法，是基于划分的思想。 
    25.  \* 快速排序算法本质上是通过把一个数组递归的划分为两个子数组。 
    26.  \* 递归的基本步骤： 
    27.  \* 1. 把数组划分成以一个元素为枢纽的左右两个子数组。 
    28.  \* 2. 调用自身的左边和右边以步骤1递归。 
    29.  \* 快速排序法的核心就是递归调用划分算法，直到基值的情况，这时数组就为有序的。 
    30.  \* 快速排序的复杂度为： 
    31.  \* O(N\*logN) 
    32.  \*  
    33.  \* 影响效率的最大障碍： 
    34.  \* 对枢纽数据的选择是影响排序的效率。例如本例子选择枢纽数据为数组的最后一个元素， 
    35.  \* 这么选择只是为方便，然而却造成了特殊情况时效率极度下降,降到O(n2)。这种特情况就是当数据为逆序的时候。 
    36.  \* 如果改变特殊情况给快速排序带来的致命影响呢，这将在下一专题中详细介绍。 
    37.  \*/  
    38.   
    39. /\*\* 
    40.  \* 定义一个数组类，封装了对自身数据的排序。 
    41.  \*/  
    42. class ArrayIns \{  
    43.   
    44.     private long\[\] theArray;//定义数组  
    45.     private int nElems;//数组中的元素个数  
    46.   
    47.     /\*\* 
    48.      \* 初始化 
    49.      \* @param max 
    50.      \*/  
    51.     public ArrayIns(int max) \{  
    52.         theArray = new long\[max\];  
    53.         nElems = 0;  
    54.     \}  
    55.   
    56.     /\*\* 
    57.      \* 为数组赋值 
    58.      \* @param value 
    59.      \*/  
    60.     public void insert(long value) \{  
    61.         theArray\[nElems\] = value;  
    62.         nElems++;  
    63.     \}  
    64.   
    65.     /\*\* 
    66.      \* 显示数组元素 
    67.      \*/  
    68.     public void display() \{  
    69.         System.out.print("A=");  
    70.         for (int j = 0; j < nElems; j++) \{  
    71.             System.out.print(theArray\[j\] + " ");  
    72.         \}  
    73.         System.out.println("");  
    74.     \}  
    75.   
    76.     /\*\* 
    77.      \* 快速排序主方法 
    78.      \*/  
    79.     public void quickSort()\{  
    80.         recQuickSort(0, nElems-1);  
    81.     \}  
    82.     /\*\* 
    83.      \* 快速排序需递归调用的方法 
    84.      \* @param left 
    85.      \* @param right 
    86.      \*/  
    87.     public void recQuickSort(int left, int right) \{  
    88.         if (right - left <= 0) \{  
    89.             return;  
    90.         \} else \{  
    91.             long pivot = theArray\[right\];  
    92.               
    93.             int partition = partitionIt(left, right, pivot);  
    94.             recQuickSort(left, partition - 1);  
    95.             recQuickSort(partition + 1, right);  
    96.         \}  
    97.     \}  
    98.   
    99.     /\*\* 
    100.      \* 快速排序划分的核心方法 
    101.      \* @param left 
    102.      \* @param right 
    103.      \* @param pivot 
    104.      \* @return 
    105.      \*/  
    106.     public int partitionIt(int left, int right, long pivot) \{  
    107.         int leftPtr = left-1;  
    108.         int rightPtr = right;  
    109.         while (true) \{  
    110.             while (theArray\[++leftPtr\] < pivot)  
    111.                 ;  
    112.             while (rightPtr > 0 && theArray\[--rightPtr\] > pivot)  
    113.                 ;  
    114.             if (leftPtr >= rightPtr) \{  
    115.                 break;  
    116.             \} else \{  
    117.                 swap(leftPtr, rightPtr);  
    118.             \}  
    119.         \}  
    120.         swap(leftPtr,right);  
    121.         return leftPtr;  
    122.     \}  
    123.   
    124.     /\*\* 
    125.      \* 交换数据中两个位置的数据 
    126.      \* @param dex1 
    127.      \* @param dex2 
    128.      \*/  
    129.     public void swap(int dex1, int dex2) \{  
    130.         long temp = theArray\[dex1\];  
    131.         theArray\[dex1\] = theArray\[dex2\];  
    132.         theArray\[dex2\] = temp;  
    133.     \}  
    134. \}  
    135. /\*\* 
    136.  \* 执行算法的主类 
    137.  \*/  
    138. public class QuickSort1 \{  
    139.   
    140.     public static void main(String\[\] args) \{  
    141.         int maxSize = 16;  
    142.         ArrayIns arr = new ArrayIns(maxSize);  
    143.   
    144.         for (int j = 0; j < maxSize; j++) \{  
    145.             long n = (int) (java.lang.Math.random()\*99);  
    146.             arr.insert(n);  
    147.         \}  
    148.         System.out.println("显示排序前数据");  
    149.         arr.display();  
    150.         arr.quickSort();  
    151.         System.out.println("显示排序后数据");  
    152.         arr.display();  
    153.     \}  
    154. \}  
    155. /\*\* 
    156.  \*  
    157.  \* 显示排序前数据： 
    158.  \* A=9 14 33 27 66 89 53 32 72 14 46 33 13 79 28 26   
    159.  \* 显示排序后数据：  
    160.  \* A=9 13 14 14 26 27 28 32 33 33 46 53 66 72 79 89  
    161.  \*/  
    162.   
    163. /\*\* 
    164.  \* 总结： 
    165.  \* 快速排序是常用排序中效率最高的一种排序方式。 
    166.  \* 但在应用中的一此特殊情况影响他的效率，这不是算法本身的问题，而是如果实现的问题。 
    167.  \* 已经有很好的实现方式改变一些特殊情况性能下降的问题。 
    168.  \*/   
        
5.  1.  1.  1.  1.   \* 
                2.   \* @author SunnyMoon 
                3.   \*/  
                4.    
                5.  /\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\* 
                6.   \* 概念介绍： 
                7.   \* \*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\* 
                8.   \* 
                9.   \* 影响效率的最大障碍： 
                10.  \* 对枢纽数据的选择是影响排序的效率。上一篇文章选择枢纽数据为数组的最后一个元素， 
                11.  \* 这么选择只是为方便，然而却造成了特殊情况时效率极度下降,降到O(n2)。这种特情况就是当数据为逆序的时候。 
                12.  \* 如果改变特殊情况给快速排序带来的致命影响呢，这将在这一专题中简要介绍。 
                13.  \* 
                14.  \* 三数据项取中划分： 
                15.  \* 目前已经有很多选择更好的枢纽的方法，选择任意一个数据项作为枢纽是一种简单的方法，便是 
                16.  \* 正如前文看到的那样，在特殊情况下性能很低。从理论上讲实际使数组中值数据是最理想的枢纽 
                17.  \* 选择，是效率最高的方式，但实际上这个过程比排序本身需要更长的时间，因此这是不可行的。 
                18.  \* 一种折衷的方法，选择数组里的第一个，最后一个以及中间位置的数据中选择一个中间值，并设 
                19.  \* 置此数据项为枢纽，这种选择枢纽的方式为三数据项选中。 
                20.  \* 查找三个数据项的中值数据项比查找所有数据项中值快很多，在大多数通常情况下这种方法是又 
                21.  \* 快又有效的方法。但是有很特殊的数据排列命名三数据项先中的方法也很低效。 
                22.  \* 
                23.  
                24. /\*\* 
                25.  \* 定义一个数组类，封装了对自身数据的排序。 
                26.  \*/  
                27. class ArrayIns \{  
                28.   
                29.     private long\[\] theArray;  
                30.     private int nElems;  
                31.   
                32.     public ArrayIns(int max) \{  
                33.         theArray = new long\[max\];  
                34.         nElems = 0;  
                35.     \}  
                36.   
                37.     public void insert(long value) \{  
                38.         theArray\[nElems\] = value;  
                39.         nElems++;  
                40.     \}  
                41.   
                42.     public void display() \{  
                43.         System.out.print("A=");  
                44.         for (int j = 0; j < nElems; j++) \{  
                45.             System.out.print(theArray\[j\] + " ");  
                46.         \}  
                47.         System.out.println("");  
                48.     \}  
                49. /\*\* 
                50.  \* 快速排序主方法 
                51.  \*/  
                52.     public void quickSort() \{  
                53.         recQuickSort(0, nElems - 1);  
                54.     \}  
                55.   
                56. /\*\* 
                57.  \* 递归调用快速的排序核心方法 
                58.  \* @param left 
                59.  \* @param right 
                60.  \*/  
                61.     public void recQuickSort(int left, int right) \{  
                62.         int size = right-left + 1;  
                63.         if (size <= 3) \{  
                64.             manualSort(left, right);  
                65.         \} else \{  
                66.             long median = medianOf3(left, right);//三数取中值  
                67.             int partition=partitionIt(left,right,median);//三数据取中值作为枢纽进行划分  
                68.             recQuickSort(left, partition - 1);//递归排序数组左子元素  
                69.             recQuickSort(partition + 1,right);//递归排序数据左子元素  
                70.         \}  
                71.     \}  
                72.   
                73. /\*\* 
                74.  \* 三数据选中 
                75.  \* @param left 
                76.  \* @param right 
                77.  \* @return 
                78.  \*/  
                79.     public long medianOf3(int left, int right) \{  
                80.         int center = (left + right) / 2;  
                81.   
                82.         if (theArray\[left\] > theArray\[center\]) \{  
                83.             swap(left, center);  
                84.         \}  
                85.         if (theArray\[left\] > theArray\[right\]) \{  
                86.             swap(left, right);  
                87.         \}  
                88.         if (theArray\[center\] > theArray\[right\]) \{  
                89.             swap(center, right);  
                90.         \}  
                91.         swap(center, right - 1);  
                92.         return theArray\[right - 1\];  
                93.     \}  
                94.       
                95. /\*\* 
                96.  \* 交换数据 
                97.  \* @param dex1 
                98.  \* @param dex2 
                99.  \*/  
                100.     public void swap(int dex1, int dex2) \{  
                101.         long temp = theArray\[dex1\];  
                102.         theArray\[dex1\] = theArray\[dex2\];  
                103.         theArray\[dex2\] = temp;  
                104.     \}  
                105.       
                106. /\*\* 
                107.  \* 根据三数据选中进行划分 
                108.  \* @param left 
                109.  \* @param right 
                110.  \* @param pivot 
                111.  \* @return 
                112.  \*/  
                113.     public int partitionIt(int left, int right, long pivot) \{  
                114.         int leftPtr = left;//定位到最左元素  
                115.         int rightPtr = right-1;//定位到枢纽  
                116.   
                117.         while (true) \{  
                118.             while (theArray\[++leftPtr\] < pivot);//寻找大于枢纽元素  
                119.             while (theArray\[--rightPtr\] > pivot);//寻找小于枢纽元素  
                120.             if (leftPtr >= rightPtr) \{ //确定划分结束退出循环  
                121.                 break;  
                122.             \} else \{  
                123.                 swap(leftPtr, rightPtr);//交换需划分的元素  
                124.             \}  
                125.         \}  
                126.         swap(leftPtr, right-1);//恢复枢纽到正确位置  
                127.         return leftPtr;//返回枢纽  
                128.     \}  
                129. /\*\* 
                130.  \* 手动排序 
                131.  \* @param left 
                132.  \* @param right 
                133.  \*/  
                134.     public void manualSort(int left, int right) \{  
                135.         int size = right-left + 1;  
                136.         if (size <= 1) \{ //当元素为1时直接返回  
                137.             return;  
                138.         \}  
                139.         if (size == 2) \{  
                140.             if (theArray\[left\] > theArray\[right\]) \{ //当元素为2时排序  
                141.                 swap(left, right);  
                142.             \}  
                143.             return;  
                144.         \} else \{ //当元素为3时排序  
                145.             if (theArray\[left\] > theArray\[right - 1\]) \{  
                146.                 swap(left, right - 1);  
                147.             \}  
                148.             if (theArray\[left\] > theArray\[right\]) \{  
                149.                 swap(left, right);  
                150.             \}  
                151.             if (theArray\[right - 1\] > theArray\[right\]) \{  
                152.                 swap(right - 1, right);  
                153.             \}  
                154.         \}  
                155.     \}  
                156. \}  
                157.   
                158. /\*\* 
                159.  \* 主类 
                160.  \*/  
                161. public class QuickSort2 \{  
                162.   
                163.   
                164.     public static void main(String\[\] args) \{  
                165.         int maxSize = 15;  
                166.         ArrayIns arr = new ArrayIns(maxSize);  
                167.         for (int j = 0; j < maxSize; j++) \{ //随机生机数据插入数组中  
                168.             long n = (int) (java.lang.Math.random() \* 99);  
                169.             arr.insert(n);  
                170.         \}  
                171.         System.out.println("显示排序前数据");  
                172.         arr.display();  
                173.         arr.quickSort();  
                174.         System.out.println("显示排序后数据");  
                175.         arr.display();  
                176.     \}  
                177. \}  
                178.   
                179. /\*\* 
                180.  \*运行结果： 
                181.  \*显示排序前数据 
                182.  \*A=38 62 44 89 50 91 36 60 47 22 83 7 33 31 38 
                183.  \*显示排序后数据 
                184.  \*A=7 22 31 33 36 38 38 44 47 50 60 62 83 89 91  
                185.  \*/  
                186.   
                187. /\*\* 
                188.  \* 总结： 
                189.  \* 快速排序是常用排序中效率最高的一种排序方式。 
                190.  \* 但在应用中的一此特殊情况影响他的效率，这不是算法本身的问题，而是如果实现的问题。 
                191.  \* 三数据项选中方法很好的解决了这样的问题。 
                192.  \*/   
                    
        2.  /\*\* 
        3.   \* @author SunnyMoon 
        4.   \*/  
        5.    
        6.  /\*\*\*\*\*\*\*\*\*\* 
        7.   \* 概念介绍： 
        8.   \* \*\*\*\*\*\*\*\* 
        9.   \*处理小划分： 
        10.  \* 1. 如果使用三数据项取中值的方法取枢纽，这时快速排序算法不能执行三个或者小于三个数据项 
        11.  \* 的划分规则，这时数字3就为排序算法的切割点。在上一篇中对三个或三个以下的数据排序时 
        12.  \* 使用手动的方式排序，这种方式实践中不是最好的选择。 
        13.  \* 2. 处理小划分的另一个选择是使用插入排序，当使用插入排序时可以将划分设定为10或其它任何 
        14.  \* 数，试验不同的切割点的值以找到最佳的切割点，专家推荐使用9为切割点。对小的子数组使用 
        15.  \* 插入排序被证时为最快的一种方法。将插入排序和快速排序相结合，可以把快速排序的性能发挥 
        16.  \* 到极极，本篇程序使用该方法。 
        17.  \* 4. 第三个选择是对数组整个使用快速排序不考虑处理小划分，当结束时数据基本有序了，然后 
        18.  \* 使用插入排序对数据排序。因为插入排序对基本有序的数组执行效率很高，许多专家提倡使用 
        19.  \* 这种方法，但是插入排序对小规模的数据排序很适合，随着数据规模的扩大性能下降明显。 
        20.  \* 
        21.  \* 消除递归： 
        22.  \* 很多人提倡对快速排序算法进行修改，取消递归包括重写算法用栈实践。但是对于现在的 
        23.  \* 系统来说消除递归所带来的改进不是很明显。 
        24.  \*/  
        25. class ArrayIns \{  
        26.   
        27.     private long\[\] theArray;  
        28.     private int nElems;  
        29.   
        30.     public ArrayIns(int max) \{  
        31.         theArray = new long\[max\];  
        32.         nElems = 0;  
        33.     \}  
        34.   
        35.     public void insert(long value) \{  
        36.         theArray\[nElems\] = value;  
        37.         nElems++;  
        38.     \}  
        39.   
        40.     public void display() \{  
        41.         System.out.print("A=");  
        42.         for (int j = 0; j < nElems; j++) \{  
        43.             System.out.print(theArray\[j\] + " ");  
        44.         \}  
        45.         System.out.println("");  
        46.     \}  
        47.   
        48.     /\*\* 
        49.      \* 快速排序主方法 
        50.      \*/  
        51.     public void quickSort() \{  
        52.         recQuickSort(0, nElems - 1);  
        53.     \}  
        54.   
        55.     /\*\* 
        56.      \* 递归调用快速的排序核心方法 
        57.      \* @param left 
        58.      \* @param right 
        59.      \*/  
        60.     public void recQuickSort(int left, int right) \{  
        61.         int size = right - left + 1;  
        62.         if (size < 10) \{  
        63.             insertionSort(left, right);  
        64.         \} else \{  
        65.             long median = medianOf3(left, right);//三数取中值  
        66.             int partition = partitionIt(left, right, median);//三数据取中值作为枢纽进行划分  
        67.             recQuickSort(left, partition - 1);//递归排序数组左子元素  
        68.             recQuickSort(partition + 1, right);//递归排序数据左子元素  
        69.         \}  
        70.     \}  
        71.   
        72.     /\*\* 
        73.      \* 三数据选中 
        74.      \* @param left 
        75.      \* @param right 
        76.      \* @return 
        77.      \*/  
        78.     public long medianOf3(int left, int right) \{  
        79.         int center = (left + right) / 2;  
        80.   
        81.         if (theArray\[left\] > theArray\[center\]) \{  
        82.             swap(left, center);  
        83.         \}  
        84.         if (theArray\[left\] > theArray\[right\]) \{  
        85.             swap(left, right);  
        86.         \}  
        87.         if (theArray\[center\] > theArray\[right\]) \{  
        88.             swap(center, right);  
        89.         \}  
        90.         swap(center, right - 1);  
        91.         return theArray\[right - 1\];  
        92.     \}  
        93.   
        94.     /\*\* 
        95.      \* 交换数据 
        96.      \* @param dex1 
        97.      \* @param dex2 
        98.      \*/  
        99.     public void swap(int dex1, int dex2) \{  
        100.         long temp = theArray\[dex1\];  
        101.         theArray\[dex1\] = theArray\[dex2\];  
        102.         theArray\[dex2\] = temp;  
        103.     \}  
        104.   
        105.     /\*\* 
        106.      \* 根据三数据选中进行划分 
        107.      \* @param left 
        108.      \* @param right 
        109.      \* @param pivot 
        110.      \* @return 
        111.      \*/  
        112.     public int partitionIt(int left, int right, long pivot) \{  
        113.         int leftPtr = left;//定位到最左元素  
        114.         int rightPtr = right - 1;//定位到枢纽  
        115.   
        116.         while (true) \{  
        117.             while (theArray\[++leftPtr\] < pivot);//寻找大于枢纽元素  
        118.             while (theArray\[--rightPtr\] > pivot);//寻找小于枢纽元素  
        119.             if (leftPtr >= rightPtr) \{ //确定划分结束退出循环  
        120.                 break;  
        121.             \} else \{  
        122.                 swap(leftPtr, rightPtr);//交换需划分的元素  
        123.             \}  
        124.         \}  
        125.         swap(leftPtr, right - 1);//恢复枢纽到正确位置  
        126.         return leftPtr;//返回枢纽  
        127.     \}  
        128.   
        129.     /\*\* 
        130.      \* 手动排序 
        131.      \* @param left 
        132.      \* @param right 
        133.      \*/  
        134.   
        135.     public void insertionSort(int left, int right) \{  
        136.         int in, out;//in为内循环指针，out为外循环指针  
        137.   
        138.         for (out = left + 1; out <= right; out++) \{  
        139.             long temp = theArray\[out\];//移除当前标记元素到临时变量  
        140.             in = out;//定位内循环  
        141.   
        142.             while (in > left && theArray\[in - 1\] >= temp) \{ //满足条件时向左移动元素  
        143.                 theArray\[in\] = theArray\[in - 1\];  
        144.                 --in;  
        145.             \}  
        146.             theArray\[in\] = temp;//插入当前标记元素到正确位置  
        147.         \}  
        148.     \}  
        149. \}  
        150.   
        151. /\*\* 
        152.  \* 主类 
        153.  \*/  
        154. public class QuickSort3 \{  
        155.   
        156.     public static void main(String\[\] args) \{  
        157.         int maxSize = 10;  
        158.         ArrayIns arr = new ArrayIns(maxSize);  
        159.         for (int j = 0; j < maxSize; j++) \{ //随机生机数据插入数组中  
        160.             long n = (int) (java.lang.Math.random() \* 99);  
        161.             arr.insert(n);  
        162.         \}  
        163.         System.out.println("显示排序前数据");  
        164.         arr.display();  
        165.         arr.quickSort();  
        166.         System.out.println("显示排序后数据");  
        167.         arr.display();  
        168.     \}  
        169. \}  
        170. /\*\* 
        171.  \* 运行结果： 
        172.  \* 显示排序前数据 
        173.  \* A=56 14 50 18 82 58 30 50 60 1 
        174.  \* 显示排序后数据 
        175.  \* A=1 14 18 30 50 50 56 58 60 82 
        176.  \*/  
        177.   
        178. /\*\* 
        179.  \* 总结： 
        180.  \* 快速排序是常用排序中效率最高的一种排序方式。 
        181.  \* 但在应用中的一此特殊情况影响他的效率，这不是算法本身的问题，而是如果实现的问题。 
        182.  \* 三数据项选中方法很好的解决了这样的问题。三数据选中方法不是最好的选择，可以将插入排序 
        183.  \* 与快速排序相结合的方式解决这样的问题，使快速排序算法发挥到极致。 
        184.  \*/

转载于:https://www.cnblogs.com/biggestfish/archive/2013/02/24/2927050.html