冒泡排序

它重復(fù)地走訪過要排序的數(shù)列，一次比較兩個元素，如果它們的順序錯誤就把它們交換過來。以此類推，直到所有元素均排序完畢。

• 時間復(fù)雜度：O(n²)
• 空間復(fù)雜度：O(1)

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

選擇排序

首先在未排序序列中找到最小（大）元素，存放到起始位置，然后再從剩余未排序元素中繼續(xù)尋找最?。ù螅┰兀缓蠓诺揭雅判蛐蛄械哪┪?。以此類推，直到所有元素均排序完畢。

• 時間復(fù)雜度：O(n²)
• 空間復(fù)雜度：O(1)

public int[] selectionSort(int[] arr) {
    for (int i = 0; i < arr.length; i++) {
        int minIndex = i;
        for (int j = i + 1; j < arr.length; j++) {
            if (arr[minIndex] > arr[j]) {
                minIndex = j;
            }
        }
        if (minIndex != i) {
            int temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
    }
    return arr;
}

插入排序

它的工作原理是通過構(gòu)建有序序列，對于未排序數(shù)據(jù)，在已排序序列中從后向前掃描，找到相應(yīng)位置并插入。

• 時間復(fù)雜度：O(n²)
• 空間復(fù)雜度：O(1)

public int[] insertionSort(int[] arr) {
    for (int i = 1; i < arr.length; i++) {
        int preIndex = i - 1;
        int current = arr[i];
        while (preIndex >= 0 && arr[preIndex] > current) {
            arr[preIndex + 1] = arr[preIndex];
            preIndex--;
        }
        arr[preIndex + 1] = current;
    }
    return arr;
}

快速排序

通過一趟排序?qū)⒋艛?shù)據(jù)錄分隔成獨立的兩部分，其中一部分記錄的關(guān)鍵字均比另一部分的關(guān)鍵字小，則可分別對這兩部分記錄繼續(xù)進(jìn)行排序，以達(dá)到整個序列有序。

1. 算法步驟：

• 從數(shù)列中挑出一個元素，稱為 “基準(zhǔn)”（pivot）
• 將所有比基準(zhǔn)值小的元素擺放在基準(zhǔn)值前面，所有比基準(zhǔn)值大的元素擺在基準(zhǔn)值的后面（相同的數(shù)可以到任一邊）
• 遞歸地（recursive）把小于基準(zhǔn)值元素的子數(shù)列和大于基準(zhǔn)值元素的子數(shù)列排序

2. 復(fù)雜度：

• 時間復(fù)雜度：O(nlogⁿ)
• 空間復(fù)雜度：O(logⁿ)

public void quickSort(int[] arr, int start, int end) {
    //遞歸出口
    if (start > end) return;
    int left = start;
    int right = end;
    int pivot = arr[left];
    while (left != right) {
        //從后向前找到比基準(zhǔn)數(shù)小的位置
        while (left < right && arr[right] >= pivot) {
            right--;
        }
        //從前向后找到比基準(zhǔn)數(shù)大的位置
        while (left < right && arr[left] <= pivot) {
            left++;
        }
        //如果不是同一個位置則交換兩個數(shù)
        if (left < right) {
            int temp = arr[left];
            arr[left] = arr[right];
            arr[right] = temp;
        }
    }
    //調(diào)整基準(zhǔn)數(shù)的位置
    arr[start] = arr[left];
    arr[left] = pivot;
    quickSort(arr, 0, left - 1);
    quickSort(arr, left + 1, end);
}