八大排序之冒泡、快排、堆排、基数排序

一、冒泡排序

   /**
    * 冒泡排序
    * @param arr
    */
public  static  void bubbleSort(int arr[]){
    for (int j=0;j<arr.length;j++){
        for (int i = 0;i<arr.length-1;i++){
            if (arr[i]>arr[i+1]){
                int temp = arr[i];
                arr[i] = arr[i+1];
                arr[i+1]= temp;
            }
        }
    }
    System.out.println(Arrays.toString(arr));
}

二、快速排序

public static void quickSort(int[] arr,int left,int right){
    if(left >= right){
        return;
    }
    //程序
    //定义数组当中的第一个数为基准数
    int baes = arr[left];
    int i = left;
    int j = right;
    while (i !=j){
        //j去找比当前基准数小的
        while (arr[j] >= baes && i<j){
            j--;
        }
        while (arr[i] <= baes && i<j){
            i++;
        }
        //数值交换
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
    // 基准数和相遇位置的数交换
    arr[left] = arr[i];
    arr[i] = baes;
    quickSort(arr,left,i-1);
    quickSort(arr,i+1,right);
}

三、堆排序

public class HeapSort {
    public static void main(String[] args) {
        int[] arr = new int[]{5,7,4,2,0,3,1,6};
        for (int p = arr.length-1;p>=0;p--){
            adjust(arr,p,arr.length);
        }
        //堆顶元素和堆底元素进行互换
        for(int i = arr.length-1;i>=0;i--){
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;
            adjust(arr,0,i);
        }
        System.out.println(Arrays.toString(arr));
    }
    /**
     * 堆得维护
     * @param arr
     * @param parent
     */
    public static void adjust(int[] arr,int parent,int length) {
        //定义出左子树
        int Child = 2 * parent + 1;

        while (Child<length){//有左子节点
            //对比左右子树
           int rChild = Child + 1;
           if(rChild<length && arr[rChild]>arr[Child]){
               Child++;
           }
           if(arr[parent] < arr[Child]){ //父子节点需要进行交换 ，，因为构建大顶堆，父节点一定要大于子节点
                int temp = arr[parent];
                arr[parent] = arr[Child];
                arr[Child] = temp;
                parent = Child;
                Child = 2 * Child + 1;
           }else {
               break;
           }
        }
    }
}

四、基数排序

import java.util.Arrays;

public class JiShuSort {
    public static void main(String[] args) {
        int[] arr = new int[]{587,956,12,47,30,20,15,11,21,31,57,91,35,120};
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static void sort(int[] arr){
        int[][] bucket = new int[10][arr.length];
        int[] bucketCounts = new int[10];

        //找到最大值
        int max = arr[0];
        for (int f = 0;f<arr.length;f++){
            if(arr[f]>max){
                max = arr[f];
            }
        }

        int maxLength = (max+"").length();

        int n = 1;
        for (int h = 0;h<maxLength;h++) {
            //按照个位的值进行排序
            for (int i = 0; i < arr.length; i++) {
                int element = arr[i] / n % 10; //计算出个位数的值
                int count = bucketCounts[element];
                bucket[element][count] = arr[i];
                bucketCounts[element] = bucketCounts[element] + 1;
            }
            //数据的取出
            int index = 0;
            for (int k = 0; k < bucketCounts.length; k++) {
                if (bucketCounts[k] != 0) {
                    for (int l = 0; l < bucketCounts[k]; l++) {
                        arr[index] = bucket[k][l];
                        index++;
                    }
                }
                //清空桶记录
                bucketCounts[k] = 0;
            }

            n = n * 10;
        }
    }
}

五、测试主方法

 public static void main(String[] args) {

        int arr[] = {9, 5, 2, 3, 1, 8, 4, 20, 11};
        //冒泡排序
        // bubbleSort(arr);
        //快速排序
//        quickSort(arr,0,arr.length-1);
//        System.out.println(Arrays.toString(arr));

        //堆排序
/*
        for (int p=arr.length-1;p>=0;p--){
            adjust(arr,p,arr.length);
        }
        for (int i =arr.length-1;i>=0;i--){
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;
            adjust(arr,0,i);
        }
        System.out.println(Arrays.toString(arr));
*/
        //基数排序
        jishu(arr);
        System.out.println(Arrays.toString(arr));
    }