这才是选择排序正确的打开方式！

五分钟学算法

发布于 2020-06-28 15:58:32

5260

发布于 2020-06-28 15:58:32

文章被收录于专栏：五分钟学算法五分钟学算法

选择排序思想

选择排序（Selection Sort）的基本思想是不断地从数组当中未排序的部分选取关键字最小的记录，并将该记录作为已排序部分的最后一个记录（考虑升序排列的情况）。算法主要就是维护一个给定数组的两个子数组：

数组已排序的部分；
数组未排序的部分；

在选择排序的每一次迭代中，从数组中未排序的部分选择出最小元素（升序排列的情况），然后将其移入数组已排序的部分。

初始时，给定一个数组，且将该数组当中的所有元素都被划分为无序部分：

遍历数组 [0,7]，找到下标为 5 最小的关键字 13：

下标为 5 最小的关键字 13 与下标为 0 的关键字 49 进行交换，这样就得到了数组有序部分的第一个关键字 13，而无序部分相应的减少了一个关键：

之后的所有操作和之前一样，在无序部分找到最小的关键字，然后与无序部分的第一个关键字交换，有序部分加一，无序部分减一：

简而言之，选择排序就两步：

选择最小（或最大）
交换

实现代码

C 实现

void swap(int *xp, int *yp) 
{ 
 int temp = *xp; 
 *xp = *yp; 
 *yp = temp; 
} 

void selectionSort(int arr[], int n) 
{ 
 int i, j, min_idx; 

 // i就相当于将数组划分为有序部分和无序部分的边界，不断地让这个边界后移
 for (i = 0; i < n-1; i++) 
 { 
  //找到数组中无序部分的最小关键字
  min_idx = i; 
  for (j = i+1; j < n; j++) 
  if (arr[j] < arr[min_idx]) 
   min_idx = j; 

  // 将最小关键字与无序部分的第一给关键字交换
  swap(&arr[min_idx], &arr[i]); 
 } 
}

Java实现

class SelectionSort 
{ 
 void sort(int arr[]) 
 { 
  int n = arr.length; 

  for (int i = 0; i < n-1; i++) 
  { 
   int min_idx = i; 
   for (int j = i+1; j < n; j++){
                if (arr[j] < arr[min_idx]) 
     min_idx = j; 
            } 

   int temp = arr[min_idx]; 
   arr[min_idx] = arr[i]; 
   arr[i] = temp; 
  } 
 } 
}

Python实现

def SelectionSort(A):
    for i in range(len(A)): 
        min_idx = i 
        for j in range(i+1, len(A)): 
            if A[min_idx] > A[j]: 
                min_idx = j 

        A[i], A[min_idx] = A[min_idx], A[i] 
    return A

复杂度分析

时间复杂度

稳定性分析

关于排序算法的稳定性问题，景禹在之前的一篇文章 排序算法的稳定性 中有分享，这里我们就直接分析选择排序的稳定性问题。

我可以直接告诉你选择排序的默认实现方式是不稳定的，具体为神马，我们接着看一个例子：

给定上面一个数组，我们按照前面的实现方式进行排序。

第一步：在数组中找到最小的关键字 1 ，并与数组中的第一个元素（红色色块 4）交换位置：

第二步：在数组中无序部分 [5，3，2，4，4] 找到最小的关键字 2 与无序部分的第一个关键字 5 交换位置：

第三步：在数组中无序部分 [3，5，4，4] 中找到最小的关键字 3 和无序部分的第一个关键字 3 交换，和之前一样：

第四步：在数组中无序部分 [5，4，4] 中找到最小的关键字 4（注意是蓝色色块的4） 和 5 交换：

第五步：在数组中无序部分 [5，4] 中找到最小的关键字 4（注意是红色色块的4） 和 5 交换：

此时我们得到一个有序数组，但是与原始的数组相比，两个 4 的相对位置发生了变化。即，本来红色色块的 4 在蓝色色块的 4 的前面，而排序后蓝色的在红色的前面，这就是我们之前所说的不稳定（两个值相同的关键字排序前后的相对位置发生了变化）。也就是说目前的实现方式下的选择排序是不稳定的。

