老狗啃骨头之算法-选择排序
source link: http://www.veiking.cn/blog/1025-page.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
简单选择排序是一种相对简单直观的基础排序算法，每一次都做简单选择，每一次都选出最大或最小。选择排序的核心思想就是：在遍历的过程中，每次都选数据样本中最小的数据，放在首位。看起来简单纯朴吧，从第一个元素开始，每次都取剩余数据元素的最小个，我们小时候摆积木的玩的时候，都已经掌握的算法，质朴归真，哈哈哈
选择排序（Selection Sort）
我们这里说的选择排序，特指简单选择排序。这个选择排序也是一种相对简单直观的基础排序算法，选择选择，每一次都做简单选择，每一次都选出最大或最小。
选择排序的核心思想就是：在遍历的过程中，每次都选数据样本中最小的数据，放在首位。看起来简单纯朴吧，从第一个元素开始，每次都取剩余数据元素的最小个，我们小时候摆积木的玩的时候，都已经掌握的算法，质朴归真，哈哈哈。
1：从待排序数据元素中，找到最小元素，放置序列首位（与首位交换）；
2：从第一位元素开始，循环1行为，直至数据遍历结束，排序完成。
import java.util.Arrays;
/**
* @author :Veiking
* @version :2020年10月10日
* 说明 :选择排序算法
*/
public class SelectionSort {
/**
* 选择排序
* @param arrays
* @return
*/
public static int[] sort(int[] arrays) {
int min;
int temp;
// 从第一个元素开始，每一轮都会选出最小的元素下标，结下对剩余的重复操作，直至处理完毕
for(int i = 0; i < arrays.length; i++) {
min = i;
// 每次都找出最小的下标，赋予min
for(int j=i; jarrays[j]) {
min = j;
}
}
// 当min不等于i时，则交换，最小的元素即被放置在最前
if (i!=min) {
temp=arrays[i];
arrays[i]=arrays[min];
arrays[min]=temp;
}
//System.out.println("第"+i+"次排序操作结果："+Arrays.toString(arrays));
}
return arrays;
}
// 执行
public static void main(String[] args) {
int[] input = new int[]{3, 7, 2, 6, 1, 5, 4};
System.out.println("样本初始样本数据："+Arrays.toString(input));
int[] output = SelectionSort.sort(input);
System.out.println("选择排序结果数据："+Arrays.toString(output));
}
}
;>选择排序算法的基本性能，归纳如下图：
1、 时间复杂度
我们可以看到，选择排序算法的规则本身，就是一个一个来，众里挑一；并且每一趟在完全遍历完之前，是不能确定是否最大或者最小，于是乎，一个艰难的结论：选择排序的比较次数，与待排数据样本的初始序列没有任何关系。
所以，选择排序的时间复杂度，无论待排数据是否有序，都要比较n×(n-1)/2次，故好坏平均的时间复杂度都认为是O(n2)。
2、 空间复杂度
看代码可以了解到，这个选择排序，只需要两个临时变量，并不需要其他的额外计算存储空间，故空间复杂度为O(1)。
2、稳定性
喧杂排序的核心是每次都选最小，放置在最前头，但是每一次选中之后都要和首位的交换，这时候如果有元素与首位元素等值，这个换一下，谁前谁后就不好说了，所以选择排序是不稳定的算法。
Recommend
-
8
插入排序，一般是说直接插入排序，是一种最直观最简单的排序算法。插入排序的原理是依次将未排序的数据元素插入已完成排序的有序数列，如此往复，最终完成所有数据的排序。在插入排序中，往前遍历的时候，遇到等值的元素就直接插入结...
-
5
归并排序是一种非常典型的分治策略应用排序算法，简而概括：分而排之，合而并之。归并排序，据说是冯·诺伊曼在1945年首次提出。冯·诺伊曼，是现代计算机科学发展史上开天辟地的大佬之一，不单单是计算机领域，这哥们在整个数学、量子...
-
8
老狗啃骨头之数据结构-栈和队列_老狗啃骨头_Veiking百草园-知识点滴,日常分享 栈和队列也是比较常见的数据结构，它们是比较特殊的线性表。相对于数组和链表，栈和队列是一种更具特性的场景应用，栈和队列都可...
-
4
冒泡排序是交换排序，是一种简单直观的排序算法。冒泡的算法原理是逐次循环遍历，比较两个相邻的元素，将小的（或大的）往前调。这样，每一轮都能得到一个最小的（或最大的），剩下的重复这个操作，最后完成排序。这个算法的名字，每...
-
5
老狗啃骨头之算法-排序算法总结_老狗啃骨头_Veiking百草园-知识点滴,日常分享 关于排序的算法，还有很多种。还有一些排序算法的思想，在不同的使用场景下再结合其它的算法逻辑，又可以衍生出新的算法设计。比...
-
6
基数排序是一种不在数据值本身之间比较的排序算法，而是通过数据按位数“切割”对比，从而实现排序的算法，所以基数排序也被认为是一种典型的非比较排序算法。在实际运用中，基数排序的使用场景不局限于整数，凡是整数可以表达的，或者...
-
6
快速排序，又称分区交换排序，简称快排。它也是一种交换排序，它是一种在处理大量数据方面有优势的算法。当数据量巨大的时候，冒泡排序这种中规中矩，挨次遍历逐个对比的玩法，估计会让人抓毛的，于是据说在公元1960年，一位叫东尼·霍...
-
5
天地玄黄，宇宙洪荒……千年以前，南梁周大侍郎，用一夜白头给我们留下了包罗万象又朗朗上口的童谣，得以千年唱诵，这是古人原始纯真的智慧。但浩瀚如宇宙，细微如尘沙，世间如此繁杂，计算机是搞不懂的，计算机的一零世界努力模拟，也...
-
4
老狗啃骨头之算法-八大排序算法_老狗啃骨头_Veiking百草园-知识点滴,日常分享 排序，就是将一组无序的数据，按照一定规则，使其有序化排列。排序时是否根据比较来决定元素间的相对次序，还可以分为比较类排序...
-
5
老狗啃骨头之数据结构-小说算法_老狗啃骨头_Veiking百草园-知识点滴,日常分享 一般说，随着数据结构复杂度和解决问题的复杂度的增长，时间复杂度也是随之增长的。在相同的资源条件下，空间复杂度和时间复杂度...
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK