1、冒泡排序

算法思想：每次扫描待排序的元素,相邻元素满足排序条件，则交换,每一趟排序使最大(或最小)元素放置到末尾，经过n-1次扫描完成排序，最坏情况是扫描后交换,最好情况是元素本身有序，只需扫描,而不需要交换元素。

public class BubbleSort {
    public static void bubbleSort(int [] arr){
        for(int i=arr.length-1; i>0; i--){ //n-1趟冒泡
            for(int j=0; j<i; j++){ //每趟冒泡交换相邻元素,找出最大值
                if(arr[j] > arr[j+1]){
                    int temp = arr[j] ;
                    arr[j] = arr[j+1];
                    arr[j+1] = temp ;
                }
            }
        }
    }
    public static void main(String[] args){
        int [] arr = {2,1,6,3,5,4,7,9,8,10,0} ;
        bubbleSort(arr) ;
                for(int k=0; k<arr.length; k++){
            System.out.print(arr[k] + " ") ;
        }
    }
}

2、插入排序

算法思想：将待排序的元素分为"已排序"和"未排序"两种,每次从未排序的元素中选择一个插入到已排序的元素中。

public class InsertSort {
    public static void insertSort(int [] arr){
        for(int i=1; i<arr.length; i++){
            int key = arr[i] ; //未排序的第一个元素
            int j = i - 1 ; //已排序的最后一个元素的下标
            while(j>=0 && arr[j] > key){
                arr[j+1] = arr[j] ; //后移一位，空出插入位置
                j -- ;
            }
            arr[j+1] = key ; //插入
        }
    }
    public static void main(String[] args){
        int [] arr = {2,1,4,3,6,7,5,0,10,9} ;
        insertSort(arr) ;
        for(int j=0; j<arr.length; j++){
            System.out.print(arr[j] + " ") ;
        }
    }
}

3、选择排序

算法思想：每次从未排序的元素中选择一个最小的，和未排序的首位元素进行交换，直至所有元素有序。

public class SelectSort {
    public static void selectSort(int [] arr){
        for(int i=0; i<arr.length; i++){
            int ith = i  ;
            for(int j=i+1; j<arr.length; j++){
                if(arr[ith] > arr[j]){
                    int temp = arr[ith];
                    arr[ith] = arr[j] ;
                    arr[j] = temp ;
                }
            }
        }
    }
    public static void main(String[] args){
        int [] arr = {3,2,1,4,6,5,8,9,7,10,0} ;
        selectSort(arr) ;
        for(int j=0; j<arr.length; j++){
            System.out.print(arr[j] + " ") ;
        }
    }
}

4、希尔排序

算法思想：一趟一个增量，用增量进行分组，组内进行插入排序,分组交错执行。

public class ShellSort {
    public static void shellSort(int [] arr){
        for(int interval = arr.length/2; interval > 0; interval=interval/2){//不断缩小增量
            for(int j=interval; j < arr.length; j++){ //分组交替执行插入排序
                int key = arr[j] ;
                int k = j - interval ;
                while(k>=0 && arr[k] > key){
                    arr[k+interval] = arr[k] ;
                    k -= interval ;
                }
                arr[k+interval] = key ; //插入
            }
        }
    }
    public static void main(String[] args){
        int [] arr = {2,1,4,3,7,6,8,0,10,9} ;
        shellSort(arr) ;
        for(int i=0; i<arr.length; i++){
            System.out.print(arr[i] + " ") ;
        }
    }
}

5、快速排序

算法思想：分治的思想,选择一个元素作为主元，直至主元左侧元素都比主元小，主元右侧元素都比主元大，缩小数组范围，递归的进行快速排序。

public class QuickSort {
    public static void swap(int [] arr, int left, int right){ //交换arr[left]和arr[right]的方法
        int temp = arr[left] ;
        arr[left] = arr[right] ;
        arr[right] = temp ;
    }
    //划分的方法,每次划分将比采用双指针扫描，找出左侧比主元大的，找出右侧比主元小的，二者交换，返回主元的位置
    public static int partition(int [] arr, int p, int r){
        int pivot = arr[p] ; //初始化主元
        int left = p + 1; //左侧扫描指针
        int right = r ; //右侧扫描指针
        while(left <= right){
            while(left <= right && arr[left] <= pivot){
                left ++ ;
            }
            while(left <= right && arr[right] >= pivot){
                right -- ;
            }
            if(left < right){ //找到左侧比主元大的，右侧比主元小的，二者交换
                swap(arr, left, right) ;
            }
        }
        swap(arr, p, right) ; //将初始化的主元与划分后得到的主元交换
        return right ;
    }
    public static void quickSort(int [] arr, int left, int right){
        if(left < right){
            int q = partition(arr, left, right) ; //每次划分得到主元，保证主元左侧元素小于主元，右侧元素大于主元
            quickSort(arr, 0, q-1) ; //对主元左侧递归快速排序
            quickSort(arr, q+1, right); //对主元右侧递归快速排序
        }
    }
    public static void main(String[] args){
        int [] arr = {2,1,3,7,6,9,4,5,0,9,10,8} ;
        quickSort(arr, 0, arr.length-1) ;
        for(int i=0; i<arr.length; i++){
            System.out.print(arr[i] + " ") ;
        }
    }
}

