集团主站
欢迎来到成都达内官方网站!达内—美国上市公司 亿元级外企IT培训企业!
成都it培训哪家好
成都it培训哪家好
全国服务监督电话:15023458194  |   联系客服   |
当前位置:主页 > 培训课程 > Java >

成都java培训-选择排序:简单选择排序

发布者: 成都达内     浏览次数:     发布时间:2021-04-01 11:13:27

成都java培训:(1.1)选择排序的基本思想是:每一趟(例如第i趟)在后面n-i+1(i=1,2, ... , n)个待排序元素中选取关键字最小的元素,作为有序子序列的第i个元素,直到第n-1趟做完,待排序元素...

  1. 选择排序思想

  (1.1)选择排序的基本思想是:每一趟(例如第i趟)在后面n-i+1(i=1,2, ... , n)个待排序元素中选取关键字最小的元素,作为有序子序列的第i个元素,直到第n-1趟做完,待排序元素只剩下1个,就不用再选了。选择排序中的堆排序算法是重点内容。

  2. 简单选择排序的思想

  (2.1)从上面选择排序的思想中可以很直观第得出简单选择排序算法的思想:假设排序表为L[1 ... n], 第i趟排序即从L[i ... n]中选择关键字最小的元素与L[i] 交换,每一趟排序可以确定一个元素的最终位置,这样经过n-1趟排序就可以使得整个待排序表有序。

  3. 简单选择排序代码实现

  1 package cn.sun.it.review;

  2

  3 import java.util.Arrays;

  4 import java.util.Scanner;

  5

  6 public class SelectSort {

  7

  8 public static void main(String[] args) {

  9 System.out.println("请输入若干个整数,以逗号分隔:");

  10 Scanner sc = new Scanner(System.in);

  11 String strNums = sc.nextLine();

  12 String[] tempArrNums = strNums.split(",");

  13 int[] arr = new int[tempArrNums.length];

  14 for (int i = 0; i < arr.length; i++) {

  15 arr[i] = Integer.valueOf(tempArrNums[i]);

  16 }

  17 System.out.println("排序前:" + Arrays.toString(arr));

  18 selectSort_v1(arr);

  19 System.out.println("排序后:" + Arrays.toString(arr));

  20 }

  21

  22 private static void selectSort_v1(int[] arr) {

  23 int min;

  24 int temp;

  25 for(int i=0;i

  26 min = i; // 记录最小元素的位置

  27 for(int j=i+1;j

  28 if(arr[j]

  29 min = j; // 更新最小元素的位置

  30 }

  31 }

  32 if(min != i){ // 与第i个位置进行交换

  33 temp = arr[i];

  34 arr[i] = arr[min];

  35 arr[min] = temp;

  36 }

  37 }

  38 }

  39

  40 }

  4. 测试结果

  成都java培训-选择排序:简单选择排序

  5. 性能分析

  (5.1)空间效率:仅使用常数个辅助单元,故而空间效率为O(1);

  (5.2)时间效率:从上述代码中可以看出,在简单选择排序过程中,元素移动的操作次数很少,不会超过3(n-1)次,最好的情况是移动0次,此时对应的表已经有序;但元素间比较的次数与序列的初始状态无关,始终是n(n-1)/2次,所以时间复杂度始终是O(n2)

  (5.3)稳定性:在第i趟找到最小的元素后,和第i个元素交换,可能会导致第i个元素与其含有相同关键字元素的相对位置发生改变。例如,表L={2,2,1},经过一趟排序后,

  L={1,2,2},最终排序序列也是L={1,2,2},显然,2与2 的相对次序已经发生了变化,因此,简单选择排序是一个不稳定第排序方法。

(责任编辑:范老师)
最新开班
  • 成都Java培训班
    免费试听名额发放中...
  • 成都C++培训班
    免费试听名额发放中...
  • 成都PHP培训班
    免费试听名额发放中...
  • 成都网络工程培训班
    免费试听名额发放中...
  • 成都Unity3D培训班
    免费试听名额发放中...
  • 成都大数据培训班
    免费试听名额发放中...
  • 成都uid培训班
    免费试听名额发放中...
  • 成都会计培训班
    免费试听名额发放中...
  • 成都Python培训班
    免费试听名额发放中...
  • 成都嵌入式培训班
    免费试听名额发放中...
  • 成都web培训班
    免费试听名额发放中...
  • 成都软件测试培训班
    免费试听名额发放中...
在线留言
提交

校区地址:成都市锦江区东大街紫东楼端35号明宇金融广场19楼1906室

联系电话:15023458194

公交路线:芷泉街(18路;21路;43路;48路;104路;152路;335路 ) 地铁路线:东门大桥站(地铁2号线)

校区地址:成都市高新区奥克斯广场蜀锦路209号一楼商铺

联系电话:15023458194

公交路线:益州大道锦城大道口(18路;21路;43路;48路;104路;152路;335路 ) 地铁路线:孵化园(地铁1号线)

校区地址:成都锦江区东大街芷泉街229号东方广场C座3楼303

联系电话:15023458194

公交路线:芷泉街(188路;115路;515路;236路;505路;501路;84路 ) 地铁路线:东门大桥站(地铁2号线)

校区地址:成都市武侯区佳灵路3号红牌楼广场2号写字楼11楼1115号

联系电话:15023458194

公交路线:红牌楼东(11路;92路;100路;111路;139路;g28路;快速公交K1/K2) 地铁路线:红牌楼站(地铁3号线)

校区地址:成都市锦江区红星路二段70号四川日报大厦502-2

联系电话:15023458194

公交路线:市二医院站(6路;49路;102路;5路;37路;g92路;) 地铁路线:地铁市二医院(地铁3号线)

校区地址:成都市锦江区东大街芷泉段229号东方广场C座16层

联系电话:15023458194

公交路线:芷泉街(18路;21路;43路;48路;104路;152路;335路 ) 地铁路线:东门大桥站(地铁2号线)

校区地址:四川省成都市武侯区高新科技孵化园9号园区E座7楼

联系电话:15023458194

公交路线:益州大道锦城大道口(18路;21路;43路;48路;104路;152路;335路 ) 地铁路线:孵化园(地铁1号线)

了解达内动态
关注成都达内教育公众号

首页 | 关于达内 | 课程中心 | 专家师资 | 视频教程 | 学员空间 | 校企合作 | 新闻资讯 | 就业指导 | 网站地图

2016-2025 达内时代科技集团有限公司 版权所有 京ICP证8000853号-56 蜀ICP备18021046号-3