---

经典排序算法：深入理解与 Python/Java 实现

排序算法是计算机科学中最基础且重要的算法之一。无论是数据库索引、搜索引擎还是机器学习，排序都扮演着至关重要的角色。本文将深入探讨几种经典的排序算法，包括它们的工作原理、时间复杂度、空间复杂度、稳定性以及适用场景，并分别提供 Python 和 Java 两种语言的实现代码。

目录

1. 冒泡排序 (Bubble Sort)
2. 选择排序 (Selection Sort)
3. 插入排序 (Insertion Sort)
4. 希尔排序 (Shell Sort)
5. 归并排序 (Merge Sort)
6. 快速排序 (Quick Sort)
7. 堆排序 (Heap Sort)
8. 计数排序 (Counting Sort)
9. 桶排序 (Bucket Sort)
10. 基数排序 (Radix Sort)
11. 总结与比较

1. 冒泡排序 (Bubble Sort)

原理：

冒泡排序是一种简单的比较排序算法。它重复地遍历要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。遍历数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

步骤：

1. 比较相邻的元素。如果第一个比第二个大，就交换它们两个。
2. 对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
3. 针对所有的元素重复以上的步骤，除了最后一个。
4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

时间复杂度：

• 最佳情况：O(n) (当输入数组已经排序好时)
• 平均情况：O(n^2)
• 最坏情况：O(n^2)

空间复杂度： O(1) (原地排序)

稳定性： 稳定 (相同元素的相对位置不会改变)

Python 实现：

python
def bubble_sort(arr):
n = len(arr)
for i in range(n):
# 提前退出标志位
swapped = False
# 每次遍历的范围逐渐缩小
for j in range(0, n - i - 1):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
swapped = True
# 如果没有发生交换，说明已经排序完成
if not swapped:
break
return arr

Java 实现：

“`java
public class BubbleSort {
public static void bubbleSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n – 1; i++) {
boolean swapped = false;
for (int j = 0; j < n – i – 1; j++) {
if (arr[j] > arr[j + 1]) {
// 交换 arr[j] 和 arr[j+1]
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = true;
}
}
// 如果没有发生交换，说明已经排序完成
if (!swapped) {
break;
}
}
}

public static void main(String[] args) {
    int[] arr = {64, 34, 25, 12, 22, 11, 90};
    bubbleSort(arr);
    System.out.println("Sorted array: " + Arrays.toString(arr));
}

}
“`

2. 选择排序 (Selection Sort)

原理：

选择排序是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。

步骤：

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

时间复杂度：

• 最佳情况：O(n^2)
• 平均情况：O(n^2)
• 最坏情况：O(n^2)

空间复杂度： O(1) (原地排序)

稳定性： 不稳定 (可能会改变相同元素的相对位置)

Python 实现：

python
def selection_sort(arr):
n = len(arr)
for i in range(n):
min_idx = i
for j in range(i + 1, n):
if arr[j] < arr[min_idx]:
min_idx = j
arr[i], arr[min_idx] = arr[min_idx], arr[i]
return arr

Java 实现：

java
public class SelectionSort {
public static void selectionSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
int min_idx = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[min_idx]) {
min_idx = j;
}
}
// 交换 arr[i] 和 arr[min_idx]
int temp = arr[min_idx];
arr[min_idx] = arr[i];
arr[i] = temp;
}
}
public static void main(String[] args) {
int[] arr = {64, 25, 12, 22, 11};
selectionSort(arr);
System.out.println("Sorted array: " + Arrays.toString(arr));
}
}

3. 插入排序 (Insertion Sort)

原理：

插入排序的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用 in-place 排序（即只需用到 O(1) 的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

步骤：

1. 从第一个元素开始，该元素可以认为已经被排序。
2. 取出下一个元素，在已经排序的元素序列中从后向前扫描。
3. 如果该元素（已排序）大于新元素，将该元素移到下一位置。
4. 重复步骤 3，直到找到已排序的元素小于或者等于新元素的位置。
5. 将新元素插入到该位置后。
6. 重复步骤 2~5。

时间复杂度：

• 最佳情况：O(n) (当输入数组已经排序好时)
• 平均情况：O(n^2)
• 最坏情况：O(n^2)

空间复杂度： O(1) (原地排序)

稳定性： 稳定

Python 实现：

python
def insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i]
j = i - 1
while j >= 0 and key < arr[j]:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
return arr

Java 实现：

“`java
public class InsertionSort {
public static void insertionSort(int[] arr) {
int n = arr.length;
for (int i = 1; i < n; ++i) {
int key = arr[i];
int j = i – 1;

        /* 将大于 key 的元素向后移动 */
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }
}
public static void main(String[] args) {
    int[] arr = { 12, 11, 13, 5, 6 };
    insertionSort(arr);
    System.out.println("Sorted array: " + Arrays.toString(arr));
}

}
“`

4. 希尔排序 (Shell Sort)

原理：

希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。希尔排序是不稳定的排序算法。

希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。

步骤：

1. 选择一个增量序列 t1，t2，…，tk，其中 ti > tj, tk = 1。
2. 按增量序列个数 k，对序列进行 k 趟排序。
3. 每趟排序，根据对应的增量 ti，将待排序列分割成若干长度为 m 的子序列，分别对各子表进行直接插入排序。仅增量因子为 1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

时间复杂度：

• 最佳情况：O(n log n) (取决于增量序列)
• 平均情况：O(n log^2 n) 或 O(n^(3/2)) (取决于增量序列)
• 最坏情况：O(n log^2 n) (取决于增量序列)

空间复杂度： O(1)

稳定性： 不稳定

Python 实现：

python
def shell_sort(arr):
n = len(arr)
gap = n // 2
while gap > 0:
for i in range(gap, n):
temp = arr[i]
j = i
while j >= gap and arr[j - gap] > temp:
arr[j] = arr[j - gap]
j -= gap
arr[j] = temp
gap //= 2
return arr

Java 实现：

java
public class ShellSort {
public static void shellSort(int[] arr) {
int n = arr.length;
for (int gap = n / 2; gap > 0; gap /= 2) {
for (int i = gap; i < n; i++) {
int temp = arr[i];
int j;
for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {
arr[j] = arr[j - gap];
}
arr[j] = temp;
}
}
}
public static void main(String[] args) {
int[] arr = {12, 34, 54, 2, 3};
shellSort(arr);
System.out.println("Sorted array: " + Arrays.toString(arr));
}
}

5. 归并排序 (Merge Sort)

原理：

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。归并排序是一种稳定的排序方法。

步骤：

1. 分解（Divide）： 将待排序的 n 个元素分成各包含 n/2 个元素的子序列。
2. 解决（Conquer）： 对两个子序列递归地进行归并排序。
3. 合并（Combine）： 合并两个已排序的子序列以产生已排序的答案。

时间复杂度：

• 最佳情况：O(n log n)
• 平均情况：O(n log n)
• 最坏情况：O(n log n)

空间复杂度： O(n) (需要额外的空间来存储临时数组)

稳定性： 稳定

Python 实现：

“`python
def merge_sort(arr):
if len(arr) > 1:
mid = len(arr) // 2
left_half = arr[:mid]
right_half = arr[mid:]

    merge_sort(left_half)
    merge_sort(right_half)

    i = j = k = 0
    while i < len(left_half) and j < len(right_half):
        if left_half[i] < right_half[j]:
            arr[k] = left_half[i]
            i += 1
        else:
            arr[k] = right_half[j]
            j += 1
        k += 1

    while i < len(left_half):
        arr[k] = left_half[i]
        i += 1
        k += 1

    while j < len(right_half):
        arr[k] = right_half[j]
        j += 1
        k += 1
return arr

“`

Java 实现：

“`java
public class MergeSort {
public static void mergeSort(int[] arr, int left, int right) {
if (left < right) {
int mid = (left + right) / 2;
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
}
public static void merge(int[] arr, int left, int mid, int right) {
int n1 = mid – left + 1;
int n2 = right – mid;
int[] leftArr = new int[n1];
int[] rightArr = new int[n2];

    for (int i = 0; i < n1; ++i)
        leftArr[i] = arr[left + i];
    for (int j = 0; j < n2; ++j)
        rightArr[j] = arr[mid + 1 + j];

    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) {
        if (leftArr[i] <= rightArr[j]) {
            arr[k] = leftArr[i];
            i++;
        } else {
            arr[k] = rightArr[j];
            j++;
        }
        k++;
    }
    while (i < n1) {
        arr[k] = leftArr[i];
        i++;
        k++;
    }
    while (j < n2) {
        arr[k] = rightArr[j];
        j++;
        k++;
    }
}
public static void main(String[] args) {
    int[] arr = {12, 11, 13, 5, 6, 7};
    mergeSort(arr, 0, arr.length - 1);
    System.out.println("Sorted array: " + Arrays.toString(arr));
}

}
“`

