腳本之家服務器常用軟件

快捷導航

淺談Java常見的排序算法

更新時間：2021年06月22日 09:00:20 作者：Stars-Nine

今天給大家?guī)淼氖顷P于Java的相關知識,文章圍繞著Java常見的排序算法展開,文中有非常詳細的介紹及代碼示例,需要的朋友可以參考下

一、直接插入排序

基本思想：
將一個記錄插入到已排序的有序表中，使插入后的表仍然有序

對初始關鍵字{49 38 65 97 76 13 27 49}進行直接插入排序

在這里插入圖片描述

package Sort;
//插入排序
public class InsertSort {
    public static void main(String[] args) {
        int [] arr={49,38,65,97,76,13,27,49};
        sort(arr);
       print(arr);
    }

    private static void sort(int [] arr) {

        for (int i = 1; i < arr.length; i++) {
           for(int j=i;j>0;j--){
               if(arr[j]<arr[j-1]){
                  swap(arr,j,j-1);
               }
           }
        }
    }
    private static void swap(int [] arr,int i,int j){
        int temp=0;
        temp=arr[i];
        arr[i]=arr[j];
        arr[j]=temp;
    }
    private static void print(int [] arr) {
        for (int i = 0; i <arr.length ; i++) {
            System.out.print(arr[i]+" ");
        }
    }
}

13 27 38 49 49 65 76 97
Process finished with exit code 0

二、希爾排序

希爾排序又稱“縮小增量排序”（Diminishing Increment Sort)）屬于插入排序類。
基本思想：
先將整個待排序的記錄分割成若干子序列分別進行“直接插入排序”，待整個序列中的記錄”基本有序“時，再對全體記錄進行一次直接插入排序。

在這里插入圖片描述

package Sort;
//希爾排序是插入排序的改良
public class ShellSort {
    public static void main(String[] args) {
        int [] arr={16,25,12,30,47,11,23,36,9,18,31};
        sort(arr);
        print(arr);
    }
    private static void sort(int [] arr) {
        //gap設置優(yōu)化
        int h=1;
        while(h<arr.length/3){
            h=h*3+1;
        }
       for(int gap=h;gap>0;gap=(gap-1)/3) {//gap:希爾排序的間距
           for (int i = gap; i < arr.length; i++) {
               for (int j = i; j >gap-1; j-=gap) {
                   if (arr[j] < arr[j - gap]) {
                       swap(arr, j, j - gap);
                   }
               }
           }
       }
    }
    private static void swap(int [] arr,int i,int j){
        int temp=0;
        temp=arr[i];
        arr[i]=arr[j];
        arr[j]=temp;
    }
    private static void print(int [] arr) {
        for (int i = 0; i <arr.length ; i++) {
            System.out.print(arr[i]+" ");
        }
    }
}

9 11 12 16 18 23 25 30 31 36 47
Process finished with exit code 0

三、冒泡排序

冒泡排序

四、快速排序

對冒泡排序的一種改進
基本思想：
通過一趟排序將待排序記錄分割成獨立的兩部分，其中一部分的關鍵字均比另一部分的關鍵字小，則可分別對這兩部分記錄繼續(xù)分別進行排序，以達到整個序列有序。

在這里插入圖片描述

package Sort;

import java.util.Arrays;

//快速排序
public class QuickSort {
    public static void main(String[] args) {
        int[] arr={49,38,65,97,76,13,27,49};
        sort(arr,0,arr.length-1);
        System.out.println(Arrays.toString(arr));
    }

    private static void sort(int [] arr,int start,int end) {
       if(start<end){
           //把數(shù)組的第0個數(shù)作為標準數(shù)
           int stared=arr[start];
           //記錄要排序的下標
           int low=start;
           int height=end;
           //循環(huán)找出比標準數(shù)大和比標準數(shù)小的數(shù)
           while(low<height){
               //右邊數(shù)字比標準數(shù)大
               while(low<height&&stared<=arr[height]){
                   height--;
               }
               //用右邊的數(shù)字替換左邊的數(shù)字
               arr[low]=arr[height];
               //左邊數(shù)字比標準數(shù)小
               while(low<height&&stared>=arr[low]){
                   low++;
               }
               //用左邊的數(shù)字替換右邊的數(shù)字
               arr[height]=arr[low];
           }
           arr[low]=stared;
           sort(arr,start,low);
           sort(arr,low+1,height);
       }

    }
    }

[13, 27, 38, 49, 76, 97, 65, 49]
Process finished with exit code 0

五、選擇排序(Selection Sort)

選擇排序

六、堆排序

  堆排序是利用堆這種數(shù)據(jù)結構而設計的一種排序算法，堆排序是一種選擇排序，它的最壞，最好，平均時間復雜度均為O(nlogn)，它也是不穩(wěn)定排序。

堆是具有以下性質的完全二叉樹：每個結點的值都大于或等于其左右孩子結點的值，稱為大頂堆, 注意 : 沒有要求結點的左孩子的值和右孩子的值的大小關系。
每個結點的值都小于或等于其左右孩子結點的值，稱為小頂堆

大頂堆舉例說明：

在這里插入圖片描述

我們對堆中的結點按層進行編號，映射到數(shù)組中就是下面這個樣子:

在這里插入圖片描述

大頂堆特點：arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2] // i 對應第幾個節(jié)點，i從0開始編號

