學習筆記【資料結構與算法-第一節：排序】

概述

什麼是資料結構？

資料結構就是把資料元素按照一定的關系組織起來的集合，用來組織和存儲資料

資料結構的分類：

邏輯結構：

• 集合結構
• 線性結構
• 樹形結構
• 圖形結構

實體結構：

• 順序結構
• 鍊式結構

什麼是算法？

根據一定的條件，對一些資料進行計算，得到需要的結果

優秀算法的目标

• 1.花最少的時間完成需求
• 2.占用最少的記憶體空間完成需求

算法分析

算法的時間複雜度分析

事後分析估算方法：如寫計算時間的代碼

事後分析估算方法：

因素：

• 算法采用的政策和方案
• 編譯産生的代碼品質
• 問題的輸入規模（所謂的問題輸入規模就是輸入量的多少）
• 機器執行指令的速度

最重要的是把核心操作的次數和輸入規模關聯起來

• 算法函數中的常數可以忽略不計
• 算法函數中最高次幂的常數因子可以忽略
• 算法函數中最高次幂越小，算法效率越高

算法時間複雜度

大O記法

• 用常數1取代運作時間中的所有加法常數
• 在修改後的運算次數中，隻保留高階項
• 如果最高階項存在，且常數因子不為1，則去除這個項相乘的常數

如：

• 算法一：3次：

  O(1)

• 算法二：n+3：

  O(n)

• 算法三：n^2+2次：

  O(n^2)

常見的大O階

• 線性階（如循環）
• 平方階（如嵌套循環）
• 立方階（如三層嵌套循環）
• 常數階
• 對數階

O(1)<O(logn)<O(n)<O(nlogn)<O(n^2)

算法的空間複雜度分析（略）

以占用記憶體為标準，這裡省略

排序

冒泡排序

public static void sort01(int[] arr){
    for (int i=0;i<arr.length-1;i++){
        for (int j=0;j<arr.length-i-1;j++){
            if (arr[j]>arr[j+1]){
                int temp=arr[j];
                arr[j]=arr[j+1];
                arr[j+1]=temp;
            }
        }
    }
    print(arr);
}
           

時間複雜度：O(n^2)

選擇排序

public static void sort02(int[] arr){
    for (int i=0;i<arr.length-1;i++){
        int min=i;
        for (int j=i+1;j<arr.length;j++){
            if (arr[min]>arr[j]){
                min=j;
            }
        }
        if (min!=i){
            int temp=arr[i];
            arr[i]=arr[min];
            arr[min]=temp;
        }
    }
    print(arr);
}
           

時間複雜度：O(n^2)

插入排序

public static void sort03(int[] arr){
    for (int i=1;i<arr.length;i++){
        for (int j=i;j>0;j--){
            if (arr[j-1]>arr[j]){
                int temp=arr[j];
                arr[j]=arr[j-1];
                arr[j-1]=temp;
            }else {
                break;
            }
        }
    }
    print(arr);
}
           

時間複雜度：O(n^2)

希爾排序

public static void sort04(int[] arr){
    int h=1;
    while (h<arr.length/2){
        h=h*2+1;
    }
    while(h>=1){
        for(int i=h;i<arr.length;i++){
            for (int j=i;j>=h;j-=h){
                if (arr[j-h]>arr[j]){
                    int temp=arr[j];
                    arr[j]=arr[j-h];
                    arr[j-h]=temp;
                }else {
                    break;
                }
            }
        }
        h=h/2;
    }
    print(arr);
}
           

歸并排序

public class test {
    public static void sort(int[] arr){
        int l=0;
        int r=arr.length-1;
        mergeSort(arr,l,r);
        for (int i=0;i<arr.length;i++){
            System.out.print(arr[i]+"\t");
        }
    }


    private static void mergeSort(int[] arr,int l,int r){
        if (l>=r){
            return;
        }

        int mid=(l+r)>>>1;
        mergeSort(arr,l,mid);
        mergeSort(arr,mid+1,r);
        merge(arr,l,mid,r);
    }

    private static void merge(int[] arr,int l,int mid,int r){
        int s1=l;
        int s2=mid+1;

        int[] tempArr=new int[r-l+1];
        int i=0;

        while (s1<=mid&&s2<=r){
            if (arr[s1]<=arr[s2]){
                tempArr[i++]=arr[s1++];
            }else {
                tempArr[i++]=arr[s2++];
            }
        }

        while (s1<=mid){
            tempArr[i++]=arr[s1++];
        }
        while (s2<=r){
            tempArr[i++]=arr[s2++];
        }

        for (int j=0;j<tempArr.length;j++){
            arr[l+j]=tempArr[j];
        }
    }
}
           

時間複雜度：O(nlogn)

快速排序

public class Quick02 {
    public static void sort(int[] arr){
        int left=0;
        int right=arr.length-1;
        partitionSort(arr,left,right);

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

    private static void partitionSort(int[] arr,int left,int right){
        if (right<=left){
            return;
        }

        int partition=partition(arr,left,right);

        partitionSort(arr,left,partition-1);
        partitionSort(arr,partition+1,right);
    }

    private static int partition(int[] arr,int left,int right){
        int s1=left;
        int s2=right+1;

        while (true){
            while (arr[left]<arr[--s2]){
                if (s2<=left){
                    break;
                }
            }
            while (arr[left]>arr[++s1]){
                if (s1>=right){
                    break;
                }
            }
            if (s1>=s2){
                break;
            }else {
                int temp=arr[s1];
                arr[s1]=arr[s2];
                arr[s2]=temp;
            }
        }

        int temp=arr[s2];
        arr[s2]=arr[left];
        arr[left]=temp;

        return s2;
    }
}
           

時間複雜度：

最優：O(nlogn)

最差：O(n^2)

平均：O(nlogn)

排序的穩定性：

數組arr中由若幹個元素，其中A元素和B元素相等且在它前面，如果使用了某種排序算法後，A元素仍然在B元素前面，則說該算法是穩定的

常見算法的穩定性：

• 冒泡排序 ：穩定的
• 選擇排序 ：不穩定的
• 插入排序 ：穩定的
• 希爾排序 ：不穩定的
• 歸并排序 ：穩定的
• 快速排序 ：不穩定的