本文共 63999 字，大约阅读时间需要 213 分钟。

转自：落尘曦的博客：

 

原文链接：

 

 

1.大O表示法：粗略的量度方法即算法的速度是如何与数据项的个数相关的

 

算法                                                              大O表示法表示的运行时间

线性查找                                                              O(N)

二分查找                                                              O(logN)

无序数组的插入                                                        O(1)

有序数组的插入                                                        O(N)

无序数组的删除                                                        O(N)

有序数组的删除                                                        O(N)

O(1)是最优秀的,O(logN)良好,O(N)还可以,O(N2)稍差(在冒泡法中见到)

 

2. 排序

1. public class JWzw {

2.     //插入排序

3.     public void insertArray(Integer[] in ) {

4.         int tem = 0;

5.         int num = 0;

6.         int upnum = 0;

7.         for (int i = 0; i < in .length; i++) {

8.             for (int j = i - 1; j >= 0; j--) {

9.                 num++;

10.                 if ( in [j + 1] < in [j]) {

11.                     tem = in [j + 1]; in [j + 1] = in [j]; in [j] = tem;

12.                     upnum++;

13.                 } else {

14.                     break;

15.                 }

16.             }

17.         }

18.         for (int i = 0; i < in .length; i++) {

19.             System.out.print( in [i]);

20.             if (i < in .length - 1) {

21.                 System.out.print(",");

22.             }

23.         }

24.         System.out.println();

25.         System.out.println("插入排序循环次数:" + num);

26.         System.out.println("移动次数：" + upnum);

27.         System.out.print("\n\n\n");

28.     }

29.     //选择排序

30.     public void chooseArray(Integer[] in ) {

31.         int tem = 0;

32.         int num = 0;

33.         int upnum = 0;

34.         for (int i = 0; i < in .length; i++) {

35.             for (int j = 0; j < in .length - 1; j++) {

36.                 num++;

37.                 if ( in [j + 1] < in [j]) {

38.                     tem = in [j + 1]; in [j + 1] = in [j]; in [j] = tem;

39.                     upnum++;

40.                 }

41.             }

42.         }

43.         for (int i = 0; i < in .length; i++) {

44.             System.out.print( in [i]);

45.             if (i < in .length - 1) {

46.                 System.out.print(",");

47.             }

48.         }

49.         System.out.println();

50.         System.out.println("选择排序循环次数:" + num);

51.         System.out.println("移动次数：" + upnum);

52.         System.out.print("\n\n\n");

53.     }

54.     //冒泡排序

55.     public void efferArray(Integer[] in ) {

56.         int tem = 0;

57.         int num = 0;

58.         int upnum = 0;

59.         for (int i = 0; i < in .length; i++) {

60.             for (int j = i; j < in .length - 1; j++) {

61.                 num++;

62.                 if ( in [j + 1] < in [i]) {

63.                     tem = in [j + 1]; in [j + 1] = in [i]; in [i] = tem;

64.                     upnum++;

65.                 }

66.             }

67.         }

68.         for (int i = 0; i < in .length; i++) {

69.             System.out.print( in [i]);

70.             if (i < in .length - 1) {

71.                 System.out.print(",");

72.             }

73.         }

74.         System.out.println();

75.         System.out.println("冒泡排序循环次数:" + num);

76.         System.out.println("移动次数：" + upnum);

77.         System.out.print("\n\n\n");

78.     }

79.     //打印乘法口诀

80.     public void printMulti() {

81.         for (int j = 1; j < 10; j++) {

82.             for (int i = 1; i <= j; i++) {

83.                 System.out.print(i + " * " + j + " = " + j * i + "\t");

84.             }

85.             System.out.print("\t\n");

86.         }

87.         System.out.print("\n\n\n");

88.     }

89.     //打印N * 1 + N * 2 + N * 3 =num的所有组合

90.     public void printNumAssemble(int num) {

91.         for (int i = 0; i < num + 1; i++) {

92.             for (int j = 0; j < num / 2 + 1; j++) {

93.                 for (int in = 0; in < num / 3 + 1; in ++) {

94.                     if (i * 1 + j * 2 + in * 3 == num) {

95.                         System.out.println("小马" + i + ",\t中马" + j + ",\t大马" + in );

96.                     }

97.                 }

98.             }

99.         }

100.     }

101.     /**

102.  

103.  * @param args

104.  

105.  */

106.     public static void main(String[] args) {

107.         JWzw jwzw = new JWzw();

108.         int num = 3;

109.         jwzw.printMulti(); //打印乘法口诀

110.         jwzw.printNumAssemble(100); //打印N * 1 + N * 2 + N * 3 =num的所有组合

111.         Integer in [] = {

112.             8, 89, 5, 84, 3, 45, 12, 33, 77, 98, 456, 878, 654, 213, 897

113.         };

114.         jwzw.efferArray( in ); //冒泡排序

115.         Integer in1[] = {

116.             8, 89, 5, 84, 3, 45, 12, 33, 77, 98, 456, 878, 654, 213, 897

117.         };

118.         jwzw.insertArray(in1); //插入排序

119.         Integer in2[] = {

120.             8, 89, 5, 84, 3, 45, 12, 33, 77, 98, 456, 878, 654, 213, 897

121.         };

122.         jwzw.chooseArray(in2); //选择排序

123.         //int i = num++;

124.         //System.out.println(i);

125.         System.out.println(1000 >> 2);

126.     }

127. }

 

3. 优先级队列

1. class PriorityQueue {

2. private long[] a = null;

3. private int nItems = 0;

4. private int maxSize = 0;

5. public PriorityQueue(int maxSize) {

6. a = new long[maxSize];

7. this.maxSize = maxSize;

8. nItems = 0;

9. }

10. public void insert(long l) {

11. //优先级队列的插入不是队尾,而是选择一个合适的按照某种顺序插入的

12. //当队列长度为0时，如下

13. //不为0时,将所有比要插入的数小的数据后移,这样大的数就在队列的头部了

14. int i = 0;

15. if (nItems == 0) {

16. a[0] = l;

17. } else {

18. for (i = nItems - 1; i >= 0; i--) {

19. if (l < a[i]) a[i + 1] = a[i];

20. else break;

21. }

22. a[i + 1] = l;

23. }

24. nItems++;

25. }

26. public long remove() {

27. //移出的是数组最上端的数，这样减少数组元素的移动

28. return a[--nItems];

29. }

30. public boolean isEmpty() {

31. return (nItems == 0);

32. }

33. public boolean isFull() {

34. return (nItems == maxSize);

35. }

36. public int size() {

37. return nItems;

38. }

39. }

40. public class duilie { // 队列体类

41. private duilie s;

42. private String data;

43. duilie(String data) {

44. this.data = data;

45. }

46. public String getData() {

47. return data;

48. }

49. public void setData(String data) {

50. this.data = data;

51. }

52. public duilie getS() {

53. return s;

54. }

55. public void setS(duilie s) {

56. this.s = s;

57. }

58. }

59. public class duiliecz { // 队列操作类

60. /**

61.  

62. * @param args

63.  

64. */

65. private int i = 0; // 队列长

66. private duilie top = new duilie(""); // 队列头

67. private duilie end = new duilie(""); // 队列尾

68. public void add(String s) { // 添加队列

69. duilie m = new duilie(s);

70. if (i != 0) {

71. m.setS(top.getS());

72. top.setS(m);

73. } else {

74. top.setS(m);

75. end.setS(m);

76. }

77. i++;

78. }

 

4. 队列

 

1. public void del() { // 删除队尾

2. if (i == 0) {

3. return;

4. } else if (i == 1) {

5. top.setS(null);

6. end.setS(null);

7. } else {

8. duilie top1 = new duilie(""); // 队列底查找用缓存

9. top1.setS(top.getS());

10. while (!top1.getS().getS().equals(end.getS())) {

11. top1.setS(top1.getS().getS());

12. }

13. end.setS(top1.getS());

14. }

15. i--;

16. }

17. public static void main(String[] args) {

18. // TODO Auto-generated method stub

19. duiliecz m = new duiliecz();

20. m.add("1");

21. m.add("2");

22. m.add("3");

23. m.add("4");

24. for (int n = 0; n < 4; n++) {

25. m.del();

26. }

27. }

28. public int getI() {

29. return i;

30. }

31. public duilie getEnd() {

32. return end;

33. }

34. public duilie getTop() {

35. return top;

36. }

37. }

 

 

5. 栈

 

1. public class Stack {

2. int[] arr;

3. int len = 0;

4. public Stack() {

5. arr = new int[100];

6. }

7. public Stack(int n) {

8. arr = new int[n];

9. }

10. public int size() {

11. return len + 1;

12. }

13. // 扩大数组

14. public void resize() {

15. int[] b = new int[arr.length * 2];

16. System.arraycopy(arr, 0, b, 0, arr.length);

17. arr = b;

18. }

19. public void show() {

20. for (int i = 0; i < len; i++) {

21. System.out.print(arr[i] + " ");

22. }

23. System.out.println();

24. }

25. // 进栈

26. public void push(int a) {

27. if (len >= arr.length) resize();

28. arr[len] = a;

29. len++;

30. }

31. // 出栈

32. public int pop() {

33. if (len == 0) {

34. System.out.println();

35. System.out.println("stack is empty!");

36. return -1;

37. }

38. int a = arr[len - 1];

39. arr[len - 1] = 0;

40. len--;

41. return a;

42. }

43. }

 

 

 

6. 链表

1. class Node {

2. Object data;

3. Node next;

4. public Node(Object data) {

5. setData(data);

6. }

7. public void setData(Object data) {

8. this.data = data;

9. }

10. public Object getData() {

11. return data;

12. }

13. }

14. class Link {

15. Node head;

16. int size = 0;

17. public void add(Object data) {

18. Node n = new Node(data);

19. if (head == null) {

20. head = n;

21. } else {

22. Node current = head;

23. while (true) {

24. if (current.next == null) {

25. break;

26. }

27. current = current.next;

28. }

29. current.next = n;

30. }

31. size++;

32. }

33. public void show() {

34. Node current = head;

35. if (current != null) {

36. while (true) {

37. System.out.println(current);

38. if (current == null) {

39. break;

40. }

41. current = current.next;

42. }

43. } else {

44. System.out.println("link is empty");

45. }

46. }

47. public Object get(int index) {

48. // ....

49. }

50. public int size() {

51. return size;

52. }

53. }

 

 

7. 单链表

1. class Node // 节点类，单链表上的节点

2. {

3. String data; // 数据域，存放String类的数据

4. Node next; // 指向下一个节点

5. Node(String data) {

6. this.data = data; // 构造函数

7. }

8. String get() {

9. return data; // 返回数据

10. }

11. }

12. class MyLinkList // 链表类

13. {

14. Node first; // 头节点

15. int size; // 链表长度

16. MyLinkList(String arg[]) {

17. // Node first = new Node("head");//生成头节点

18. first = new Node("head"); // J.F. 这里不需要定义局部变量 first

19. // 如果定义了局部变量，那成员变量 first 就一直没有用上

20. // 所以，它一直为空

21. size = 0;

22. Node p = first;

23. for (int i = 0; i < arg.length; i++) // 将arg数组中的元素分别放入链表中

24. {

25. Node q = new Node(arg[i]);

26. q.next = p.next; // 每一个节点存放一个arg数组中的元素

27. p.next = q;

28. p = p.next;

29. size++;

30. }

31. }

32. MyLinkList() // 无参数构造函数

33. {

34. // Node first = new Node("head");

35. first = new Node("head"); // J.F. 这里犯了和上一个构造方法同样的错误

36. size = 0;

37. }

38. int size() // 返回链表长度

39. {

40. return size;

41. }

42. void insert(Node a, int index) // 将节点a 插入链表中的第index个位置

43. {

44. Node temp = first;

45. for (int i = 0; i < index; i++) {

46. temp = temp.next; // 找到插入节点的前一节点

47. }

48. a.next = temp.next; // 插入节点

49. temp.next = a;

50. size++;

51. }

52. Node del(int index) // 删除第index个节点，并返回该值

53. {

54. Node temp = first;

55. for (int i = 0; i < index; i++) {

56. temp = temp.next; // 找到被删除节点的前一节点

57. }

58. Node node = temp.next;

59. temp.next = node.next;

60. size--; // 删除该节点，链表长度减一

61. return node;

62. }

63. void print() // 在屏幕上输出该链表（这段程序总是出错，不知道错在哪里）

64. {

65. Node temp = first;

66. for (int i = 1; i < size; i++) // 将各个节点分别在屏幕上输出

67. {

68. temp = temp.next;

69. System.out.print(temp.get() + "->");

70. }

71. }

72. void reverse() // 倒置该链表

73. {

74. for (int i = 0; i < size; i++) {

75. insert(del(size - 1), 0); // 将最后一个节点插入到最前

76. // J.F. 最后一个节点的 index 应该是 size - 1

77. // 因为第一个节点的 index 是 0

78. }

79. }

80. String get(int index) // 查找第index个节点，返回其值

81. {

82. if (index >= size) {

83. return null;

84. }

85. Node temp = first;

86. for (int i = 0; i < index; i++) {

87. temp = temp.next; // 找到被查找节点的前一节点

88. }

89. return temp.next.get();

90. }

91. }

92. class MyStack // 堆栈类，用单链表实现

