日撸代码300行（41-50天，查找与排序）
package day50;
/**
* Day 41-49: 查找,排序.
* 和老板保持一致，用键值对数据进行学习.
*
* @author pzf
*/
public class DataArray {
/**
* 内部类. 数据节点.
*/
static class DataNode {
int key; // 键
String content; // 值
/**
* 构造方法1.
*
* @param paraKey 键
* @param paraContent 值
*/
public DataNode(int paraKey, String paraContent) {
this.content = paraContent;
this.key = paraKey;
}// Of the first contractor
/**
* 重写toString
*
* @return 字符串
*/
public String toString() {
return "(" + key + ", " + content + ") ";
}// Of toString
}// Of class DataNode
DataNode[] data; // 数据
int length; // 数据个数
/**
* 构造方法1.
*
* @param paraKeyArray Key数组.
* @param paraContentArray Content数组.
*/
public DataArray(int[] paraKeyArray, String[] paraContentArray) {
// = ;
this.length = Math.min(paraKeyArray.length, paraContentArray.length); // 避免越界
data = new DataNode[length];
for (int i = 0; i < length; i++) {
data[i] = new DataNode(paraKeyArray[i], paraContentArray[i]);
}// Of for i
}// Of the first contractor
/**
* 构造方法2. For Hash.
* 求余构造
* 线性探测开放定址法处理冲突.
*
* @param paraKeyArray 键 数组
* @param paraContentArray 值 数组
* @param paraLength Hash表长度
*/
public DataArray(int[] paraKeyArray, String[] paraContentArray, int paraLength) {
length = paraLength;
data = new DataNode[length];
// 长度合法判断
if (paraKeyArray.length > length) {
System.out.println("Invalid length");
return;
}// Of if
for (int i = 0; i < length; i++) {
data[i] = null;
}// Of for i
int tempPosition;
for (int i = 0; i < paraKeyArray.length; i++) {
// 合法判断
if (paraKeyArray[i] < 0) {
System.out.println("Invalid key: " + i);
return;
}// Of if
tempPosition = paraKeyArray[i] % paraLength;
while (data[tempPosition] != null) {
tempPosition = (tempPosition + 1) % paraLength;
}// Of while
data[tempPosition] = new DataNode(paraKeyArray[i], paraContentArray[i]);
}// Of for i
}// Of the second contractor
/**
* 重写toString
*
* @return 字符串
*/
public String toString() {
String resString = "";
for (int i = 0; i < this.length; i++) {
resString += data[i] + " ";
}// Of for i
return resString;
}// Of toString
/**
* 顺序查找,用了"哨兵",所以data中下标为0的数据为无效数据.
*
* @param paraKey 查找的键
* @return 值
*/
public String sequentialSearch(int paraKey) {
data[0].key = paraKey;
int i;
for (i = length - 1; data[i].key != paraKey; i--) {
}// Of for i
return data[i].content;
}// Of sequentialSearch
/**
* 二分查找.
* 仅适用于有序数据.
*
* @param paraKey 要查找的键
* @return 找到:值 , 没找到: null.
*/
public String binarySearch(int paraKey) {
int left = 0;
int right = length;
int mid;
String resString = "null";
while (left <= right) {
mid = (left + right) / 2;
if (data[mid].key == paraKey) {
resString = data[mid].content;
break;
} else if (data[mid].key < paraKey) {
left = mid + 1;
} else {
right = mid - 1;
}// Of if
}// Of while
return resString;
}// Of binarySearch
/**
* 哈希查找
*
* @param paraKey 要找的键
* @return 对应值
*/
public String hashSearch(int paraKey) {
int tempPosition = paraKey % length;
while (data[tempPosition] != null) {
if (data[tempPosition].key == paraKey) {
// For test
System.out.println("Hash key = " + tempPosition);
return data[tempPosition].content;
}// Of if
tempPosition = (tempPosition + 1) % length;
}// Of while
return "null";
}// Of hashSearch
/**
* 插入排序
* 0号位为哨兵，存放无效数据
*/
public void insertSort() {
DataNode tempNode;
int j;
for (int i = 2; i < length; i++) {
tempNode = data[i];
for (j = i - 1; j > 0 && data[j].key > tempNode.key; j--) {
data[j + 1] = data[j];
}
data[j + 1] = tempNode;
}// Of for i
}// Of insertSearch
/**
* 希尔排序
* 不用哨兵
*/
public void shellSort() {
DataNode tempNode;
int sortLength = length / 2;
int k;
while (sortLength > 0) { // 步长循环
for (int i = 0; i < sortLength; i++) { //分段
for (int j = i + sortLength; j < length; j = j + sortLength) { // 单段
tempNode = data[j];
for (k = j - sortLength; k >= 0; k -= sortLength) { // 内部插排
if (data[k].key > tempNode.key) {
data[k + sortLength] = data[k];
} else {
break;
}// Of if
}// Of for k
data[k + sortLength] = tempNode;
}// Of for j
}// Of for i
sortLength /= 2;
// Test
System.out.println("***");
System.out.println(this);
}// Of while
}// Of shellSort
/**
* 冒泡排序
*/
public void bubbleSort() {
DataNode tempNode;
boolean tempFlag = false;
for (int i = length - 1; i > 0; i--) {
for (int j = 0; j < i; j++) {
tempFlag = false;
if (data[j].key > data[j + 1].key) {
// swap
tempFlag = true;
tempNode = data[j];
data[j] = data[j + 1];
data[j + 1] = tempNode;
}// Of if
}// Of for j
if (!tempFlag) {
break;
}// Of if
}// Of for i
}// Of bubbleSort
/**
* 快排的每一轮
*
* @param paraStart 起始位置
* @param paraEnd 结束位置
*/
public void quickSortCircle(int paraStart, int paraEnd) {
if (paraStart >= paraEnd) {
return;
}// Of if
DataNode tempPivot = data[paraStart];
int tempStart = paraStart;
int tempEnd = paraEnd;
while (tempStart < tempEnd) {
while (tempStart < tempEnd && (data[tempEnd].key >= tempPivot.key)) {
tempEnd--;
}// Of while
data[tempStart] = data[tempEnd];
while (tempStart < tempEnd && (data[tempStart].key <= tempPivot.key)) {
tempStart++;
}// Of while
data[tempEnd] = data[tempStart];
}// Of while
data[tempStart] = tempPivot;
quickSortCircle(paraStart, tempStart - 1);
quickSortCircle(tempStart + 1, paraEnd);
}
/**
* 快排
*/
public void quickSort() {
quickSortCircle(0, length - 1);
}
/**
* 选择排序
*/
public void selectSort() {
DataNode tempNode;
int tempMinPosition;
for (int i = 0; i < length - 1; i++) {
tempNode = data[i];
tempMinPosition = i;
for (int j = i + 1; j < length; j++) {
if (tempNode.key > data[j].key) {
tempMinPosition = j;
tempNode = data[j];
}// Of if
}// Of for j
// swap
data[tempMinPosition] = data[i];
data[i] = tempNode;
}// Of for i
}// Of selectSort
/**
* 根堆调整 (大根堆)
*
* @param paraStart 起始节点
* @param paraLength 长度
*/
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) {
// 选出最大的子节点
if (tempChild + 1 < paraLength) {
if (data[tempChild].key < data[tempChild + 1].key) {
tempChild++;
}// Of if
}// Of if
//("The parent position is "+ tempParent + " and the child is " + tempChild);
// 子节点更大, 交换
if (tempKey < data[tempChild].key) {
data[tempParent] = data[tempChild];
tempParent = tempChild;
} else {
// 未发生交换 后续也一定满足根堆条件,跳出循环
break;
}// Of if
data[tempParent] = tempNode;
}// Of for
}// Of adjustHeap
/**
* 堆排序
*/
public void headSort() {
DataNode tempNode;
// 1.创建初始堆
// 从length/2开始 (子节点是最后一个). 依次向前调整.
for (int i = length / 2; i >= 0; i--) {
adjustHeap(i, length);
}// Of for i
// 2.每次将最大的和最后的节点交换 (最大的到最后,当做出堆,最后的节点到堆顶)
for (int i = length - 1; i > 0; i--) {
tempNode = data[0];
data[0] = data[i];
data[i] = tempNode;
adjustHeap(0, i);
}// Of for i
}// Of headSort
/**
* 归并
*
* @param paraLeft 起始点
* @param paraRight 结束点
*/
public void merge(int paraLeft, int paraRight) {
// 1.辅助数组
DataNode[] tempArray = new DataNode[paraRight - paraLeft + 1];
int tempCopy = 0;
for (int i = paraLeft; i <= paraRight; i++) {
tempArray[tempCopy++] = data[i];
}
// 2. 定义左右指针
int mid = paraLeft + (paraRight - paraLeft) / 2;
int lPoint = paraLeft;
int rPoint = mid + 1;
int tempPos = 0;
// 3.左右指针移动，找小的
while (lPoint <= mid && rPoint <= paraRight) {
if (data[lPoint].key <= data[rPoint].key) {
tempArray[tempPos++] = data[lPoint++];
} else {
tempArray[tempPos++] = data[rPoint++];
}// Of if
}// Of while
// 4.处理剩下的
while (lPoint <= mid) {
tempArray[tempPos++] = data[lPoint++];
}// Of while
while (rPoint <= mid) {
tempArray[tempPos++] = data[rPoint++];
}// Of while
// 复制回去
for (int i = 0; i < tempArray.length; i++) {
data[paraLeft + i] = tempArray[i];
}// Of for i
}// Of merge
/**
* 归并排序
*
* @param paraLeft 起始
* @param paraRight 结束
*/
public void mergeSort(int paraLeft, int paraRight) {
if (paraLeft < paraRight) {
int mid = (paraLeft + paraRight) / 2;
mergeSort(paraLeft, mid);
mergeSort(mid + 1, paraRight);
merge(paraLeft, paraRight);
}// Of if
}// Of mergeSort
/**
* 归并排序
*/
public void mergeSort() {
this.mergeSort(0, length - 1);
}// Of mergeSort
/**
* main
*
* @param args
*/
public static void main(String[] args) {
String[] tempContents = {"null", "if", "then", "else", "switch", "case", "for", "while"};
int[] tempUnsortedKeys = {-1, 5, 3, 6, 10, 7, 1, 9};
int[] tempSortedKeys = {1, 3, 5, 6, 7, 9, 10};
int[] tempHashKeys = {16, 33, 38, 69, 57, 95, 86};
String[] tempContentsPlus = {"null", "if", "then", "else", "switch", "case", "for", "while", "hello", "world"};
int[] tempUnsortedKeysPlus = {5, 3, 6, 10, 7, 1, 9, 12, 8, 4};
DataArray tempDataArrayUnsorted = new DataArray(tempUnsortedKeys, tempContents); // 无序
DataArray tempDataArraySorted = new DataArray(tempSortedKeys, tempContents); // 有序
DataArray tempDataArrayHash = new DataArray(tempHashKeys, tempContents, 19); // 哈希
DataArray tempDataArrayUnsortedPlus = new DataArray(tempUnsortedKeysPlus, tempContentsPlus); // 无序
DataArray tempDataArrayUnsortedBubble = new DataArray(tempUnsortedKeysPlus, tempContentsPlus); // 无序
DataArray tempDataArrayUnsortedQuick = new DataArray(tempUnsortedKeysPlus, tempContentsPlus); // 无序
DataArray tempDataArrayUnsortedSelect = new DataArray(tempUnsortedKeysPlus, tempContentsPlus); // 无序
DataArray tempDataArrayUnsortedHeap = new DataArray(tempUnsortedKeysPlus, tempContentsPlus); // 无序
DataArray tempDataArrayUnsortedMerge = new DataArray(tempUnsortedKeysPlus, tempContentsPlus); // 无序
// 1.顺序
System.out.println(tempDataArrayUnsorted);
System.out.println("Key = 3 : " + tempDataArrayUnsorted.sequentialSearch(3));
// 2.折半
System.out.println(tempDataArraySorted);
System.out.println("Key = 7 : " + tempDataArraySorted.binarySearch(7));
// 3.哈希
System.out.println(tempDataArrayHash);
System.out.println("Hash : " + tempDataArrayHash.hashSearch(38));
// 4.插入排序
System.out.println("原:" + tempDataArrayUnsorted);
tempDataArrayUnsorted.insertSort();
System.out.println("插排:" + tempDataArrayUnsorted);
// 5.希尔
System.out.println("希尔:");
System.out.println(tempDataArrayUnsortedPlus);
tempDataArrayUnsortedPlus.shellSort();
// 6.冒泡
System.out.println("冒泡:");
System.out.println("原:" + tempDataArrayUnsortedBubble);
tempDataArrayUnsortedBubble.bubbleSort();
System.out.println("冒:" + tempDataArrayUnsortedBubble);
// 7.快排
System.out.println("快排:");
System.out.println("原:" + tempDataArrayUnsortedQuick);
tempDataArrayUnsortedQuick.quickSort();
System.out.println("排:" + tempDataArrayUnsortedQuick);
// 8.选择
System.out.println("选择:");
System.out.println("原:" + tempDataArrayUnsortedSelect);
tempDataArrayUnsortedSelect.selectSort();
System.out.println("排:" + tempDataArrayUnsortedSelect);
// 9.堆
System.out.println("堆:");
System.out.println("原:" + tempDataArrayUnsortedHeap);
tempDataArrayUnsortedHeap.headSort();
System.out.println("排:" + tempDataArrayUnsortedHeap);
// 10.归并
System.out.println("归并:");
System.out.println("原:" + tempDataArrayUnsortedMerge);
tempDataArrayUnsortedMerge.mergeSort();
System.out.println("归:" + tempDataArrayUnsortedMerge);
}// Of main
}// Of class DataArray