首页 > 算法 > 算法系列之一 选择排序

算法系列之一 选择排序

选择排序是从待排序的序列中选出最小的一个元素,将其跟已经有序的序列后面的元素交换位置,直到全部待排序的元素处理完。

设数组为a[0...n-1]
1、初始时,数组全为无序区为a[0..n-1]。令i=0
2、对于a[i],在a[i...n-1]中选择一个最小元素,并将其与a[i]交互。交换后a[0,i]就是有序的
3、i++重复第2步,直到处理完i==n-1,排序完成

void SelectSort(int a[], int n) 
{
     for (int i = 0; i < n; i++)
     {
          int maxIndex = i;
          for (int j = i + 1; j < n; j++)
          {
               if (a[j] > a[maxIndex]) 
               {
                    maxIndex = j;
               }
          }
          swap(a[i], a[maxIndex]);
     }
}

时间复杂度:
上述程序的原操作有赋值、比较及交换,显然基本操作应该取比较。总的比较次数显然是:(n-1)+(n-2)+(n-3)+…+1这是一个等差数列之和,结果是n(n-1)/2
选择排序平均时间复杂度为O(n*n)

稳定性:
不稳定的
序列5 8 5 2,我们知道第一遍选择第1个元素5会和2交换,那么原序列中2个5的相对前后顺序就被破坏了,所以选择排序不是一个稳定的排序算法。

(转载本站文章请注明出处 www.helloitworks.com ,请勿用于任何商业用途)

分类: 算法 标签:
  1. 本文目前尚无任何评论.
  1. 本文目前尚无任何 trackbacks 和 pingbacks.