93. {

94. MyLinkList tmp;

95. Node temp;

96. MyStack() {

97. // MyLinkList tmp = new MyLinkList();

98. tmp = new MyLinkList(); // J.F. 和 MyLinkList 构造方法同样的错误

99. }

100. void push(String a) // 压栈，即往链表首部插入一个节点

101. {

102. Node temp = new Node(a);

103. tmp.insert(temp, 0);

104. }

105. String pop() // 出栈，将链表第一个节点删除

106. {

107. Node a = tmp.del(0);

108. return a.get();

109. }

110. int size() {

111. return tmp.size();

112. }

113. boolean empty() // 判断堆栈是否为空

114. {

115. if (tmp.size() == 0) return false;

116. else return true;

117. }

118. }

119. public class MyLinkListTest // 测试程序部分

120. {

121. public static void main(String arg[]) // 程序入口

122. {

123. if ((arg.length == 0) || (arg.length > 10)) System.out.println("长度超过限制或者缺少参数");

124. else {

125. MyLinkList ll = new MyLinkList(arg); // 创建一个链表

126. ll.print(); // 先输出该链表（运行到这一步抛出异常）

127. ll.reverse(); // 倒置该链表

128. ll.print(); // 再输出倒置后的链表

129. String data[] = new String[10];

130. int i;

131. for (i = 0; i < ll.size(); i++) {

132. data[i] = ll.get(i); // 将链表中的数据放入数组

133. }

134. // sort(data);// 按升序排列data中的数据（有没有现成的排序函数？）

135. for (i = 0; i < ll.size(); i++) {

136. System.out.print(data[i] + ";"); // 输出数组中元素

137. }

138. System.out.println();

139. MyStack s = new MyStack(); // 创建堆栈实例s

140. for (i = 0; i < ll.size(); i++) {

141. s.push(data[i]); // 将数组元素压栈

142. }

143. while (!s.empty()) {

144. System.out.print(s.pop() + ";"); // 再将堆栈里的元素弹出

145. }

146. }

147. }

148. }

 

8. 双端链表

1. class Link {

2. public int iData = 0;

3. public Link next = null;

4. public Link(int iData) {

5. this.iData = iData;

6. }

7. public void display() {

8. System.out.print(iData + " ");

9. }

10. }

11. class FirstLastList {

12. private Link first = null;

13. private Link last = null;

14. public FirstLastList() {

15. first = null;

16. last = null;

17. }

18. public void insertFirst(int key) {

19. Link newLink = new Link(key);

20. if (this.isEmpty()) last = newLink;

21. newLink.next = first;

22. first = newLink;

23. }

24. public void insertLast(int key) {

25. Link newLink = new Link(key);

26. if (this.isEmpty()) first = newLink;

27. else last.next = newLink;

28. last = newLink;

29. }

30. public Link deleteFirst() {

31. Link temp = first;

32. if (first.next == null) last = null;

33. first = first.next;

34. return temp;

35. }

36. public boolean isEmpty() {

37. return (first == null);

38. }

39. public void displayList() {

40. System.out.print("List (first-->last): ");

41. Link current = first;

42. while (current != null) {

43. current.display();

44. current = current.next;

45. }

46. System.out.println("");

47. }

48. }

49. class FirstLastListApp {

50. public static void main(String[] args) {

51. // TODO Auto-generated method stub

52. FirstLastList theList = new FirstLastList();

53. theList.insertFirst(22); // insert at front

54. theList.insertFirst(44);

55. theList.insertFirst(66);

56. theList.insertLast(11); // insert at rear

57. theList.insertLast(33);

58. theList.insertLast(55);

59. theList.displayList(); // display the list

60. theList.deleteFirst(); // delete first two items

61. theList.deleteFirst();

62. theList.displayList(); // display again

63. }

64. }

 

9. 有序链表

1. package arithmetic;

2. class Link {

3. public int iData = 0;

4. public Link next = null;

5. public Link(int iData) {

6. this.iData = iData;

7. }

8. public void display() {

9. System.out.print(iData + " ");

10. }

11. }

12. class SortedList {

13. private Link first = null;

14. public SortedList() {

15. first = null;

16. }

17. public void insert(int key) {

18. Link newLink = new Link(key);

19. Link previous = null;

20. Link current = first;

21. // while的第一个条件是没有到达链表的尾端,第二个是按顺序找到一个合适的位置

22. while (current != null && key > current.iData) {

23. previous = current;

24. current = current.next;

25. }

26. // 如果是空表或者要插入的元素最小,则在表头插入key

27. if (current == first) first = newLink;

28. else previous.next = newLink;

29. newLink.next = current;

30. }

31. /**

32.  

33. * 删除表头的节点

34.  

35. *

36.  

37. * @return 要删除的节点

38.  

39. */

40. public Link remove() {

41. Link temp = first;

42. first = first.next;

43. return temp;

44. }

45. public boolean isEmpty() {

46. return (first == null);

47. }

48. public void displayList() {

49. System.out.print("List (first-->last): ");

50. Link current = first; // start at beginning of list

51. while (current != null) // until end of list,

52. {

53. current.display(); // print data

54. current = current.next; // move to next link

55. }

56. System.out.println("");

57. }

58. }

59. class SortedListApp {

60. public static void main(String[] args) { // create new list

61. SortedList theSortedList = new SortedList();

62. theSortedList.insert(20); // insert 2 items

63. theSortedList.insert(40);

64. theSortedList.displayList(); // display list

65. theSortedList.insert(10); // insert 3 more items

66. theSortedList.insert(30);

67. theSortedList.insert(50);

68. theSortedList.displayList(); // display list

69. theSortedList.remove(); // remove an item

70. theSortedList.displayList(); // display list

71. }

72. }

 

 

10. 双向链表

1. class Link {

2. // 双向链表,有两个指针,一个向前,一个向后

3. public int iData = 0;

4. public Link previous = null;

5. public Link next = null;

6. public Link(int iData) {

7. this.iData = iData;

8. }

9. public void display() {

10. System.out.print(iData + " ");

11. }

12. }

13. class DoublyLinked {

14. // 分别指向链表的表头和表尾

15. private Link first = null;

16. private Link last = null;

17. public boolean isEmpty() {

18. return first == null;

19. }

20. /**

21.  

22. * 在表头插入数据

23.  

24. *

25.  

26. * @param 要插入的节点的数据

27.  

28. */

29. public void insertFirst(int key) {

30. Link newLink = new Link(key);

31. // 如果开始链表为空,则插入第一个数据后,last也指向第一个数据

32. if (this.isEmpty()) last = newLink;

33. else { // 表不为空的情况

34. first.previous = newLink;

35. newLink.next = first;

36. }

37. // 无论怎样,插入后都的让first重新指向第一个节点

38. first = newLink;

39. }

40. public void insertLast(int key) { // 在尾端插入数据,同上

41. Link newLink = new Link(key);

42. if (this.isEmpty()) first = newLink;

43. else {

44. last.next = newLink;

45. newLink.previous = last;

46. }

47. last = newLink;

48. }

49. /**

50.  

51. * 在指定的节点后插入数据

52.  

53. *

54.  

55. * @param key

56.  

57. * 指定的节点的值

58.  

59. * @param iData

60.  

61. * 要插入的数据

62.  

63. * @return 是否插入成功

64.  

65. */

66. public boolean insertAfter(int key, int iData) {

67. Link newLink = new Link(key);

68. Link current = first;

69. // 从first开始遍历,看能否找到以key为关键字的节点

70. while (current.iData != key) {

71. current = current.next;

72. // 若能找到就跳出循环,否则返回false,插入失败

73. if (current == null) return false;

74. }

75. // 如果插入点在last的位置

76. if (current == last) {

77. last = newLink;

78. } else { // 非last位置,交换各个next和previous的指针

79. newLink.next = current.next;

80. current.next.previous = newLink;

81. }

82. current.next = newLink;

83. newLink.previous = current;

84. return true;

85. }

86. /**

87.  

88. * 删除表头的节点

89.  

90. *

91.  

92. * @return

93.  

94. */

95. public Link deleteFirst() {

96. Link temp = first;

97. // 如果表中只有一个元素,删除后则为空表,所以last=null

98. if (first.next == null) last = null;

99. else

100. // 否则,让第二个元素的previous=null

101. first.next.previous = null;

102. // 删除头指针,则first指向原来的second

103. first = first.next;

104. return temp;

105. }

106. public Link deleteLast() { // 同上

107. Link temp = last;

108. if (last.previous == null) first = null;

109. else last.previous.next = null;

110. last = last.previous;

111. return temp;

112. }

113. public Link deleteKey(int key) {

114. Link current = first;

115. // 遍历整个链表查找对应的key,如果查到跳出循环,否则...

116. while (current.iData != key) {

117. current = current.next;

118. // ...否则遍历到表尾,说明不存在此key,返回null,删除失败

119. if (current == null) return null;

120. }

121. if (current == first) first = first.next;

122. else current.previous.next = current.next;

123. if (current == last) last = last.previous;

124. else current.next.previous = current.previous;

125. return current;

126. }

127. public void displayForward() {

128. Link current = first;

129. while (current != null) {

130. current.display();

131. current = current.next;

132. }

133. System.out.println();

134. }

135. public void displayBackward() {

136. Link current = last;

137. while (current != null) {

138. current.display();

139. current = current.previous;

140. }

141. System.out.println();

142. }

143. }

144. class DoublyLinkedApp {

145. public static void main(String[] args) { // make a new list

146. DoublyLinked theList = new DoublyLinked();

147. theList.insertFirst(22); // insert at front

148. theList.insertFirst(44);

149. theList.insertFirst(66);

150. theList.insertLast(11); // insert at rear

151. theList.insertLast(33);

152. theList.insertLast(55);

153. theList.displayForward(); // display list forward

154. theList.displayBackward(); // display list backward

155. theList.deleteFirst(); // delete first item

156. theList.deleteLast(); // delete last item

157. theList.deleteKey(11); // delete item with key 11

158. theList.displayForward(); // display list forward

159. theList.insertAfter(22, 77); // insert 77 after 22

160. theList.insertAfter(33, 88); // insert 88 after 33

161. theList.displayForward(); // display list forward

162. }

163. }

 

 

11. 实现二叉树前序遍历迭代器

 

1. class TreeNode这个类用来声明树的结点，其中有左子树、右子树和自身的内容。

2. class MyTree这个类用来声明一棵树，传入根结点。这里设计的比较简单

3. class TreeEum这个类是树的迭代器，通过 MyTree类的方法获取，这里主要就是设计它了。代码如下：

4. //TreeNode类，使用了泛型，由于比较简单，考试.大提示不作解释

5. 　　 class TreeNode < E > {

6. E node;　　

7. private TreeNode < String > left;　　

8. private TreeNode < String > right;　　

9. public TreeNode(E e) {　　

10. this(e, null, null);

11. }　　

12. public TreeNode(E e, TreeNode < String > left, TreeNode < String > right) {　　

13. this.node = e;　　

14. this.left = left;　　

15. this.right = right;

16. }　　

17. public TreeNode < String > left() {　　

18. return left;

19. }　　

20. public TreeNode < String > right() {　　

21. return right;

22. }

23. }

24. // MyTree类，没什么功能，传入根结点构造，getEnumerator()方法获取迭代器。

25. 　　

26. class MyTree {

27. TreeNode < String > root;　　

28. public MyTree(TreeNode < String > root) {　　

29. this.root = root;

30. }　　

31. public TreeEnum getEnumerator() {　　

32. return new TreeEnum(root);

33. }

34. }

35. // 这个类为迭代器，有详细解释，相信各位能看懂。在栈中用了两次泛型。

36. 　　

37. import java.util.Stack;　　

38. public class TreeEnum {　　

39. private TreeNode < String > root;　　

40. private Stack < TreeNode < String >> store; /* 保存遍历左子树但未遍历右子树的结点 */ 　　

41. private TreeNode < String > next;　　

42. public TreeEnum(TreeNode < String > root) {　　

43. this.root = root;

44. store = new Stack < TreeNode < String >> ();

45. next = root;

46. }　　

47. public TreeNode < String > next() {

48. TreeNode < String > current = next;　　

49. if (next != null) {

50. /* 如果当前结点的左子树不为空,则遍历左子树,并标记当前结点未遍历右子树 */

51. 　　

52. if (next.left() != null) {

53. store.push(next);

54. next = next.left();

55. }

56. // 如果当前结点的左子树为空,则遍历右子树

57. 　　

58. else if (next.right() != null) {

59. next = next.right();

60. }

61. /* 如果当前结点为叶子,则找未遍历右子树的结点并且遍历它的右子树 */

62. 　　

63. else {　　

64. if (!store.empty()) /* 判断是否还有结点的右子树未遍历 */ {

65. TreeNode < String > tmp = store.pop();

66. /* 如果有未遍历右子树的结点,但它的右子树为空,且还有结点的右子树未遍历, */

67. /* 则一直往上取,直到取到未遍历右子树且右子树不为空的结点,遍历它的右子树. */

68. 　　

69. while ((tmp.right() == null) && !store.empty()) {

70. tmp = store.pop();

71. }

72. next = tmp.right();

73. }　　

74. else {

75. /* 如果没有哪个结点右子树未遍历,则表示没有下一个结点了,设置next为null */

76. next = null;

77. }

78. }

79. }　　

80. return current;

81. }　　

82. public boolean hasMoreElement() {　　

83. return next != null;

84. }

85. }　　下面写个测试类，不作解释，相信大家看得懂　　

