选择排序以及改进方案
介绍:
选择排序是一种简单直观的排序算法,它的基本思想是在未排序序列中选择最小(或最大)的元素,然后将其放在已排序序列的末尾。选择排序的过程就像是每次从待排序的元素中选择最小的一个,依次放到已排序序列的末尾,直到整个序列有序。
图示:
选择排序性能
算法 | 最好时间 | 最坏时间 | 平均时间 | 额外空间 | 稳定性 |
---|---|---|---|---|---|
选择 | 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] > 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进行投诉反馈,一经查实,立即删除!
声明:本站所有文章,如无特殊说明或标注,均为本站原创发布。任何个人或组织,在未征得本站同意时,禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益,可联系我们进行处理。