选择排序（Selection Sort）

**选择排序（Selection Sort）**

选择排序是一种简单而有效的排序算法，它通过在每一步中找到最小或最大元素，并将其放置在当前未排序序列的起始位置来实现排序。

**工作原理**

1. 首先，选择排序从未排序序列的起始位置开始。
2. 然后，它找到未排序序列中的最小（或最大）元素，并将其移动到起始位置。
3. 接着，它继续寻找下一个未排序的元素，并将其移动到当前未排序序列的起始位置。
4. 这个过程重复直到整个序列被排序。

**选择排序的步骤**

1. **找到最小（或最大）元素**
* 从未排序序列中找到最小（或最大）的元素。
* 将该元素移动到当前未排序序列的起始位置。
2. **重复上述过程**
* 重复步骤1，直到整个序列被排序。

**选择排序的时间复杂度**

选择排序的时间复杂度为 O(n^2)，其中 n 是序列的长度。这种情况是因为在每一步中，我们都需要扫描整个未排序序列来找到最小（或最大）的元素。

**选择排序的空间复杂度**

选择排序的空间复杂度为 O(1)，因为我们只使用了常数数量的额外空间来存储临时变量。

**选择排序的优缺点**

优点：

* 简单易懂* 不需要额外的空间缺点：

* 时间效率较低（O(n^2))
* 不适合大规模数据的排序**选择排序的实现**

下面是选择排序的 Java 实现：

javapublic class SelectionSort {
 public static void sort(int[] arr) {
 int n = arr.length;
 // 遍历未排序序列 for (int i =0; i < n -1; i++) {
 // 找到最小元素的索引 int minIndex = i;
 // 扫描未排序序列找到最小元素 for (int j = i +1; j < n; j++) {
 if (arr[j] < arr[minIndex]) {
 minIndex = j;
 }
 }
 // 交换最小元素与当前位置的元素 int temp = arr[i];
 arr[i] = arr[minIndex];
 arr[minIndex] = temp;
 }
 }

 public static void main(String[] args) {
 int[] arr = {5,2,8,3,1,6,4};
 System.out.println("原始数组:");
 printArray(arr);
 sort(arr);
 System.out.println("排序后数组:");
 printArray(arr);
 }

 public static void printArray(int[] arr) {
 for (int i =0; i < arr.length; i++) {
 System.out.print(arr[i] + " ");
 }
 System.out.println();
 }
}