上查看所有课程
选择排序是一种排序算法，它在每次迭代中从未排序列表中选择最小的元素，并将其放置在未排序列表的开头。
选择排序的工作原理
- 将第一个元素设置为
minimum。
选择第一个元素作为最小值 - 将
minimum与第二个元素进行比较。如果第二个元素小于minimum，则将第二个元素赋值给minimum。
将minimum与第三个元素进行比较。如果第三个元素更小，则将minimum赋值给第三个元素，否则不执行任何操作。该过程一直持续到最后一个元素。
将最小值与其余元素进行比较 - 每次迭代后，
minimum会被放置在未排序列表的前面。
将第一个元素与最小值交换 - 对于每次迭代，索引从第一个未排序元素开始。步骤1到3重复执行，直到所有元素都放置在正确的位置。
第一次迭代 
第二次迭代 
第三次迭代 
第四次迭代
选择排序算法
selectionSort(array, size)
for i from 0 to size - 1 do
set i as the index of the current minimum
for j from i + 1 to size - 1 do
if array[j] < array[current minimum]
set j as the new current minimum index
if current minimum is not i
swap array[i] with array[current minimum]
end selectionSortPython、Java和C/C++中的选择排序代码
# Selection sort in Python
def selectionSort(array, size):
for step in range(size):
min_idx = step
for i in range(step + 1, size):
# to sort in descending order, change > to < in this line
# select the minimum element in each loop
if array[i] < array[min_idx]:
min_idx = i
# put min at the correct position
(array[step], array[min_idx]) = (array[min_idx], array[step])
data = [-2, 45, 0, 11, -9]
size = len(data)
selectionSort(data, size)
print('Sorted Array in Ascending Order:')
print(data)// Selection sort in 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++) {
// To sort in descending order, change > to < in this line.
// Select the minimum element in each loop.
if (array[i] < array[min_idx]) {
min_idx = i;
}
}
// put min at the correct position
int temp = array[step];
array[step] = array[min_idx];
array[min_idx] = temp;
}
}
// driver code
public static void main(String args[]) {
int[] data = { 20, 12, 10, 15, 2 };
SelectionSort ss = new SelectionSort();
ss.selectionSort(data);
System.out.println("Sorted Array in Ascending Order: ");
System.out.println(Arrays.toString(data));
}
}// Selection sort in C
#include <stdio.h>
// function to swap the the position of two elements
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++) {
// To sort in descending order, change > to < in this line.
// Select the minimum element in each loop.
if (array[i] < array[min_idx])
min_idx = i;
}
// put min at the correct position
swap(&array[min_idx], &array[step]);
}
}
// function to print an array
void printArray(int array[], int size) {
for (int i = 0; i < size; ++i) {
printf("%d ", array[i]);
}
printf("\n");
}
// driver code
int main() {
int data[] = {20, 12, 10, 15, 2};
int size = sizeof(data) / sizeof(data[0]);
selectionSort(data, size);
printf("Sorted array in Acsending Order:\n");
printArray(data, size);
}// Selection sort in C++
#include <iostream>
using namespace std;
// function to swap the the position of two elements
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
// function to print an array
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++) {
// To sort in descending order, change > to < in this line.
// Select the minimum element in each loop.
if (array[i] < array[min_idx])
min_idx = i;
}
// put min at the correct position
swap(&array[min_idx], &array[step]);
}
}
// driver code
int main() {
int data[] = {20, 12, 10, 15, 2};
int size = sizeof(data) / sizeof(data[0]);
selectionSort(data, size);
cout << "Sorted array in Acsending Order:\n";
printArray(data, size);
}选择排序复杂度
| 时间复杂度 | |
|---|---|
| 最佳 | O(n2) |
| 最坏 | O(n2) |
| 平均 | O(n2) |
| 空间复杂度 | O(1) |
| 稳定性 | 否 |
| 循环 | 比较次数 |
|---|---|
| 第 1 次 | (n-1) |
| 第 2 次 | (n-2) |
| 第 3 次 | (n-3) |
| ... | ... |
| 最后一个 | 1 |
比较次数：(n - 1) + (n - 2) + (n - 3) + ..... + 1 = n(n - 1) / 2，约等于n2。
复杂度 = O(n2)
此外，我们还可以通过简单地观察循环次数来分析复杂度。有2个循环，因此复杂度为n*n = n2。
时间复杂度
- 最坏情况复杂度：
O(n2)
如果我们想按升序排序，而数组是按降序排列的，则会发生最坏情况。 - 最佳情况复杂度：
O(n2)
当数组已排序时发生 - 平均情况复杂度：
O(n2)
当数组元素乱序（既不升序也不降序）时发生
选择排序的时间复杂度在所有情况下都是相同的。在每个步骤中，您都需要找到最小元素并将其放在正确的位置。在到达数组末尾之前，无法确定最小元素。
空间复杂度
空间复杂度为O(1)，因为使用了一个额外的变量min_idx。
选择排序的应用
选择排序用于
- 要排序的列表很小
- 交换成本无关紧要
- 必须检查所有元素
- 写入内存的成本很重要，例如闪存（写入/交换次数为
O(n)，而冒泡排序为O(n2)）