左神算法整理筆記01

1.左神算法基礎篇

時間複雜度

時間複雜度是衡量算法好壞的重要名額之一。時間複雜度反映的是不确定性樣本量的增長對于算法操作所需時間的影響程度，與算法操作是否涉及到樣本量以及涉及了幾次直接相關，如周遊數組時時間複雜度為數組長度n（對應時間複雜度為O(n)），而對資料的元操作（如加減乘除與或非等）、邏輯操作（如if判斷）等都屬于常數時間内的操作（對應時間複雜度O(1)）。

三種排序算法

冒泡排序

public void bubbleSort(int[] array) {
    if (array == null || array.length < 2) return;
    for (int end = array.length-1; end > 0; end--) {
        for (int i = 1; i < end; i++) {
            if (array[i] > array[i+1]) {
                swap(array, i, i+1);
            }
        }
    }
}
           

插入排序

public void insertSort(int[] array) {
    if (array == null || array.length < 2) return;
    for (int i = 1; i < array.length; i++) {
        for (int j = i-1; j >=0 && array[j] > array[j+1];j--) {
            swap(array, j, j+1);
        }
    }
}
           

對連結清單進行插入排序-leetcode:147

class Solution {
    public ListNode insertionSortList(ListNode head) {
        if (head == null) return head;
        
        ListNode dummy = new ListNode(0);
        dummy.next = head;

        ListNode lastSort = head;
        ListNode curr = head.next;
        while (curr != null) {
            // 如果是有序的
            if (lastSort.val <= curr.val) {
                lastSort = lastSort.next;
            } else {
                // 如果是無序的
                ListNode pre = dummy;
                while (pre.next.val < curr.val) {
                    pre = pre.next;
                }
                lastSort.next = curr.next;
                curr.next = pre.next;
                pre.next = curr;
            }
            curr = lastSort.next;
        }
        return dummy.next;
    }
}
           

選擇排序&&對數器

public static void selectSort(int[] array) {
    if (array == null || array.length < 2) return;
    for (int i = 0; i < array.length; i++) {
        int minIndex = i;
        for (int j = i+1; j < array.length; j++) {
            minIndex = array[j] < array[minIndex] ? j : minIndex;
        }
        swap(array, minIndex, i);
    }
}

//========對數器：用于驗證算法的正确性==========

// for test，生成長度随機的數組
public static int[] generayrRandomArray(int size, int value) {
    int[] arr = new int[(int)((size+1)*Math.random())];
    for (int i = 0; i < arr.length; i++) {
        arr[i] = (int) ((value+1)*Math.random())-(int)(value*Math.random());
    }
    return arr;
}
// 大樣本測試
public static void main(String[] args) {
    int testTime = 5000000;
    int size = 10;
    int value = 100;
    for (int i = 0; i < testTime; i++) {
        int[] arr1 = generayrRandomArray(size,value);
        int[] arr2 = copyArray(arr1);
        int[] arr3 = copyArray(arr1);
        selectSort(arr1);
        rightMethod(arr2);
        if (!isEqual(arr1,arr2)) {
            printArray(arr3);
            break;
        }
    }
    System.out.println("通過測試");
}
           

對數器的作用

• 驗證算法的正确性，将錯誤的案例輸出，用于定位問題
• 驗證貪婪算法