6. 快速排序 (Quick Sort)

原理：

快速排序也是一种分治算法。它选择一个元素作为“基准”（pivot），通过一趟排序将待排记录分隔成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

步骤：

1. 从数列中挑出一个元素，称为 “基准”（pivot）。
2. 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
3. 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

时间复杂度：

• 最佳情况：O(n log n)
• 平均情况：O(n log n)
• 最坏情况：O(n^2) (当输入数组已经排序好或几乎排序好，且基准选择不当时)

空间复杂度： O(log n) ~ O(n) (取决于递归深度)

稳定性： 不稳定

Python 实现：

python
def quick_sort(arr):
if len(arr) <= 1:
return arr
pivot = arr[len(arr) // 2]
left = [x for x in arr if x < pivot]
middle = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
return quick_sort(left) + middle + quick_sort(right)

Java 实现：

“`java
public class QuickSort {
public static void quickSort(int[] arr, int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
quickSort(arr, low, pi – 1);
quickSort(arr, pi + 1, high);
}
}

public static int partition(int[] arr, int low, int high) {
    int pivot = arr[high];
    int i = (low - 1);
    for (int j = low; j < high; j++) {
        if (arr[j] < pivot) {
            i++;
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    int temp = arr[i + 1];
    arr[i + 1] = arr[high];
    arr[high] = temp;
    return i + 1;
}
 public static void main(String[] args) {
    int[] arr = {10, 7, 8, 9, 1, 5};
    quickSort(arr, 0, arr.length - 1);
    System.out.println("Sorted array: " + Arrays.toString(arr));
}

}
“`

7. 堆排序 (Heap Sort)

原理：
堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

步骤：

1. 创建一个堆（最大堆或最小堆）。
2. 将堆顶元素（最大值或最小值）与最后一个元素交换。
3. 将堆的大小减 1，并对堆顶元素进行堆化操作（heapify），使其重新成为一个堆。
4. 重复步骤 2 和 3，直到堆的大小为 1。

时间复杂度：

• 最佳情况：O(n log n)
• 平均情况：O(n log n)
• 最坏情况：O(n log n)

空间复杂度： O(1) (原地排序)

稳定性： 不稳定

Python 实现：
“`python
def heapify(arr, n, i):
largest = i
left = 2 * i + 1
right = 2 * i + 2

if left < n and arr[left] > arr[largest]:
    largest = left

if right < n and arr[right] > arr[largest]:
    largest = right

if largest != i:
    arr[i], arr[largest] = arr[largest], arr[i]
    heapify(arr, n, largest)

def heap_sort(arr):
n = len(arr)

# 构建最大堆
for i in range(n // 2 - 1, -1, -1):
    heapify(arr, n, i)

# 一个个交换元素
for i in range(n - 1, 0, -1):
    arr[i], arr[0] = arr[0], arr[i]  # 交换
    heapify(arr, i, 0)
return arr

“`

Java 实现：
“`java
public class HeapSort {
public static void heapSort(int[] arr) {
int n = arr.length;

    // 构建最大堆 (从最后一个非叶子节点开始)
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(arr, n, i);

    // 一个个从堆顶取出元素
    for (int i = n - 1; i >= 0; i--) {
        // 将当前堆顶元素(最大值)移动到数组末尾
        int temp = arr[0];
        arr[0] = arr[i];
        arr[i] = temp;

        // 重新调整为最大堆
        heapify(arr, i, 0);
    }
}
public static void heapify(int[] arr, int n, int i) {
    int largest = i; // 初始化最大值为根节点
    int left = 2 * i + 1;
    int right = 2 * i + 2;

     // 如果左子节点大于根节点
    if (left < n && arr[left] > arr[largest])
        largest = left;

    // 如果右子节点大于目前的最大值
    if (right < n && arr[right] > arr[largest])
        largest = right;

    // 如果最大值不是根节点
    if (largest != i) {
        int swap = arr[i];
        arr[i] = arr[largest];
        arr[largest] = swap;

        // 递归调整被交换的子树
        heapify(arr, n, largest);
    }
}
public static void main(String[] args) {
    int[] arr = {12, 11, 13, 5, 6, 7};
    heapSort(arr);
    System.out.println("Sorted array: " + Arrays.toString(arr));
}

}
“`

8. 计数排序 (Counting Sort)

原理:

计数排序不是基于比较的排序算法，其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。 作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。

步骤：

1. 找出待排序的数组中最大和最小的元素。
2. 统计数组中每个值为 i 的元素出现的次数，存入数组 C 的第 i 项。
3. 对所有的计数累加（从 C 中的第一个元素开始，每一项和前一项相加）。
4. 反向填充目标数组：将每个元素 i 放在新数组的第 C[i] 项，每放一个元素就将 C[i] 减去 1。

时间复杂度：

• 最佳情况：O(n+k)
• 平均情况：O(n+k)

• 最坏情况：O(n+k)

  其中 n 是待排序元素的个数，k 是整数的范围。

空间复杂度： O(k)

稳定性: 稳定

Python 实现：

“`python
def counting_sort(arr):
max_val = max(arr)
min_val = min(arr)
range_of_elements = max_val – min_val + 1
count_arr = [0] * range_of_elements
output_arr = [0] * len(arr)

for i in range(0, len(arr)):
    count_arr[arr[i] - min_val] += 1

for i in range(1, len(count_arr)):
    count_arr[i] += count_arr[i - 1]

for i in range(len(arr) - 1, -1, -1):
    output_arr[count_arr[arr[i] - min_val] - 1] = arr[i]
    count_arr[arr[i] - min_val] -= 1

for i in range(0, len(arr)):
    arr[i] = output_arr[i]

return arr

“`

Java 实现：

“`java
public class CountingSort {
public static void countingSort(int[] arr) {
int max = Arrays.stream(arr).max().getAsInt();
int min = Arrays.stream(arr).min().getAsInt();
int range = max – min + 1;
int[] count = new int[range];
int[] output = new int[arr.length];

    for (int i = 0; i < arr.length; i++) {
        count[arr[i] - min]++;
    }

    for (int i = 1; i < count.length; i++) {
        count[i] += count[i - 1];
    }

    for (int i = arr.length - 1; i >= 0; i--) {
        output[count[arr[i] - min] - 1] = arr[i];
        count[arr[i] - min]--;
    }

    for (int i = 0; i < arr.length; i++) {
        arr[i] = output[i];
    }
}
public static void main(String[] args) {
    int[] arr = {4, 2, 2, 8, 3, 3, 1};
    countingSort(arr);
    System.out.println("Sorted array: " + Arrays.toString(arr));
}

}
“`

9. 桶排序 (Bucket Sort)

原理:
桶排序 (Bucket sort) 或所谓的箱排序，是一个排序算法，工作的原理是将数组分到有限数量的桶子里。每个桶子再个别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序）。桶排序是鸽巢排序的一种归纳结果。

步骤：

1. 设置一个定量的数组当作空桶子。
2. 遍历输入数据，并且把数据一个一个放到对应的桶子去。
3. 对每个不是空的桶子进行排序。
4. 从不是空的桶子里把排好序的数据拼接起来。

时间复杂度：

• 最佳情况：O(n+k)
• 平均情况：O(n+k)

• 最坏情况：O(n^2) (当所有元素都分配到一个桶中时)

  其中 n 是待排序元素的个数，k 是桶的个数。

空间复杂度： O(n+k)

稳定性: 稳定 (取决于桶内使用的排序算法)

Python 实现：

“`python
def bucket_sort(arr):
# 假设 arr 中的值在 0 到 1 之间
num_buckets = len(arr)
buckets = [[] for _ in range(num_buckets)]

# 将元素放入桶中
for val in arr:
    index_b = int(num_buckets * val)
    buckets[index_b].append(val)

# 对每个桶进行排序
for i in range(num_buckets):
    buckets[i] = sorted(buckets[i])  # 使用内置的 Timsort

# 合并桶
k = 0
for i in range(num_buckets):
    for j in range(len(buckets[i])):
        arr[k] = buckets[i][j]
        k += 1
return arr

“`

Java 实现：
“`java
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class BucketSort {
public static void bucketSort(float[] arr) {
int n = arr.length;
if (n <= 0)
return;

    // 1) 创建 n 个空桶
    @SuppressWarnings("unchecked")
    List<Float>[] buckets = new ArrayList[n];
    for (int i = 0; i < n; i++) {
        buckets[i] = new ArrayList<Float>();
    }

    // 2) 将数组元素放入桶中
    for (int i = 0; i < n; i++) {
        int bucketIndex = (int) (n * arr[i]); // 假设arr的值在[0,1)
        buckets[bucketIndex].add(arr[i]);
    }

    // 3) 对每个桶进行排序
    for (int i = 0; i < n; i++) {
        Collections.sort(buckets[i]);
    }

    // 4) 将桶中的元素合并到原数组
    int index = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < buckets[i].size(); j++) {
            arr[index++] = buckets[i].get(j);
        }
    }
}
public static void main(String[] args) {
    float[] arr = {0.897f, 0.565f, 0.656f, 0.1234f, 0.665f, 0.3434f};
    bucketSort(arr);
    System.out.println("Sorted array: " + Arrays.toString(arr));
}

}
“`
注意: 桶排序的性能很大程度上取决于数据的分布。 如果数据分布不均匀， 那么性能可能会下降到 O(n^2)。 通常桶排序需要数据是均匀分布的。上面的 Java 例子中，我们假设了数据是在 [0, 1) 之间的浮点数。

10. 基数排序 (Radix Sort)

原理:

基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。基数排序也可以应用于字符串（比如名字或日期）和特定格式的浮点数。

步骤：

1. 找出待排序的数组中最大的数，确定排序的趟数（即最大数的位数）。
2. 对数组中的每个元素的个位数进行排序（可以使用计数排序）。
3. 对数组中的每个元素的十位数进行排序（可以使用计数排序）。
4. 以此类推，直到对最高位数进行排序。

时间复杂度：

• 最佳情况：O(nk)
• 平均情况：O(nk)

• 最坏情况：O(nk)

  其中 n 是待排序元素的个数，k 是最大数的位数。

空间复杂度： O(n+k)

稳定性： 稳定

Python 实现：

“`python
def counting_sort_for_radix(arr, exp):
n = len(arr)
output = [0] * n
count = [0] * 10 # 0-9

for i in range(0, n):
    index = (arr[i] // exp) % 10
    count[index] += 1

for i in range(1, 10):
    count[i] += count[i - 1]

i = n - 1
while i >= 0:
    index = (arr[i] // exp) % 10
    output[count[index] - 1] = arr[i]
    count[index] -= 1
    i -= 1

for i in range(0, n):
    arr[i] = output[i]

def radix_sort(arr):
max_val = max(arr)
exp = 1
while max_val // exp > 0:
counting_sort_for_radix(arr, exp)
exp *= 10
return arr
“`

Java 实现：
“`java
public class RadixSort {
public static void radixSort(int[] arr) {
int max = Arrays.stream(arr).max().getAsInt();

    // 对每个位数进行计数排序
    for (int exp = 1; max / exp > 0; exp *= 10)
        countingSortForRadix(arr, exp);
}

public static void countingSortForRadix(int[] arr, int exp) {
    int n = arr.length;
    int[] output = new int[n];
    int[] count = new int[10];
    Arrays.fill(count, 0);

    // 统计每个数字出现的次数
    for (int i = 0; i < n; i++)
        count[(arr[i] / exp) % 10]++;

    // 计算累积次数
    for (int i = 1; i < 10; i++)
        count[i] += count[i - 1];

    // 构建输出数组
    for (int i = n - 1; i >= 0; i--) {
        output[count[(arr[i] / exp) % 10] - 1] = arr[i];
        count[(arr[i] / exp) % 10]--;
    }

    // 将输出数组复制到原数组
    for (int i = 0; i < n; i++)
        arr[i] = output[i];
}
 public static void main(String[] args) {
    int[] arr = {170, 45, 75, 90, 802, 24, 2, 66};
    radixSort(arr);
    System.out.println("Sorted array: " + Arrays.toString(arr));
}

}
“`

11. 总结与比较

下表总结了上述排序算法的关键特性：

排序算法	最佳时间复杂度	平均时间复杂度	最坏时间复杂度	空间复杂度	稳定性	适用场景
冒泡排序	O(n)	O(n^2)	O(n^2)	O(1)	稳定	数据基本有序
选择排序