86. public class TreeReader {　　

87. public static void main(String[] args) {

88. TreeNode < String > n1 = new TreeNode < String > ("n1");

89. TreeNode < String > n2 = new TreeNode < String > ("n2");

90. TreeNode < String > n3 = new TreeNode < String > ("n3");

91. TreeNode < String > n4 = new TreeNode < String > ("n4");

92. TreeNode < String > n5 = new TreeNode < String > ("n5");

93. TreeNode < String > n6 = new TreeNode < String > ("n6", null, n1);

94. TreeNode < String > n7 = new TreeNode < String > ("n7", n2, null);

95. TreeNode < String > n8 = new TreeNode < String > ("n8", n7, null);

96. TreeNode < String > n9 = new TreeNode < String > ("n9", null, n5);

97. TreeNode < String > n10 = new TreeNode < String > ("n10", n4, n9);

98. TreeNode < String > n11 = new TreeNode < String > ("n11", n6, n8);

99. TreeNode < String > n12 = new TreeNode < String > ("n12", n3, n10);

100. TreeNode < String > root = new TreeNode < String > ("root", n11, n12);

101. MyTree tree = new MyTree(root);

102. TreeEnum eum = tree.getEnumerator();　　

103. while (eum.hasMoreElement()) {

104. System.out.print(eum.next().node + "--");

105. }

106. System.out.println("end");

107. }

108. }

 

 

12. 迭代器

1. package TreeIterator;

2. public interface Iterator {

3. public boolean hasNext();

4. public Object next();

5. }这个接口我们有

6. 2个方法， hasNext()是否还有下一条数据， next返回具体的 Object这里也就是树。我们先不必要忙着做他的实现类，我们现在要来做的是这个容器（不是 JAVA中容器，与 arraylist什么的无关），正所谓树的容器是什么，是山也！我们想想山应该具有什么呢！？首先它要有种植树的功能，这里可以看作添加树。我们可以想像山的功能是和树相互关联的，那么他们之间是什么关系呢，我们给他们一种聚合的关系，聚合的关系大家可以参考 UML图，我在这里给出它的一种程序表现形式。

7. package TreeIterator;

8. public class Hall {

9. Tree[] tree; // 这里可以看作是聚合关系

10. private int index; // 指向Tree[]的标签

11. public Hall(int maxNumber) {

12. tree = new Tree[maxNumber];

13. index = 0;

14. }

15. public void add(Tree tree) {

16. this.tree[index] = tree;

17. index++;

18. }

19. public Iterator connectIterator() {

20. return new TreeIterator(this);

21. }

22. }

23.  

24. 这里我们定义的山可以抽象出

25. Hall类来， Tree[] tree可以看作是山和树之间的一种聚合关系。 add方法就是添加树。问题来了，山和树有了关系，那么山和迭代器有什么关系呢。它们之间肯定有一种关系。我们有了这个容器（山），就要把这个容器来实现迭代的方法： hasNext()和 Next().恩这里我们可以看出，山和迭代器之间也是一种关联关系。我们就把它看成是一种聚合关系（TIP：聚合关系一种特殊的关联关系）。我们可以通过一个 connectIterator方法来链接山和迭代器，接下来我们要去做一个具体的迭代类，这个具体的类中间有了 hasNext()和 Next()的具体实现方法

26.  

27. package TreeIterator;

28. public class TreeIterator implements Iterator {

29. private int last = 0;

30. private Hall hall;

31. public TreeIterator(Hall hall) {

32. this.hall = hall;

33. }

34. public boolean hasNext() {

35. if (last < hall.tree.length) return true;

36. else return false;

37. }

38. public Tree next() {

39. Tree t = hall.tree[last];

40. last++;

41. return t;

42. }

43. }

44.  
45.  

46. 这里Hall hall就可以看作是一种关联关系，我们要把山和迭代器联系起来就通过构造函数来实现， hasNext和 next实现方法就体现出来了有了山，有了迭代器，可是树还没有定义，不过这个树的方法还很好解决！树不关联其他的事务，我们可以简单的这么写：

47.  

48. package TreeIterator;

49. public class Tree {

50. private String name;

51. public Tree(String name) {

52. this.name = name;

53. }

54. public String getName() {

55. return this.name;

56. }

57. }

58.  

59. 好了似乎我们整个工程完工了，我们现在来模拟一下农民老大伯来种树撒肥的过程；

60.  

61. package TreeIterator;

62. public class Pren {

63. public Pren() {}

64. public static void main(String[] args) {

65. Hall hall = new Hall(4);

66. hall.add(new Tree("苹果树"));

67. hall.add(new Tree("梨树"));

68. hall.add(new Tree("橘子树"));

69. hall.add(new Tree("凤梨树"));

70. for (Iterator i = hall.connectIterator(); i.hasNext();) {

71. String Type = ((Tree)(i.next())).getName();

72. if (Type == "苹果树") {

73. System.out.println("洒苹果树的农药,");

74. }

75. if (Type == "梨树") {

76. System.out.println("洒梨树的农药");

77. }

78. if (Type == "橘子树") {

79. System.out.println("洒橘子树的农药,洒了也没用,还没到成熟日,现在没结果实");

80. }

81. if (Type == "凤梨树") {

82. System.out.println("南风天，湿气大，让它烂在地里吧");

83. }

84. }

85. }

86. }

87. 种4个树，山小而五脏俱全，更像一个土包，再要有树才行啊，所以 4个树的实例出现。好了接下来种树，几毫秒解决！山了有我们就要把山放到迭代器中间去了。遍历这个山（容器）。联想我们看看 arrayList中的迭代器模式是怎么实现的！

88. ArrayList a = new ArrayList();

89. a.add("a1");

90. a.add("a2");

91. a.add("a3");

92. a.add("a4");

93. for (Iterator i = a.iterator(); i.hasNext();) {

94. System.out.println(i.next().toString());

95. }

 

13. 合并搜索算法

1. public class MergeSortArray {

2. private long[] theArray;

3. private int nElems;

4. public MergeSortArray(int max) {

5. theArray = new long[max];

6. nElems = 0;

7. }

8. public void insert(long value) {

9. theArray[nElems] = value; // insert it

10. nElems++; // increment size

11. }

12. public void display() {

13. for (int j = 0; j < nElems; j++) System.out.print(theArray[j] + " ");

14. System.out.println("");

15. }

16. public void mergeSort() {

17. long[] workSpace = new long[nElems];

18. recMergeSort(workSpace, 0, nElems - 1);

19. }

20. private void recMergeSort(long[] workSpace, int lowerBound, int upperBound) {

21. if (lowerBound == upperBound) // if range is 1,

22. return; // no use sorting

23. else { // find midpoint

24. int mid = (lowerBound + upperBound) / 2;

25. // sort low half

26. recMergeSort(workSpace, lowerBound, mid);

27. // sort high half

28. recMergeSort(workSpace, mid + 1, upperBound);

29. // merge them

30. merge(workSpace, lowerBound, mid + 1, upperBound);

31. }

32. }

33. private void merge(long[] workSpace, int lowPtr, int highPtr, int upperBound) {

34. int j = 0; // workspace index

35. int lowerBound = lowPtr;

36. int mid = highPtr - 1;

37. int n = upperBound - lowerBound + 1; // # of items

38. while (lowPtr <= mid && highPtr <= upperBound)

39. if (theArray[lowPtr] < theArray[highPtr]) workSpace[j++] = theArray[lowPtr++];

40. else workSpace[j++] = theArray[highPtr++];

41. while (lowPtr <= mid) workSpace[j++] = theArray[lowPtr++];

42. while (highPtr <= upperBound) workSpace[j++] = theArray[highPtr++];

43. for (j = 0; j < n; j++) theArray[lowerBound + j] = workSpace[j];

44. }

45. public static void main(String[] args) {

46. int maxSize = 100; // array size

47. MergeSortArray arr = new MergeSortArray(maxSize); // create the array

48. arr.insert(14);

49. arr.insert(21);

50. arr.insert(43);

51. arr.insert(50);

52. arr.insert(62);

53. arr.insert(75);

54. arr.insert(14);

55. arr.insert(2);

56. arr.insert(39);

57. arr.insert(5);

58. arr.insert(608);

59. arr.insert(36);

60. arr.display();

61. arr.mergeSort();

62. arr.display();

63. }

64. }

 

14. 递归

1. public class Recursion {

2.  

3. public static void main(String[] args) {

4. // TODO Auto-generated method stub

5. Recursion re = new Recursion();

6. System.out.println(re.RecursionNum(10));

7. }

8. public int RecursionNum(int num) {

9. if (num > 0) {

10. return num + RecursionNum(num - 1);

11. }

12. Else {

13. return 0;

14. }

15. }

16. }

 

 

15. 归并排序

1. /**

2.  

3. * 归并排序，要求待排序的数组必须实现Comparable接口

4.  

5. */

6. public class MergeSort implements SortStrategy {

7. private Comparable[] bridge;

8. /**

9.  

10. * 利用归并排序算法对数组obj进行排序

11.  

12. */

13. public void sort(Comparable[] obj) {

14. if (obj == null) {

15. throw new NullPointerException("The param can not be null!");

16. }

17. bridge = new Comparable[obj.length]; // 初始化中间数组

18. mergeSort(obj, 0, obj.length - 1); // 归并排序

19. bridge = null;

20. }

21. /**

22.  

23. * 将下标从left到right的数组进行归并排序

24.  

25. *

26.  

27. * @param obj

28.  

29. * 要排序的数组的句柄

30.  

31. * @param left

32.  

33. * 要排序的数组的第一个元素下标

34.  

35. * @param right

36.  

37. * 要排序的数组的最后一个元素的下标

38.  

39. */

40. private void mergeSort(Comparable[] obj, int left, int right) {

41. if (left < right) {

42. int center = (left + right) / 2;

43. mergeSort(obj, left, center);

44. mergeSort(obj, center + 1, right);

45. merge(obj, left, center, right);

46. }

47. }

48. /**

49.  

50. * 将两个对象数组进行归并，并使归并后为升序。归并前两个数组分别有序

51.  

52. *

53.  

54. * @param obj

55.  

56. * 对象数组的句柄

57.  

58. * @param left

59.  

60. * 左数组的第一个元素的下标

61.  

62. * @param center

63.  

64. * 左数组的最后一个元素的下标

65.  

66. * @param right

67.  

68. * 右数组的最后一个元素的下标

69.  

70. */

71. private void merge(Comparable[] obj, int left, int center, int right) {

72. int mid = center + 1;

73. int third = left;

74. int tmp = left;

75. while (left <= center && mid <= right) { // 从两个数组中取出小的放入中间数组

76. if (obj[left].compareTo(obj[mid]) <= 0) {

77. bridge[third++] = obj[left++];

78. } else bridge[third++] = obj[mid++];

79. }

80. // 剩余部分依次置入中间数组

81. while (mid <= right) {

82. bridge[third++] = obj[mid++];

83. }

84. while (left <= center) {

85. bridge[third++] = obj[left++];

86. }

87. // 将中间数组的内容拷贝回原数组

88. copy(obj, tmp, right);

89. }

90. /**

91.  

92. * 将中间数组bridge中的内容拷贝到原数组中

93.  

94. *

95.  

96. * @param obj

97.  

98. * 原数组的句柄

99.  

100. * @param left

101.  

102. * 要拷贝的第一个元素的下标

103.  

104. * @param right

105.  

106. * 要拷贝的最后一个元素的下标

107.  

108. */

109. private void copy(Comparable[] obj, int left, int right) {

110. while (left <= right) {

111. obj[left] = bridge[left];

112. left++;

113. }

114. }

115. }

 

 

16. 希尔排序

1. 间隔序列：

2. h = 3 * h + 1， h = (h - 1) / 3

3. public class ShellSort {

4. /**

5.  

6. * @param args

7.  

8. */

9. public static void main(String[] args) {

10. // TODO Auto-generated method stub

11. ShellSort ss = new ShellSort();

12. int num[] = {

13. 546, 87, 21, 3124, 65, 2, 9, 3, 213, 54, 98, 23, 6, 4, 7,

14. 8, 123, 872, 61, 5, 8954

15. };

16. ss.shellArray(num);

17. for (int i = 0; i < num.length; i++) {

18. System.out.println(num[i]);

19. }

20. }

21. public void shellArray(int[] num) {

22. int i = 1;

23. int tem, in ;

24. for (; i < num.length / 3;) {

25. i = 3 * i + 1;

26. }

27. for (; i >= 1;) {

28. for (int j = i; j < num.length; j++) {

29. tem = num[j]; in = j;

30. while ( in > i - 1 && num[ in -i] >= tem) {

31. num[ in ] = num[ in -i]; in = in -i;

32. }

33. num[ in ] = tem;

34. }

35. i = (i - 1) / 3;

36. }

37. }

38. }

 

17. 快速排序

