Skip to content

Commit 723a771

Browse files
author
monsoon
committed
Basic Algorithms
0 parents  commit 723a771

File tree

12 files changed

+795
-0
lines changed

12 files changed

+795
-0
lines changed

‎.gitignore‎

Lines changed: 9 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,9 @@
1+
target/
2+
out/
3+
.idea/
4+
*.iml
5+
.settings/
6+
.metadata/
7+
.classpath
8+
.project
9+
Servers/

‎src/com/xfj/sort/heap/MaxHeap.java‎

Lines changed: 86 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,86 @@
1+
package com.xfj.sort.heap;
2+
3+
import com.xfj.sort.util.SwapUtil;
4+
5+
import java.lang.reflect.Array;
6+
import java.util.Random;
7+
8+
/**
9+
* Created by asus on 2017/4/16.
10+
*/
11+
public class MaxHeap<T extends Comparable>{
12+
13+
private T[] arr = null;
14+
15+
private int count;
16+
17+
private int capacity;
18+
19+
public MaxHeap(int capacity,Class clazz){
20+
this.count = 0;
21+
this.capacity = capacity;
22+
this.arr = (T[]) Array.newInstance(clazz,capacity + 1);
23+
}
24+
25+
public boolean isEmpty(){
26+
return count == 0;
27+
}
28+
29+
public int size(){
30+
return count;
31+
}
32+
33+
public void insert(T item){
34+
if(item != null && (count + 1<= capacity )){
35+
arr[count + 1] = item;
36+
count++;
37+
shiftUp(count);
38+
}
39+
}
40+
41+
//将新加入的值一直进行上升，使数组保持完全二叉树
42+
private void shiftUp(int index){
43+
while ( index > 1 && arr[index/2].compareTo(arr[index]) < 0){
44+
//父节点如果小于子节点 ，则交换
45+
SwapUtil.swap(arr,index/2,index);
46+
index = index /2;
47+
}
48+
}
49+
50+
public T extractMax(){
51+
assert (count > 0);
52+
T item = arr[1];
53+
if(count / 2 >= 1 )
54+
SwapUtil.swap(arr,1,count);
55+
count--;
56+
shiftDown(1);
57+
return arr[1];
58+
}
59+
60+
private void shiftDown(int index){
61+
//首先确保2*index有值，即该节点作为父节点必存在左子结点，可能存在右子节点
62+
while ((2 * index <= count)){
63+
int leftIndex = 2 * index;
64+
if(((leftIndex +1)<=count) && arr[leftIndex].compareTo(arr[leftIndex+1]) < 0)
65+
leftIndex = leftIndex + 1;
66+
if(arr[index].compareTo(arr[leftIndex]) > 0) break;
67+
SwapUtil.swap(arr,index,leftIndex);
68+
index = leftIndex;
69+
}
70+
}
71+
72+
public static void main(String[] args) {
73+
Random random = new Random();
74+
MaxHeap<Integer> heap = new MaxHeap<Integer>(100,Integer.class);
75+
for(int i = 0;i<100;i++){
76+
heap.insert(random.nextInt(100));
77+
}
78+
for(int i = 0;i<100;i++){
79+
System.out.print(heap.extractMax() + " ");
80+
}
81+
82+
}
83+
84+
85+
86+
}

‎src/com/xfj/sort/insert/InsertSort.java‎

