选择排序本页面将简要介绍选择排序．
定义选择排序（Selection sort）是一种简单直观的排序算法．它的工作原理是每次找出第 𝑖i 小的元素（也就是 𝐴𝑖..𝑛Ai..n 中最小的元素），然后将这个元素与数组第 𝑖i 个位置上的元素交换．
性质稳定性选择排序的稳定性取决于其具体实现．
倘若使用链表实现，由于链表的任意位置插入和删除均为 𝑂(1)O(1)，故无需使用 swap（交换两个元素）操作：每次从未排序部分选择最小元素（若有多个，选取第一个）后，将其插入到未排序部分的第一个元素之前，这样就能够保证稳定性．
数组实现一般会使用 swap 将最小元素移到已排序部分，以此减少移动次数，所以不稳定．
下面给出的实现示例均是基于数组元素的交换，因此均为 不稳定的．
时间复杂度选择排序的最优时间复杂度、平均时间复杂度和最坏时间复杂度均为 𝑂(𝑛2)O(n2)．
代码实现伪代码1𝐈𝐧𝐩𝐮𝐭. An array 𝐴 consisting of 𝑛 elements.2𝐎𝐮𝐭𝐩𝐮𝐭. 𝐴 will be sorted in nondecreasing order.3𝐌𝐞𝐭𝐡𝐨𝐝. 4𝐟𝐨𝐫 𝑖←1 𝐭𝐨 𝑛−15𝑖𝑡ℎ←𝑖6𝐟𝐨𝐫 𝑗←𝑖+1 𝐭𝐨 𝑛7𝐢𝐟 𝐴[𝑗]<𝐴[𝑖𝑡ℎ]8𝑖𝑡ℎ←𝑗9swap 𝐴[𝑖] and 𝐴[𝑖𝑡ℎ]1Input. An array A consisting of n elements.2Output. A will be sorted in nondecreasing order.3Method. 4for i←1 to n−15ith←i6for j←i+1 to n7if A[j] 2 3 4 5 6 7 8 9 10 11 12 13#include void selection_sort(int* a, int n) { for (int i = 1; i < n; ++i) { int ith = i; for (int j = i + 1; j <= n; ++j) { if (a[j] < a[ith]) { ith = j; } } std::swap(a[i], a[ith]); } } 1 2 3 4 5 6 7def selection_sort(a, n): for i in range(1, n): ith = i for j in range(i + 1, n + 1): if a[j] < a[ith]: ith = j a[i], a[ith] = a[ith], a[i] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15// arr 数组的下标从 1 开始 static void selection_sort(int[] arr, int n) { for (int i = 1; i < n; i++) { int ith = i; for (int j = i + 1; j <= n; j++) { if (arr[j] < arr[ith]) { ith = j; } } // swap int temp = arr[i]; arr[i] = arr[ith]; arr[ith] = temp; } } 本页面最近更新：2026/9/28 01:09:54，更新历史发现错误？想一起完善？ 在 GitHub 上编辑此页！本页面贡献者：NachtgeistW, Tiphereth-A, c-forrest, iamtwz, Junyan721113, Xeonacid, Early0v0, Enter-tainer, ksyx, mcendu, Menci, ouuan, partychicken, shawlleyw, tfia, TrickEye, WException, ZbohZbp本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用