1. class QuickSort {

2. private int[] data;

3. QuickSort(int[] data) {

4. this.data = data;

5. }

6. public void quickSort() {

7. recQuickSort(data, 0, data.length - 1);

8. }

9. private void recQuickSort(int[] data, int low, int high) {

10. // 设置两个滑标

11. int lowCursor = low + 1;

12. int highCursor = high;

13. // 交换时的临时变量

14. int temp = 0;

15. // 比较枢值,设为数组的第一个值

16. int medi = data[low];

17. while (true) {

18. // 从低端开始查找，确定大于数 data[low] 所在的位置

19. while (lowCursor < high && data[lowCursor] < medi) {

20. lowCursor++;

21. }

22. // 从高端开始查找，确定小于数 data[low] 所在的位置。这里要使用 >= 判断确定小于值

23. while (highCursor > low && data[highCursor] >= medi) {

24. highCursor--;

25. }

26. // 两游标位置出现越界，退出循环

27. if (lowCursor >= highCursor) {

28. break;

29. }

30. // 交换 data[highCursor] 和 data[lowCursor] 位置数据

31. temp = data[highCursor];

32. data[highCursor] = data[lowCursor];

33. data[lowCursor] = temp;

34. }

35. // 由 while 循环退出条件可知：lowCursor > highCursor

36. // 当前 lowCursor 指向右侧大于 data[low]的第一个位置;

37. // 而 highCursor 指向左侧小于 data[low]的第一个位置，所以需要交换 data[low] 和

38. // data[highCursor]的值

39. data[low] = data[highCursor];

40. data[highCursor] = medi;

41. // 递归运算左半部分

42. if (low < highCursor) {

43. recQuickSort(data, low, highCursor);

44. }

45. // 递归运算右半部分

46. if (lowCursor < high) {

47. recQuickSort(data, lowCursor, high);

48. }

49. }

50. public void display() {

51. for (int i = 0; i < data.length; i++) {

52. System.out.print(data[i] + " ");

53. }

54. System.out.println();

55. }

56. public static void main(String[] args) {

57. int[] data = new int[] {

58. 43, 12, 32, 55, 33, 67, 54, 65, 43, 22, 66,

59. 98, 74

60. };

61. QuickSort sort = new QuickSort(data);

62. sort.display();

63. sort.quickSort();

64. sort.display();

65. }

66. }

 

18. 二叉树

 

1. //******************************************************************************************************//

2. //*****本程序包括简单的二叉树类的实现和前序,中序,后序,层次遍历二叉树算法,*******//

3. //******以及确定二叉树的高度,制定对象在树中的所处层次以及将树中的左右***********//

4. //******孩子节点对换位置,返回叶子节点个数删除叶子节点,并输出所删除的叶子节点**//

5. //*******************************CopyRight By phoenix*******************************************//

6. //************************************Jan 12,2008*************************************************//

7. //****************************************************************************************************//

8. public class BinTree {

9. public final static int MAX = 40;

10. BinTree[] elements = new BinTree[MAX]; // 层次遍历时保存各个节点

11. int front; // 层次遍历时队首

12. int rear; // 层次遍历时队尾

13. private Object data; // 数据元数

14. private BinTree left, right; // 指向左,右孩子结点的链

15. public BinTree() {}

16. public BinTree(Object data) { // 构造有值结点

17. this.data = data;

18. left = right = null;

19. }

20. public BinTree(Object data, BinTree left, BinTree right) { // 构造有值结点

21. this.data = data;

22. this.left = left;

23. this.right = right;

24. }

25. public String toString() {

26. return data.toString();

27. }

28. // 前序遍历二叉树

29. public static void preOrder(BinTree parent) {

30. if (parent == null) return;

31. System.out.print(parent.data + " ");

32. preOrder(parent.left);

33. preOrder(parent.right);

34. }

35. // 中序遍历二叉树

36. public void inOrder(BinTree parent) {

37. if (parent == null) return;

38. inOrder(parent.left);

39. System.out.print(parent.data + " ");

40. inOrder(parent.right);

41. }

42. // 后序遍历二叉树

43. public void postOrder(BinTree parent) {

44. if (parent == null) return;

45. postOrder(parent.left);

46. postOrder(parent.right);

47. System.out.print(parent.data + " ");

48. }

49. // 层次遍历二叉树

50. public void LayerOrder(BinTree parent) {

51. elements[0] = parent;

52. front = 0;

53. rear = 1;

54. while (front < rear) {

55. try {

56. if (elements[front].data != null) {

57. System.out.print(elements[front].data + " ");

58. if (elements[front].left != null) elements[rear++] = elements[front].left;

59. if (elements[front].right != null) elements[rear++] = elements[front].right;

60. front++;

61. }

62. } catch (Exception e) {

63. break;

64. }

65. }

66. }

67. // 返回树的叶节点个数

68. public int leaves() {

69. if (this == null) return 0;

70. if (left == null && right == null) return 1;

71. return (left == null ? 0 : left.leaves()) + (right == null ? 0 : right.leaves());

72. }

73. // 结果返回树的高度

74. public int height() {

75. int heightOfTree;

76. if (this == null) return -1;

77. int leftHeight = (left == null ? 0 : left.height());

78. int rightHeight = (right == null ? 0 : right.height());

79. heightOfTree = leftHeight < rightHeight ? rightHeight : leftHeight;

80. return 1 + heightOfTree;

81. }

82. // 如果对象不在树中,结果返回-1;否则结果返回该对象在树中所处的层次,规定根节点为第一层

83. public int level(Object object) {

84. int levelInTree;

85. if (this == null) return -1;

86. if (object == data) return 1; // 规定根节点为第一层

87. int leftLevel = (left == null ? -1 : left.level(object));

88. int rightLevel = (right == null ? -1 : right.level(object));

89. if (leftLevel < 0 && rightLevel < 0) return -1;

90. levelInTree = leftLevel < rightLevel ? rightLevel : leftLevel;

91. return 1 + levelInTree;

92. }

93. // 将树中的每个节点的孩子对换位置

94. public void reflect() {

95. if (this == null) return;

96. if (left != null) left.reflect();

97. if (right != null) right.reflect();

98. BinTree temp = left;

99. left = right;

100. right = temp;

101. }

102. // 将树中的所有节点移走,并输出移走的节点

103. public void defoliate() {

104. if (this == null) return;

105. // 若本节点是叶节点，则将其移走

106. if (left == null && right == null) {

107. System.out.print(this + " ");

108. data = null;

109. return;

110. }

111. // 移走左子树若其存在

112. if (left != null) {

113. left.defoliate();

114. left = null;

115. }

116. // 移走本节点，放在中间表示中跟移走...

117. // innerNode += this + " ";

118. data = null;

119. // 移走右子树若其存在

120. if (right != null) {

121. right.defoliate();

122. right = null;

123. }

124. }

125. /**

126.  

127. * @param args

128.  

129. */

130. public static void main(String[] args) {

131. // TODO Auto-generated method stub

132. BinTree e = new BinTree("E");

133. BinTree g = new BinTree("G");

134. BinTree h = new BinTree("H");

135. BinTree i = new BinTree("I");

136. BinTree d = new BinTree("D", null, g);

137. BinTree f = new BinTree("F", h, i);

138. BinTree b = new BinTree("B", d, e);

139. BinTree c = new BinTree("C", f, null);

140. BinTree tree = new BinTree("A", b, c);

141. System.out.println("前序遍历二叉树结果: ");

142. tree.preOrder(tree);

143. System.out.println();

144. System.out.println("中序遍历二叉树结果: ");

145. tree.inOrder(tree);

146. System.out.println();

147. System.out.println("后序遍历二叉树结果: ");

148. tree.postOrder(tree);

149. System.out.println();

150. System.out.println("层次遍历二叉树结果: ");

151. tree.LayerOrder(tree);

152. System.out.println();

153. System.out.println("F所在的层次: " + tree.level("F"));

154. System.out.println("这棵二叉树的高度: " + tree.height());

155. System.out.println("--------------------------------------");

156. tree.reflect();

157. System.out.println("交换每个节点的孩子节点后......");

158. System.out.println("前序遍历二叉树结果: ");

159. tree.preOrder(tree);

160. System.out.println();

161. System.out.println("中序遍历二叉树结果: ");

162. tree.inOrder(tree);

163. System.out.println();

164. System.out.println("后序遍历二叉树结果: ");

165. tree.postOrder(tree);

166. System.out.println();

167. System.out.println("层次遍历二叉树结果: ");

168. tree.LayerOrder(tree);

169. System.out.println();

170. System.out.println("F所在的层次: " + tree.level("F"));

171. System.out.println("这棵二叉树的高度: " + tree.height());

172. }

173. }

 

 

 

 

 

 

经典算法的Java实现

（1）河内塔问题：

说明：

河内之塔(Towers of Hanoi)是法国人M.Claus(Lucas)于1883年从泰国带至法国的，河内为越战时北越的首都，即现在的胡志明市；1883年法国数学家 Edouard Lucas曾提及这个故事，据说创世纪时Benares有一座波罗教塔，是由三支钻石棒（Pag）所支撑，开始时神在第一根棒上放置64个由上至下依由小至大排列的金盘（Disc），并命令僧侣将所有的金盘从第一根石棒移至第三根石棒，且搬运过程中遵守大盘子在小盘子之下的原则，若每日仅搬一个盘子，则当盘子全数搬运完毕之时，此塔将毁损，而也就是世界末日来临之时。

解法：

如果柱子标为ABC，要由A搬至C，在只有一个盘子时，就将它直接搬至C，当有两个盘子，就将B当作辅助柱。

如图所示：

事实上，若有n个盘子，则移动完毕所需之次数为2^n - 1，所以当盘数为64时，则所需次数为：264- 1 = 18446744073709551615 为5.05390248594782e+16年，也就是约5000世纪，如果对这数字没什么概念，就假设每秒钟搬一个盘子好了，也要约5850亿年左右。 

实现：

1. //Java程序的实现

2. import java.io.*;

3. public class Hanoi {

4. public static void main(String args[]) throws IOException {

5. int n;

6. BufferedReader buf;

7. buf = new BufferedReader(new InputStreamReader(System. in ));

8. System.out.print("请输入盘数：");

9. n = Integer.parseInt(buf.readLine());

10. Hanoi hanoi = new Hanoi();

11. hanoi.move(n, 'A', 'B', 'C');

12. }

13. public void move(int n, char a, char b, char c) {

14. if (n == 1) System.out.println("盘 " + n + " 由 " + a + " 移至 " + c);

15. else {

16. move(n - 1, a, c, b);

17. System.out.println("盘 " + n + " 由 " + a + " 移至 " + c);

18. move(n - 1, b, a, c);

19. }

20. }

21. }

 

（2）费式数列

说明：

Fibonacci为1200年代的欧洲数学家，在他的著作中曾经提到：“若有一只免子每个月生一只小免子，一个月后小免子也开始生产。起初只有一只免子，一个月后就有两只免子，二个月后有三只免子，三个月后有五只免子（小免子投入生产）......”。

如果不太理解这个例子的话，举个图就知道了，注意新生的小免子需一个月成长期才会投入生产，类似的道理也可以用于植物的生长，这就是Fibonacci数列，一般习惯称之为费氏数列，例如以下：

1、1 、2、3、5、8、13、21、34、55、89......

解法：

依说明，我们可以将费氏数列定义为以下：

fn = fn-1 + fn-2　　   if n > 2

fn = 1　　　　　　        if n = 0, 1 

实现：

1. //Java程序的实现：

2. public class Fibonacci {

3. public static void main(String[] args) {

4. int[] fib = new int[20];

5. fib[0] = 0;

6. fib[1] = 1;

7. for (int i = 2; i < fib.length; i++) fib[i] = fib[i - 1] + fib[i - 2];

8. for (int i = 0; i < fib.length; i++) System.out.print(fib[i] + " ");

9. System.out.println();

10. }

11. }

 

（3）巴斯卡（Pascal）三角形

说明：

巴斯卡（Pascal）三角形基本上就是在解 nCr ，因为三角形上的每一个数字各对应一个nCr，其中 n 为 row，而 r 为 column，如下：

0C0

1C0 1C1

2C0 2C1 2C2

3C0 3C1 3C2 3C3

4C0 4C1 4C2 4C3 4C4

 

对应的数据如下图所示：

 

 

解法：

巴斯卡三角形中的 nCr 可以使用以下这个公式来计算，以避免阶乘运算时的数值溢位：

nCr = [(n-r+1)*nCr-1]/r

nC0 = 1 

 

实现：

 

 

1. //java实现

2. import java.awt.*;

3. import javax.swing.*;

4. public class Pascal extends JFrame {

5. public Pascal() {

6. setBackground(Color.white);

7. setTitle("巴斯卡三角形");

8. setSize(520, 350);

9. setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);

10. setSize(700, 700);

11. setVisible(true);

12. }

13. private long combi(int n, int r) {

14. int i;

15. long p = 1;

16. for (i = 1; i <= r; i++) p = p * (n - i + 1) / i;

17. return p;

18. }

19. public void paint(Graphics g) {

20. g.setColor(Color.white);

21. g.clearRect(0, 0, getSize().width, getSize().height);

22. g.setColor(Color.red);

23. final int N = 12;

24. int n, r, t;

25. for (n = 0; n <= N; n++) {

26. for (r = 0; r <= n; r++) g.drawString(" " + combi(n, r), (N - n) * 20 + r * 40, n * 20 + 50);

27. }

28. }

29. public static void main(String args[]) {

30. Pascal frm = new Pascal();

31. }

32. }

 

 

（4）蒙地卡罗法求 PI

说明：

