选择排序算法
提示
- 基本原理:选择排序算法通过在每次迭代中选择未排序列表中的最小元素,并将其置于未排序列表的起始位置来对数组进行排序。
- 执行步骤:首先设定列表中的第一个元素为最小值,然后与其余元素比较,找到实际的最小值,并将其 置于适当位置;接着对剩余的未排序列表重复此过程。
- 复杂度分析:选择排序在所有情况下的时间复杂度均为 O(n²),空间复杂度为 O(1),是一种不稳定的排序算法。
选择排序是一种排序算法,它在每次迭代中从未排序的列表中选择最小的元素,并将该元素放置在未排序列表的开始位置。
选择排序的工作原理
-
将第一个元素设为
最小值
。 -
将
最小值
与第二个元素比较。如果第二个元素小于最小值
,则将第二个元素设为最小值
。将
最小值
与第三个元素比较。同样,如果第三个元素更小,则将最小值
指定为第三个元素,否则不做任何操作。这个过程一直进行到最后一个元素。 -
每次迭代后,
最小值
被放置在未排序列表的前面。 -
每次迭代,索引都从第一个未排序的元素开始。重复步骤 1 到 3,直到所有元素都放置在正确的位置上。
选择排序算法
selectionSort(array, size)
重复 (size - 1) 次
将第一个未排序的元素设为最小值
对每个未排序的元素
如果 element < currentMinimum
将 element 设为新的最小值
将最 小值与第一个未排序的位置交换
end selectionSort
Python、Java 和 C/C++ 中的选择排序代码
# Python 中的选择排序
def selectionSort(array, size):
for step in range(size):
min_idx = step
for i in range(step + 1, size):
# 若要按降序排序,请在此行中将 > 更改为 <
# 在每次循环中选择最小元素
if array[i] < array[min_idx]:
min_idx = i
# 将最小值放置在正确位置上
(array[step], array[min_idx]) = (array[min_idx], array[step])
data = [-2, 45, 0, 11, -9]
size = len(data)
selectionSort(data, size)
print('按升序排列的数组:')
print(data)
// Java 中的选择排序
import java.util.Arrays;
class SelectionSort {
void selectionSort(int array[]) {
int size = array.length;
for (int step = 0; step < size - 1; step++) {
int min_idx = step;
for (int i = step + 1; i < size; i++) {
// 若要按降序排序,请在此行 中将 > 更改为 <
// 在每次循环中选择最小元素
if (array[i] < array[min_idx]) {
min_idx = i;
}
}
// 将最小值放置在正确位置上
int temp = array[step];
array[step] = array[min_idx];
array[min_idx] = temp;
}
}
// 驱动代码
public static void main(String args[]) {
int[] data = { 20, 12, 10, 15, 2 };
SelectionSort ss = new SelectionSort();
ss.selectionSort(data);
System.out.println("按升序排列的数组: ");
System.out.println(Arrays.toString(data));
}
}
// C 语言中的选择排序
#include <stdio.h>
// 交换两个元素位置的函数
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
void selectionSort(int array[], int size) {
for (int step = 0; step < size - 1; step++) {
int min_idx = step;
for (int i = step + 1; i < size; i++) {
// 若要按降序排序,请在此行将 > 改为 <
// 在每次循环中选择最小元素
if (array[i] < array[min_idx])
min_idx = i;
}
// 将最小值放置在正确位置上
swap(&array[min_idx], &array[step]);
}
}
// 打印数组的函数
void printArray(int array[], int size) {
for (int i = 0; i < size; ++i) {
printf("%d ", array[i]);
}
printf("\n");
}
// 驱动代码
int main() {
int data[] = {20, 12, 10, 15, 2};
int size = sizeof(data) / sizeof(data[0]);
selectionSort(data, size);
printf("按升序排列的数组:\n");
printArray(data, size);
}
// C++ 中的选择排序
#include <iostream>
using namespace std;
// 交换两个元素位置的函数
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
// 打印数组的函数
void printArray(int array[], int size) {
for (int i = 0; i < size; i++) {
cout << array[i] << " ";
}
cout << endl;
}
void selectionSort(int array[], int size) {
for (int step = 0; step < size - 1; step++) {
int min_idx = step;
for (int i = step + 1; i < size; i++) {
// 若要按降序排序,请在此行将 > 改为 <
// 在每次循环中选择最小元素
if (array[i] < array[min_idx])
min_idx = i;
}
// 将最小值放置在正确位置上
swap(&array[min_idx], &array[step]);
}
}
// 驱动代码
int main() {
int data[] = {20, 12, 10, 15, 2};
int size = sizeof(data) / sizeof(data[0]);
selectionSort(data, size);
cout << "按升序排列的数组:\n";
printArray(data, size);
}
选择排序的复杂度
时间复杂度 | |
---|---|
最优情况 | O(n²) |
最坏情况 | O(n²) |
平均情况 | O(n²) |
空间复杂度 | O(1) |
--- | --- |
稳定性 | 否 |
--- | --- |
循环次数 | 比较次数 |
---|---|
第1次 | (n-1) |
第2次 | (n-2) |
第3次 | (n-3) |
... | ... |
最后一次 | 1 |
比较次数: (n - 1) + (n - 2) + (n - 3) + ..... + 1 = n(n - 1) / 2
近似等于 n²
。
复杂度 = O(n²)
通过观察循环的次数也可以简单分析复杂度。这里有2个循环,所以复杂度为 n*n = n²
。
时间复杂度:
- 最坏情况复杂度:
O(n²)
如果我们想对一个降序数组进行升序排序,那么就会发生最坏情况。 - 最优情况复杂度:
O(n²)
发生在数组已经排序的情况下。 - 平均情况复杂度:
O(n²)
发生在数组元素顺序杂乱(既不是升序也不是降序)的情况下。
选择排序在所有情况下的时间复杂度都是一样的。在每一步,你都需要找到最小元素并将其放置在正确的位置。在没有遍历完整个数组之前,最小元素是未知的。
空间复杂度:
空间复杂度为 O(1)
,因为使用了额外的变量 temp
。
选择排序的应用
选择排序适用于以下情况:
- 排序小型列表
- 交换成本不重要
- 必须检查所有元素
- 写入内存的成本很重要,如在闪存中(写入/交换的次数为
O(n)
,与冒泡排序的O(n²)
相比)