15、数据结构和算法 - 实战:选择排序算法

1.1 什么是选择排序

选择排序是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。以此类推,直到全部待排序的数据元素排完。

1.2 算法基本思想

选择排序是每一次从待排序的数据元素中选出最小的一个元素,存放在序列的起始位置,直到全部待排序的数据元素排完。

分为三步

1、 从待排序序列中,找到关键字最小的元素;
2、 如果最小元素不是待排序序列的第一个元素,将其和第一个元素互换;
3、 从余下的N-1个元素中,找出关键字最小的元素,重复(1)、(2)步,直到排序结束;

 

1.3 选择排序复杂度分析

选择排序的时间复杂度是 :选择排序的时间复杂度并不低,可以看到是由两个for循环构成,所以他的时间复杂度肯定是   。但但是它比冒泡好在的是交换次数少,不过选择排序并不是一个稳定排序。

1.3 选择排序代码实现

package com.yuanxw.datastructure.chapter15;

import java.util.Arrays;

/**
 * 选择排序
 * 选择排序是每一次从待排序的数据元素中选出最小的一个元素,存放在序列的起始位置,直到全部待排序的数据元素排完。
 * - 分为三步:
 *     1. 从待排序序列中,找到关键字最小的元素
 *     2. 如果最小元素不是待排序序列的第一个元素,将其和第一个元素互换
 *     3. 从余下的 N - 1 个元素中,找出关键字最小的元素,重复(1)、(2)步,直到排序结束
 */
public class SelectionSort {
   
     
    public static void main(String[] args) {
   
     
        int[] array = new int[]{
   
     10, -7, 8, -2, 5, -4};
        System.out.println("【选择排序】前的结果:" + Arrays.toString(array));
        selectionSort(array);
        System.out.println("【选择排序】后的结果:" + Arrays.toString(array));
    }

    public static void selectionSort(int[] array) {
   
     
        // 第一个位置开始比较,找最小的元素。假设最小值为:0,在比较之后如果存在还有比array[0]更小的值,则进对min进行重新复制
        for (int i = 0; i < array.length - 1; i++) {
   
     
            int min = array[i];
            int minIndex = i;

            // 查找最小
            for (int j = 1 + i; j < array.length; j++) {
   
     
                if (min > array[j]) {
   
     
                    min = array[j];
                    minIndex = j;
                }
            }

            // 判断如果不存在最小的,则不需要进行重新赋值
            if (minIndex != i) {
   
     
                array[minIndex] = array[i];
                array[i] = min;
            }
        }
    }
}

执行结果:

【选择排序】前的结果:[10, -7, 8, -2, 5, -4]
【选择排序】后的结果:[-7, -4, -2, 5, 8, 10]