Java基礎之八大排序算法

目錄

前言

關(guān)系

復雜度

一、直接插入排序

基本思想：

將新的數據插入已經(jīng)排好的數據列中。

將第一個(gè)和第二個(gè)數排序，構成有序數列

然后將第三個(gè)數插進(jìn)去，構成新的有序數列，后面的數重復這個(gè)步驟

算法描述

1、設定插入的次數，即是循環(huán)次數,for(int i=1;i<length;i++)，1個(gè)數的那次不用插入。

2、設定插入的數和得到的已經(jīng)排好的序列的最后一個(gè)數,insertNum和j=i-1。

3、從最后一個(gè)數向前開(kāi)始循環(huán)，如果插入數小于當前數就將當前數向前移動(dòng)一位

4、將當前位置放置到空的位置，即j+1。

代碼實(shí)現

public class Demo01 {
    public static void main(String[] args) {
        int [] data = {2,1,41,21,14,33,5};
        int temp; //要插入的數
        for (int i = 1; i < data.length; i++) {  // 插入的次數
            temp = data[i]; //要插入的數
            int j  = i-1;   //已經(jīng)排好的數字
            while (j>=0&&data[j]>temp){ //判斷后一個(gè)數，將大于要插入的數向后移動(dòng)一格
                data[j+1] =data[j]; //元素移動(dòng)一格
                j--;
            }
            data[j+1]=temp;     //將要插入的數字放入1插入的位置
        }
        for (int i = 0; i < data.length; i++) {
            System.out.print(data[i]+" ");
        }
    }
}

二、希爾排序

基本思想：

對于直接插入的數，數據量巨大：

1.將數的個(gè)數設置為n，取奇數k = n/2,將下標的差值k的數分為一組，構成有序數列。

2.再取k = k/2,將下標差值為k的數構成一組，構成有序數列，

3.重復第二步，直到k=1執行簡(jiǎn)單的插入排序

算法描述

1.首先確定分組的數字

2.然后對組中的數字進(jìn)行插入排序

3.然后將length/2，重復1,2步驟。直到length=0為止。

代碼實(shí)現

public class Demo02 {
    public static void main(String[] args) {
        int [] data = {2,5,14,34,12,4,87,21,1,6};
        int d = data.length;
        while (d!=0){
            d = d/2;
            for (int x = 0; x < d; x++) {
                for (int i = d+x; i < data.length; i += d) {
                    int j = i - d;      //j為有序序列最后一位的位數
                    int temp = data[i]; //要插入的元素
                    for (;j>=0&&temp < data[j]; j -=d){
                        data[j+d]=data[j]; //向后移動(dòng)d位
                    }
                    data[j+d] = temp;
                }
            }
        }
        for (int i = 0; i < data.length; i++) {
            System.out.print(data[i]+" ");
        }

    }
}

三、簡(jiǎn)單選擇排序

基本思想：

常用于取序列數中最大最小的幾棵樹(shù)

(如果每次比較都交換，那么就是交換排序；如果每次比較完一個(gè)循環(huán)再交換，就是簡(jiǎn)單選擇排序。)

1.遍歷整個(gè)序列，將最小的數放在最前面

2.遍歷剩余的序列，將最小的數字放在最前面

3.重復步驟2，知道剩余最后一個(gè)數字。

算法描述

1.首先確定循環(huán)次數，并且記住當前的位置和當前數字

2.將當前位置后面的所有數字和當前位置的數字作比較，小數賦值給key,并記住小值的位置

3.比對完成后，將最小的值和第一個(gè)數的值交換

4.重復2,3步驟

代碼實(shí)現

public class Demo03 {
    public static void main(String[] args) {
        int[] data = {2,6,123,56,23,1};
        for (int i = 0; i < data.length; i++) { //循環(huán)次數
            int key = data[i];//最小值
            int position=i;  //當前位置
            for (int j = i+1; j < data.length; j++) {//選出最小值
                if(data[j]<key){
                    key = data[j];
                    position =j;
                }
            }
            data[position] = data[i];//交換位置
            data[i] = key;
        }
        for (int i = 0; i < data.length; i++) {
            System.out.print(data[i]+" ");
        }
    }
}

四、堆排序

基本思想：

對簡(jiǎn)單選擇排序的優(yōu)化

1.將序列構建為大頂堆

2.將根節點(diǎn)與最后一個(gè)節點(diǎn)兌換，然后斷開(kāi)最后一個(gè)節點(diǎn)

