48.1 堆排序可能是排序算法中最难的. 用到了二叉树.
48.2 建初始堆比较费劲.
48.3 调整堆的时间复杂度为O(logn), 所以总体时间复杂度只有 O(nlogn).
48.4 空间复杂度只有O(1).
代码：
public static void selectionSortTest() {
int[] tempUnsortedKeys = { 5, 3, 6, 10, 7, 1, 9 };
String[] tempContents = { "if", "then", "else", "switch", "case", "for", "while" };
DataArray tempDataArray = new DataArray(tempUnsortedKeys, tempContents);
System.out.println(tempDataArray);
tempDataArray.selectionSort();
System.out.println("Resultrn" + tempDataArray);
} //Of selectionSortTest
public void heapSort() {
DataNode tempNode;
// Step 1. Construct the initial heap.
for (int i = length / 2; i >= 0; i--) {
adjustHeap(i, length);
} // Of for i
System.out.println("The initial heap: " + this + "rn");
// Step 2. Swap and reconstruct.
for (int i = length - 1; i > 0; i--) {
tempNode = data[0];
data[0] = data[i];
data[i] = tempNode;
adjustHeap(0,i);
System.out.println("Round " + (length - i) + ": " + this);
} // Of for i
} // Of heapSort
public void adjustHeap(int paraStart, int paraLength) {
DataNode tempNode = data[paraStart];
int tempParent = paraStart;
int tempKey = data[paraStart].key;
for (int tempChild = paraStart * 2 + 1; tempChild < paraLength; tempChild = tempChild * 2 + 1) {
// The right child is bigger.
if (tempChild + 1 < paraLength) {
if (data[tempChild].key < data[tempChild + 1].key) {
tempChild++;
} // Of if
} // Of if
System.out.println("The parent position is " + tempParent + " and the child is " + tempChild);
if (tempKey < data[tempChild].key) {
// The child is bigger.
data[tempParent] = data[tempChild];
System.out.println("Move " + data[tempChild].key + "to position " + tempParent);
tempParent = tempChild;
} else {
break;
} // Of if
} // Of for tempChild
data[tempParent] = tempNode;
System.out.println("Adjust " + paraStart + " to " + paraLength + ": " + this);
} // Of adjustHeap
public static void heapSortTest() {
int[] tempUnsortedKeys = { 5, 3, 6, 10, 7, 1, 9 };
String[] tempContents = { "if", "then", "else", "switch", "case", "for", "while" };
DataArray tempDataArray = new DataArray(tempUnsortedKeys, tempContents);
System.out.println(tempDataArray);
tempDataArray.heapSort();
System.out.println("Resultrn" + tempDataArray);
} // Of heapSortTest
public static void main(String[] args) {
System.out.println("rn-------------sequentialSearchTest-------------");
sequentialSearchTest();
System.out.println("rn-------------binarySearchTest-------------");
binarySearchTest();
System.out.println("rn-------------hashSearchTest-------------");
hashSearchTest();
System.out.println("rn-------------insertionSort-------------");
insertionSortTest();
System.out.println("rn-------------shellSort-------------");
shellSortTest();
System.out.println("rn-------------bubbleSort-------------");
bubbleSortTest();
System.out.println("rn-------------quickSort-------------");
quickSortTest();
System.out.println("rn-------------selectionSort-------------");
selectionSortTest();
System.out.println("rn-------------heapSort-------------");
heapSortTest();
} // Of main
截图：
49 天: 归并排序
49.1 logn 轮, 每轮O(n) 次拷贝. 因此时间复杂度为O(nlogn).
49.2 空间复杂度为O(n). 只需要一行辅助空间.
49.3 全都是在拷贝引用, 而不是数据本身. 这是 Java 的特性.
49.4 里面的两重循环总共只有O(n). 这里是分成了若干个小组.
49.5 归并两个有序小组的时候, 用了三个并列的循环.
49.6 涉及分组后尾巴的各种情况, 所以需要相应的 if 语句.
代码：
public void mergeSort() {
// Step 1. Allocate space.
int tempRow; // The current row
int tempGroups; // Number of groups
int tempActualRow; // Only 0 or 1
int tempNextRow = 0;
int tempGroupNumber;
int tempFirstStart, tempSecondStart, tempSecondEnd;
int tempFirstIndex, tempSecondIndex;
int tempNumCopied;
for (int i = 0; i < length; i++) {
System.out.println(data[i]);
} // Of for i
System.out.println();
DataNode[][] tempMatrix = new DataNode[2][length];
// Step 2. Copy data.
for (int i = 0; i < length; i++) {
tempMatrix[0][i] = data[i];
} // Of for i
// Step 3. Merge. log n rounds
tempRow = -1;
for (int tempSize = 1; tempSize <= length; tempSize *= 2) {
// Reuse the space of the two rows.
tempRow++;
System.out.println("Current row = " + tempRow);
tempActualRow = tempRow % 2;
tempNextRow = (tempRow + 1) % 2;
tempGroups = length / (tempSize * 2);
if (length % (tempSize * 2) != 0) {
tempGroups++;
} // Of if
System.out.println("tempSize = " + tempSize + ", numGroups = " + tempGroups);
for (tempGroupNumber = 0; tempGroupNumber < tempGroups; tempGroupNumber++) {
tempFirstStart = tempGroupNumber * tempSize * 2;
tempSecondStart = tempGroupNumber * tempSize * 2 + tempSize;
if (tempSecondStart > length - 1) {
// Copy the first part.
for (int i = tempFirstStart; i < length; i++) {
tempMatrix[tempNextRow][i] = tempMatrix[tempActualRow][i];
} // Of for i
continue;
} // Of if
tempSecondEnd = tempGroupNumber * tempSize * 2 + tempSize * 2 - 1;
if (tempSecondEnd > length - 1) {
tempSecondEnd = length - 1;
} // Of if
System.out
.println("Trying to merge [" + tempFirstStart + ", " + (tempSecondStart - 1)
+ "] with [" + tempSecondStart + ", " + tempSecondEnd + "]");
tempFirstIndex = tempFirstStart;
tempSecondIndex = tempSecondStart;
tempNumCopied = 0;
while ((tempFirstIndex <= tempSecondStart - 1)
&& (tempSecondIndex <= tempSecondEnd)) {
if (tempMatrix[tempActualRow][tempFirstIndex].key <= tempMatrix[tempActualRow][tempSecondIndex].key) {
tempMatrix[tempNextRow][tempFirstStart + tempNumCopied] = tempMatrix[tempActualRow][tempFirstIndex];
tempFirstIndex++;
System.out.println("Copying " + tempMatrix[tempActualRow][tempFirstIndex]);
} else {
tempMatrix[tempNextRow][tempFirstStart + tempNumCopied] = tempMatrix[tempActualRow][tempSecondIndex];
System.out.println("Copying " + tempMatrix[tempActualRow][tempSecondIndex]);
tempSecondIndex++;
} // Of if
tempNumCopied++;
} // Of while
while (tempFirstIndex <= tempSecondStart - 1) {
tempMatrix[tempNextRow][tempFirstStart + tempNumCopied] = tempMatrix[tempActualRow][tempFirstIndex];
tempFirstIndex++;
tempNumCopied++;
} // Of while
while (tempSecondIndex <= tempSecondEnd) {
tempMatrix[tempNextRow][tempFirstStart + tempNumCopied] = tempMatrix[tempActualRow][tempSecondIndex];
tempSecondIndex++;
tempNumCopied++;
} // Of while
} // Of for groupNumber
System.out.println("Round " + tempRow);
for (int i = 0; i < length; i++) {
System.out.println(tempMatrix[tempNextRow][i] + " ");
} // Of for i
System.out.println();
} // Of for tempSize
data = tempMatrix[tempNextRow];
} // Of mergeSort
public static void mergeSortTest() {
int[] tempUnsortedKeys = { 5, 3, 6, 10, 7, 1, 9 };
String[] tempContents = { "if", "then", "else", "switch", "case", "for", "while" };
DataArray tempDataArray = new DataArray(tempUnsortedKeys, tempContents);
System.out.println(tempDataArray);
tempDataArray.mergeSort();
System.out.println("Resultrn" + tempDataArray);
} // Of mergeSortTest
public static void main(String[] args) {
System.out.println("rn-------------sequentialSearchTest-------------");
sequentialSearchTest();
System.out.println("rn-------------binarySearchTest-------------");
binarySearchTest();
System.out.println("rn-------------hashSearchTest-------------");
hashSearchTest();
System.out.println("rn-------------insertionSort-------------");
insertionSortTest();
System.out.println("rn-------------shellSort-------------");
shellSortTest();
System.out.println("rn-------------bubbleSort-------------");
bubbleSortTest();
System.out.println("rn-------------quickSort-------------");
quickSortTest();
System.out.println("rn-------------selectionSort-------------");
selectionSortTest();
System.out.println("rn-------------heapSort-------------");
heapSortTest();
System.out.println("rn-------------mergeSort-------------");
mergeSortTest();
} // Of main
截图：