稳定的选择排序

不稳定的选择排序结果：

目标 -- 实现一个稳定的选择排序：

为了实现现在这一目标，我们分析一下原始的选择排序为什么不稳定？

答案就是交换操作造成了不稳定。选择排序的工作原理就是在未排序的部分找到关键字最小的元素，然后将该元素与未排序部分的第一个元素进行交换位置。也就是这个交换操作导致其不稳定，比如前面分析的时候，第一次交换就是的 4 得相对位置发生了变化。

因此可以考虑对这里的交换操作进行修改使得选择排序变得稳定。

要想每一次将最小元素放置在其位置而不进行交换，可以通过将每一次选择出的最小关键字前面的无序数组元素都向后移动一个位置，使选择排序稳定。简单来说，就是利用类似于插入排序的技术将最小的元素插入正确的位置。

第一步：找到最小元素是 1 ，此时不再是将红色色块 4 和最小元素 1 进行交换，而是将 1 插入到正确的位置，然后将 1 之前的每一个元素都向后移动一个位置：

第二步：找到数组无序部分的最小元素 2 ，将 2 之前的 [4，5，3] 的每一个元素向后移动一个位置：

第三步：找到数组无序部分的最小元素 3 ，将 3 之前的 [4，5] 的每一个元素向后移动一个位置：

第四步：找到数组无序部分的最小元素 4（红色色块） ，其前面没有无序元素，什么都不做；

第五步：找到数组无序部分的最小元素 4（蓝色色块） ，将其前面的元素 5 向后移动，我们得到了一个稳定的有序数组：

稳定的选择排序的实现

Java实现

class JingYuSorting 
{ 
 static void stableSelectionSort(int[] a, int n) 
 { 
  // 与默认的实现方式相同
  for (int i = 0; i < n - 1; i++) 
  { 
   // a[i - 1] 之前的元素为数组的有序部分 
   // 从 arr[i] 到 arr[n - 1] 找到最小元素的下标保存到min中
   int min = i; 
   for (int j = i + 1; j < n; j++) 
    if (a[min] > a[j]) 
     min = j; 

   // 将最小的元素移动到当前的位置 i.
   int key = a[min]; 
            // 将从 i 到 min - 1 的元素都向后移动一个位置
   while (min > i) 
   { 
    a[min] = a[min - 1]; 
    min--; 
   } 
   // 将当前选择的最小元素放到正确的位置
   a[i] = key; 
  } 
 } 
}

复杂度分析

时间复杂度

实战演练

给定一个字符串数组，使用选择排序对数组进行排序。

输入: paper true soap floppy flower 输出: floppy, flower, paper, soap, true

我们前面所讲的所有例子都是用整数进行说明的，这里要使用选择排序对字符串数组进行排序，我们仅需要对原始的实现中整型的比较操作和拷贝操作转化为字符串的比较和拷贝操作。

java 中字符串的比较操作使用 compareTo() 函数即可；C++/C 的比较操作可以使用 strcmp() 函数进行比较，拷贝可以使用 strcpy() 函数进行拷贝。这里就给大家提供 Java 的参考代码。

题外话：面试中，好多面试官会考察函数 strcmp() 与 strcpy() 的底层实现，对这个点不太熟悉的小禹禹可以了解一下，觉得没时间，希望景禹解析的，评论区留下你的足迹。

// 使用选择排序对字符串数组进行排序
static void selectionSort(String arr[],int n) 
{ 
 // 将有序部分和无序部分的界限 i 不断向后移动
 for(int i = 0; i < n - 1; i++) 
 { 
 
  // 在数组未排序部分找到最小的字符串
  int min_index = i; //保存最小的字符串的下标
  String minStr = arr[i]; //保存最小的字符串
  for(int j = i + 1; j < n; j++) 
  { 
   if(arr[j].compareTo(minStr) < 0) 
   { 
    minStr = arr[j]; 
    min_index = j; 
   } 
  } 
        // 将最小字符串与 位置为 i 的字符串进行交换
        if(min_index != i) 
        { 
            String temp = arr[min_index]; 
            arr[min_index] = arr[i]; 
            arr[i] = temp; 
        } 
 } 
}