日撸代码300行（41-50天，查找与排序）

原文：日撸代码300行（41-50天，查找与排序）

41.顺序查找与折半查找

42.哈希表

43.插入排序

44.希尔排序

45.冒牌排序

46.快速排序

47.选择排序

48.堆排序

49.归并排序

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 DataNodeDataNode[] data; // 数据int length; // 数据个数/*** 构造方法1.** @param paraKeyArray     Key数组.* @param paraContentArray Content数组.*/public DataArray(int[] paraKeyArray, String[] paraContentArray) {//this.length = paraKeyArray.length;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 iffor (int i = 0; i < length; i++) {data[i] = null;}// Of for iint tempPosition;for (int i = 0; i < paraKeyArray.length; i++) {// 合法判断if (paraKeyArray[i] < 0) {System.out.println("Invalid key: " + i);return;}// Of iftempPosition = paraKeyArray[i] % paraLength;while (data[tempPosition] != null) {tempPosition = (tempPosition + 1) % paraLength;}// Of whiledata[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 ireturn 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 ireturn 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 whilereturn 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 testSystem.out.println("Hash key = " + tempPosition);return data[tempPosition].content;}// Of iftempPosition = (tempPosition + 1) % length;}// Of whilereturn "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 kdata[k + sortLength] = tempNode;}// Of for j}// Of for isortLength /= 2;// TestSystem.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) {// swaptempFlag = true;tempNode = data[j];data[j] = data[j + 1];data[j + 1] = tempNode;}// Of if}// Of for jif (!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 ifDataNode tempPivot = data[paraStart];int tempStart = paraStart;int tempEnd = paraEnd;while (tempStart < tempEnd) {while (tempStart < tempEnd && (data[tempEnd].key >= tempPivot.key)) {tempEnd--;}// Of whiledata[tempStart] = data[tempEnd];while (tempStart < tempEnd && (data[tempStart].key <= tempPivot.key)) {tempStart++;}// Of whiledata[tempEnd] = data[tempStart];}// Of whiledata[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// swapdata[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//System.out.println("The parent position is "+ tempParent + " and the child is " + tempChild);// 子节点更大, 交换if (tempKey < data[tempChild].key) {data[tempParent] = data[tempChild];tempParent = tempChild;} else {// 未发生交换 后续也一定满足根堆条件,跳出循环break;}// Of ifdata[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 whilewhile (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

50.小结

比较分析各种查找算法.
设计一个自己的 Hash 函数和一个冲突解决机制.
比较分析各种排序算法.
描述各种排序算法的特点和基本思想.

咕咕咕

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！