网站建设购销合同,配件网站模板,万网登录,手游托在什么网站申请直接插入排序(Selection Sort)算法 1.基本思想#xff1a; 选择排序#xff08;Selection sort#xff09;是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小#xff08;或最大#xff09;的一个元素#xff0c;存放在序列的起始位置#xf… 直接插入排序(Selection Sort)算法 1.基本思想 选择排序Selection sort是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小或最大的一个元素存放在序列的起始位置直到全部待排序的数据元素排完。 选择排序是不稳定的排序方法比如序列[5 5 3]第一次就将第一个[5]与[3]交换导致第一个5挪动到第二个5后面。 n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果 ①初始状态无序区为R[1..n]有序区为空。 ②第1趟排序 在无序区R[1..n]中选出关键字最小的记录R[k]将它与无序区的第1个记录R[1]交换使R[1..1]和R[2..n]分别变为记录 个数增加1个的新有序区和记录个数减少1个的新无序区。 …… ③第i趟排序 第i趟排序开始时当前有序区和无序区分别为R[1..i-1]和R(i..n。该趟排序从当前无序区中选出关键字最小的记录 R[k] 将它与无序区的第1个记录R交换使R[1..i]和R分别变为记录个数增加1个的新有序区和记录个数减少1个的新无 序区。 基本方法 1. 算法完成需要 n - 1 趟排序按照算法的描述n - 1 趟排序之后数组中的前 n - 1 个元素已经处于相应的位置第 n 个元素也处于相应的位置上。 2. 第 i 趟排序实际上就是需要将数组中第 i 个元素放置到数组的合适位置这里需要一个临时变量 j 来遍历序列中未 排好序的那些元素另一临时变量 d 来记录未排好序的那些元素中值最小的元素的下标值 3. 一趟遍历开始时令 d i假定未排序序列的第一个元素就是最小的元素遍历完成后变量 d 所对应的值就是值 最小的元素判断 d 是否是未排序序列的第一个元素如果是则不需要交换元素如果不是则需要交换array[d] 和 array[i]。 4. 此方法是不稳定排序算法可对数组{a1 49a2 38, a3 65, a4 49, a5 12, a6 42} 排序就可以看出排序 完成后 a1 和 a4的相对位置改变了。 5. 此方法移动元素的次数比较少但是不管序列中元素初始排列状态如何第 i 趟排序都需要进行 n - i 次元素之间的 比较因此总的比较次数为1 2 3 4 5 . . . n - 1 n(n-1)/2, 时间复杂度是 O(n^2). 2.时间复杂度 3.模拟动画
http://v.youku.com/v_show/id_XMjU4NTY5NTcy.html
4.Java 代码 // 简单选择排序算法public static void selectSort(int a[]) {for (int i 0; i a.length; i) {int min a[i];int n i;// 最小数的索引for (int j i 1; j a.length; j) {if (a[j] min) {// 找出最小的数min a[j];n j;}}a[n] a[i];a[i] min;}}
