65Python排序算法——选择排序

65 Python排序算法—— 选择排序 一、选择排序(selection sort) 选择排序（Selection sort）是一种简单直观的排序算法。 它的工作原理是每一次从待排序的数据元素中选出最小（或最大） 的一个元素，存放在序列的起始位置，所以称为：选择排序。 二、选择排序原理 设第一个元素为比较元素，依次和后面的元素比较，比较完所有元素并找到最小元素，记录最小元素下标，和第0个下表元素进行交换 在未排序区域中，重复上述操作，以此类推找出剩余最小元素将它换到前面，即完成排序。 基本思想 选择排序的基本思路是每次从未排序的数列中选择最小（或最大）的元素（最小即升序，最大即降序），将其放到已排序数列的末尾。重复这个过程，直到所有元素都被排序为止。选择排序是一种简单但效率较低的排序算法，其时间复杂度为O(n^2)，不适用于大规模数据的排序。 三、选择排序和冒泡排序对比 选择排序是一种简单直观的排序算法。它与冒泡排序很相似，都是比较 n-1 轮，每轮都是比较 n–1–i 次，每轮找出一个最大值或最小值。 只不过，冒泡排序是将每轮找出的最值放到最右边，而选择排序是将每轮找出的最值放到最左边。 并且在算法上，冒泡排序是将相邻的数进行逐个比较，以从小到大排序为例，只要前面的比后面的大，就互换这两个数，直到最后将最大的数“浮”到最右边，如此依次循环。 而选择排序是先保存第一个元素的下标，然后后面所有的数依次与第一个元素相比，如果遇到更小的，则记录更小的那个数的下标，然后后面所有的数都依次与那个更小的数比较，直到最后将最小的数的下标找出来，然后再将这个数放到最左边，即与下标为 0 的数互换。如果最小的数的下标就是 0 那么就不用互换。 动态演示 四、算法步骤 实现步骤 （1）设数组长度为n。 （2）从数组中找到最小的元素，并记录其下标。 （3）将最小元素与第1个元素交换位置。 （4）在剩下的n-1个元素中，找到最小的元素，记录其下标。 （5）将最小元素与第2个元素交换位置。 （6）重复步骤4-5，直到排序完成。 案例：使用选择排序算法，对列表排序 l=[54,226,93,17,77,31,44,55,20] $$