选择排序法的C/C++实现，及库函数sort等排序函数的使用

野性酷女 2022-02-04 03:21 219阅读 0赞

1、介绍：

<table> 
 <tbody> 
  <tr> 
   <th>分类</th> 
   <td><a href="https://zh.wikipedia.org/wiki/%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95" rel="nofollow">排序算法</a></td> 
  </tr> 
  <tr> 
   <th>数据结构</th> 
   <td><a href="https://zh.wikipedia.org/wiki/%E6%95%B8%E7%B5%84" rel="nofollow">数组</a></td> 
  </tr> 
  <tr> 
   <th>最坏时间复杂度</th> 
   <td><em>О(n²)</em></td> 
  </tr> 
  <tr> 
   <th>最优时间复杂度</th> 
   <td><em>О(n²)</em></td> 
  </tr> 
  <tr> 
   <th>平均时间复杂度</th> 
   <td><em>О(n²)</em></td> 
  </tr> 
  <tr> 
   <th>最坏空间复杂度</th> 
   <td><em>О(n)</em>&nbsp;total,&nbsp; &nbsp; <em>O(1)</em>&nbsp;辅助</td> 
  </tr> 
 </tbody> 
</table>

2、算法：（比如递增排序）

第一步：在未排序的 n 个数中找到最小数，将它与 a\[0\] 交换，查找范围：a\[0\]~a\[n-1\]

第二步：在未排序的（n-1）个数中找到最小数，将它与 a\[1\] 交换，查找范围：a\[1\]~a\[n-1\]

.......

第n-1步：在未排序的 2 个数中找到最小数，将它与 a\[n-2\] 交换，查找范围：a\[n-2\]~a\[n-1\]

重：选择排序每次交换一对元素，它们当中至少有一个将被移到其最终位置上，对![n][]个元素的表进行排序总共进行至多![\{\\displaystyle n-1\}][displaystyle n-1]次交换。

C语言：

void swap(int *a,int *b) //交換兩個元素的值
    {
        int temp = *a;
        *a = *b;
        *b = temp;
    }
    void selection_sort(int arr[], int len) 
    {
        int i,j;
    
    	for (i = 0 ; i < len - 1 ; i++) 
        {
    		int min = i;
    		for (j = i + 1; j < len; j++)     //与所有未排序的元素比较
    			if (arr[j] < arr[min])    //找到目前最小值
    				min = j;    //记录最小值
    	   	swap(&arr[min], &arr[i]);    //做交換
    	}
    }

C++语言：

template<typename T> //整數或浮點數皆可使用
    void selection_sort(std::vector<T>& arr) 
    {
    	for (int i = 0; i < arr.size() - 1; i++) 
        {
    		int min = i;
    		for (int j = i + 1; j < arr.size(); j++)
    			if (arr[j] < arr[min])
    				min = j;
    		std::swap(arr[i], arr[min]);
    	}
    }

在实际的编程中，较多使用C++的库函数：

（1）**sort函数**：用于排序，使用时需加上头文件“\#include<algorithm>" 和”using namespace std;“

使用方式：sort（首元素地址(必填)，尾元素地址的**下一个**地址(必填)，比较函数(非必填)）；

若不写比较函数，则**默认**对前面的区间**递增排序**

第三个可选项是 可自定义的**cmp函数**，即人为的指定比较规则，对于sort函数，重点在于cmp函数的编写

实例：

对char型数组从大到小排序:

#include<stdio.h>
    #include<algorithm>
    using namespace std;
    bool cmp(char a,char b)
    {
        return a>b;  //可以理解为当a>b时,把a放在b前面
    }
    
    int main()
    {
        char c[]={'w','u','y','a','x','i','n'};
        sort(c,c+7,cmp);
        for(int i=0;i<7;i++)
        {
            printf("%2d",c[i]);
        }
    }

2、strcmp：按字典序，返回两个**字符串**大小的比较结果 （一个字符一个字符的依次比较）

使用：strcmp(字符串1，字符串2)，将字符串存入数组中，直接使用数组名即可。

[n]: https://wikimedia.org/api/rest_v1/media/math/render/svg/a601995d55609f2d9f5e233e36fbe9ea26011b3b
[displaystyle n-1]: https://wikimedia.org/api/rest_v1/media/math/render/svg/fbd0b0f32b28f51962943ee9ede4fb34198a2521