蒙地卡罗为摩洛哥王国之首都，该国位于法国与义大利国境，以赌博闻名。蒙地卡罗的基本原理为以乱数配合面积公式来进行解题，这种以机率来解题的方式带有赌博的意味，虽然在精确度上有所疑虑，但其解题的思考方向却是个值得学习的方式。

解法：

蒙地卡罗的解法适用于与面积有关的题目，例如求PI值或椭圆面积，这边介绍如何求PI值；假设有一个圆半径为1，所以四分之一圆面积就为PI，而包括此四分之一圆的正方形面积就为1，如下图所示：

 

 

如果随意的在正方形中投射飞标（点）好了，则这些飞标（点）有些会落于四分之一圆内，假设所投射的飞标（点）有n点，在圆内的飞标（点）有c点，则依比例来算，就会得到上图中最后的公式。

至于如何判断所产生的点落于圆内，很简单，令乱数产生X与Y两个数值，如果X^2+Y^2等于1就是落在圆内。

 

实现：

1. //java程序实现

2. public class PI {

3. public static void main(String[] args) {

4. final int N = 50000;

5. int sum = 0;

6. for (int i = 1; i < N; i++) {

7. double x = Math.random();

8. double y = Math.random();

9. if ((x * x + y * y) < 1) sum++;

10. }

11. System.out.println("PI = " + (double) 4 * sum / N);

12. }

13. }

 

（5）最大公因数、最小公倍数

说明：

解法：

最大公因数使用辗转相除法来求，最小公倍数则由这个公式来求：

GCD * LCM = 两数乘积

实现：

1. //java程序实现

2. import java.io.*;

3. public class GcdLcm {

4. public static int gcdOf(int m, int n) {

5. int r;

6. while (n != 0) {

7. r = m % n;

8. m = n;

9. n = r;

10. }

11. return m;

12. }

13. public static int lcmOf(int m, int n) {

14. return m * n / gcdOf(m, n);

15. }

16. public static void main(String[] args) throws IOException {

17. BufferedReader ln = new BufferedReader(new InputStreamReader(System. in ));

18. System.out.print("请输入第一个数：");

19. int x = Integer.parseInt(ln.readLine());

20. System.out.print("请输入第二个数：");

21. int y = Integer.parseInt(ln.readLine());

22. System.out.println("GCD of (" + x + "," + y + ")=" + GcdLcm.gcdOf(x, y));

23. System.out.println("LCM of (" + x + "," + y + ")=" + GcdLcm.lcmOf(x, y));

24. }

25. }

 

（6）阿姆斯壮数

说明：

在三位的整数中，例如153可以满足13 + 53 + 33 = 153，这样的数称之为Armstrong数，试写出一程式找出所有的三位数Armstrong数。

解法：

Armstrong数的寻找，其实就是在问如何将一个数字分解为个位数、十位数、百位数......，这只要使用除法与余数运算就可以了，例如输入 input为abc，则：

a = input / 100

b = (input%100) / 10

c = input % 10

 

实现：

1. //java程序实现

2. public class Armstrong {

3. public static void main(String[] args) {

4. System.out.println("寻找Armstrong数：");

5. for (int i = 100; i <= 999; i++) {

6. int a = i / 100;

7. int b = (i % 100) / 10;

8. int c = i % 10;

9. if (a * a * a + b * b * b + c * c * c == i) System.out.print(i + " ");

10. }

11. System.out.println();

12. }

13. }

 

（7）最大访客数

说明：

现将举行一个餐会，让访客事先填写到达时间与离开时间，为了掌握座位的数目，必须先估计不同时间的最大访客数。

解法：

这个题目看似有些复杂，其实相当简单，单就计算访客数这个目的，同时考虑同一访客的来访时间与离开时间，反而会使程式变得复杂；只要将来访时间与离开时间分开处理就可以了，假设访客 i 的来访时间为x[i]，而离开时间为y[i]。

在资料输入完毕之后，将x[i]与y[i]分别进行排序（由小到大），道理很简单，只要先计算某时之前总共来访了多少访客，然后再减去某时之前的离开访客，就可以轻易的解出这个问题

实现：

1. //java实现

2. import java.io.*;

3. import java.util.*;

4. public class MaxVisit {

5. public static int maxGuest(int[] x, int[] y, int time) {

6. int num = 0;

7. for (int i = 0; i < x.length; i++) {

8. if (time > x[i]) num++;

9. if (time > y[i]) num--;

10. }

11. return num;

12. }

13. public static void main(String[] args) throws IOException {

14. BufferedReader buf = new BufferedReader(new InputStreamReader(System. in ));

15. System.out.println("输入来访时间与离开时间(0~24)：");

16. System.out.println("范例：10 15");

17. System.out.println("输入-1结束");

18. java.util.ArrayList list = new ArrayList();

19. while (true) {

20. System.out.print(">>");

21. String input = buf.readLine();

22. if (input.equals("-1")) break;

23. list.add(input);

24. }

25. int[] x = new int[list.size()];

26. int[] y = new int[list.size()];

27. for (int i = 0; i < x.length; i++) {

28. String input = (String) list.get(i);

29. String[] strs = input.split(" ");

30. x[i] = Integer.parseInt(strs[0]);

31. y[i] = Integer.parseInt(strs[1]);

32. }

33. Arrays.sort(x);

34. Arrays.sort(y);

35. for (int time = 0; time < 25; time++) {

36. System.out.println(time + " 时的最大访客数：" + MaxVisit.maxGuest(x, y, time));

37. }

38. }

39. }

 

（8）洗扑克牌（乱数排列）

说明：

洗扑克牌的原理其实与乱数排列是相同的，都是将一组数字（例如1～N）打乱重新排列，只不过洗扑克牌多了一个花色判断的动作而已。

解法：

初学者通常会直接想到，随机产生1～N的乱数并将之存入阵列中，后来产生的乱数存入阵列前必须先检查阵列中是否已有重复的数字，如果有这个数就不存入，再重新产生下一个数，运气不好的话，重复的次数就会很多，程式的执行速度就很慢了，这不是一个好方法。

以1～52的乱数排列为例好了，可以将阵列先依序由1到52填入，然后使用一个回圈走访阵列，并随机产生1～52的乱数，将产生的乱数当作索引取出阵列值，并与目前阵列走访到的值相交换，如此就不用担心乱数重复的问题了，阵列走访完毕后，所有的数字也就重新排列了。

至于如何判断花色？这只是除法的问题而已，取商数判断花色，取余数判断数字，您可以直接看程式比较清楚。

 

实现：

1. //java实现

2. public class ShuffleCard {

3. public static void main(String args[]) {

4. final int N = 52;

5. int[] poker = new int[N + 1];

6. // 初始化阵列

7. for (int i = 1; i <= N; i++) poker[i] = i;

8. // 洗牌

9. for (int i = 1; i <= N; i++) {

10. int j = (int)(Math.random() * N);

11. if (j == 0) j = 1;

12. int tmp = poker[i];

13. poker[i] = poker[j];

14. poker[j] = tmp;

15. }

16. for (int i = 1; i <= N; i++) {

17. // 判断花色

18. switch ((poker[i] - 1) / 13) {

19. case 0:

20. System.out.print("桃");

21. break;

22. case 1:

23. System.out.print("心");

24. break;

25. case 2:

26. System.out.print("砖");

27. break;

28. case 3:

29. System.out.print("梅");

30. break;

31. }

32. // 扑克牌数字

33. int remain = poker[i] % 13;

34. switch (remain) {

35. case 0:

36. System.out.print("K ");

37. break;

38. case 12:

39. System.out.print("Q ");

40. break;

41. case 11:

42. System.out.print("J ");

43. break;

44. default:

45. System.out.print(remain + " ");

46. break;

47. }

48. if (i % 13 == 0) System.out.println("");

49. }

50. }

51. }

 

（9）约瑟夫问题（Josephus Problem）

说明：

据说着名犹太历史学家 Josephus有过以下的故事：在罗马人占领乔塔帕特后，39 个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人到，于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人 开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。

然而Josephus 和他的朋友并不想遵从，Josephus要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。

解法：

约瑟夫问题可用代数分析来求解，将这个问题扩大好了，假设现在您与m个朋友不幸参与了这个游戏，您要如何保护您与您的朋友？只要画两个圆圈就可以让自己与朋友免于死亡游戏，这两个圆圈内圈是排列顺序，而外圈是自杀顺序，如下图所示：

 

使用程式来求解的话，只要将阵列当作环状来处理就可以了，在阵列中由计数1开始，每找到三个无资料区就填入一个计数，直而计数达41为止，然后将阵列由索引1开始列出，就可以得知每个位置的自杀顺序，这就是约瑟夫排列，41个人而报数3的约琴夫排列如下所示：

14 36 1 38 15 2 24 30 3 16 34 4 25 17 5 40 31 6 18 26 7 37 19 8 35 27 9 20 32 10 41 21 11 28 39 12 22 33 13 29 23

 

由上可知，最后一个自杀的是在第31个位置，而倒数第二个自杀的要排在第16个位置，之前的人都死光了，所以他们也就不知道约琴夫与他的朋友并没有遵守游戏规则了。

实现：

1. //java实现

2. public class Josephus {

3. public static int[] arrayOfJosephus(int number, int per) {

4. int[] man = new int[number];

5. for (int count = 1, i = 0, pos = -1; count <= number; count++) {

6. do {

7. pos = (pos + 1) % number; // 环状处理

8. if (man[pos] == 0) i++;

9. if (i == per) { // 报数为3了

10. i = 0;

11. break;

12. }

13. } while (true);

14. man[pos] = count;

15. }

16. return man;

17. }

18. public static void main(String[] args) {

19. int[] man = Josephus.arrayOfJosephus(41, 3);

20. int alive = 3;

21. System.out.println("约琴夫排列：");

22. for (int i = 0; i < 41; i++) System.out.print(man[i] + " ");

23. System.out.println("\nL表示3个存活的人要放的位置：");

24. for (int i = 0; i < 41; i++) {

25. if (man[i] > (41 - alive)) System.out.print("L");

26. else System.out.print("D");

27. if ((i + 1) % 5 == 0) System.out.print(" ");

28. }

29. System.out.println();

30. }

31. }

 

（10）排列组合

说明：

将一组数字、字母或符号进行排列，以得到不同的组合顺序，例如1 2 3这三个数的排列组合有：1 2 3、1 3 2、2 1 3、2 3 1、3 1 2、3 2 1。

解法：

可以使用递回将问题切割为较小的单元进行排列组合，例如1 2 3 4的排列可以分为1 [2 3 4]、2 [1 3 4]、3 [1 2 4]、4 [1 2 3]进行排列，这边利用旋转法，先将旋转间隔设为0，将最右边的数字旋转至最左边，并逐步增加旋转的间隔，例如：

1 2 3 4 -> 旋转1 -> 继续将右边2 3 4进行递回处理

2 1 3 4 -> 旋转1 2 变为 2 1-> 继续将右边1 3 4进行递回处理

3 1 2 4 -> 旋转1 2 3变为 3 1 2 -> 继续将右边1 2 4进行递回处理

4 1 2 3 -> 旋转1 2 3 4变为4 1 2 3 -> 继续将右边1 2 3进行递回处理

 

实现：

1. //java实现

2. public class Permutation {

3. public static void perm(int[] num, int i) {

4. if (i < num.length - 1) {

5. for (int j = i; j <= num.length - 1; j++) {

6. int tmp = num[j];

7. // 旋转该区段最右边数字至最左边

8. for (int k = j; k > i; k--) num[k] = num[k - 1];

9. num[i] = tmp;

10. perm(num, i + 1);

11. // 还原

12. for (int k = i; k < j; k++) num[k] = num[k + 1];

13. num[j] = tmp;

14. }

15. } else {

16. // 显示此次排列

17. for (int j = 1; j <= num.length - 1; j++) System.out.print(num[j] + " ");

18. System.out.println();

19. }

20. }

21. public static void main(String[] args) {

22. int[] num = new int[4 + 1];

23. for (int i = 1; i <= num.length - 1; i++) num[i] = i;

24. perm(num, 1);

25. }

26. }

 

（11）得分排行

说明：

假设有一教师依学生座号输入考试分数，现希望在输入完毕后自动显示学生分数的排行，当然学生的分数可能相同。

 

解法：

这个问题基本上要解不难，只要使用额外的一个排行阵列走访分数阵列就可以了，直接使用下面的程式片段作说明：

for(i = 0; i < count; i++) {

    juni[i] = 1;

    for(j = 0; j < count; j++) {

        if(score[j] > score[i])

            juni[i]++;

   }

}

printf("得分\t排行\n");

for(i = 0; i < count; i++)

    printf("%d\t%d\n", score[i], juni[i]);

上面这个方法虽然简单，但是反覆计算的次数是n^2，如果n值变大，那么运算的时间就会拖长；改变juni阵列的长度为n+2，并将初始值设定为0，如下所示：

接下来走访分数阵列，并在分数所对应的排行阵列索引元素上加1，如下所示： 将排行阵列最右边的元素设定为1，然后依序将右边的元素值加至左边一个元素，最后排行阵列中的「分数+1」」就是得该分数的排行，如下所示： 这样的方式看起来复杂，其实不过在计算某分数之前排行的人数，假设89分之前的排行人数为x人，则89分自然就是x+1了，这也是为什么排行阵列最右边要设定为1的原因；如果89分有y人，则88分自然就是x+y+1，整个阵列右边元素向左加的原因正是如此。 如果分数有负分的情况，由于C/C++或Java等程式语言无法处理负的索引，所以必须加上一个偏移值，将所有的分数先往右偏移一个范围即可，最后显示的时候记得减回偏移值就可以了。

