选择排序以及改进方案

介绍

选择排序是一种简单直观的排序算法,它的基本思想是在未排序列中选择最小(或最大)的元素然后将其放在已排序序列末尾。选择排序过程就像是每次从待排序的元素中选择最小一个,依次放到已排序序列末尾,直到整个序列有序

图示:

gif01

选择排序性能

算法 最好时间 最坏时间 平均时间 额外空间 稳定
选择 O(n2) O(n2) O(n2) 1 稳定

普通版本的选择排序

通过简单的两层遍历,就可以实现了:

for (int i = 0; i < array.length - 1; i++) {
    int minIndex = i; // 假设当前位置元素最小
    for (int j = i + 1; j < array.length; j++) {
        if (array[j] < array[minIndex]) {
            minIndex = j; // 在未排序的部分找到最小元素索引
        }
    }
    // 将找到的最小元素当前位置交换
    int temp = array[i];
    array[i] = array[minIndex];
    array[minIndex] = temp;
}

改进

在每次遍历中,不仅找到未排序部分最小元素,还找到未排序部分最大元素然后分别将最小元素放在已排序部分开头,将最大元素放在已排序部分末尾。这样每次遍历可以减少一半的交换次数

public class SelectionSort {

    public static void improvedSelectionSort(int[] array) {
        for (int i = 0; i < array.length / 2; i++) {
            int minIndex = i; // 假设当前位置的元素是最小
            int maxIndex = i; // 假设当前位置的元素是最大
            for (int j = i + 1; j < array.length - i; j++) {
                if (array[j] < array[minIndex]) {
                    minIndex = j; // 在未排序的部分中找到最小元素的索引
                } else if (array[j] &gt; array[maxIndex]) {
                    maxIndex = j; // 在未排序的部分中找到最大元素的索引
                }
            }
            // 将找到的最小元素与当前位置交换
            int tempMin = array[i];
            array[i] = array[minIndex];
            array[minIndex] = tempMin;
            // 将找到的最大元素与当前位置交换
            int tempMax = array[array.length - i - 1];
            array[array.length - i - 1] = array[maxIndex];
            array[maxIndex] = tempMax;
        }
    }

    public static void main(String[] args) {
        int[] arr = { 64, 34, 25, 12, 22, 11, 90 };

        System.out.println("原始数组:");
        printArray(arr);

        improvedSelectionSort(arr);

        System.out.println("排序后的数组:");
        printArray(arr);
    }

    // 辅助方法,用于打印数组
    public static void printArray(int[] array) {
        for (int i : array) {
            System.out.print(i + " ");
        }
        System.out.println();
    }
}

原文地址:https://blog.csdn.net/m0_66492535/article/details/134674757

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任

如若转载,请注明出处:http://www.7code.cn/show_43826.html

如若内容造成侵权/违法违规/事实不符,请联系代码007邮箱suwngjj01@126.com进行投诉反馈,一经查实,立即删除

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注