简单选择排序

简单选择排序(Simple Selection Sort)就是通过n-i次关键字间的比较,从n-i+1个记录中选出关键字最小的记录,并和第i(1≤i≤n)个记录交换之。

核心代码

 1 void SelectSort(int arr[], int len)
 2 {
 3     int i;
 4     int j;
 5     int min;
 6 
 7     //检测参数
 8     assert(arr!=NULL && len>0);
 9     
10     for(i=0; i<len-1; ++i)
11     {
12         min = i;
13         for(j=i+1; j<len; ++j)
14         {
15             if(arr[j] < arr[min])
16             {
17                 min = j;
18             }
19         }
20         //把最小值放在对应位置
21         if(min != i)
22         {
23             arr[min] = arr[min] ^ arr[i];
24             arr[i] = arr[min] ^ arr[i];
25             arr[min] = arr[min] ^ arr[i];
26         }
27     }
28 }

算法分析:

  最好时间复杂度:O(n^2)

  平均时间复杂度:O(n^2)

  最坏时间复杂度:O(n^2)

    空间复杂度:O(1)

      稳定性:不稳定

简单选择排序在性能上要略优于冒泡排序。

原文地址:https://www.cnblogs.com/chen-cai/p/7705830.html