每一趟从待排序的数据元素中选出最小(或最大)的一个元素,顺序放在已排好序的数列的最后,直到全部待排序的数据元素排完。
算法描述
比如在一个长度为N的无序数组中,在第一趟遍历N个数据,找出其中最小的数值和第一个元素交换,第二趟遍历剩下的N-1个数据,找出其中最小的数值和第二个元素交换......第N-1趟遍历剩下的2个数据,找出其中最小的数值与第N-1个元素交换,至此选择排序完成。
常见的选择排序细分为简单选择排序,树形选择排序(锦标赛排序)、堆排序。本文仅介绍简单选择排序。
以下为简单选择排序的存储状态,其中大括号内为无序区,大括号外为有序序列:
初始序列:{ 49 27 65 97 76 12 38 }
第1趟: 12 { 27 65 97 76 49 38 } //找出最小元素12与第一元素49交换:
第2趟: 12 27 { 65 97 76 49 38 } //27不动
第3趟: 12 27 38 { 97 76 49 65 } //65与38交换
第4趟: 12 27 38 49 { 76 97 65 } //97与49交换
第5趟: 12 27 38 49 65 { 97 76 } //65与76交换
第6趟: 12 27 38 49 65 76 97 //97与76交换,排序完成
Java代码实现如下
private static void selectSort(int[] a) { for(int i = 0; i<a.length-1;i++){ int min = i; for(int j = i+1;j<a.length;j++){ //找到最小的 if(a[j]<a[min]) min = j; } //将最小的放到i的位置上; swap(i,min,a); System.out.print("第"+(i+1)+"趟选择排序:"); print(a); System.out.println(); } //排完序后; print(a); } private static void swap(int i,int j,int[] arr){ int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } private static void print(int[] a) { for(int i:a) System.out.print(i+" "); }
选择排序的另一种排序变种如下:
public class SelectSort { public static void main(String[] args) { int a[] = {1,2,6,9,3,8,5,4,0,7}; selectSort(a); } /** * 选择排序 * 基本思想:1.从i~a.length中选择一个最小的放在i的位置 * 2.以此迭代 * 3.i从0开始; * @param a */ private static void selectSort(int[] a) { for(int i=0;i<a.length;i++){ //找到最小 for(int j=i+1;j<a.length;j++){ if(a[i]>a[j]){ int temp = a[i]; a[i] = a[j]; a[j] = temp; } } System.out.print(" 第"+i+"趟选择排序:"); print(a); } } private static void print(int[] a) { for(int i:a) System.out.print(i+" "); System.out.println(); } }上述选择排序就是:
第 一次选择排序的过程如下(排行第0个元素,去上面排序中的i=0):
该选择排序就是每一次排序的每次比较都要交换元素;
算法分析
通过以上代码我们知道简单选择排序的算法复杂度为:平均时间复杂度:O(n2)
空间复杂度:O(1) (用于交换和记录索引)
稳定性
举个例子,序列5 8 5 2 9,我们知道第一遍选择第1个元素5会和2交换,那么原序列中2个5的相对前后顺序就被破坏了,所以选择排序不是一个稳定的排序算法。
相关推荐
(1) 完成5种常用内部排序算法的演示,5种排序算法为:快速排序,直接插入排序,选择排序,堆排序,希尔排序; (2) 待排序元素为整数,排序序列存储在数据文件中,要求排序元素不少于30个; (3) 演示程序开始,...
实现以下常用的内部排序算法并进行性能比较:"直接插入排序"," 折半插入排序"," 2—路插入排序"," 表插入排序"," 希尔排序"," 起泡排序"," 快速排序"," 简单选择排序"," 树形选择排序"," 堆排序"," 归并排序"," 链式...
冒泡排序 简单选择排序 c语言基础 排序算法 数组操作 排序算法实验 简单的c语言程序 排序算法输出
直接插入排序 选择排序 堆排序 归并排序 快速排序 冒泡排序等七种排序方法
选择排序 ss_sort(int e[],int n) 直接插入排序 ss_sort(int e[],int n) 冒泡排序 sb_sort(int e[],int n) 二路合并排序 Merge(int e[],int n) 对给定的数组E[N]={213,111,222,77,400,300,987,1024,632,555} 分别...
插入排序,选择排序,基数排序,冒泡排序的C++实现
选择排序、插入排序、冒泡排序以及快速排序和归并排序的C语言实现,绝对可用
用选择排序法对数组排序,选择排序用函数对立起来。
交换排序 选择排序 冒泡排序 插入排序
希尔排序,堆排序,快速排序,简单选择排序,插入排序,冒泡排序
选择排序法源代码,具体代码与解释,绝对能运行成功的,放心使用。
算法作业的线性选择排序 算法作业的线性选择排序 算法作业的线性选择排序
有一个模板类写出了快速排序,冒泡排序,插入排序,选择排序四种算法。用的是C++哦
用函数实现简单选择排序,并输出每趟排序的结果 Input 第一行:键盘输入待排序关键的个数n 第二行:输入n个待排序关键字,用空格分隔数据 Output 每行输出每趟排序的结果,数据之间用一个空格分隔 Sample Input 10...
插入排序、快速排序、选择排序、选择排序、内部排序方法的比较
7大排序算法(快速排序,冒泡排序,选择排序,归并排序,插入排序,希尔排序,堆排序)实现源码
冒泡排序,选择排序,插入排序,希尔排序,堆排序,归并排序,快速排序源码实现,里面有详细讲解,对新手应该有帮助
六种内部排序算法比较:直接插入排序、希尔排序、冒泡排序、快速排序、选择排序、堆排序。包含实验报告和源代码设计。
选择排序,比较常见的排序算法之一。这是两个例子,两个关于选择排序的例子。
该代码类实现了选择排序的可视化。 程序的关键点主要有两点: 1. 如何在页面上表示出排序程序的运行过程。 2. 如何将排序程序的运行过程和可视化排序结合起来,保持状态一致。 我的解决方法如下: 我采用了...