选择排序

我个人认为冒泡排序和选择排序真是一对孪生兄弟,因为我总感觉这两个算法的思想很像,时间复杂度也相同。但其实他们的算法思想是不同的。

冒泡排序是从前往后逐个比较相邻的元素,从而使得最大的元素”冒”到数组的最右边。

而选择排序则是将某一个元素与其余所有元素相比较,选出一个最小/最大的元素放在当前位置。

代码如下:

T>
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void SelectSort(vector<T>& v)
{
if(v.size()<=1)
return;
int length=v.size();
int i,j;
for(i=0;i<length;++i)
{
for(j=i+1;j<length;++j)
{
if(-1==compair(v[j],v[i]))
{
swap(v[j],v[i]);
}
}
}
}

<!--more-->

这里说过,”所有基于位置的比较排序的时间复杂度都逃不了O(n2)的厄运”,所以选择排序的时间复杂度同样也是O(n<sup>2</sup>)。

同样来看看可以改进的地方:

**改进一:如果一趟排序中没有进行交换,则表明排序完成。**具体算法再冒泡排序中说过,再次不在表述。

改进二:在每一趟排序中进行双向选择。

代码如下:

T>
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void SelectSort(vector&lt;T&gt;&amp; v)
{
if(v.size()&lt;=1)
return;
int length=v.size();
int i,j;
for(i=0;i&lt;length;++i)
{
for(j=i+1;j&lt;length-i;++j)
{
int ma=max(v,i,j,length-i-1);
int mi=min(v,i,j,length-i-1);
swap(v[i],v[mi]);
if(1==compair(v[ma],v[length-i-1]))
swap(v[length-i-1],v[ma]);
}
}
}

以上

如果你有任何想法或是可以改进的地方,欢迎和我交流!

完整代码及测试用例在github上:点我前往