几种常见的【排序】与【数据结构】

(一)常见排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157

<!-- more -->
import java.util.Arrays;

public class Sort {
//快速排序
private static int partition(int[] arr, int low, int hight) {
int pivotkey = arr[low];
while (low < hight) {
while (low < hight && pivotkey <= arr[hight])
--hight;
int temp1 = arr[low];
arr[low]=arr[hight];
arr[hight]=temp1;
//arr[low] = arr[hight];
while (low < hight && pivotkey >= arr[low])
++low;
int temp2 = arr[low];
arr[low]=arr[hight];
arr[hight]=temp2;
//arr[hight] = arr[low];
}
return low;
}
//快速排序
public static void qSort(int[] arr, int low, int hight) {
if (low < hight) {
int pivotkey = partition(arr, low, hight);
qSort(arr, low, pivotkey - 1);
qSort(arr, pivotkey + 1, hight);
}
}
//插入排序
public static int[] insertOrder(int a[]){
for (int i = 1; i < a.length; i++) {
int k = a[i];
int j;
for (j = i - 1; j >= 0 && k < a[j]; j--) {
a[j + 1] = a[j];
}
a[j + 1] = k;
//System.out.println(Arrays.toString(a));
}
return a;
}
//冒泡排序
public static int[] maopao(int[] a){

for(int i=0;i<a.length-1;i++){//i 代表伦次
for(int j=0;j<a.length-i-1;j++){//j和j+1代表相邻元素
if(a[j]>a[j+1]){
int temp = a[j];
a[j]= a[j+1];
a[j+1]=temp;
}
}
//System.out.println(Arrays.toString(a));
//Arrays.sort(a);
}
return a;
}
//选择排序
public int[] selectOrder(int arr[] ) {
for (int i = 0; i <arr.length; i++) {
int max = arr[i];
for (int j = i + 1; j < arr.length; j++) {
if (arr[j] < max) {
int temp = arr[j];
arr[j] = max;
max = temp;
arr[i] = max;
}
}
}
return arr;
}

// 二分查找
public void binarySearch() {
int b[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16 };
int start = 0;
int end = b.length - 1;
int mid;
int target = 1;
while (true) {
mid = ((end + start) / 2);
if (b[mid] == target) {
System.out.println(mid);
break;
}
if (target < b[mid]) {
end = mid;
}
if (target > b[mid]) {
start = mid + 1;
}

}
}

public static void main(String args[]) {
int Arr[] = { 10, 30, 20, 50, 90, 80, 60, 40, 70 };
System.out.println(Arrays.toString(Arr));
qSort(Arr, 0, Arr.length -1);
System.out.println(Arrays.toString(Arr));
}
}
希尔排序:
算法思想

它是对插入插入排序的改进

搜索维基百科可知
希尔排序,也称递减增量排序算法
假设有这样一组数[ 13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10 ]
,我们分别以步长为5,3,1进行排序(希尔排序最后的步长一定是1)

步长为5,我们可以得到如下数据,
13 14 94 33 82
25 59 94 65 23
45 27 73 25 39
10
然后 按照列排序
10 14 73 25 23
13 27 94 33 39
25 59 94 65 82
45

将上述四行数字,依序接在一起时我们得到:[ 10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45 ].这时10已经移至正确位置了,然后再以3为步长进行排序:
10 14 13
25 23 33
27 25 59
39 65 73
45 94 82
94
-最后以1步长进行排序(此时就是简单的插入排序了)。

public static void shellPass(Integer[] array, int d) {
for (int i = d; i < array.length; i++) {
int temp = array[i];
int j = i - d;
while (j >= 0 && array[j] > temp) {
array[j + d] = array[j];
j -= d;
}
array[j + d] = temp;
}
}

public static void shellSort(Integer[] data) {
int increment = 12;
do {
increment = increment / 3 + 1;
shellPass(data, increment);
} while (increment > 1);

}

(二)常见数据结构
2.1 graph
2.1.1图节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class GraphNode {
int val;
GraphNode next;
GraphNode[] neighbors;
boolean visited;

GraphNode(int x) {
val = x;
}

GraphNode(int x, GraphNode[] n){
val = x;
neighbors = n;
}

public String toString(){
return "value: "+ this.val;
}
}

2.1.2队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

public class Queue {
GraphNode first, last;

public void enqueue(GraphNode n){
if(first == null){
first = n;
last = first;
}else{
last.next = n;
last = n;
}
}

public GraphNode dequeue(){
if(first == null){
return null;
}else{
GraphNode temp = new GraphNode(first.val, first.neighbors);
first = first.next;
return temp;
}
}
}

2.1.3测试类

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
public class GraphTest {
public static void main(String[] args) {
GraphNode n1 = new GraphNode(1);
GraphNode n2 = new GraphNode(2);
GraphNode n3 = new GraphNode(3);
GraphNode n4 = new GraphNode(4);
GraphNode n5 = new GraphNode(5);

n1.neighbors = new GraphNode[]{n2,n3,n5};
n2.neighbors = new GraphNode[]{n1,n4};
n3.neighbors = new GraphNode[]{n1,n4,n5};
n4.neighbors = new GraphNode[]{n2,n3,n5};
n5.neighbors = new GraphNode[]{n1,n3,n4};

breathFirstSearch(n1, 5);
}

public static void breathFirstSearch(GraphNode root, int x){
if(root.val == x)
System.out.println("find in root");

Queue queue = new Queue();
root.visited = true;
queue.enqueue(root);

while(queue.first != null){
GraphNode c = (GraphNode) queue.dequeue();
for(GraphNode n: c.neighbors){

if(!n.visited){
System.out.print(n + " ");
n.visited = true;
if(n.val == x)
System.out.println("Find "+n);
queue.enqueue(n);
}
}
}
}
}

2.2link
2.2.1链表实例节点

1
2
3
4
5
6
7
8
9
10
public class Node {
int val;
Node next;

Node(int x) {
val = x;
next = null;
}
}

2.3Queue
2.3.1队列节点

1
2
3
4
5
6
7
8
9
10
public class Node {
int val;
Node next;

Node(int x) {
val = x;
next = null;
}
}

2.3.2队列操作类

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

public class Queue {
Node first, last;

public void enqueue(Node n){
if(first == null){
first = n;
last = first;
}else{
last.next = n;
last = n;
}
}

public Node dequeue(){
if(first == null){
return null;
}else{
Node temp = new Node(first.val);
first = first.next;
return temp;
}
}
}

2.4stack
2.4.1栈的节点

1
2
3
4
5
6
7
8
9
10
public class Node {
int val;
Node next;

Node(int x) {
val = x;
next = null;
}
}

2.4.2栈的操作类

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

public class Stack {
Node top;

public Node peek(){
if(top != null){
return top;
}

return null;
}

public Node pop(){
if(top == null){
return null;
}else{
Node temp = new Node(top.val);
top = top.next;
return temp;
}
}

public void push(Node n){
if(n != null){
n.next = top;
top = n;
}
}
}

2.5Tree
2.5.1数的节点

1
2
3
4
5
6
public class TreeNode {
int value;
TreeNode left;
TreeNode right;
}