排序算法java

稳定性：排序前后两个相等的数相对位置不变，则算法稳定。
1、不稳定：堆排序、快速排序、希尔排序、直接选择；
2、稳定：基数排序、冒泡排序、直接插入排序、折半插入排序、归并排序

// "static void main" must be defined in a public class.
import java.util.Arrays; 
public class Main {
    public static void main(String[] args) {
        int[] arr = {1,2,0,5,3,2};
        // BubbleSort(arr);
        // SelectSort(arr);
        // InsertSort(arr);
        QuickSort(arr, 0, arr.length-1);
        System.out.println("==========");    
        for(int a:arr){
            System.out.print(a+" ");    
        }
    }
    
    public static void QuickSort(int[] arr, int left, int right){
    //分治法，不稳定，O(NlogN)
        if(left>right) return;
        int l=left, r=right;
        int base = arr[l];
        while(l=base) r--;
            if(lright) return;
        int l = left, r = right;
        int keep = arr[l]; // 把最左边的数挖出来留作基准
        while(l=keep) r--; //从右往左找小于基准的数
            if(lkeep，把arr[l]挖出来填到刚才挖出来的右边的坑中
                arr[r] = arr[l];
                r--;
            }
        }
        // 当 i==j 的时候，退出循环
        arr[l] = keep;
        QuickSort(arr, left, l-1);
        QuickSort(arr, l+1, right);   
    }
    
    public static void InsertSort(int[] array){
        // 不稳定，O(n^2)
        int[] arr = (int[])Arrays.copyOf(array, array.length);
        for(int i=0;i0;j--){
                if(arr[j]arr[j]){
                    pos = j; //记录未排序部分的最小元素的下标
                }
            }
            if(pos!=i){
                    int tmp = arr[i];
                    arr[i] = arr[pos];
                    arr[pos] = tmp;
            }
        }
        for(int a:arr){
            System.out.print(a+" ");    
        }
    }
    
    public static void BubbleSort(int[] array){
        // 稳定，O(n^2)
        int[] arr = (int[])Arrays.copyOf(array, array.length);
        for(int i=0;iarr[j+1]){
                    int tmp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = tmp;
                }
            }
        }
        for(int a:arr){
            System.out.print(a+" ");    
        }
        
    }
}