实现：

 

1. //

2. import java.io.*;

3. public class ScoreRank {

4. public static void main(String[] args)

5. throws NumberFormatException, IOException {

6. final int MAX = 100;

7. final int MIN = 0;

8. int[] score = new int[MAX + 1];

9. int[] juni = new int[MAX + 2];

10. BufferedReader reader = new BufferedReader(new InputStreamReader(System. in ));

11. int count = 0;

12. do {

13. System.out.print("输入分数，-1结束：");

14. score[count++] = Integer.parseInt(reader.readLine());

15. } while ((score[count - 1] != -1));

16. count--;

17. for (int i = 0; i < count; i++) juni[score[i]]++;

18. juni[MAX + 1] = 1;

19. for (int i = MAX; i >= MIN; i--) juni[i] = juni[i] + juni[i + 1];

20. System.out.println("得分\t排行");

21. for (int i = 0; i < count; i++) {

22. System.out.println(score[i] + "\t" + juni[score[i] + 1]);

23. }

24. }

25. }

 

（12）选择、插入、气泡排序

说明：

选择排序（Selection sort）、插入排序（Insertion sort）与气泡排序（Bubble sort）这三个排序方式是初学排序所必须知道的三个基本排序方式，它们由于速度不快而不实用（平均与最快的时间复杂度都是O(n2)），然而它们排序的方式确是值得观察与探讨的。

解法：

 

 

① 选择排序

将要排序的对象分作两部份，一个是已排序的，一个是未排序的，从后端未排序部份选择一个最小值，并放入前端已排序部份的最后一个，例如：

 

排序前：70 80 31 37 10 1 48 60 33 80

 

[1] 80 31 37 10 70 48 60 33 80 选出最小值1

[1 10] 31 37 80 70 48 60 33 80 选出最小值10

[1 10 31] 37 80 70 48 60 33 80 选出最小值31

[1 10 31 33] 80 70 48 60 37 80 ......

[1 10 31 33 37] 70 48 60 80 80 ......

[1 10 31 33 37 48] 70 60 80 80 ......

[1 10 31 33 37 48 60] 70 80 80 ......

[1 10 31 33 37 48 60 70] 80 80 ......

[1 10 31 33 37 48 60 70 80] 80 ......

 

② 插入排序

像是玩朴克一样，我们将牌分作两堆，每次从后面一堆的牌抽出最前端的牌，然后插入前面一堆牌的适当位置，例如：

 

排序前：92 77 67 8 6 84 55 85 43 67

 

[77 92] 67 8 6 84 55 85 43 67 将77插入92前

[67 77 92] 8 6 84 55 85 43 67 将67插入77前

[8 67 77 92] 6 84 55 85 43 67 将8插入67前

[6 8 67 77 92] 84 55 85 43 67 将6插入8前

[6 8 67 77 84 92] 55 85 43 67 将84插入92前

[6 8 55 67 77 84 92] 85 43 67 将55插入67前

[6 8 55 67 77 84 85 92] 43 67 ......

[6 8 43 55 67 77 84 85 92] 67 ......

[6 8 43 55 67 67 77 84 85 92] ......

 

③ 气泡排序法

顾名思义，就是排序时，最大的元素会如同气泡一样移至右端，其利用比较相邻元素的方法，将大的元素交换至右端，所以大的元素会不断的往右移动，直到适当的位置为止。

 

基本的气泡排序法可以利用旗标的方式稍微减少一些比较的时间，当寻访完阵列后都没有发生任何的交换动作，表示排序已经完成，而无需再进行之后的回圈比较与交换动作，例如：

 

排序前：95 27 90 49 80 58 6 9 18 50

 

27 90 49 80 58 6 9 18 50 [95] 95浮出 

27 49 80 58 6 9 18 50 [90 95] 90浮出 

27 49 58 6 9 18 50 [80 90 95] 80浮出 

27 49 6 9 18 50 [58 80 90 95] ......

27 6 9 18 49 [50 58 80 90 95] ......

6 9 18 27 [49 50 58 80 90 95] ......

6 9 18 [27 49 50 58 80 90 95] 由于接下来不会再发生交换动作，排序提早结束

 

在上面的例子当中，还加入了一个观念，就是当进行至i与i+1时没有交换的动作，表示接下来的i+2至n已经排序完毕，这也增进了气泡排序的效率。

 

实现：

1. //Java程序实现

2. public class BasicSort {

3. public static void selectionSort(int[] number) {

4. for (int i = 0; i < number.length - 1; i++) {》》

5. int m = i;

6. for (int j = i + 1; j < number.length; j++)

7. if (number[j] < number[m]) m = j; === = if (i != m) swap(number, i, m);

8. }

9. }

10. public static void injectionSort(int[] number) {

11. for (int j = 1; j < number.length; j++) {

12. int tmp = number[j];

13. int i = j - 1;

14. while (tmp < number[i]) {

15. number[i + 1] = number[i];

16. i--;

17. if (i == -1) break;

18. }

19. number[i + 1] = tmp;

20. }

21. }

22. public static void bubbleSort(int[] number) {

23. boolean flag = true;

24. for (int i = 0; i < number.length - 1 && flag; i++) {

25. flag = false;

26. for (int j = 0; j < number.length - i - 1; j++) {

27. if (number[j + 1] < number[j]) {

28. swap(number, j + 1, j);

29. flag = true;

30. }

31. }

32. }

33. }

34. private static void swap(int[] number, int i, int j) {

35. int t;

36. t = number[i];

37. number[i] = number[j];

38. number[j] = t;

39. }

40. public static void main(String[] args) {

41. //测试：

42. int[] a = {

43. 10, 9, 1, 100, 20, 200, 39, 45, 23, 18, 2, 2, 15

44. };

45. //测试选择排序：

46. System.out.println("选择排序前：");

47. for (int x: a) System.out.print(x + " ");

48. System.out.println();

49. int[] b = new int[a.length];

50. b = a;

51. selectionSort(b);

52. System.out.println("选择排序后：");

53. for (int x: b) System.out.print(x + " ");

54. System.out.println();

55. //测试插入排序：

56. System.out.println("插入排序前：");

57. for (int x: a) System.out.print(x + " ");

58. System.out.println();

59. int[] c = new int[a.length];

60. c = a;

61. injectionSort(c);

62. System.out.println("插入排序后：");

63. for (int x: c) System.out.print(x + " ");

64. System.out.println();

65. //测试气泡排序：

66. System.out.println("气泡排序前：");

67. for (int x: a) System.out.print(x + " ");

68. System.out.println();

69. int[] d = new int[a.length];

70. d = a;

71. bubbleSort(d);

72. System.out.println("气泡排序后：");

73. for (int x: d) System.out.print(x + " ");

74. }

75. }

 

（13）快速排序（一）

说明：

快速排序法（quick sort）是目前所公认最快的排序方法之一（视解题的对象而定），虽然快速排序法在最差状况下可以达O(n2)，但是在多数的情况下，快速排序法的效率表现是相当不错的。

快速排序法的基本精神是在数列中找出适当的轴心，然后将数列一分为二，分别对左边与右边数列进行排序，而影响快速排序法效率的正是轴心的选择。

这边所介绍的第一个快速排序法版本，是在多数的教科书上所提及的版本，因为它最容易理解，也最符合轴心分割与左右进行排序的概念，适合对初学者进行讲解。

解法：

这边所介绍的快速演算如下：将最左边的数设定为轴，并记录其值为 s

廻圈处理：

令索引 i 从数列左方往右方找，直到找到大于 s 的数

令索引 j 从数列左右方往左方找，直到找到小于 s 的数

如果 i >= j，则离开回圈

如果 i < j，则交换索引i与j两处的值

将左侧的轴与 j 进行交换

对轴左边进行递回

对轴右边进行递回

 

透过以下演算法，则轴左边的值都会小于s，轴右边的值都会大于s，如此再对轴左右两边进行递回，就可以对完成排序的目的，例如下面的实例，*表示要交换的数，[]表示轴：

[41]　24　76*　11　45　64　21　69　19　36*

[41]　24　36　11　45*　64　21　69　19*　76

[41]　24　36　11　19　64*　21*　69　45　76

[41]　24　36　11　19　21　64　69　45　76

21　24　36　11　19　[41]　64　69　45　76

 

在上面的例子中，41左边的值都比它小，而右边的值都比它大，如此左右再进行递回至排序完成。

 

实现：

 

 

1. //java实现

2. public class QuickSort {

3. public static void sort(int[] number) {

4. sort(number, 0, number.length - 1);

5. }

6. private static void sort(int[] number, int left, int right) {

7. if (left < right) {

8. int s = number[left];

9. int i = left;

10. int j = right + 1;

11. while (true) {

12. // 向右找

13. while (i + 1 < number.length && number[++i] < s);

14. // 向左找

15. while (j - 1 > -1 && number[--j] > s);

16. if (i >= j) break;

17. swap(number, i, j);

18. }

19. number[left] = number[j];

20. number[j] = s;

21. sort(number, left, j - 1);

22. // 对左边进行递回

23. sort(number, j + 1, right);

24. // 对右边进行递回

25. }

26. }

27. private static void swap(int[] number, int i, int j) {

28. int t;

29. t = number[i];

30. number[i] = number[j];

31. number[j] = t;

32. }

33. }

 

 

（14）快速排序（二）

说明：

在快速排序法（一）中，每次将最左边的元素设为轴，而之前曾经说过，快速排序法的加速在于轴的选择，在这个例子中，只将轴设定为中间的元素，依这个元素作基准进行比较，这可以增加快速排序法的效率。

解法：

在这个例子中，取中间的元素s作比较，同样的先得右找比s大的索引 i，然后找比s小的索引 j，只要两边的索引还没有交会，就交换 i 与 j 的元素值，这次不用再进行轴的交换了，因为在寻找交换的过程中，轴位置的元素也会参与交换的动作，例如：

41　24　76　11　45　64　21　69　19　36

 

首先left为0，right为9，(left+right)/2 = 4（取整数的商），所以轴为索引4的位置，比较的元素是45，您往右找比45大的，往左找比45小的进行交换：

41　24　76*　11　[45]　64　21　69　19　*36

41　24　36　11　45*　64　21　69　19*　76

41　24　36　11　19　64*　21*　69　45　76

[41　24　36　11　19　21]　[64　69　45　76]

 

完成以上之后，再初别对左边括号与右边括号的部份进行递回，如此就可以完成排序的目的。

实现：

 

 

1. public class QuickSort {

2. public static void sort(int[] number) {

3. sort(number, 0, number.length - 1);

4. }

5. private static void sort(int[] number, int left, int right) {

6. if (left < right) {

7. int s = number[(left + right) / 2];

8. int i = left - 1;

9. int j = right + 1;

10. while (true) {

11. // 向右找

12. while (number[++i] < s);

13. // 向左找

14. while (number[--j] > s);

15. if (i >= j) break;

16. swap(number, i, j);

17. }

18. sort(number, left, i - 1);

19. // 对左边进行递回

20. sort(number, j + 1, right);

21. // 对右边进行递回

22. }

23. }

24. private static void swap(int[] number, int i, int j) {

25. int t;

26. t = number[i];

27. number[i] = number[j];

28. number[j] = t;

29. }

30. }

 

 

 

（15）快速排序（三）

说明：

之前说过轴的选择是快速排序法的效率关键之一，在这边的快速排序法的轴选择方式更加快了快速排序法的效率，它是来自演算法名书 Introduction to Algorithms 之中。

解法：

先说明这个快速排序法的概念，它以最右边的值s作比较的标准，将整个数列分为三个部份，一个是小于s的部份，一个是大于s的部份，一个是未处理的部份，如下所示 ：

 

 

在排序的过程中，i 与 j 都会不断的往右进行比较与交换，最后数列会变为以下的状态：

 

 

然后将s的值置于中间，接下来就以相同的步骤会左右两边的数列进行排序的动作，如下所示：

 

 

整个演算的过程，直接摘录书中的虚拟码来作说明：

 

实现：

1. public class QuickSort3 {

2. public static void sort(int[] number) {

3. sort(number, 0, number.length - 1);

4. }

5. private static void sort(int[] number, int left, int right) {

6. if (left < right) {

7. int q = partition(number, left, right);

8. sort(number, left, q - 1);

9. sort(number, q + 1, right);

10. }

11. }

12. private static int partition(int number[], int left, int right) {

13. int s = number[right];

14. int i = left - 1;

15. for (int j = left; j < right; j++) {

16. if (number[j] <= s) {

17. i++;

18. swap(number, i, j);

19. }

20. }

21. swap(number, i + 1, right);

22. return i + 1;

23. }

24. private static void swap(int[] number, int i, int j) {

25. int t;

26. t = number[i];

27. number[i] = number[j];

28. number[j] = t;

29. }

30. }

 

（16）合并排序

说明：

之前所介绍的排序法都是在同一个阵列中的排序，考虑今日有两笔或两笔以上的资料，它可能是不同阵列中的资料，或是不同档案中的资料，如何为它们进行排序？

 

解法：

可以使用合并排序法，合并排序法基本是将两笔已排序的资料合并并进行排序，如果所读入的资料尚未排序，可以先利用其它的排序方式来处理这两笔资料，然后再将排序好的这两笔资料合并。

