C++数据结构与STL--选择排序

￡神魔★判官ぃ 2021-12-14 10:27 252阅读 0赞

**注：本系列笔记来源于：C++数据结构与应用标准模板库（虽是10年前出版的，个人认为还可以，于是整理数据结构的知识时选了它）**

**1.使用选择排序排序整数数组50，20，40，75，35**

**\*外部循环对表进行n-1次遍历。pass控制变量的范围0-n-2  
\*对于每次重复过程，都有一个内部循环扫描arr\[pass\]到arr\[n-1\]的无序子表，并判定最小元素的下标。  
\*只有最小元素的下标(smallIndex)不等于pass，才交换arr\[pass\]和arr\[smallIndex\];  
![20130725210855015][]  
  
  
  
  
实现代码：  
  
template<typename T>  
//对长度为n的数组进行选择排序  
 void selectSort(T arr\[\],int n)   
 \{   
  
  
 int pass=0;//控制外层循环  
int smallIndex=0;//记录子表最小元素的下标  
int j=0;//控制内层循环  
for( ;pass<n-1;pass++) //pass控制外层循环，共n-1次  
\{   
smallIndex=pass; //假设每次外层子循环都是第一个数最小  
for(j=pass+1;j<n;j++)  
\{   
if(arr\[smallIndex\]>arr\[j\])  
\{   
smallIndex=j;//每找到一个更小的元素，就记录下该元素的下标   
\}  
\}  
  
  
if(smallIndex!=pass)//交换arr\[pass\],arr\[smallIndex\]   
\{   
 T tem;  
 tem=arr\[pass\];  
 arr\[pass\]=arr\[smallIndex\];  
 arr\[smallIndex\]=tem;  
\}  
\}  
  
  
 \}**

**template<typename T>**

**//打印长度为n的数组内容**

**void print(T arr\[\],int n)  
\{   
for(int i=0;i<n;i++)  
\{   
cout<<arr\[i\]<<ends;  
\}  
\}  
  
  
 int main(void)  
 \{   
 int arr\[\]=\{50,20,40,75,35\};  
 selectSort(arr,5);  
print(arr,5);  
 cout<<endl;  
  
 string str\[\]=\{"hello","how","are","you"\};  
 selectSort(str,4);  
 print(str,4);  
  
  
 return 0;  
 \}  
  
  
output:  
  
20 35 40 50 75  
are hello how you**

[20130725210855015]: /images/20211214/11c876f6f725452fb9630bea51915566.png