3.重復一二步驟，直到所有節點(diǎn)斷開(kāi)

代碼實(shí)現：

public class Demo04 {
    public static void main(String[] args) {
        int []data = {21,13,3,2,1,23,11,25};
        heapsort(data);
    }
    public static void heapsort(int a[]){
        System.out.println("開(kāi)始排序");
        int arrayLength = a.length;
        for (int i = 0; i < arrayLength-1; i++) {
            buildMaxHeap(a,arrayLength-1-i);
            swap(a,0,arrayLength-1-i);
            System.out.println(Arrays.toString(a));
        }
    }
    private static void swap(int[] data, int i, int j) {
        // TODO Auto-generated method stub
        int tmp=data[i];
        data[i]=data[j];
        data[j]=tmp;
    }

    public static void buildMaxHeap(int[] data,int lastIndex){
        //從lastIndex處節點(diǎn)（最后一個(gè)節點(diǎn)）的父節點(diǎn)開(kāi)始
        for (int i = (lastIndex-1)/2;i>=0;i--){
            //k 保存當前判斷的節點(diǎn)
            int k = i;
//            如果當前k節點(diǎn)存在子節點(diǎn)
            while (k*2+1<=lastIndex){
//                k節點(diǎn)的左子節點(diǎn)的索引
                int biggerIndex = 2*k+1;
//                如果biggerIndex小于lastIndex，即biggerIndex+1代表的k節點(diǎn)的右子節點(diǎn)存在
                if (biggerIndex<lastIndex){
//                    如果右子節點(diǎn)的值較大
                    if(data[biggerIndex]<data[biggerIndex+1]){
                        biggerIndex++;
                    }
                }
//                如果k節點(diǎn)的值小于其較大的子節點(diǎn)的值
                if (data[k]<data[biggerIndex]){
                    swap(data,k,biggerIndex);
                    k = biggerIndex;
                }else {
                    break;
                }
            }
        }
    }
}

五、冒泡排序

基本思想

1.將序列中所有的元素兩兩比較

2.將剩余序列的所有元素兩兩比較，將最大的放到最后面

3.重復第二步，知道最后一個(gè)數

算法描述

1.設置循環(huán)次數

2.設置比較的位數和結束的位數

3.兩兩比較，將最小的放到前面去

4.重復2，3步驟，直到循環(huán)結束

代碼實(shí)現

public class Demo05 {
    public static void main(String[] args) {
        int[] data={1,34,31,2,65,87,255,8,33,64,3};
       int temp;
        for (int i = 0; i < data.length; i++) {
            for (int j = 0; j < data.length-i-1; j++) {
                if(data[j] > data[j+1]){
                    temp = data[j];
                    data[j] = data[j+1];
                    data[j+1] = temp;
                }
            }
        }
        for (int i = 0; i < data.length; i++) {
            System.out.print(data[i]+" ");
        }
    }
}

六、快速排序

基本思想

要求時(shí)間最快

1.選擇第一個(gè)數作為P,小于P的放左邊，大于p的放右邊

2.遞歸將p的左邊和右邊的數按照步驟一進(jìn)行，直到不能遞歸

代碼實(shí)現

public class Demo06 {
    public static void main(String[] args) {
        int[] data = {5,33,22,11,23,2,32,12,21,10};
        quickSort(data,0,data.length-1);
        sorts(data);
    }
    public static void quickSort(int[] data,int L,int R){
        if(L < R){
//            先選擇比較的基數
            int base = data[L];
            int temp;
            int left=L,right=R;
            do{
                while ((data[left] < base) && (left < R)){
                    left++;
                }
                while ((data[right]) > base &&(right > L)){
                    right--;
                }
                if (left <= right){
                    temp = data[left];
                    data[left] = data[right];
                    data[right] = temp;
                    left++;
                    right--;
                }
            }while (left <= right);
            if (L < right){
                quickSort(data,L,right);
            }
            if (R > left){
                quickSort(data,left,R);
            }
        }
    }
    public static void sorts(int[] data){
        for (int i = 0; i < data.length; i++) {
            if (i == data.length-1){
                System.out.print(data[i]);
            }else {
                System.out.print(data[i]+",");
            }

        }
    }
}

七、歸并排序

基本思想

速度僅次于快排，內存少的時(shí)候使用，可以進(jìn)行并行運算的時(shí)候使用。

1.選擇相鄰兩個(gè)數組成的有序序列

2.選擇相鄰的兩個(gè)有序序列組成的一個(gè)有序序列

3.重復步驟二，直到組成一個(gè)有序序列