有人问道，如果两笔资料本身就无排序顺序，何不将所有的资料读入，再一次进行排序？排序的精神是尽量利用资料已排序的部份，来加快排序的效率，小笔资料的排序较为快速，如果小笔资料排序完成之后，再合并处理时，因为两笔资料都有排序了，所有在合并排序时会比单纯读入所有的资料再一次排序来的有效率。

那么可不可以直接使用合并排序法本身来处理整个排序的动作？而不动用到其它的排序方式？答案是肯定的，只要将所有的数字不断的分为两个等分，直到最后剩一个数字为止，然后再反过来不断的合并，就如下图所示：

 

不过基本上分割又会花去额外的时间，不如使用其它较好的排序法来排序小笔资料，再使用合并排序来的有效率。

 

实现：

1. public class MergeSort {

2. public static int[] sort(int[] number1, int[] number2) {

3. int[] number3 = new int[number1.length + number2.length];

4. int i = 0, j = 0, k = 0;

5. while (i < number1.length && j < number2.length) {

6. if (number1[i] <= number2[j]) number3[k++] = number1[i++];

7. else number3[k++] = number2[j++];

8. }

9. while (i < number1.length) number3[k++] = number1[i++];

10. while (j < number2.length) number3[k++] = number2[j++];

11. return number3;

12. }

13. }

 

（17）基数排序

说明：

在之前所介绍过的排序方法，都是属于「比较性」的排序法，也就是每次排序时 ，都是比较整个键值的大小以进行排序。

这边所要介绍的「基数排序法」（radix sort）则是属于「分配式排序」（distribution sort），基数排序法又称「桶子法」（bucket sort）或bin sort，顾名思义，它是透过键值的部份资讯，将要排序的元素分配至某些「桶」中，藉以达到排序的作用，基数排序法是属于稳定性的排序，其时间复杂度为O (nlog(r)m)，其中r为所采取的基数，而m为堆数，在某些时候，基数排序法的效率高于其它的比较性排序法。

 

解法：

基数排序的方式可以采用LSD（Least sgnificant digital）或MSD（Most sgnificant digital），LSD的排序方式由键值的最右边开始，而MSD则相反，由键值的最左边开始。

以LSD为例，假设原来有一串数值如下所示：

73, 22, 93, 43, 55, 14, 28, 65, 39, 81

首先根据个位数的数值，在走访数值时将它们分配至编号0到9的桶子中：

0	1	2	3	4	5	6	7	8	9
	81				65				39
			43	14	55			28
			93
		22	73

 

接下来将这些桶子中的数值重新串接起来，成为以下的数列：

81, 22, 73, 93, 43, 14, 55, 65, 28, 39

接着再进行一次分配，这次是根据十位数来分配：

0	1	2	3	4	5	6	7	8	9
	28	39
	14	22		43	55	65	73	81	93

 

接下来将这些桶子中的数值重新串接起来，成为以下的数列：

14, 22, 28, 39, 43, 55, 65, 73, 81, 93

这时候整个数列已经排序完毕；如果排序的对象有三位数以上，则持续进行以上的动作直至最高位数为止。

LSD的基数排序适用于位数小的数列，如果位数多的话，使用MSD的效率会比较好，MSD的方式恰与LSD相反，是由高位数为基底开始进行分配，其他的演 算方式则都相同。

 

实现：

 

 

1. public class RadixSort {

2. public static void sort(int[] number, int d) {

3. int k = 0;

4. int n = 1;

5. int[][] temp = new int[number.length][number.length];

6. int[] order = new int[number.length];

7. while (n <= d) {

8. for (int i = 0; i < number.length; i++) {

9. int lsd = ((number[i] / n) % 10);

10. temp[lsd][order[lsd]] = number[i];

11. order[lsd]++;

12. }

13. for (int i = 0; i < number.length; i++) {

14. if (order[i] != 0)

15. for (int j = 0; j < order[i]; j++) {

16. number[k] = temp[i][j];

17. k++;

18. }

19. order[i] = 0;

20. }

21. n *= 10;

22. k = 0;

23. }

24. }

25. public static void main(String[] args) {

26. int[] data = {

27. 73, 22, 93, 43, 55, 14, 28, 65, 39, 81, 33, 100

28. };

29. RadixSort.sort(data, 100);

30. for (int i = 0; i < data.length; i++) {

31. System.out.print(data[i] + " ");

32. }

33. }

34. }

 

 

（18）循序查找法（使用卫兵）

说明：

搜寻的目的，是在「已排序的资料」中寻找指定的资料，而当中循序搜寻是最基本的搜寻法，只要从资料开头寻找到最后，看看是否找到资料即可。

 

解法：

    初学者看到循序搜寻，多数都会使用以下的方式来进行搜寻：

while(i < MAX) {

    if(number[i] == k) {

        printf("找到指定值");

        break;

    }

    i++;

}

这个方法基本上没有错，但是可以加以改善，可以利用设定卫兵的方式，省去if判断式，卫兵通常设定在数列最后或是最前方，假设设定在列前方好了（索引0的 位置），我们从数列后方向前找，如果找到指定的资料时，其索引值不是0，表示在数列走访完之前就找到了，在程式的撰写上，只要使用一个while回圈就可 以了。

实现：

1. public class LinearSearch {

2. public static int search(int[] number, int des) {

3. int[] tmp = new int[number.length + 1];

4. for (int i = 1; i < tmp.length; i++) {

5. tmp[i] = number[i - 1];

6. }

7. tmp[0] = des;

8. int k = tmp[0];

9. int i = number.length;

10. while (tmp[i] != k) i--;

11. return i - 1;

12. }

13. public static void main(String[] args) {

14. int[] number = {

15. 1, 4, 2, 6, 7, 3, 9, 8

16. };

17. QuickSort.sort(number);

18. int find = LinearSearch.search(number, 3);

19. if (find != 0) System.out.println("找到数值于索引" + find);

20. else System.out.println("找不到数值");

21. }

22. }

 

（19）二分查找法

说明：

如果搜寻的数列已经有排序，应该尽量利用它们已排序的特性，以减少搜寻比对的次数，这是搜寻的基本原则，二分搜寻法是这个基本原则的代表。

解法：

    在二分搜寻法中，从数列的中间开始搜寻，如果这个数小于我们所搜寻的数，由于数列已排序，则该数左边的数一定都小于要搜寻的对象，所以无需浪费时间在左边的数；如果搜寻的数大于所搜寻的对象，则右边的数无需再搜寻，直接搜寻左边的数。

所以在二分搜寻法中，将数列不断的分为两个部份，每次从分割的部份中取中间数比对，例如要搜寻92于以下的数列，首先中间数索引为(0+9)/2 = 4（索引由0开始）：

[3 24 57 57 67 68 83 90 92 95]

由于67小于92，所以转搜寻右边的数列：

3 24 57 57 67 [68 83 90 92 95]

由于90小于92，再搜寻右边的数列，这次就找到所要的数了：

3 24 57 57 67 68 83 90 [92 95]

 

实现：

1. public class BinarySearch {

2. public static int search(int[] number, int des) {

3. int low = 0;

4. int upper = number.length - 1;

5. while (low <= upper) {

6. int mid = (low + upper) / 2;

7. if (number[mid] < des) low = mid + 1;

8. else if (number[mid] > des) upper = mid - 1;

9. else return mid;

10. }

11. return -1;

12. }

13. public static void main(String[] args) {

14. int[] number = {

15. 1, 4, 2, 6, 7, 3, 9, 8

16. };

17. QuickSort.sort(number);

18. int find = BinarySearch.search(number, 3);

19. if (find != -1) System.out.println("找到数值于索引" + find);

20. else System.out.println("找不到数值");

21. }

22. }

 

（20）插补查找法

说明：

如果却搜寻的资料分布平均的话，可以使用插补（Interpolation）搜寻法来进行搜寻，在搜寻的对象大于500时，插补搜寻法会比 二分搜寻法 来的快速。

 

解法：

插补搜寻法是以资料分布的近似直线来作比例运算，以求出中间的索引并进行资料比对，如果取出的值小于要寻找的值，则提高下界，如果取出的值大于要寻找的值，则降低下界，如此不断的减少搜寻的范围，所以其本原则与二分搜寻法是相同的，至于中间值的寻找是透过比例运算，如下所示，其中K是指定要寻找的对象， 而m则是可能的索引值：

 

 

实现：

1. public class InterpolationSearch {

2. public static int search(int[] number, int des) {

3. int low = 0;

4. int upper = number.length - 1;

5. while (low <= upper) {

6. int mid = (upper - low) * (des - number[low]) / (number[upper] - number[low]) + low;

7. if (mid < low || mid > upper) return -1;

8. if (des < number[mid]) upper = mid - 1;

9. else if (des > number[mid]) low = mid + 1;

10. else return mid;

11. }

12. return -1;

13. }

14. public static void main(String[] args) {

15. int[] number = {

16. 1, 4, 2, 6, 7, 3, 9, 8

17. };

18. QuickSort.sort(number);

19. int find = InterpolationSearch.search(number, 3);

20. if (find != -1) System.out.println("找到数值于索引" + find);

21. else System.out.println("找不到数值");

22. }

23. }

 

 

（21）费式查找法

说明：

二分搜寻法每次搜寻时，都会将搜寻区间分为一半，所以其搜寻时间为O(log(2)n)，log(2)表示以2为底的log值，这边要介绍的费氏搜寻，其利用费氏数列作为间隔来搜寻下一个数，所以区间收敛的速度更快，搜寻时间为O(logn)。

 

解法：

    费氏搜寻使用费氏数列来决定下一个数的搜寻位置，所以必须先制作费氏数列，这在之前有提过；费氏搜寻会先透过公式计算求出第一个要搜寻数的位置，以及其代表的费氏数，以搜寻对象10个数字来说，第一个费氏数经计算后一定是F5，而第一个要搜寻的位置有两个可能，例如若在下面的数列搜寻的话（为了计算方便， 通常会将索引0订作无限小的数，而数列由索引1开始）：

 

-infin; 1 3 5 7 9 13 15 17 19 20

 

如果要搜寻5的话，则由索引F5 = 5开始搜寻，接下来如果数列中的数小于指定搜寻值时，就往左找，大于时就向右，每次找的间隔是F4、F3、F2来寻找，当费氏数为0时还没找到，就表示寻找失败，如下所示：

 

 

由于第一个搜寻值索引F5 = 5处的值小于19，所以此时必须对齐数列右方，也就是将第一个搜寻值的索引改为F5+2 = 7，然后如同上述的方式进行搜寻，如下所示：

 

至于第一个搜寻值是如何找到的？我们可以由以下这个公式来求得，其中n为搜寻对象的个数：

Fx + m = n

Fx <= n

也就是说Fx必须找到不大于n的费氏数，以10个搜寻对象来说：

Fx + m = 10

    取Fx = 8, m = 2，所以我们可以对照费氏数列得x = 6，然而第一个数的可能位置之一并不是F6，而是第x-1的费氏数，也就是F5 = 5。

如果数列number在索引5处的值小于指定的搜寻值，则第一个搜寻位置就是索引5的位置，如果大于指定的搜寻值，则第一个搜寻位置必须加上m，也就是F5 + m = 5 + 2 = 7，也就是索引7的位置，其实加上m的原因，是为了要让下一个搜寻值刚好是数列的最后一个位置。

费氏搜寻看来难懂，但只要掌握Fx + m = n这个公式，自己找几个实例算一次，很容易就可以理解；费氏搜寻除了收敛快速之外，由于其本身只会使用到加法与减法，在运算上也可以加快。

 

实现：

 

1. public class FibonacciSearch {

2. public static int search(int[] number, int des) {

3. int[] fib = createFibonacci(number.length);

4. int x = findX(fib, number.length + 1, des);

5. int m = number.length - fib[x];

6. x--;

7. int i = x;

8. if (number[i] < des) i += m;

9. while (fib[x] > 0) {

10. if (number[i] < des) i += fib[--x];

11. else if (number[i] > des) i -= fib[--x];

12. else return i;

13. }

14. return -1;

15. }

16. private static int[] createFibonacci(int max) {

17. int[] fib = new int[max];

18. for (int i = 0; i < fib.length; i++) {

19. fib[i] = Integer.MIN_VALUE;

20. }

21. fib[0] = 0;

22. fib[1] = 1;

23. for (int i = 2; i < max; i++) fib[i] = fib[i - 1] + fib[i - 2];

24. return fib;

25. }

26. private static int findX(int[] fib, int n, int des) {

27. int i = 0;

28. while (fib[i] <= n) i++;

29. i--;

30. return i;

31. }

32. public static void main(String[] args) {

33. int[] number = {

34. 1, 4, 2, 6, 7, 3, 9, 8

35. };

36. QuickSort.sort(number);

37. int find = FibonacciSearch.search(number, 3);

38. if (find != -1) System.out.println("找到数值于索引" + find);

39. else System.out.println("找不到数值");

40. }

41. }

 

 

 

（22）稀疏矩阵

说明：

    如果在矩阵中，多数的元素并没有资料，称此矩阵为稀疏矩阵（sparse matrix），由于矩阵在程式中常使用二维阵列表示，二维阵列的大小与使用的记忆体空间成正比，如果多数的元素没有资料，则会造成记忆体空间的浪费，为 此，必须设计稀疏矩阵的阵列储存方式，利用较少的记忆体空间储存完整的矩阵资讯。

 

