数据结构和算法-10-选择排序

灰太狼 2022-01-12 07:51 180阅读 0赞

接着学习简单排序算法的第二种，叫选择排序。

**1.选择排序定义和优点**

选择排序（Selection Sort）是一种简单直观的排序算法。它的工作原理是这样的：  
首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中  
继续寻找最小（大）元素，然后放到已排序系列的末尾。依次类推，直到所有全是均排序完毕。

选择排序主要优点与数据移动有关。如果某个元素位于正确的最终位置上，则它不会被移动。选择排序  
每次交换一对元素，它们当中至少有一个将被移动到其他最终位置上，因此，对n个元素的表进行排序总共  
进行至多n-1此交换。在所有的完全依靠交换去移动元素的排序方法中，选择排序属于非常好的一种。

**2.选择排序图解分析过程**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTE1NDE5NDY_size_16_color_FFFFFF_t_70][]

从这个图来看，选择排序实际上把列表分成了左右的两部分，左边是已经排序好的部分，右边是没有排序的数列。第一次，13是最小，位置不用移动，第二次从13之外剩余数列中选择一个最小的数是27，然后把27拿出来，放到13的后面。依次类推，左边已经排序好的越来越多，右边未排序的越来越少，直到右边没有元素。

**3.选择排序代码实现**

先看看python代码实现

# coding:utf-8
    
    def select_sort(alist):
        """选择排序"""
        n = len(alist)
        for i in range(0, n-1):
            # 每次循环开始设置i 索引位置元素最小
            min_index = i
            for j in range(i + 1, n):
                # 判断，如果前面设置最小索引位置数 大于 当前循环数，重新设置最小索引
                if alist[min_index] > alist[j]:
                    min_index = j
            # 退出循环，开始交换位置
            alist[i], alist[min_index] = alist[min_index], alist[i]
    
    
    if __name__ == "__main__":
        alist = [17, 20, 93, 54, 77, 32, 45, 226]
        print(alist)
        select_sort(alist)
        print(alist)

注意上面，在退出内部循环中，交换位置，需要注意两点，第一点就是需要在退出内部循环才交换位置，第二个注意点就是是拿min\_index所处的元素和外层i中所处元素进行位置交换，而不是拿内层j位置元素进行交换。

[17, 20, 93, 54, 77, 32, 45, 226]
    [17, 20, 32, 45, 54, 77, 93, 226]

Java代码实现

import java.util.Arrays;
    
    public class SelectSort {
    
        public static void main(String[] args){
            int[] arr = {17, 20, 93, 54, 77, 32, 45, 226};
            System.out.println(Arrays.toString(arr));
            selectSort(arr);
            System.out.println(Arrays.toString(arr));
        }
    
        public static void selectSort(int[] arr){
            for(int i = 0; i < arr.length -1; i ++){
                // 每次进入内层循环之前，都把i所处位置元素假设最小的元素
                int min_index = i;
                for(int j = i + 1; j < arr.length; j++){
                    // 判断
                    if(arr[min_index] > arr[j]){
                        // 交换min_index
                        min_index = j;
                    }
                }
                // 退出内层循环，交换 arr[i] 和arr[min_index]位置
                int tmp = arr[i];
                arr[i] = arr[min_index];
                arr[min_index] =  tmp;
    
            }
        }
    }

运行结果

[17, 20, 93, 54, 77, 32, 45, 226]
    [17, 20, 32, 45, 54, 77, 93, 226]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTE1NDE5NDY_size_16_color_FFFFFF_t_70]: /images/20220109/7b8a774e0ea743cdb0eaa064f19a7aac.png