import java.util.PriorityQueue;
public class sort_test {
//冒泡排序
public static void BublleSort(int []arr){
if (arr==null||arr.length<2){
return;
}
for (int i=0;i< arr.length;i++){
for (int j=0;jarr[j+1]){
swap(arr, j, j+1);
}
}
}
}
private static void swap(int[] arr, int j, int i) {
arr[i] = arr[i]^arr[j];
arr[j] = arr[i]^arr[j];
arr[i] = arr[i]^arr[j];
}
//选择排序
public static void SelectionSort(int []arr){
if (arr==null||arr.length<2){
return;
}
for (int i=0;i=0&&arr[j]>arr[j+1];j--){
swap(arr, j, j+1);
}
}
}
//归并排序
public static void MergeSort(int []arr){
if (arr==null||arr.length==2){
return;
}
MergeSort(arr,0, arr.length-1);
}
public static void MergeSort(int []arr, int l, int r){
if (l==r){
return;
}
int mid = l + ((r-l)>>1);
MergeSort(arr, l, mid);
MergeSort(arr, mid+1, r);
Merge(arr,l,mid,r);
}
private static void Merge(int[] arr, int l, int mid, int r) {
int[] help = new int[r - l + 1];
int i = 0;
int p1=l;
int p2=mid+1;
while (p1<=mid&&p2<=r){
help[i++] = arr[p1]=high){
return;
}
int i=low;
int j = high;
int index = array[i];
while (i=index){
j--;
}
if (i 0) {
heapify(arr, 0, size);
swap(arr, 0, --size);
}
}
// 某个数处于index位置 向上移动
public static void heapInsert(int[] arr, int index) {
while (arr[index] > arr[(index - 1) / 2]) {
swap(arr, index, (index - 1) /2);
index = (index - 1)/2 ;
}
}
//某个数在index位置 能否向下移动
public static void heapify(int[] arr, int index, int size) {
//左孩子的下标
int left = index * 2 + 1;
while (left < size) { //判断有没有左孩子
// 两个孩子中 谁的值最大 把下标给largest
int largest = left + 1 < size && arr[left + 1] > arr[left] ? left + 1 : left;
// 父和孩子之间 谁的值大 把下标给largest
largest = arr[largest] > arr[index] ? largest : index;
// 父节点就是最大值的时候
if (largest == index) {
break;
}
// 较大的孩子和父交换
swap(arr, largest, index);
index = largest;
left = index * 2 + 1;
}
}
//桶排序
public static void radixSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
radixSort(arr, 0, arr.length - 1, maxbits(arr));
}
// 找最大值
public static int maxbits(int[] arr) {
int max = Integer.MIN_VALUE;
for (int i = 0; i < arr.length; i++) {
max = Math.max(max, arr[i]);
}
int res = 0;
while (max != 0) {
res++;
max /= 10;
}
return res;
}
public static void radixSort(int[] arr, int begin, int end, int digit) {
final int radix = 10;
int i = 0, j = 0;
int[] bucket = new int[end - begin + 1];
for (int d = 1; d <= digit; d++) {
int[] count = new int[radix];
for (i = begin; i <= end; i++) {
j = getDigit(arr[i], d);
count[j]++;
}
for (i = 1; i < radix; i++) {
count[i] = count[i] + count[i - 1];
}
for (i = end; i >= begin; i--) {
j = getDigit(arr[i], d);
bucket[count[j] - 1] = arr[i];
count[j]--;
}
for (i = begin, j = 0; i <= end; i++, j++) {
arr[i] = bucket[j];
}
}
}
public static int getDigit(int x, int d) {
return ((x / ((int) Math.pow(10, d - 1))) % 10);
}
public static void main(String[] args){
int []arr={2,5,3,1,6,9,8,7,0,4};
for (int j : arr) {
System.out.print(" " + j);
}
System.out.println("");
System.out.println("冒泡sort result");
BublleSort(arr);
for (int j : arr) {
System.out.print(" " + j);
}
System.out.println("");
System.out.println("选择sort result");
SelectionSort(arr);
for (int j : arr) {
System.out.print(" " + j);
}
System.out.println("");
System.out.println("插入sort result");
InsertSort(arr);
for (int j : arr) {
System.out.print(" " + j);
}
System.out.println("");
System.out.println("归并sort result");
MergeSort(arr);
for (int j : arr) {
System.out.print(" " + j);
}
System.out.println("");
System.out.println("快速sort result");
quickSort(arr);
for (int j : arr) {
System.out.print(" " + j);
}
System.out.println("");
System.out.println("堆sort result");
heapSort(arr);
for (int j : arr) {
System.out.print(" " + j);
}
System.out.println("");
System.out.println("桶sort result");
radixSort(arr);
for (int j : arr) {
System.out.print(" " + j);
}
// System.out.println("");
// PriorityQueue heap = new PriorityQueue<>();
// heap.add(3);
// heap.add(5);
// heap.add(4);
// while (!heap.isEmpty()){
// System.out.println(heap.poll());
// }
}
}
`
```
