算法：冒泡、选择、插入、快速

冒泡排序

---

它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。以此类推，直到所有元素均排序完毕。

• 时间复杂度：O(n²)
• 空间复杂度：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;
}

选择排序

---

首先在未排序序列中找到最小（大）元素，存放到起始位置，然后再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

• 时间复杂度：O(n²)
• 空间复杂度：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;
}

插入排序

---

它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

• 时间复杂度：O(n²)
• 空间复杂度：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;
}

快速排序

---

通过一趟排序将待排数据录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

1. 算法步骤：

• 从数列中挑出一个元素，称为 “基准”（pivot）
• 将所有比基准值小的元素摆放在基准值前面，所有比基准值大的元素摆在基准值的后面（相同的数可以到任一边）
• 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序

2. 复杂度：

• 时间复杂度：O(nlogⁿ)
• 空间复杂度：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) {
        //从后向前找到比基准数小的位置
        while (left < right && arr[right] >= pivot) {
            right--;
        }
        //从前向后找到比基准数大的位置
        while (left < right && arr[left] <= pivot) {
            left++;
        }
        //如果不是同一个位置则交换两个数
        if (left < right) {
            int temp = arr[left];
            arr[left] = arr[right];
            arr[right] = temp;
        }
    }
    //调整基准数的位置
    arr[start] = arr[left];
    arr[left] = pivot;
    quickSort(arr, 0, left - 1);
    quickSort(arr, left + 1, end);
}