首页 > 其他 > 详细

秒懂算法2——选择排序(C#实现)

时间:2014-01-23 09:38:51      阅读:380      评论:0      收藏:0      [点我收藏+]

算法思路:

每趟走访元素揪出一个最小(或最大)的元素,和相应位置的元素交换。(用数组{6,9,13,2,4,64} 举例)

 

{},{6  9  13  【2】 4  64}       //第一趟,揪出2

2},{    9   13  6  4   64}             //把2和第一位的元素互换

{2},{    9    13  6 【4】  64}            //第二趟,揪出4

{2  4},{     13  6    9   64}       //把4和第二位的元素互换

... ... 

 

性质:

选择排序是一种原地排序(只有常数个元素存到数组以外的空间),最坏的时间复杂度,和平均时间复杂度都是n2。它是不稳定的排序算法

 

*选择排序和冒泡排序的区别:

它俩写起来很像,运行过程也有点像。但是性能上,选择排序要稍好一些,简单的理解就是冒泡排序总是在进行交换,而选择排序相比之下交换的次数少很多。

另,冒泡是稳定的,选择排序是不稳定的。

 

代码:

bubuko.com,布布扣
int[] SelectionSort1(int[] a)
 {
     int item;
     for (int i = 0; i < a.Length; i++)
     {
         int minIndex=i;              //记录最小元素的下标

         for (int j = i+1; j < a.Length; j++)   //遍历剩余元素
         {
             if (a[minIndex] > a[j])  minIndex = j; 
         }
         if (a[minIndex] != a[i]) 
         {
             item = a[i];
             a[i] = a[minIndex];
             a[minIndex] = item;
         }
     }
         return a;
 }
bubuko.com,布布扣

秒懂算法2——选择排序(C#实现)

原文:http://www.cnblogs.com/hydor/p/3530590.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!