6、归并排序

算法思想:划分后，对左侧和右侧分别进行归并排序，再合并。合并借助辅助数组。

public class MergeSort {
    public static void mergeSort(int [] arr, int p, int r){
        if(p < r){
            int mid = (p + r) >>> 1 ;
            mergeSort(arr, 0, mid - 1) ;
            mergeSort(arr, mid + 1, r) ;
            merge(arr, p, r, mid) ;
        }
    }
    public static void merge(int [] arr, int p, int r, int mid){
        int [] helper = new int [arr.length] ;
        for(int i=0; i<arr.length; i++){ //将数组元素值存放到辅助数组helper上
            helper[i] = arr[i] ;
        }
        int left = p ;//左半部分头指针
        int right = mid + 1 ; //右半部分头指针
        int current = p ; //原数组头指针
        while(left<=mid && right <= r){
            if(helper[left] <= helper[right]){
                arr[current++] = helper[left++] ;
            }else{
                arr[current++] = helper[right++] ;
            }
        }
        while(left <= mid){ //左边指针未到头，需要填充到数组arr尾部，右侧指针未到头，不需要进行处理
            arr[current ++] = helper[left++] ;
        }
    }
    public static void main(String[] args){
        int [] arr = {2,1,5,4,7,6,9,3,10,0} ;
        mergeSort(arr, 0, arr.length - 1) ;
        for(int j=0; j<arr.length; j++){
            System.out.print(arr[j] + " ") ;
        }
    }
}

7、堆排序

算法思想:先堆化,以n/2-1为根元素开始，不停调整堆，建立大根堆,再将堆顶元素与最后元素交换,缩小堆元素的范围，递归向下调整，直至最终有序。

public class HeapSort {
    public static void maxHeap(int [] arr, int n){
        for(int i = n/2-1; i>=0; i--){ //递归向下调整，建立大根堆
            fixHeap(arr, i, n) ;
        }
    }
    public static void fixHeap(int [] arr, int i, int n){ //i为根节点,n为堆中元素个数
        int left = 2 * i + 1 ;
        int right = 2 * i + 2 ;
        int max = right ;
        if(left >= n){ //左孩子越界，则右孩子必越界
            return ;
        }
        if(right >= n && left < n){ //左孩子不越界，右孩子越界
            max =left ;
        }
        if(right < n){ //右孩子不越界，左孩子不越界
            if(arr[right] >= arr[left]){
                max = right ;
            }else{
                max = left ;
            }
        }
        if(arr[i] >= arr[max]){ //根节点元素比左右孩子元素都大，不调整
            return ;
        }else { //反之，选择左右孩子大的与根节点元素交换，递归向下调整
            int temp = arr[max];
            arr[max] = arr[i];
            arr[i] = temp;
            fixHeap(arr, max, n);
        }
    }
    public static void heapSort(int [] arr, int n){
        maxHeap(arr,n) ;//建立大根堆
        for(int j=n-1; j>=0; j--){ //交换堆顶元素与最后一个元素,递归调整为大根堆
            int temp = arr[0] ;
            arr[0] = arr[j] ;
            arr[j] = temp ;
            fixHeap(arr, 0, j) ;
        }
    }
    public static void main(String[] args){
        int [] arr = {2,1,5,6,4,7,0,3,10,9,8} ;
        heapSort(arr, arr.length) ;
        for(int i=0; i<arr.length; i++){
            System.out.print(arr[i] + " ") ;
        }
    }
}

8、计数排序

算法思想:用辅助数组，对原数组中出现的数字进行计数，元素转下标，最后下标转元素。

public class CountingSort {
    public static int max(int [] arr){ //求出数组中最大元素
        int max = arr[0] ;
        for(int i=1; i<arr.length; i++){
            if(max < arr[i]){
                max = arr[i] ;
            }
        }
        return max ;
    }
    public static int min(int [] arr){ //求出数组中最小元素
        int min = arr[0] ;
        for(int i=1; i<arr.length; i++){
            if(min > arr[i]){
                min = arr[i] ;
            }
        }
        return min ;
    }
    public static void countingSort(int [] arr){ //计数排序
        int max = max(arr) ;
        int min = min(arr) ;
        int [] helper = new int [max - min + 1] ; //辅助数组
        for(int i=0; i<arr.length; i++){ //计数
            helper[arr[i] - min] ++ ;
        }
        int index = 0, j = 0 ;
        while(j < arr.length){ //依次存放到原来数组
            while(helper[index] > 0){
                arr[j] = index - min ;
                j ++ ;
                helper[index] -- ;
            }
            index ++ ;
        }
    }
    public static void main(String[] args){
        int [] arr = {2,1,3,-1,3,6,0,10,9,8,7,4} ;
        countingSort(arr) ;
        for(int i=0; i<arr.length; i++){
            System.out.print(arr[i] + " ") ;
        }
    }
}

