排序——选择排序(Selection sort)

广告位

算法思想 第一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,然后再从剩余的未排序元…

算法思想

第一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,然后再从剩余的未排序元素中寻找到最小(大)元素,然后放到已排序的序列的末尾。以此类推,直到全部待排序的数据元素的个数为零。

图示过程

假设一个数列为{6, 3, 5, 7, 0},对该数列进行排序。整个排序过程入下图所示:

排序——选择排序(Selection sort)

说明:上图为未优化的选择排序示意图。

动画展示

排序——选择排序(Selection sort)

说明:此动图为优化后的选择排序,每趟只交换一次。

算法描述

  • 第1趟比较:拿第1个元素依次和它后面的每个元素进行比较,如果第1个元素大于后面某个元素,交换它们,经过第1趟比较,数组中最小的元素被选出,它被排在第一位。
  • 第2趟比较:拿第2个元素依次和它后面的每个元素进行比较,如果第2个元素大于后面某个元素,交换它们,经过第2趟比较,数组中第2小的元素被选出,它被排在第二位。
  • ……
  • 第n-1趟比较:第n-1个元素和第n个元素作比较,如果第n-1个元素大于第n个元素,交换它们。

算法优化

选择排序的核心是,在每趟比较中,找到本趟中最小的元素放在本趟比较的第1个位置,所以选择排序的每趟比较只需要交换一次即可,只要找到本趟比较中最小的元素和本趟比较中第1位置的元素交换即可。

算法性能

时间复杂度

排序——选择排序(Selection sort)

空间复杂度

排序——选择排序(Selection sort),只需要一个附加程序单元用于交换数据。

稳定性

不稳定排序方法。

代码实现

C语言和C++

 inline void swap(int &a, int &b) {     int temp = a;     a = b;     b = temp; }  void selection_sort(int nums[], int len) {     if (len < 2) {         return;     }      for (int i=0; i<len-1; i++) {         int index = i;         for (int j=i+1; i<len; j++) {             if (nums[i] > num[j]) {                 index = nums[j]<nums[index] ? j : index;             }         }         swap(i, index);     } }

JAVA

 public static void selectionSort(int[] nums) {     if (nums == null || nums.length < 2) {         return;     }      for(int i = 0; i < nums.length - 1; i++) {         int minIndex = i;         for(int j = i + 1; j < nums.length; j++) {             if (nums[i] > nums[j]) {                 minIndex = nums[j] < nums[minIndex] ? j : minIndex;             }         }         swap(nums, i, minIndex);     } }

Python

 def selection_sort(list2):     for i in range(0, len (list2)-1):         min_ = i         for j in range(i + 1, len(list2)):             if list2[j] < list2[min_]:                 min_ = j         list2[i], list2[min_] = list2[min_], list2[i]  # swap

 

发布了130 篇原创文章 · 获赞 4 · 访问量 12万+

月明星稀

关于作者: 月明星稀

为您推荐