8000 增加 Java 实现 by corningsun · Pull Request #16 · hustcc/JS-Sorting-Algorithm · GitHub
[go: up one dir, main page]

Skip to content

增加 Java 实现 #16

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Merged
merged 2 commits into from
Jan 8, 2018
Merged
Show file tree
Hide file tree
Changes from all commits
Commits
File filter

Filter by extension

Filter by extension


Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
4 changes: 4 additions & 0 deletions .gitignore
Original file line number Diff line number Diff line change
Expand Up @@ -15,3 +15,7 @@ _book
*.mobi
*.pdf
\.idea/

*.iml

src/javaSortTest/target/
33 changes: 33 additions & 0 deletions 1.bubbleSort.md
Original file line number Diff line number Diff line change
Expand Up @@ -77,3 +77,36 @@ func bubbleSort(arr []int) []int {
return arr
}
```

## 8. Java 代码实现

```java
public class BubbleSort implements IArraySort {

@Override
public int[] sort(int[] sourceArray) throws Exception {
// 对 arr 进行拷贝,不改变参数内容
int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

for (int i = 1; i < arr.length; i++) {
// 设定一个标记,若为true,则表示此次循环没有进行交换,也就是待排序列已经有序,排序已经完成。
boolean flag = true;

for (int j = 0; j < arr.length - i; j++) {
if (arr[j] > arr[j + 1]) {
int tmp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = tmp;

flag = false;
}
}

if (flag) {
break;
}
}
return arr;
}
}
```
87 changes: 86 additions & 1 deletion 10.radixSort.md
Original file line number Diff line number Diff line change
Expand Up @@ -47,4 +47,89 @@ function radixSort(arr, maxDigit) {
}
return arr;
}
```
```

## 4. Java 代码实现

```java
/**
* 基数排序
* 考虑负数的情况还可以参考: https://code.i-harness.com/zh-CN/q/e98fa9
*/
public class RadixSort implements IArraySort {

@Override
public int[] sort(int[] sourceArray) throws Exception {
// 对 arr 进行拷贝,不改变参数内容
int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

int maxDigit = getMaxDigit(arr);
return radixSort(arr, maxDigit);
}

/**
* 获取最高位数
*/
private int getMaxDigit(int[] arr) {
int maxValue = getMaxValue(arr);
return getNumLenght(maxValue);
}

private int getMaxValue(int[] arr) {
int maxValue = arr[0];
for (int value : arr) {
if (maxValue < value) {
maxValue = value;
}
}
return maxValue;
}

protected int getNumLenght(long num) {
if (num == 0) {
return 1;
}
int lenght = 0;
for (long temp = num; temp != 0; temp /= 10) {
lenght++;
}
return lenght;
}

private int[] radixSort(int[] arr, int maxDigit) {
int mod = 10;
int dev = 1;

for (int i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {
// 考虑负数的情况,这里扩展一倍队列数,其中 [0-9]对应负数,[10-19]对应正数 (bucket + 10)
int[][] counter = new int[mod * 2][0];

for (int j = 0; j < arr.length; j++) {
int bucket = ((arr[j] % mod) / dev) + mod;
counter[bucket] = arrayAppend(counter[bucket], arr[j]);
}

int pos = 0;
for (int[] bucket : counter) {
for (int value : bucket) {
arr[pos++] = value;
}
}
}

return arr;
}

/**
* 自动扩容,并保存数据
*
* @param arr
* @param value
*/
private int[] arrayAppend(int[] arr, int value) {
arr = Arrays.copyOf(arr, arr.length + 1);
arr[arr.length - 1] = value;
return arr;
}
}
```
34 changes: 34 additions & 0 deletions 2.selectionSort.md
Original file line number Diff line number Diff line change
Expand Up @@ -71,3 +71,37 @@ func selectionSort(arr []int) []int {
return arr
}
```

## 6. Java 代码实现

```java
public class SelectionSort implements IArraySort {

@Override
public int[] sort(int[] sourceArray) throws Exception {
int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

// 总共要经过 N-1 轮比较
for (int i = 0; i < arr.length - 1; i++) {
int min = i;

// 每轮需要比较的次数 N-i
for (int j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[min]) {
// 记录目前能找到的最小值元素的下标
min = j;
}
}

// 将找到的最小值和i位置所在的值进行交换
if (i != min) {
int tmp = arr[i];
arr[i] = arr[min];
arr[min] = tmp;
}

}
return arr;
}
}
```
34 changes: 34 additions & 0 deletions 3.insertionSort.md
Original file line number Diff line number Diff line change
Expand Up @@ -65,3 +65,37 @@ func insertionSort(arr []int) []int {
return arr
}
```

## 6. Java 代码实现

```java
public class InsertSort implements IArraySort {

@Override
public int[] sort(int[] sourceArray) throws Exception {
// 对 arr 进行拷贝,不改变参数内容
int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

// 从下标为1的元素开始选择合适的位置插入,因为下标为0的只有一个元素,默认是有序的
for (int i = 1; i < arr.length; i++) {

// 记录要插入的数据
int tmp = arr[i];

// 从已经排序的序列最右边的开始比较,找到比其小的数
int j = i;
while (j > 0 && tmp < arr[j - 1]) {
arr[j] = arr[j - 1];
j--;
}

// 存在比其小的数,插入
if (j != i) {
arr[j] = tmp;
}

}
return arr;
}
}
```
33 changes: 33 additions & 0 deletions 4.shellSort.md
Original file line number Diff line number Diff line change
Expand Up @@ -87,3 +87,36 @@ func shellSort(arr []int) []int {
return arr
}
```

## 5. Java 代码实现

```java
public class ShellSort implements IArraySort {

@Override
public int[] sort(int[] sourceArray) throws Exception {
// 对 arr 进行拷贝,不改变参数内容
int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

int gap = 1;
while (gap < arr.length) {
gap = gap * 3 + 1;
}

while (gap > 0) {
for (int i = gap; i < arr.length; i++) {
int tmp = arr[i];
int j = i - gap;
while (j >= 0 && arr[j] > tmp) {
arr[j + gap] = arr[j];
j -= gap;
}
arr[j + gap] = tmp;
}
gap = (int) Math.floor(gap / 3);
}

return arr;
}
}
```
50 changes: 50 additions & 0 deletions 5.mergeSort.md
Original file line number Diff line number Diff line change
Expand Up @@ -136,3 +136,53 @@ func merge(left []int, right []int) []int {
return result
}
```

## 7. Java 代码实现

```java
public class MergeSort implements IArraySort {

@Override
public int[] sort(int[] sourceArray) throws Exception {
// 对 arr 进行拷贝,不改变参数内容
int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

if (arr.length < 2) {
return arr;
}
int middle = (int) Math.floor(arr.length / 2);

int[] left = Arrays.copyOfRange(arr, 0, middle);
int[] right = Arrays.copyOfRange(arr, middle, arr.length);

return merge(sort(left), sort(right));
}

protected int[] merge(int[] left, int[] right) {
int[] result = new int[left.length + right.length];
int i = 0;
while (left.length > 0 && right.length > 0) {
if (left[0] <= right[0]) {
result[i++] = left[0];
left = Arrays.copyOfRange(left, 1, left.length);
} else {
result[i++] = right[0];
right = Arrays.copyOfRange(right, 1, right.length);
}
}

while (left.length > 0) {
result[i++] = left[0];
left = Arrays.copyOfRange(left, 1, left.length);
}

while (right.length > 0) {
result[i++] = right[0];
right = Arrays.copyOfRange(right, 1, right.length);
}

return result;
}

}
```
47 changes: 46 additions & 1 deletion 6.quickSort.md
Original file line number Diff line number Diff line change
Expand Up @@ -177,9 +177,54 @@ func swap(arr []int, i, j int) {
void QuickSort(int A[], int low, int high) //快排母函数
{
if (low < high) {
int pivot = Paritition1(A, low, high);
int pivot = Paritition1(A, low, high);
QuickSort(A, low, pivot - 1);
QuickSort(A, pivot + 1, high);
}
}
```

## 7. Java 代码实现

```java
public class QuickSort implements IArraySort {

@Override
public int[] sort(int[] sourceArray) throws Exception {
// 对 arr 进行拷贝,不改变参数内容
int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

return quickSort(arr, 0, arr.length - 1);
}

private int[] quickSort(int[] arr, int left, int right) {
if (left < right) {
int partitionIndex = partition(arr, left, right);
quickSort(arr, left, partitionIndex - 1);
quickSort(arr, partitionIndex + 1, right);
}
return arr;
}

private int partition(int[] arr, int left, int right) {
// 设定基准值(pivot)
int pivot = left;
int index = pivot + 1;
for (int i = index; i <= right; i++) {
if (arr[i] < arr[pivot]) {
swap(arr, i, index);
index++;
}
}
swap(arr, pivot, index - 1);
return index - 1;
}

private void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}

}
```
Loading
0