快速排序算法
import java.util.Arrays;
public class QuickSort {
public static void main(String[] args) {
int[] arr = {4,5,1,9,10,5};
quickSore(arr, 0, arr.length-1);
System.out.println(Arrays.toString(arr));
}
public static int getIndex(int[] arr,int left,int right) {
int key = arr[left];
while(left<right) {
while(arr[right]>=key&&right>left) {
right--;
}
arr[left] = arr[right];
while(arr[left]<=key&&right>left) {
left++;
}
}
arr[left] = key;
return left;
}
public static void quickSore(int[] arr,int left,int right) {
if(left>=right) {
return;
}
int index = getIndex(arr, left, right);
quickSore(arr, left, index-1);
quickSore(arr, index+1, right);
}
}
计数排序算法
import java.util.Arrays;
public class jiShu {
public static int[] JiShu(int[] arr){
int num =0;
int len = arr[0];
for(int i=1;i<arr.length;i++) {
if(len<arr[i]) {
len=arr[i];
}
}
int[] arrNew = new int[len+1];
int[] arr2 = new int[arr.length];
for(int i=0;i<arr.length;i++) {
arrNew[arr[i]] = arrNew[arr[i]]+1;
}
for(int i=0;i<arrNew.length;i++) {
if(arrNew[i]>0) {
for(int j=0;j<arrNew[i];j++) {
arr2[num++] =i;
}
}
}
return arr2;
}
public static void main(String[] args) {
int[] arr = {5,4,1,4,8,2};
System.out.println(Arrays.toString(JiShu(arr)));
}
}
二路归并排序
import java.util.Arrays;
public class testMerge {
public static void main(String[] args) {
int[] arr={3,1,2,5,7,5,3,8,7,6,4,8,9,34,56,78,23,12,11};
int[] newArr=new int[arr.length];
System.out.println(Arrays.toString(arr));
chai(arr,0,arr.length-1,newArr);
System.out.println(Arrays.toString(arr));
}
public static void chai(int[] arr,int left,int right,int[] newArr) {
if(left>=right) {
return;
}else {
//计算中间值
int mid = (left+right)/2;
//递归调用
chai(arr, left, mid, newArr);
chai(arr, mid+1, right, newArr);
//并
mergeRe(arr, left, right, mid, newArr);
}
}
//并
public static void mergeRe(int[] arr,int left,int right,int mid,int[] newArr) {
//数据集左侧的边界
int m = left;
int n = mid+1;
//数据集右边的边界
int x = mid;
int y = right;
//记录新数组的下标
int index = 0;
while(m<=x&&n<=y) {
if(arr[m]<arr[n]) {
newArr[index++] = arr[m++];
}
else {
newArr[index++] = arr[n++];
}
}
while(m<=x) {
newArr[index++] = arr[m++];
}
while(n<=y) {
newArr[index++] = arr[n++];
}
for(int i=0;i<index;i++) {
arr[i+left]=newArr[i];
}
}
}