归并排序:算法复杂度logN
先不断二分,直到分成单个元素,无法再分为止,然后比较大小合并处理
import java.util.*;
public class MergeSort {
public int[] mergeSort(int[] A, int n) {
if(A.length == 0 || n <= 0) {
return A;
}
mergeSort(A, 0, n-1);
return A;
}
public void mergeSort(int[] A, int left , int right) {
if(left >= right) { //注意是>= 相等的时候代表不可再分
return;
}
int mid = left + (right-left)/2;
mergeSort(A, left, mid); //二分
mergeSort(A, mid+1, right); //二分
merge(A, left, mid, right); //归并
}
public void merge(int[] A, int left, int mid, int right) {
//[left, mid]
//[mid+1, right]
int[] arr = new int[right-left+1];
int index = -1;
int l = left;
int r = mid+1;
while(l <= mid && r <= right) {
if(l <= mid && A[l] < A[r]) {
arr[++ index] = A[l ++];
}
else if(r <= right && A[r] <= A[l]) {
arr[++ index] = A[r ++];
}
}
while(l <= mid) {
arr[++ index] = A[l ++];
}
while(r <= right) {
arr[++ index] = A[l ++];
}
for(int i = 0; i < right-left+1; i++) {
A[left+i] = arr[i];
}
}
}
快速排序
- 思想:随机在数组中选择一个数据random, <random的放在左边 >random的放在右边,然后左边, 右边分别快排
import java.util.*;
public class QuickSort {
public int[] quickSort(int[] A, int n) {
if(A.length == 0 || n <= 0) {
return A;
}
quickSort(A, 0, n-1);
return A;
}
public void quickSort(int[] A, int left, int right) {
if(left >= right) {
return;
}
int index = partition(A, left, right);
quickSort(A, left, index-1);
quickSort(A, index+1, right);
}
public int partition(int[] A, int left, int right) {
//分割
int comparator = A[right];
int l = left-1;
for(int i = left; i < right; i++) {
if(A[i] < comparator) {
swap(A, ++l, i);
}
}
swap(A, ++ l, right);
return l;
}
public void swap(int[] A, int l, int r) {
int tmp = A[l];
A[l] = A[r];
A[r] = tmp;
}
}
堆排序
import java.util.*;
public class HeapSort {
public int[] heapSort(int[] A, int n) {
if(A.length == 0 || n <= 0) {
return A;
}
for(int i = n/2-1; i >= 0; i--) {
shiftUp(A, i, n-1);
}
for(int j = n-1; j > 0; j--) {
swap(A, 0, j);
shiftUp(A, 0, j-1);
}
return A;
}
public void swap(int[] A, int start, int end) {
int tmp = A[start];
A[start] = A[end];
A[end] = tmp;
}
public void shiftUp(int[] A, int start, int end) {
if(start >= end) {
return;
}
int parent = start;
int child = parent*2 + 1; //左子节点
int val = A[parent];
while(child <= end) {
if(child < end && A[child] < A[child+1]) { //这里child < end 必须, 否则下面child++会超出范围
child++;
}
if(A[child] > val) {
A[parent] = A[child];
parent = child;
child = parent*2+1;
} else {
break;
}
}
A[parent] = val;
}
}
希尔排序
import java.util.*;
public class ShellSort {
public int[] shellSort(int[] A, int n) {
if(A.length == 0 || n <= 0) {
return A;
}
int feet = n/2;
int index = 0;
while(feet > 0) {
for(int i = feet; i<n; i++) {
index = i;
while(index >= feet) { //注意这里的循环, 必须到达最前方
if(A[index] < A[index-feet]) {
swap(A, index, index-feet);
index = index - feet;
} else {
break;
}
}
}
feet /= 2;
}
return A;
}
public void swap(int[] A, int i, int j) {
int tmp = A[i];
A[i] = A[j];
A[j] = tmp;
}
}
网友评论