把各种排序算法实现一遍
1. quick sort:
public void quick_sort(int[] arr, int low, int high) {
if(low<high){
int p = partition(arr, low, high);
quick_sort(arr, low, p - 1);
quick_sort(arr, p + 1, high);
}
}
private void swap(int[] arr, int value1, int value2) {
int temp = arr[value1];
arr[value1] = arr[value2];
arr[value2] = arrtemp;
}
private int partition(int[] arr, int low, int high) {
int p = low;
int j = low+1;
while(j<=high) {
if(arr[j]<arr[low]){
swap(arr, ++p, j);
}
j++;
}
swap(arr, low, p);
return p;
}
2. merge sort
public void merge_sort(int[] arr) {
int n = arr.length;
if(n<2) {
return;
}
int mid = n/2;
int[] leftPart = new int[mid];
int[] rightPart = new int[n-mid];
for(int i=0;i<mid;i++) {
leftPart[i] = arr[i];
}
for(int i = mid;i<n;i++) {
rightPart[i - mid] = arr[i];
}
merge_sort(leftPart, mid);
merge_sort(rightPart, mid);
merge(arr, leftPart, rightPart);
}
private void merge(int[] arr, int[] left, int[] right) {
int a = arr.length, m = left.length, n = right.length;
int i = 0, j = 0, k =0;
while(i<m && j< n) {
if(left[m] < right[n]) {
a[k++] = left[i++];
} else {
a[k++] = right[j++];
}
}
while(i<m) {
a[k++] = left[i++];
}
while(j<n) {
a[k++] = right[j++];
}
}
---还有几种待续