Lines changed: 69 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,69 @@
1+
package com.xfj.sort.insert;
2+
3+
import com.xfj.sort.interfac.Sort;
4+
import com.xfj.sort.select.SelectionSort;
5+
import com.xfj.sort.util.SortGeneratorHelper;
6+
import com.xfj.sort.util.SwapUtil;
7+
8+
import java.util.Arrays;
9+
10+
/**
11+
* Created by asus on 2017/4/15.
12+
*/
13+
public class InsertSort implements Sort{
14+
@Override
15+
public <T extends Comparable> void sort(T[] arr, int n) {
16+
if(n < 1) return;
17+
/*
18+
for(int i = 1;i < n;i++){
19+
for(int j = i ;j >0;j-- ){
20+
if(arr[j].compareTo(arr[j - 1 ]) < 0){
21+
SwapUtil.swap(arr,j,j - 1);
22+
}else
23+
break;
24+
}
25+
}
26+
*/
27+
for(int i = 1;i< n;i++){
28+
T e = arr[i];
29+
int j;
30+
for(j= i;j > 0 && arr[j-1].compareTo(e) > 0;j--){
31+
arr[j] = arr[j-1];
32+
}
33+
arr[j] = e;
34+
}
35+
}
36+
37+
38+
public static <T extends Comparable> void sortPart(T[] t,int low ,int high){
39+
if(t == null || t.length == 0) return;
40+
for(int i = low; i <= high ; i++){
41+
T e = t[i];
42+
int j;
43+
for (j = i; j > low && t[j-1].compareTo(e) >0 ;j--){
44+
t[j] = t[j-1];
45+
}
46+
t[j] = e;
47+
}
48+
}
49+
50+
51+
52+
public static void main(String[] args) {
53+
Integer[] arrtest = SortGeneratorHelper.generatorIntegerArray(10000, 0, 10000);
54+
Sort sort = new InsertSort();
55+
sort.sort(arrtest,1000);
56+
SortGeneratorHelper.printArray(arrtest);
57+
System.out.println("");
58+
System.out.println(SortGeneratorHelper.isSorted(arrtest,1000));
59+
60+
Integer[] clone = Arrays.copyOf(arrtest, 10000);
61+
SortGeneratorHelper.testSort("selectSort",new SelectionSort(),clone,10000);
62+
SortGeneratorHelper.printArray(clone);
63+
System.out.println("");;
64+
SortGeneratorHelper.testSort("insertSort",new InsertSort(),arrtest,10000);
65+
SortGeneratorHelper.printArray(arrtest);
66+
}
67+
68+
69+
}

‎src/com/xfj/sort/interfac/Sort.java‎

Lines changed: 8 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,8 @@
1+
package com.xfj.sort.interfac;
2+
3+
/**
4+
* Created by asus on 2017/4/15.
5+
*/
6+
public interface Sort {
7+
public <T extends Comparable> void sort(T[] arr,int n);
8+
}

‎src/com/xfj/sort/merge/MergeSort.java‎

Lines changed: 82 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,82 @@
1+
package com.xfj.sort.merge;
2+
3+
import com.xfj.sort.insert.InsertSort;
4+
import com.xfj.sort.interfac.Sort;
5+
import com.xfj.sort.select.SelectionSort;
6+
import com.xfj.sort.util.SortGeneratorHelper;
7+
8+
import java.lang.reflect.Array;
9+
import java.util.ArrayList;
10+
import java.util.Arrays;
11+
import java.util.List;
12+
13+
/**
14+
* Created by asus on 2017/4/15.
15+
*/
16+
public class MergeSort<T> implements Sort{
17+
@Override
18+
public <T extends Comparable> void sort(T[] arr, int n) {
19+
__mergeSort(arr,0,n -1);
20+
}
21+
22+
private <T extends Comparable> void __mergeSort(T[] arr,int l,int h){
23+
//递归退出条件
24+
//if(l >= h) return ;
25+
if( h - l <= 15) {
26+
//当要排序数组小到一定值后，插入排序的性能要好于递归
27+
InsertSort.sortPart(arr,l,h);
28+
return;
29+
}
30+
int mid = (l + h)/ 2;
31+
__mergeSort(arr,l,mid);
32+
__mergeSort(arr,mid + 1,h);
33+
if(arr[mid].compareTo(arr[mid+1]) > 0){
34+
__merge(arr,l,mid,h);
35+
}
36+
}
37+
38+
private <T extends Comparable> void __merge(T[] arr,int l,int mid,int h){
39+
T[] aux = (T[]) createArray(arr[0].getClass(),h - l + 1);
40+
for(int i = l ;i <= h;i++){
41+
aux[i - l] = arr[i];
42+
}
43+
int i ;
44+
int j ;
45+
int k = l;
46+
for(i=l,j= mid +1;k <= h;k++)
47+
{
48+
if(i > mid){
49+
arr[k] = aux[j - l];
50+
j++;
51+
}else if( j > h){
52+
arr[k] = aux[i - l];
53+
i++;
54+
}else if(aux[i - l].compareTo(aux[j - l ]) < 0){
55+
arr[k] = aux[i - l];
56+
i++;
57+
}else{
58+
arr[k] = aux[j -l ];
59+
j++;
60+
}
61+
}
62+
}
63+
64+
private <T extends Comparable> T[] createArray(Class<T> clazz,int initialCapacity){
65+
//创建泛型数组的方法。
66+
return (T[])Array.newInstance(clazz,initialCapacity);
67+
68+
}
69+
70+
public static void main(String[] args) {
71+
Integer[] arr = SortGeneratorHelper.generatorIntegerArray(10000, 0, 10000);
72+
SortGeneratorHelper.printArray(arr);
73+
Sort sort = new MergeSort<Integer>();
74+
System.out.println("");
75+
sort.sort(arr,10000);
76+
SortGeneratorHelper.printArray(arr);
77+
System.out.println();
78+
System.out.println(SortGeneratorHelper.isSorted(arr,10000));
79+
/* Sort iort = new InsertSort();
80+
iort.sort(arr,10000);*/
81+
}
82+
}

