1.数组
package javaDataStruct.array01;
public class MyArray {
private int[] arr;
// 表示有效数据的长度
private int elementsSize;
public MyArray() {
// TODO Auto-generated constructor stub
arr = new int[50];
}
public MyArray(int maxSize) {
arr = new int[maxSize];
}
/**
* 添加数据
*/
public void insert(int value) {
arr[elementsSize] = value;
elementsSize++;
}
/**
* 打印数据
*/
public void printArray() {
System.out.print("[ ");
for (int i = 0; i < elementsSize; i++) {
System.out.print(arr[i] + " ");
}
System.out.println("]");
}
/**
* 查找数据
*/
public int indexSearch(int value) {
int i;
for (i = 0; i < elementsSize; i++) {
if (value == arr[i]) {
break;
}
}
if (i == elementsSize) {
return -1;
} else {
return i;
}
}
/**
* 二分法查找数据 前提：数组有序
*/
public int binarySearch(int value) {
int middle;
int low = 0;
int high = elementsSize;
while (true) {
middle = (low + high) / 2;
if (arr[middle] == value)
return middle;
else if (low > high) {
return -1;
} else {
if (arr[middle] < value)
low = middle + 1;
else
high = middle - 1;
}
}
}
/**
* 查找数据，根据索引查找
*/
public int get(int index) {
if (index < 0 || index >= elementsSize) {
throw new ArrayIndexOutOfBoundsException();
} else {
return arr[index];
}
}
/**
* 删除数据
*/
public void delete(int index) {
if (index < 0 || index >= elementsSize) {
throw new ArrayIndexOutOfBoundsException();
} else {
for (int i = index; i < elementsSize; i++) {
arr[i] = arr[i + 1];
}
elementsSize--;
}
}
/**
* 更新数据
*/
public void update(int index, int value) {
if (index < 0 || index >= elementsSize) {
throw new ArrayIndexOutOfBoundsException();
} else {
arr[index] = value;
}
}
}package javaDataStruct.array01;
public class TestMyArray {
public static void main(String[] args) {
// TODO Auto-generated method stub
MyArray array = new MyArray();
array.insert(13);
array.insert(17);
array.insert(34);
array.insert(55);
array.insert(90);
array.printArray();
System.out.println(array.indexSearch(34));
System.out.println(array.indexSearch(90));
System.out.println(array.indexSearch(190));
System.out.println(array.get(2));
// System.out.println(array.get(3));
array.delete(1);
array.printArray();
array.update(1, 33);
array.printArray();
System.out.println(array.binarySearch(55));
System.out.println(array.binarySearch(33));
System.out.println(array.binarySearch(13));
}
}2.简单排序
2.1冒泡排序
https://www.cnblogs.com/jingmoxukong/p/4302718.html
假设要对一个大小为 N 的无序序列进行升序排序（即从小到大）。
(1) 每趟排序过程中需要通过比较找到第 i 个小的元素。
所以，我们需要一个外部循环，从数组首端(下标 0) 开始，一直扫描到倒数第二个元素（即下标 N - 2) ，剩下最后一个元素，必然为最大。
(2) 假设是第 i 趟排序，可知，前 i-1 个元素已经有序。现在要找第 i 个元素，只需从数组末端开始，扫描到第 i 个元素，将它们两两比较即可。
所以，需要一个内部循环，从数组末端开始（下标 N - 1），扫描到 (下标 i + 1)。
package javaDataStruct.sort02;
public class BubbleSort {
public static void sort(int[] array) {
int temp = 0;
// 需要遍历的次数
for (int i = 0; i < array.length - 1; i++) {
for (int j = array.length - 1; j > i; j--) { // 注意 array.length - 1// 比较相邻的元素，如果前面的数大于后面的数，则交换
if (array[j] < array[j - 1]) {
temp = array[j];
array[j] = array[j - 1];
array[j - 1] = temp;
}
}
}
}
}
2.2选择排序
https://www.cnblogs.com/jingmoxukong/p/4303289.html
(1)从待排序序列中，找到关键字最小的元素；
(2)如果最小元素不是待排序序列的第一个元素，将其和第一个元素互换；
(3)从余下的 N - 1 个元素中，找出关键字最小的元素，重复(1)、(2)步，直到排序结束。
package javaDataStruct.sort02;
public class SelectionSort {
public static void sort(int[] array) { // 需要遍历获得最小值的次数
// 要注意一点，当要排序 N 个数，已经经过 N-1 次遍历后，已经是有序数列
int k = 0; // 保存最小数据的索引
int temp = 0;
for (int i = 0; i < array.length-1; i++) {
k = i;
for (int j = i+1; j < array.length; j++) {
if (array[j] < array[k])
k = j; // 更新最小数据的索引
}
// 将最小数据交换
temp = array[k];
array[k] = array[i];
array[i] = temp;
}
}
}
2.3插入排序
https://www.cnblogs.com/jingmoxukong/p/4303270.html
package javaDataStruct.sort02;
public class InsertSort {
public static void sort(int[] arr) {
int temp = 0;
int i, j;
// 第1个数肯定是有序的，从第2个数开始遍历，依次插入有序序列
for (i = 1; i < arr.length; i++) {
temp = arr[i]; // 取出第i个数，和前i-1个数比较后，插入合适位置
// 因为前i-1个数都是从小到大的有序序列，所以只要当前比较的数(list[j])比temp大，就把这个数后移一位
for (j = i - 1; j >= 0 && temp < arr[j]; j--) {
arr[j + 1] = arr[j];
}
arr[j + 1] = temp;
}
}
}package javaDataStruct.sort02;
import javaDataStruct.util.Tool;
public class TestSort {
public static void main(String[] args) {
int[] array = { 1, 2, 6, 8, 16, 3, 5 };
// BubbleSort.sort(array);
// SelectionSort.sort(array);
InsertSort.sort(array);
Tool.printArray(array);
}
}2.4希尔排序
https://www.cnblogs.com/jingmoxukong/p/4303279.html
希尔(Shell)排序又称为缩小增量排序，它是一种插入排序。它是直接插入排序算法的一种威力加强版。
该方法因DL．Shell于1959年提出而得名。
希尔排序的基本思想是：
把记录按步长 gap 分组，对每组记录采用直接插入排序方法进行排序。
随着步长逐渐减小，所分成的组包含的记录越来越多，当步长的值减小到 1 时，整个数据合成为一组，构成一组有序记录，则完成排序。
我们来通过演示图，更深入的理解一下这个过程。
在上面这幅图中：
初始时，有一个大小为 10 的无序序列。
在第一趟排序中，我们不妨设 gap1 = N / 2 = 5，即相隔距离为 5 的元素组成一组，可以分为 5 组。
接下来，按照直接插入排序的方法对每个组进行排序。
在第二趟排序中，我们把上次的 gap 缩小一半，即 gap2 = gap1 / 2 = 2 (取整数)。这样每相隔距离为 2 的元素组成一组，可以分为 2 组。
按照直接插入排序的方法对每个组进行排序。
在第三趟排序中，再次把 gap 缩小一半，即gap3 = gap2 / 2 = 1。 这样相隔距离为 1 的元素组成一组，即只有一组。
按照直接插入排序的方法对每个组进行排序。此时，排序已经结束。
需要注意一下的是，图中有两个相等数值的元素 5 和 5 。我们可以清楚的看到，在排序过程中，两个元素位置交换了。
所以，希尔排序是不稳定的算法
public static void shellSort(int[] array) {
int gap = array.length;
while (gap > 0) {
int temp;
int j;
for (int i = 1; i < array.length; i++) {
temp = array[i];
for (j = i - gap; j >= 0 && temp < array[j]; j = j - gap) {
array[j + gap] = array[j];
}
array[j + gap] = temp;
}
gap = gap / 2;
}
}2.5快速排序
https://www.cnblogs.com/jingmoxukong/p/4302891.html
public static int division(int[] list, int left, int right) {
// 以最左边的数(left)为基准
int base = list[left];
while (left < right) {
// 从序列右端开始，向左遍历，直到找到小于base的数
while (left < right && list[right] >= base)
right--;
// 找到了比base小的元素，将这个元素放到最左边的位置
list[left] = list[right];
// 从序列左端开始，向右遍历，直到找到大于base的数
while (left < right && list[left] <= base)
left++;
// 找到了比base大的元素，将这个元素放到最右边的位置
list[right] = list[left];
}
// 最后将base放到left位置。此时，left位置的左侧数值应该都比left小；
// 而left位置的右侧数值应该都比left大。
list[left] = base;
return left;
}
public static void quickSort(int[] list, int left, int right) {
// 左下标一定小于右下标，否则就越界了
if (left < right) {
// 对数组进行分割，取出下次分割的基准标号
int base = division(list, left, right);
// 对“基准标号“左侧的一组数值进行递归的切割，以至于将这些数值完整的排序
quickSort(list, left, base - 1);
// 对“基准标号“右侧的一组数值进行递归的切割，以至于将这些数值完整的排序
quickSort(list, base + 1, right);
}
}2.6归并排序
归并排序是一种概念上最简单的排序算法，与快速排序一样，归并排序也是基于分治法的。归并排序将待排序的元素序列分成两个长度相等的子序列，为每一个子序列排序，然后再将他们合并成一个子序列。合并两个子序列的过程也就是两路归并。
package datastruct.t02sort;
import datastruct.Tookit;
public class MergeSort {
public static void mergeSort(int[] a, int left, int right) {
if (left >= right)
return;
int mid = (left + right) / 2;
mergeSort(a, left, mid);
mergeSort(a, mid + 1, right);
mergeArray(a, left, mid, right);//合并
}
// 两个排好序的子序列合并为一个子序列
public static void mergeArray(int[] a, int left, int mid, int right) {
int[] temp = new int[a.length];//辅助数组
int p1 = left, p2 = mid + 1, k = left;//p1、p2是检测指针，k是存放指针
while (p1 <= mid && p2 <= right) {
if (a[p1] < a[p2])
temp[k++] = a[p1++];
else
temp[k++] = a[p2++];
}
while (p1 <= mid) {//如果第一个序列未检测完，直接将后面所有元素加到合并的序列中
temp[k++] = a[p1++];
}
while (p2 <= right) {//同上
temp[k++] = a[p2++];
}
for (int i = left; i <= right; i++) {
a[i] = temp[i];
}
}
public static void main(String[] args) {
int[] a = { 1, 5, 3, 7, 4, 8, 10 };
System.out.println("原数组为：");
Tookit.print(a);
mergeSort(a, 0, a.length - 1);
System.out.println("排序之后的数组为");
Tookit.print(a);
}
}2.7堆排序
heapify操作顺序
从构建好的堆进行排序
1.交换根结点和最后一个结点
2.取出最后一个结点
3.再次从根结点进行heapify
4.交换根结点和最后一个结点
5.取出最后一个结点
重复上述步骤。。。
package datastruct.t02sort;
import util.*;
public class HeapSort {
// 构建堆
public static void buildHeap(int[] tree, int n) {
int lastNode = n - 1;
int parent = (lastNode - 1) / 2;
int i;
for (i = parent; i >= 0; i--) {
heapify(tree, n, i);
}
}
/**
*
* @param tree
* @param n：结点数目
* @param i：当前的结点
*/
public static void heapify(int[] tree, int n, int i) {
if (i >= n)
return;
int c1 = 2 * i + 1;
int c2 = 2 * i + 2;
int max = i;
if (c1 < n && tree[c1] > tree[max]) {
max = c1;
}
if (c2 < n && tree[c2] > tree[max]) {
max = c2;
}
if (max != i) {
swap(tree, max, i);
heapify(tree, n, max);
}
}
// 交换元素
public static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
// 堆排序
public static void heapSort(int[] tree, int n) {
buildHeap(tree, n);
for (int i = n - 1; i >= 0; i--) {
swap(tree, i, 0);
heapify(tree, i, 0);
}
}
public static void main(String[] args) {
/*int[] tree = { 4, 10, 3, 5, 1, 2 };
int n = 6;
heapify(tree, n, 0);
Tool.printArray(tree);*/
/*int[] tree = { 2, 5, 3, 1, 10, 4 };
int n = 6;
buildHeap(tree, n);*/
int[] tree = { 23, 4, 5, 2, 1, 8, 24, 55 };
heapSort(tree, tree.length);
Tool.printArray(tree);
}
}3.栈
package javaDataStruct.ch03_stack_and_queue;
import com.sun.javafx.geom.AreaOp.AddOp;
public class MyStack {
private int[] arr;
private int top;
public MyStack() {
// TODO Auto-generated constructor stub
arr = new int[10];
top = -1;
}
/**
* 带参数的构造方法
*/
public MyStack(int maxSize) {
arr = new int[maxSize];
top = -1;
}
/**
* 添加数据
*/
public void push(int value) {
arr[++top] = value;
}
/**
* 移除数据
*/
public int pop() {
return arr[top--];
}
/**
* 查看数据
*/
public int peek() {
return arr[top];
}
/**
* 是否为空
*/
public boolean isEmpty() {
return top == -1;
}
/**
* 判断是否满了
*/
public boolean isFull() {
return top == arr.length - 1;
}
}package javaDataStruct.ch03_stack_and_queue;
public class TestMyStack {
public static void main(String[] args) {
// TODO Auto-generated method stub
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(10);
myStack.push(12);
myStack.push(16);
System.out.println(myStack.isEmpty());
System.out.println(myStack.isFull());
System.out.println(myStack.peek());
System.out.println(myStack.pop());
System.out.println(myStack.pop());
System.out.println(myStack.pop());
System.out.println(myStack.pop());
System.out.println(myStack.isEmpty());
}
}4.队列
package javaDataStruct.ch03_stack_and_queue;
public class MyQueue {
private int[] arr;
private int elementsSize;
private int front;
private int tail;
public MyQueue() {
// TODO Auto-generated constructor stub
arr = new int[10];
elementsSize = 0;
front = 0;
tail = -1;
}
public MyQueue(int maxSize) {
// TODO Auto-generated constructor stub
arr = new int[maxSize];
elementsSize = 0;
front = 0;
tail = -1;
}
/**
* 从队尾插入数据
*/
public void insert(int value) {
arr[++tail] = value;
elementsSize++;
}
/**
* 从对头删除数据
*/
public int remove() {
elementsSize--;
return arr[front++];
}
/**
* 从对头查看数据
*/
public int peek() {
return arr[front];
}
/**
* 判断是否为空
*/
public boolean isEmpty() {
return elementsSize == 0;
}
/**
* 判断是否满了
*/
public boolean isFull() {
return elementsSize == arr.length;
}
}package javaDataStruct.ch03_stack_and_queue;
public class TestMyQueue {
public static void main(String[] args) {
// TODO Auto-generated method stub
MyQueue mq = new MyQueue();
mq.insert(1);
mq.insert(2);
mq.insert(3);
mq.insert(4);
System.out.println(mq.isEmpty());
System.out.println(mq.isFull());
System.out.println(mq.peek());
while (!mq.isEmpty()) {
System.out.print(mq.remove() + " ");
}
System.out.println();
}
}5.链表
5.1普通单向链表
1.在头部插入一个节点
2.在头部删除一个节点
package cn.jxufe.ch04_link; /*
* 链结点，相当于是车厢
*/
public class Node {
public int data;
public Node next; public Node(int value) {
this.data = value;
} /**
* 显示方法
*/
public void display() {
System.out.print(data + " ");
}
}
package cn.jxufe.ch04_link; /**
* 链表相当于火车
*/
public class LinkList {
private Node first; public LinkList() {
first = null;
} /**
* 插入一个节点，在头部进行插入
*/
public void insertNode(int value) {
Node node = new Node(value);
if (first == null) {
first = node;
} else {
node.next = first;
first = node;
}
} /**
* 在头部进行删除
*/
public Node deleteFirst() {
Node temp = first;
first = temp.next;
return temp;
} /**
* 显示方法
*/
public void display() {
Node current = first;
while (current != null) {
current.display();
current = current.next;
}
System.out.println();
} /**
* 查找方法
*/
public Node find(int value) {
Node current = first;
while (current.data != value) {
if (current.next == null) {
return null;
}
current = current.next;
}
return current;
} /**
* 删除方法
*/ public Node delete(int value) {
Node current = first;
Node previous = first;
while (current.data != value) {
if (current.next == null) {
return null;
}
previous = current;
current = current.next;
}
if(current==first){
first = first.next;
}else {
previous.next = current.next;
}
return current; }
}
package cn.jxufe.ch04_link;
public class TestLinkList {
public static void main(String[] args) {
LinkList linkList = new LinkList();
linkList.insertNode(34);
linkList.insertNode(23);
linkList.insertNode(12);
linkList.insertNode(0);
linkList.insertNode(-1);
linkList.display();
linkList.deleteFirst();
linkList.display();
Node node = linkList.find(23);
node.display();
System.out.println();
Node node1 = linkList.delete(0);
node1.display();
System.out.println();
linkList.display();
linkList.display();
}
}5.2双端链表
1.在尾部插入一个节点
package cn.jxufe.ch05_first_last_link; import cn.jxufe.ch04_link.Node; /**
* 双端链表
*/
public class FirstLastLink {
private Node first;
private Node last; public FirstLastLink() {
first = null;
last = null;
} /**
* 插入一个节点，在头部进行插入
*/
public void insertNode(int value) {
Node node = new Node(value);
if (isEmpty()) {
last = node;
}
node.next = first;
first = node;
} /**
* 插入一个节点，从尾部插入
*/
public void insertLast(int value) {
Node node = new Node(value);
if (isEmpty()) {
first = node;
} else {
last.next = node;
}
last = node;
} /**
* 在头部进行删除
*/
public Node deleteFirst() {
Node temp = first;
if(first.next == null){
last = null;
}
first = temp.next;
return temp;
} /**
* 显示方法
*/
public void display() {
Node current = first;
while (current != null) {
current.display();
current = current.next;
}
System.out.println();
} /**
* 查找方法
*/
public Node find(int value) {
Node current = first;
while (current.data != value) {
if (current.next == null) {
return null;
}
current = current.next;
}
return current;
} /**
* 删除方法
*/ public Node delete(int value) {
Node current = first;
Node previous = first;
while (current.data != value) {
if (current.next == null) {
return null;
}
previous = current;
current = current.next;
}
if (current == first) {
first = first.next;
} else {
previous.next = current.next;
}
return current; } /**
* 判读是否为空
*/
public boolean isEmpty() {
return first == null;
}
}
package cn.jxufe.ch05_first_last_link;
public class TestFirstLastLink {
public static void main(String[] args) {
FirstLastLink fl = new FirstLastLink();
fl.insertNode(34);
fl.insertNode(22);
fl.insertNode(4);
fl.insertNode(56);
fl.display();
fl.deleteFirst();
fl.deleteFirst();
fl.display();
fl.insertLast(28);
fl.insertLast(90);
fl.display();
}
}5.3双向链表
1.在头部插入一个节点
2.在尾部插入一个节点
3.从头部进行删除
package cn.jxufe.ch05_first_last_link; /**
* 双向链表
* 每个列表除了保存对下一个节点的引用，同时还保存对前一个节点的引用。
*/
public class DoubleLink {
private Node first;
private Node last; public DoubleLink() {
first = null;
last = null;
} /**
* 插入一个节点，在头部进行插入
* 首先对列表进行判断，如果为空，则设置尾结点为新添加的节点；如果不为空，则设置头节点的前一个节点为新添加的节点。
*/
public void insertFirst(int value) {
Node node = new Node(value);
if (isEmpty()) {
last = node;
} else {
first.prev = node;
}
node.next = first;
first = node;
} /**
* 插入一个节点，从尾部插入
* 如果为空，则直接设置头节点为新添加的节点；否则设置尾结点的后一个节点为新添加的节点，同时设置新添加的
* 节点的前一个节点为尾结点。
*/
public void insertLast(int value) {
Node node = new Node(value);
if (isEmpty()) {
first = node;
} else {
last.next = node;
node.prev = last; }
last = node;
} /**
* 在头部进行删除
*/
public Node deleteFirst() {
Node temp = first;
if (first.next == null) {
last = null;
} else {
first.next.prev = null;
}
first = temp.next;
return temp;
} /**
* 从尾部进行删除
* 如果头节点后没有其他节点，则设置尾节点为null；否则设置尾节点的前一个节点的next为null。设置为节点为其前一个节点。
*/
public Node deleteLast() {
Node temp = last;
if (first.next == null) {
last = null;
} else {
last.prev.next = null;
}
last = last.prev;
return last;
} /**
* 显示方法
*/
public void display() {
Node current = first;
while (current != null) {
current.display();
current = current.next;
}
System.out.println();
} /**
* 查找方法
*/
public Node find(int value) {
Node current = first;
while (current.data != value) {
if (current.next == null) {
return null;
}
current = current.next;
}
return current;
} /**
* 删除方法
*/ public Node delete(int value) {
Node current = first;
while (current.data != value) {
if (current.next == null) {
return null;
}
current = current.next;
}
if (current == first) {
first = first.next;
} else {
current.prev.next = current.next;
}
return current; } /**
* 判读是否为空
*/
public boolean isEmpty() {
return first == null;
}
}
package cn.jxufe.ch05_first_last_link;
public class TestDoubleLink {
public static void main(String[] args) {
DoubleLink dl = new DoubleLink();
dl.insertLast(45);
dl.insertLast(23);
dl.insertLast(-1);
dl.insertLast(56);
dl.display();
dl.insertFirst(21);
dl.insertFirst(1);
dl.insertFirst(27);
dl.display();
dl.deleteFirst();
dl.display();
dl.deleteLast();
dl.display();
dl.delete(21);
dl.display();
}
}