小頂堆舉例說明

在這里插入圖片描述

小頂堆：arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2] // i 對應第幾個節(jié)點，i從0開始編號

一般升序采用大頂堆，降序采用小頂堆
堆排序基本思想

堆排序的基本思想是：

將待排序序列構造成一個大頂堆
此時，整個序列的最大值就是堆頂?shù)母?jié)點。
將其與末尾元素進行交換，此時末尾就為最大值。
然后將剩余n-1個元素重新構造成一個堆，這樣會得到n個元素的次小值。如此反復執(zhí)行，便能得到一個有序序列了。

代碼示例

package Sort;
import java.util.Arrays;
/**構造大頂堆
 * 1、原順序二叉樹     非葉子節(jié)點在數(shù)組中的索引i=1時；arr[i]=6    i=0時                           
 *     4                   i的右節(jié)點值比它大，交換得 ：              9   
 *    /\                         4                                  /\
 *   6  8                       /\                                 6  8
 *  /\                         9  8                               /\
 * 5 9                        /\                                 5 4
 *                           5 6
 */


public class HeapSort {
    public static void main(String[] args) {
        int [] arr={4,6,8,5,9};
        heapSort(arr);
    }
    //編寫一個堆排序的方法
    public static void heapSort(int[] arr){
        int temp=0;
        for(int i=arr.length/2-1;i>=0;i--){
            adjustHeap(arr,i,arr.length);
        }
        //將堆頂元素與末尾元素進行交換，此時末尾就為最大值，將最大值全放在數(shù)組最后
        //重新調(diào)整結構，使其滿足堆定義，繼續(xù)交換堆頂元素與當前末尾元素，反復執(zhí)行調(diào)整交換步驟，使整個序列達到有序
        for(int j=arr.length-1;j>0;j--) {
            //交換
            temp = arr[j];
            arr[j] = arr[0];
            arr[0] = temp;
            adjustHeap(arr, 0, j);
        }
        System.out.println("數(shù)組"+Arrays.toString(arr));

    }
    //將數(shù)組調(diào)整為一個大頂堆
    /**
     * 功能：完成將以i對應的非葉子節(jié)點的樹調(diào)整成大頂堆
     * 舉例：int[]arr={4,6,8,5,9};=>i=1=>adjustHeap=>得到{4，9，8，5，6}
     * 如果再次調(diào)整adjustHeap傳入i=0,{4，9，8，5，6}=>得到{9，6，8，5，4}
     * @param arr  表示要調(diào)整的數(shù)組
     * @param i   表示非葉子節(jié)點在數(shù)組中的索引
     * @param length  表示對多少個元素進行調(diào)整，length在逐漸減少
     */
    public static void adjustHeap(int[]arr,int i,int length){
         int temp=arr[i];//先取出當前元素的值，保存在臨時變量中
        //開始調(diào)整
        //k=i*2+1;k是i節(jié)點的左子節(jié)點
        for(int k=i*2+1;k<length;k=k*2+1){
              if(k+1<length&&arr[k]<arr[k+1]){//說明左子節(jié)點的值小于右子節(jié)點的值
                 k++;//k指向右子節(jié)點
              }
              if(arr[k]>temp){//如果子節(jié)點大于父節(jié)點
                  arr[i]=arr[k];//把較大的值賦給當前節(jié)點
                  i=k;//!!!i指向k，繼續(xù)循環(huán)比較
              }else{
                  break;
              }
        }
        //當for循環(huán)結束后，已經(jīng)將以i為父結點的最大值放在了堆頂上（局部）
          arr[i]=temp;//將temp的值放在調(diào)整后的位置
    }
}

堆排序結果：
數(shù)組[4, 5, 6, 8, 9]

七、歸并排序

定義：

又一類不同的排序方法，將兩個或兩個以上的有序表合并成一個新的有序表。
需要輔助空間：O(n)
整個歸并需要 [log2n] 趟
時間復雜度：O(nlog2n)

缺點：歸并排序占用附加存儲較多, 需要另外一個與原待排序對象數(shù)組同樣大小的輔助數(shù)組。

優(yōu)點：歸并排序是一個穩(wěn)定的排序方法

思路可以推廣到“多路歸并”
常用于外部排序

在這里插入圖片描述

package Sort;
//歸并排序
public class MergeSort {
    public static void main(String[] args) {
        int [] arr={4,5,7,8,1,2,3,6};
        sort(arr);
        print(arr);
    }

    private static void sort(int [] arr) {
        int mid=arr.length/2;
        int[]temp=new int[arr.length];
        int i=0;//標記左邊數(shù)組
        int j=mid+1;//標記右邊數(shù)組起始點
        int k=0;
        while(i<=mid&&j<arr.length){
            if(arr[i]<=arr[j]){
               temp[k]=arr[i];
               i++;
               k++;
            }else{
                temp[k]=arr[j];
                j++;
                k++;
            }
        }
        while(i<=mid){temp[k++]=arr[i++];}//將左邊剩余的，復制到數(shù)組
        while(j<arr.length){temp[k++]=arr[j++];}//將右邊剩余的，復制到數(shù)組
    }


    private static void print(int [] arr) {
        for (int i = 0; i <arr.length ; i++) {
            System.out.print(arr[i]+" ");
        }
    }
}