‎src/com/xfj/sort/pojo/Student.java‎

Lines changed: 38 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,38 @@
1+
package com.xfj.sort.pojo;
2+
3+
/**
4+
* Created by asus on 2017/4/14.
5+
*/
6+
public class Student implements Comparable<Student>{
7+
8+
private String name;
9+
10+
private Integer age;
11+
12+
public Student(String name, Integer age) {
13+
this.name = name;
14+
this.age = age;
15+
}
16+
17+
@Override
18+
public int compareTo(Student o) {
19+
if( o instanceof Student){
20+
if(this.age > o.age){
21+
return 1;
22+
}else if(this.age < o.age){
23+
return -1;
24+
}else {
25+
return 0;
26+
}
27+
}
28+
return 0;
29+
}
30+
31+
@Override
32+
public String toString() {
33+
return "Student{" +
34+
"name='" + name + '\'' +
35+
", age=" + age +
36+
'}';
37+
}
38+
}

‎src/com/xfj/sort/quick/QuickSort.java‎

Lines changed: 53 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,53 @@
1+
package com.xfj.sort.quick;
2+
3+
import com.xfj.sort.interfac.Sort;
4+
import com.xfj.sort.util.SortGeneratorHelper;
5+
import com.xfj.sort.util.SwapUtil;
6+
7+
/**
8+
* Created by asus on 2017/4/15.
9+
*/
10+
public class QuickSort implements Sort{
11+
@Override
12+
public <T extends Comparable> void sort(T[] arr, int n) {
13+
//对闭区间[0,n-1]进行排序
14+
QuickSort.quickS(arr,0,n-1);
15+
}
16+
//对闭区间[0,n-1]进行排序
17+
public static <T extends Comparable> void quickS(T[] arr,int lo,int hi){
18+
//递归退出条件
19+
if(lo >= hi) return;
20+
int j = QuickSort.partition(arr, lo, hi);
21+
QuickSort.quickS(arr,lo,j-1);
22+
QuickSort.quickS(arr,j+1,hi);
23+
}
24+
25+
private static <T extends Comparable> int partition(T[] arr,int lo,int hi){
26+
int i = lo;
27+
int j = hi+1;
28+
while (true){
29+
//一直循环 直到找到第一个大于arr[lo]的i的位置
30+
while (less(arr[++i],arr[lo]))
31+
if(i == hi) break;
32+
//一直循环 直到找到第一个小于arr[lo]的j的位置
33+
while (less(arr[lo],arr[--j]))
34+
if( j == lo) break;
35+
if(i >= j) break;
36+
SwapUtil.swap(arr,i,j);
37+
}
38+
SwapUtil.swap(arr,lo,j);
39+
return j;
40+
}
41+
42+
private static <T extends Comparable> boolean less(T a,T b){
43+
return a.compareTo(b) <= 0 ? true : false;
44+
}
45+
46+
public static void main(String[] args){
47+
Integer[] arr = SortGeneratorHelper.generatorIntegerArray(10000, 0, 10000);
48+
SortGeneratorHelper.testSort("quickSort",new QuickSort(),arr,10000);
49+
SortGeneratorHelper.printArray(arr);
50+
System.out.println();
51+
System.out.println(SortGeneratorHelper.isSorted(arr,10000));
52+
}
53+
}

0 commit comments

Comments
 (0)