解法：

在这边所介绍的方法较为简单，阵列只储存矩阵的行数、列数与有资料的索引位置及其值，在需要使用矩阵资料时，再透过程式运算加以还原，例如若矩阵资料如下，其中0表示矩阵中该位置没有资料：

0 0 0 0 0 0

0 3 0 0 0 0

0 0 0 6 0 0

0 0 9 0 0 0

0 0 0 0 12 0

这个矩阵是5X6矩阵，非零元素有4个，您要使用的阵列第一列记录其列数、行数与非零元素个数：

5 6 4

阵列的第二列起，记录其位置的列索引、行索引与储存值：

1 1 3

2 3 6

3 2 9

4 4 12

所以原本要用30个元素储存的矩阵资讯，现在只使用了15个元素来储存，节省了不少记忆体的使用。

 

实现：

 

1. public class SparseMatrix {

2. public static int[][] restore(int[][] sparse) {

3. int row = sparse[0][0];

4. int column = sparse[0][1];

5. int[][] array = new int[row][column];

6. int k = 1;

7. for (int i = 0; i < row; i++) {

8. for (int j = 0; j < column; j++) {

9. if (k <= sparse[0][2] && i == sparse[k][0] && j == sparse[k][1]) {

10. array[i][j] = sparse[k][2];

11. k++;

12. } else array[i][j] = 0;

13. }

14. }

15. return array;

16. }

17. public static void main(String[] args) {

18. int[][] sparse = {

19. {

20. 5, 6, 4

21. }, {

22. 1, 1, 3

23. }, {

24. 2, 3, 6

25. }, {

26. 3, 2, 9

27. }, {

28. 4, 4, 12

29. }

30. };

31. int[][] array = SparseMatrix.restore(sparse);

32. for (int i = 0; i < array.length; i++) {

33. for (int j = 0; j < array[i].length; j++) {

34. System.out.print(array[i][j] + " ");

35. }

36. System.out.println();

37. }

38. }

39. }

 

 

 

（23）多维矩阵转一维矩阵

说明：

    有的时候，为了运算方便或资料储存的空间问题，使用一维阵列会比二维或多维阵列来得方便，例如上三角矩阵、下三角矩阵或对角矩阵，使用一维阵列会比使用二维阵列来得节省空间。

解法：

以二维阵列转一维阵列为例，索引值由0开始，在由二维阵列转一维阵列时，我们有两种方式：「以列（Row）为主」或「以行（Column）为主」。由于 C/C++、Java等的记忆体配置方式都是以列为主，所以您可能会比较熟悉前者（Fortran的记忆体配置方式是以行为主）。

以列为主的二维阵列要转为一维阵列时，是将二维阵列由上往下一列一列读入一维阵列，此时索引的对应公式如下所示，其中row与column是二维阵列索引，loc表示对应的一维阵列索引：

loc = column + row*行数

以行为主的二维阵列要转为一维阵列时，是将二维阵列由左往右一行一行读入一维阵列，此时索引的对应公式如下所示：

loc = row + column*列数

公式的推导您画图看看就知道了，如果是三维阵列，则公式如下所示，其中i（个数u1）、j（个数u2）、k（个数u3）分别表示三维阵列的三个索引：

以列为主：loc = i*u2*u3 + j*u3 + k

以行为主：loc = k*u1*u2 + j*u1 + i

    更高维度的可以自行依此类推，但通常更高维度的建议使用其它资料结构（例如物件包装）会比较具体，也不易搞错。

 

实现：

  

1. public class TwoDimArray {

2. public static int[] toOneDimByRow(int[][] array) {

3. int[] arr = new int[array.length * array[0].length];

4. for (int row = 0; row < array.length; row++) {

5. for (int column = 0; column < array[0].length; column++) {

6. int i = column + row * array[0].length;

7. arr[i] = array[row][column];

8. }

9. }

10. return arr;

11. }

12. public static int[] toOneDimByColumn(int[][] array) {

13. int[] arr = new int[array.length * array[0].length];

14. for (int row = 0; row < array.length; row++) {

15. for (int column = 0; column < array[0].length; column++) {

16. int i = i = row + column * array.length;

17. arr[i] = array[row][column];

18. }

19. }

20. return arr;

21. }

22. }

 

 

（24）上三角、下三角、对称矩阵

说明：

    上三角矩阵是矩阵在对角线以下的元素均为0，即Aij = 0，i > j，例如：

1  2  3   4   5

0  6  7   8   9

0  0  10   11  12

0  0  0   13  14

0  0  0   0  15

下三角矩阵是矩阵在对角线以上的元素均为0，即Aij = 0，i < j，例如：

 1  0  0  0  0

 2  6  0  0  0

 3  7  10 0  0

 4  8  11 13 0

 5  9  12 14 15

对称矩阵是矩阵元素对称于对角线，例如：

 1  2  3  4  5

 2  6  7  8  9

 3  7  10 11 12

 4  8  11 13 14

 5  9  12 14 15

上三角或下三角矩阵也有大部份的元素不储存值（为0），我们可以将它们使用一维阵列来储存以节省储存空间，而对称矩阵因为对称于对角线，所以可以视为上三角或下三角矩阵来储存。

解法：

假设矩阵为nxn，为了计算方便，我们让阵列索引由1开始，上三角矩阵化为一维阵列，若以列为主，其公式为：loc = n*(i-1) - i*(i-1)/2 + j

化为以行为主，其公式为：loc = j*(j-1)/2 + i

下三角矩阵化为一维阵列，若以列为主，其公式为：loc = i*(i-1)/2 + j

若以行为主，其公式为：loc = n*(j-1) - j*(j-1)/2 + i

实现：

 

1. public class TriangleArray {

2. private int[] arr;

3. private int length;

4. public TriangleArray(int[][] array) {

5. length = array.length;

6. arr = new int[length * (1 + length) / 2];

7. int loc = 0;

8. for (int i = 0; i < length; i++) {

9. for (int j = 0; j < length; j++) {

10. if (array[i][j] != 0) arr[loc++] = array[i][j];

11. }

12. }

13. }

14. public int getValue(int i, int j) {

15. int loc = length * i - i * (i + 1) / 2 + j;

16. return arr[loc];

17. }

18. public static void main(String[] args) {

19. int[][] array = {

20. {

21. 1, 2, 3, 4, 5

22. }, {

23. 0, 6, 7, 8, 9

24. }, {

25. 0, 0, 10, 11, 12

26. }, {

27. 0, 0, 0, 13, 14

28. }, {

29. 0, 0, 0, 0, 15

30. }

31. };

32. TriangleArray triangleArray = new TriangleArray(array);

33. System.out.print(triangleArray.getValue(2, 2));

34. }

35. }

 

 

（25）奇数魔方阵

说明：

    将1到n(为奇数)的数字排列在nxn的方阵上，且各行、各列与各对角线的和必须相同，如下所示：

 

 

解法：

    填魔术方阵的方法以奇数最为简单，第一个数字放在第一行第一列的正中央，然后向右(左)上填，如果右(左)上已有数字，则向下填，如下图所示：

 

一般程式语言的阵列索引多由0开始，为了计算方便，我们利用索引1到n的部份，而在计算是向右(左)上或向下时，我们可以将索引值除以n值，如果得到余数为1就向下，否则就往右(左)上，原理很简单，看看是不是已经在同一列上绕一圈就对了。

 

实现：

  

1. public class Matrix {

2. public static int[][] magicOdd(int n) {

3. int[][] square = new int[n + 1][n + 1];

4. int i = 0;

5. int j = (n + 1) / 2;

6. for (int key = 1; key <= n * n; key++) {

7. if ((key % n) == 1) i++;

8. else {

9. i--;

10. j++;

11. }

12. if (i == 0) i = n;

13. if (j > n) j = 1;

14. square[i][j] = key;

15. }

16. int[][] matrix = new int[n][n];

17. for (int k = 0; k < matrix.length; k++) {

18. for (int l = 0; l < matrix[0].length; l++) {

19. matrix[k][l] = square[k + 1][l + 1];

20. }

21. }

22. return matrix;

23. }

24. public static void main(String[] args) {

25. int[][] magic = Matrix.magicOdd(5);

26. for (int k = 0; k < magic.length; k++) {

27. for (int l = 0; l < magic[0].length; l++) {

28. System.out.print(magic[k][l] + " ");

29. }

30. System.out.println();

31. }

32. }

33. }

 

 

（26）4N魔方阵

说明：

    与  相同，在于求各行、各列与各对角线的和相等，而这次方阵的维度是4的倍数。

解法：

    先来看看4X4方阵的解法：

 

简单的说，就是一个从左上由1依序开始填，但遇对角线不填，另一个由左上由16开始填，但只填在对角线，再将两个合起来就是解答了；如果N大于2，则以 4X4为单位画对角线：

 

至于对角线的位置该如何判断，有两个公式，有兴趣的可以画图印证看看，如下所示：

左上至右下：j % 4 == i % 4

右上至左下：(j % 4 + i % 4) == 1

实现：

 

1. public class Matrix2 {

2. public static int[][] magicFourN(int n) {

3. int[][] square = new int[n + 1][n + 1];

4. for (int j = 1; j <= n; j++) {

5. for (int i = 1; i <= n; i++) {

6. if (j % 4 == i % 4 || (j % 4 + i % 4) == 1) square[i][j] = (n + 1 - i) * n - j + 1;

7. else square[i][j] = (i - 1) * n + j;

8. }

9. }

10. int[][] matrix = new int[n][n];

11. for (int k = 0; k < matrix.length; k++) {

12. for (int l = 0; l < matrix[0].length; l++) {

13. matrix[k][l] = square[k + 1][l + 1];

14. }

15. }

16. return matrix;

17. }

18. public static void main(String[] args) {

19. int[][] magic = Matrix2.magicFourN(8);

20. for (int k = 0; k < magic.length; k++) {

21. for (int l = 0; l < magic[0].length; l++) {

22. System.out.print(magic[k][l] + " ");

23. }

24. System.out.println();

25. }

26. }

27. }

 

 

 

（27）2(2n+1)魔方阵

说明：

    方阵的维度整体来看是偶数，但是其实是一个奇数乘以一个偶数，例如6X6，其中6=2X3，我们也称这种方阵与单偶数方阵。

解法：

    如果您会解奇数魔术方阵，要解这种方阵也就不难理解，首先我们令n=2(2m+1)，并将整个方阵看作是数个奇数方阵的组合，如下所示：

 

首先依序将A、B、C、D四个位置，依奇数方阵的规则填入数字，填完之后，方阵中各行的和就相同了，但列与对角线则否，此时必须在A-D与C- B之间，作一些对应的调换，规则如下：

将A中每一列(中间列除外)的头m个元素，与D中对应位置的元素调换。

将A的中央列、中央那一格向左取m格，并与D中对应位置对调

将C中每一列的倒数m-1个元素，与B中对应的元素对调

举个实例来说，如何填6X6方阵，我们首先将之分解为奇数方阵，并填入数字，如下所示：

 

接下来进行互换的动作，互换的元素以不同颜色标示，如下：

 

 

实现：

   

 

1. public class Matrix3 {

2. public static int[][] magic22mp1(int n) {

3. int[][] square = new int[n][n];

4. magic_o(square, n / 2);

5. exchange(square, n);

6. return square;

7. }

8. private static void magic_o(int[][] square, int n) {

9. int row = 0;

10. int column = n / 2;

11. for (int count = 1; count <= n * n; count++) {

12. square[row][column] = count;

13. // 填A

14. square[row + n][column + n] = count + n * n;

15. // 填B

16. square[row][column + n] = count + 2 * n * n;

17. // 填C

18. square[row + n][column] = count + 3 * n * n;

19. // 填D

20. if (count % n == 0) row++;

21. else {

22. row = (row == 0) ? n - 1 : row - 1;

23. column = (column == n - 1) ? 0 : column + 1;

24. }

25. }

26. }

27. private static void exchange(int[][] x, int n) {

28. int i, j;

29. int m = n / 4;

30. int m1 = m - 1;

31. for (i = 0; i < n / 2; i++) {

32. if (i != m) {

33. for (j = 0; j < m; j++)

34. // 处理规则 1

35. swap(x, i, j, n / 2 + i, j);

36. for (j = 0; j < m1; j++)

37. // 处理规则 2

38. swap(x, i, n - 1 - j, n / 2 + i, n - 1 - j);

39. } else {

40. // 处理规则 3

41. for (j = 1; j <= m; j++) swap(x, m, j, n / 2 + m, j);

42. for (j = 0; j < m1; j++) swap(x, m, n - 1 - j, n / 2 + m, n - 1 - j);

43. }

44. }

45. }

46. private static void swap(int[][] number, int i, int j, int k, int l) {

47. int t;

48. t = number[i][j];

49. number[i][j] = number[k][l];

50. number[k][l] = t;

51. }

52. public static void main(String[] args) {

53. int[][] magic = Matrix3.magic22mp1(6);

54. for (int k = 0; k < magic.length; k++) {

55. for (int l = 0; l < magic[0].length; l++) {

56. System.out.print(magic[k][l] + " ");

57. }

58. System.out.println();

59. }

60. }

61. }

转载地址：http://bhwxi.baihongyu.com/