9、桶排序

算法思想:通过分配和收集的方式完成排序设计k个桶,编号0-k-1,将n个元素分配存到不同的桶中,桶内排序,然后遍历桶，从桶中取出即可。

public class BucketSort {
    public static void bucketSort(int [] arr){
        int max = Integer.MIN_VALUE ;
        int min = Integer.MAX_VALUE ;
        for(int i=0; i<arr.length; i++){ //找出数组中的最大元素和最小元素
            max = (max <= arr[i]) ? arr[i] : max ;
            min = (min >= arr[i]) ? arr[i] : min ;
        }
        //计算桶的数量
        int bucketNum = (max - min) / arr.length + 1 ;
        ArrayList<ArrayList<Integer>> bucketArr = new ArrayList<>() ;
        for(int i=0; i<bucketNum; i++){
            bucketArr.add(new ArrayList<>()) ;
        }
        //将元素入桶
        for(int i=0; i<arr.length; i++){
            int num = (arr[i] - min) / arr.length ; //计算进入哪个桶
            bucketArr.get(num).add(arr[i]) ;
        }
        //每个桶的桶内元素排序
        for(int i=0; i<bucketArr.size(); i++){
            Collections.sort(bucketArr.get(i)) ;
        }
        int index = 0 ;
        for(int j=0; j<bucketArr.size(); j++){
            for(int k=0; k<bucketArr.get(j).size(); k++){
                arr[index++] = bucketArr.get(j).get(k) ;
            }
        }
    }
    public static void main(String[] args){
        int [] arr = {1,5,2,9,3,0,4,10,8,7,6,-1} ;
        bucketSort(arr) ;
        for(int i=0; i<arr.length; i++){
            System.out.print(arr[i] + " ") ;
        }
    }
}

10、基数排序

算法思想:按照位数进行分配和回收,n次分配回收后,元素有序。

public class RadixSort {
    private static ArrayList [] bucket = new ArrayList [10] ; //定义10个桶
    static {
        for(int i=0; i<bucket.length; i++){
            //为每个桶分配对象
            bucket[i] = new ArrayList() ;
        }
    }
    public static int max(int [] arr){ //找出数组元素的最大值
        int max = arr[0] ;
        for(int i=1; i<arr.length; i++){
            if(arr[i] > max){
                max = arr[i] ;
            }
        }
        return max ;
    }
    public static void putInBucket(int data, int digit){ //入桶
        switch(digit){ //根据基数位判断进入哪个桶
            case 0 : bucket[0].add(data) ; break ;
            case 1 : bucket[1].add(data) ; break ;
            case 2 : bucket[2].add(data) ; break ;
            case 3 : bucket[3].add(data) ; break ;
            case 4 : bucket[4].add(data) ; break ;
            case 5 : bucket[5].add(data) ; break ;
            case 6 : bucket[6].add(data) ; break ;
            case 7 : bucket[7].add(data) ; break ;
            case 8 : bucket[8].add(data) ; break ;
            case 9 : bucket[9].add(data) ; break ;
            default: break ;
        }
    }
    public static Integer getDigitOn(int elements, int d){ //取出数字的第d位
        String s = String.valueOf(elements) ;
        return Integer.parseInt(s.charAt(d-1)+"") ;
    }
    //将数组按照d个位来分配和收集
    public static void sort(int [] arr, int d){
        for(int i=0; i<arr.length; i++){ //入桶
            putInBucket(arr[i], getDigitOn(arr[i], d)) ;
        }
        //出桶
        int index = 0 ;
        for(int j=0; j<bucket.length; j++){
            for(Object m : bucket[j]){
                arr[index++] = (Integer)m ;
            }
        }
        clearAll() ;
    }
    public static void clearAll(){ //清空桶
        for(ArrayList b : bucket){
            b.clear() ;
        }
    }
    public static void radixSort(int [] arr){
        int d = 1 ; //入桶时候初始化位数
        int max = max(arr) ; //数组中最大元素
        int length = 1 ; //最大数据的位数
        while(max / 10 != 0){
            length ++ ;
            max /= 10 ;
        }
        while(length >= d){
            sort(arr, d++) ; //递归的进行分配和收集
        }
    }
    public static void main(String[] args){
        int [] arr = {2,1,5,4,0,7,9,8,6} ;
        radixSort(arr) ;
        for(int i=0; i<arr.length; i++){
            System.out.print(arr[i] + " ") ;
        }
    }
}