在前面的博客中已经讲述了交换类的排序算法,这节中开始说说选择类的排序算法了,首先来看一下选择排序的算法思想;
选择排序的基本算法思想:
每一趟在 n-i+1 (i=1,2,3,……,n-1)个记录中选取关键字最小的记录作为有序序列中第i个记录。
简单选择排序:
设所排序序列的记录个数为n。i取1,2,…,n-1,从所有n-i+1个记录(Ri,Ri+1,…,Rn)中找出排序码最小的记录,与第i个记录交换。执行n-1趟 后就完成了记录序列的排序。
算法实现代码如下:
package exp_sort;
public class SimpleSelectSort {
static int i;
static int temp;
public static void selectSort(int array[]) {
for (i = 0; i < array.length; i++) {
int k = i; //记录当前位置
for (int j = i + 1; j < array.length; j++) {
if (array[j] < array[k]) { //找出最小的数,并用k指向最小数的位置
k = j;
}
}
//交换最小数array[k]与第i位上的数
if (k != i) {
temp = array[i];
array[i] = array[k];
array[k] = temp;
}
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int array[] = { 38, 62, 35, 77, 55, 14, 35, 98 };
selectSort(array);
for (int i = 0; i < array.length; i++) {
System.out.print(array[i] + " ");
}
System.out.println("\n");
}
}
算法分析:
在此排序过程中,需要移动记录的次数比较少。最好情况下,即待排序记录初始状态就已经是正序排列了,则不需要移动记录;最坏情况下,即待排序记录初始状态是按照逆序排列的,则需要移动次数最多是:3(n-1)。排序过程中需要进行的比较次数与初始状态下待排序的记录序列的排列情况无关。当i=1时,需要进行n-1次比较;当i=n时,共需要进行的比较次数是:n(n-1)/2,即比较操作的时间复杂度是:O(n^2),进行移动操作的时间复杂度为O(n);该排序是不稳定排序。
分享到:
相关推荐
数据结构与算法(Python) 一、引入概念 1-01算法引入 1-02 时间复杂度与大O表示法 1-03-最坏时间复杂度与计算规则 1-04-常见时间复杂度与大小关系 1-05-代码执行时间测量模块 1-06-Python列表类型不同操作的...
数据结构中个各种排序法,快速,直接插入,冒泡...
白话数据结构7大排序算法详解。
详细讲述了8中常见算法的原理及思想,并用JAVA进行了实现,代码中有详细的注释,解释了算法的实现逻辑和一些小技巧。
主要知识点 插入排序 直接插入排序 O(n2) 希尔排序 O(n(lbn)2) 选择排序 直接选择排序O(n2) 堆排序O(nlbn) 交换排序 冒泡排序O(n2) 快速排序O(nlbn) 二路归并排序O(nlbn) 基数排序O(mn)
主要介绍了java数据结构排序算法之树形选择排序,结合具体实例形式分析了java树形选择排序的原理、实现技巧与相关注意事项,需要的朋友可以参考下
数据结构教程》根据高等院校计算机专业数据结构课程的教学大纲要求,结合十年战斗在一线教授的丰富教学经验编写而成。全书按照课程的授课顺序,阐述了线性表、栈和队列、串和数组、树和二叉树、图、查找、排序等内容...
七、第七章作业答案本系列博客为《数据结构》(C语言版)的学习笔记(上课笔记),仅用于学习交流和自我复习数据结构合集链接: 《数据结构》C语言版(严蔚敏版) 全书
C语言数据结构 快速排序实例详解 一、快速排序简介 快速排序采用分治的思想,第一趟先将一串数字分为两部分,第一部分的数值都比第二部分要小,然后按照这种方法,依次对两边的数据进行排序。 二、代码实现 #...
堆排序
主要介绍了java数据结构与算法之简单选择排序,结合实例形式分析了选择排序的原理、实现方法与相关操作技巧,需要的朋友可以参考下
主要介绍了java数据结构排序算法之归并排序,结合具体实例形式详细分析了归并排序的原理、实现技巧与相关注意事项,需要的朋友可以参考下
此文档,包含了 树,二叉树,数据结构与算法,排序,哈希表等难点重点详解。希望对于学习有帮助。
8.4.1 简单选择排序 243 8.4.2 堆排序 244 8.5 二路归并排序 247 8.6 基数排序 248 8.7 外部排序 252 8.7.1 概念与流程 252 8.7.2 置换-选择排序 253 8.7.3 佳归并树 254 8.7.4 败者树 255 8.7.5 时间与空间复杂度...
主要介绍了java 数据结构之堆排序(HeapSort)详解及实例的相关资料,需要的朋友可以参考下
数据结构(C语言版)在选材与编排上,贴近当前普通高等院校“数据结构”课程的现状和发展趋势,符合新研究生考试大纲,内容难度适度,突出实用性和应用性。全书共7章,内容包括绪论,线性表,栈和队列,串、数组和...
最快的排序算法 腾讯算法面试题:64匹马8个跑道需要多少轮才能选出最快的四匹(详解)?,排序算法数据结构
【数据结构】八大排序(超详解+附动图+源码)(csdn)————程序