c++实现选择排序的几种方式

╰半橙微兮° 2023-06-10 06:22 72阅读 0赞

#                                                一、选择排序 #

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNDc5NDY0_size_16_color_FFFFFF_t_70][]

### 第一种类型： ###

**思路：10,15,20,1,2,3,6,45,21,22   由当前位置的后一个位置，去寻找最小的然后与当前位置做一次交换即可，也就是，现在位置是0数字是10，现在向后找最小的，每次向后找，与一开始的值比较，直到拿到最小值，然后与当前的位置作一次交换，最后执行多次，直到结束。**

#include<iostream> 
    #include<algorithm>
    using namespace std;
    void selectSort(int arr[] ,int n){
    	for(int i=0;i<n;i++){
    		//寻找[i,n)区间里的最小值 
    		int minIndex = i;  
    		for(int j=i+1;j<n;j++){
    			if(arr[j]<arr[minIndex]){
    				minIndex = j;//更新索引		 
    			}	
    		}
    		//找到最小位置的索引，然后交换最小位置的数和当前的位置的数
    		swap(arr[i],arr[minIndex]); 
    	}
    }
    int main(){
    	int a[10]={10,15,20,1,2,3,6,45,21,22};
    	selectSort(a,10);
    	for(int i=0;i<10;i++)
    		cout<<a[i]<<" ";	
    	cout<<endl;
    	return 0;
    }

### 第二、改进的可以输入任意类型（加入泛型）： ###

#include<iostream> 
    #include<algorithm>
    using namespace std;
    template<typename T> //泛型 
    void selectSort(T arr[] ,int n){
    	for(int i=0;i<n;i++){
    		//寻找[i,n)区间里的最小值 
    		int minIndex = i;  
    		for(int j=i+1;j<n;j++){
    			if(arr[j]<arr[minIndex]){
    				minIndex = j;//更新索引		 
    			}	
    		}
    		//找到最小位置的索引，然后交换最小位置的数和当前的位置的数
    		swap(arr[i],arr[minIndex]); 
    	}
    }
    int main(){
    	//整数排序 
    	int a[10]={10,15,20,1,2,3,6,45,21,22};
    	selectSort(a,10);
    	for(int i=0;i<10;i++)
    		cout<<a[i]<<" ";	
    	cout<<endl;
    	//float类型 
    	float b[4] = {1.1,2.3,0.8,3.6};
    	selectSort(b,4);
    	for(int i=0;i<4;i++)
    		cout<<b[i]<<" ";
    	cout<<endl;
    	// 字符串类型 
    	string c[5]={"wo","xi","huan","ni","xiao"};
    	selectSort(c,5);
    	for(int i=0;i<5;i++)	
    		cout<<c[i]<<" ";
    	cout<<endl;
    	return 0;
    }

**结果：**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNDc5NDY0_size_16_color_FFFFFF_t_70 1][]

###  第三、使用自定义类型进行排序： ###

**定义了一个.h文件实现自定义排序：**

**Student.h**

#include<iostream> 
    #include<algorithm>
    using namespace std;
    struct Student{
    	string name;
    	int score;
    	bool operator<(const Student &otherStudent){
    		return score <otherStudent.score;
    	}
    	friend ostream &operator<<(ostream &os,Student &student){
    		os<<"Student: " <<student.name<<" "<<student.score<<endl;
    		return os;
    	}
    };

**main.cpp**

#include<iostream> 
    #include<algorithm>
    #include "Student.h"
    using namespace std;
    template<typename T> //泛型 
    void selectSort(T arr[] ,int n){
    	for(int i=0;i<n;i++){
    		//寻找[i,n)区间里的最小值 
    		int minIndex = i;  
    		for(int j=i+1;j<n;j++){
    			if(arr[j]<arr[minIndex]){
    				minIndex = j;//更新索引		 
    			}	
    		}
    		//找到最小位置的索引，然后交换最小位置的数和当前的位置的数
    		swap(arr[i],arr[minIndex]); 
    	}
    }
    int main(){
    	Student d[4] = {
       {"A",10},{"B",50,},{"C",5},{"D",1}};
    	selectSort(d,4);
    	for(int i=0;i<4;i++)	
    		cout<<d[i]<<" ";
    	cout<<endl;
    	return 0;	
    	
    	
    }

结果：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNDc5NDY0_size_16_color_FFFFFF_t_70 2][]

###  第四、使用代码来生成随机数测试算法的用例： ###

### **SortTestHelper.h** ###

#include<iostream> 
    #include<algorithm>
    #include<ctime> 
    #include<cassert> 
    using namespace std;
    namespace SortTestHelper{
    	//生成n个随机数组，每个元素的随机范围为[rangeL,rangeR] 
    	int * generatorRandomArray(int n,int rangeL,int rangeR){
    		//保证范围左边小于右边的 
    		assert(rangeL<rangeR);
    		int *arr = new int [n];
    		//引入随机种子 
    		srand(time(NULL));
    		for(int i=0;i<n;i++)
    			arr[i] = rand()%(rangeR-rangeL+1)+rangeL;
    		return arr;	
    	}	
    }

**main.cpp**

#include<iostream> 
    #include<algorithm>
    #include "SortTestHelper.h"
    using namespace std;
    
    template<typename T> //泛型 
    void selectSort(T arr[] ,int n){
    	for(int i=0;i<n;i++){
    		//寻找[i,n)区间里的最小值 
    		int minIndex = i;  
    		for(int j=i+1;j<n;j++){
    			if(arr[j]<arr[minIndex]){
    				minIndex = j;//更新索引		 
    			}	
    		}
    		//找到最小位置的索引，然后交换最小位置的数和当前的位置的数
    		swap(arr[i],arr[minIndex]); 
    	}
    }
    int main(){
    	
    	//随机数生成
    	int n=1000;
    	int *arr = SortTestHelper::generatorRandomArray(n,0,n);
    	selectSort(arr,n);
    	for(int i=0;i<n;i++)	
    		cout<<arr[i]<<" ";
    	cout<<endl;
    	//因为 generatorRandomArray使用的new开辟了空间，需要释放 
    	delete []arr; 
    
    	return 0;	
    	
    	
    }

**结果：**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNDc5NDY0_size_16_color_FFFFFF_t_70 3][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNDc5NDY0_size_16_color_FFFFFF_t_70]: /images/20230531/31ab6b92b7fc4a9e8e4d45f2aad3c5b4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNDc5NDY0_size_16_color_FFFFFF_t_70 1]: /images/20230531/e1d0cca45ca042479f464e67135a5809.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNDc5NDY0_size_16_color_FFFFFF_t_70 2]: /images/20230531/c2df0cbe8b694cc594bc641245c736cd.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNDc5NDY0_size_16_color_FFFFFF_t_70 3]: /images/20230531/d95414a170c24ac7a88a29a80421b846.png