public class Demo0701 {
    public static void main(String[] args) {
        int[] arr = {12,34,3,2,13,43,34,25,83};
        mSort(arr, 0, arr.length-1);
        sorts(arr);
    }

    /**
     * 遞歸分治
     * @param arr 待排數組
     * @param left 左指針
     * @param right 右指針
     */
    public static void mSort(int[] arr, int left, int right) {
        if(left >= right)
            return ;
        int mid = (left + right) / 2;

        mSort(arr, left, mid); //遞歸排序左邊
        mSort(arr, mid+1, right); //遞歸排序右邊
        merge(arr, left, mid, right); //合并
    }

    /**
     * 合并兩個(gè)有序數組
     * @param arr 待合并數組
     * @param left 左指針
     * @param mid 中間指針
     * @param right 右指針
     */
    public static void merge(int[] arr, int left, int mid, int right) {
        //[left, mid] [mid+1, right]
        int[] temp = new int[right - left + 1]; //中間數組
        int i = left;
        int j = mid + 1;
        int k = 0;

        //執行完這個(gè)while循環(huán)，相當于將兩個(gè)子序列合并后重新進(jìn)行了一次排序并將排序結果記錄在了臨時(shí)數組temp[k]中。
        // while走完后k的值等于數組的長(cháng)度，i的值此時(shí)大于mid，j的值大于right
        while(i <= mid && j <= right) {
            if(arr[i] <= arr[j]) {
                temp[k++] = arr[i++];
            }
            else {
                temp[k++] = arr[j++];
            }
        }

        while(i <= mid) {
            temp[k++] = arr[i++];
        }

        while(j <= right) {
            temp[k++] = arr[j++];
        }

        //將有序的臨時(shí)數組temp[k]一個(gè)一個(gè)賦值到原數組arr[]中
        for(int p=0; p<temp.length; p++) {
            arr[left + p] = temp[p];
        }
    }
    public static void sorts(int[] data){
        for (int i = 0; i < data.length; i++) {
            if (i == data.length-1){
                System.out.print(data[i]);
            }else {
                System.out.print(data[i]+",");
            }
        }
    }
}

八、基數排序(桶排序)

基本思想

用于大量數，很長(cháng)數進(jìn)行排列

1.將所有的數的個(gè)數取出來(lái)，按照個(gè)位數排序，構成序列

2.將新構成的所有數的十位數取出，按照十位數進(jìn)行排序

代碼實(shí)現

public class Demo08 {
    public static void main(String[] args) {
        int[] data = {12,34,3,2,13,43,34,25,83};
        if(data == null && data.length == 0)
            return ;

        int maxBit = getMaxBit(data);


        for(int i=1; i<=maxBit; i++) {

            List<List<Integer>> buf = distribute(data, i); //分配
            collecte(data, buf); //收集
        }
        new PrintSort(data);
    }

    /**
     * 分配
     * @param arr 待分配數組
     * @param iBit 要分配第幾位
     * @return
     */
    public static List<List<Integer>> distribute(int[] arr, int iBit) {
        List<List<Integer>> buf = new ArrayList<List<Integer>>();
        for(int j=0; j<10; j++) {
            buf.add(new LinkedList<Integer>());
        }
        for(int i=0; i<arr.length; i++) {
            buf.get(getNBit(arr[i], iBit)).add(arr[i]);
        }
        return buf;
    }

    /**
     * 收集
     * @param arr 把分配的數據收集到arr中
     * @param buf
     */
    public static void collecte(int[] arr, List<List<Integer>> buf) {
        int k = 0;
        for(List<Integer> bucket : buf) {
            for(int ele : bucket) {
                arr[k++] = ele;
            }
        }


    }

    /**
     * 獲取最大位數
     * @param
     * @return
     */
    public static int getMaxBit(int[] arr) {
        int max = Integer.MIN_VALUE;
        for(int ele : arr) {
            int len = (ele+"").length();
            if(len > max)
                max = len;
        }
        return max;
    }

    /**
     * 獲取x的第n位，如果沒(méi)有則為0.
     * @param x
     * @param n
     * @return
     */
    public static int getNBit(int x, int n) {
        String sx = x + "";
        if(sx.length() < n)
            return 0;
        else
            return sx.charAt(sx.length()-n) - '0';
    }
}

到此這篇關(guān)于Java基礎之八大排序算法的文章就介紹到這了,更多相關(guān)java八大排序算法內容請搜索腳本之家以前的文章或繼續瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！