数据结构------简单选择排序 C++ 实现

小咪咪 2022-04-03 09:46 216阅读 0赞

*  ## 简单选择排序是一种选择排序。 ##
 *  ## 选择排序：每趟从待排序的记录中选出关键字最小的记录，顺序放在已排序的记录序列末尾，直到全部排序结束为止。 ##

### (1)从待排序序列中，找到关键字最小的元素； ###

### (2)如果最小元素不是待排序序列的第一个元素，将其和第一个元素互换； ###

### (3)从余下的 N - 1 个元素中，找出关键字最小的元素，重复(1)、(2)步，直到排序结束。 ###

*  ## 简单选择排序的时间复杂度是 O(n\*n）；空间复杂度为 O(1)。 ##

### **以下是C++源代码：** ###

#include<iostream> 
    using namespace std;
    #define MAXSIZE 100
    typedef struct 
    {
    	int key;
    	int otherinfo;
    }RedType;
    typedef struct
    {
    	RedType r[MAXSIZE+1];
    	int length;
    }SqList;
    void SelectSort(SqList &L)
    {
    	for(int i=1;i<L.length;++i)	//在 L.r[i...L.length] 中选择关键字最小的记录 
    	{
    		int k=i;
    		for(int j=i+1;j<=L.length;++j)
    			if(L.r[j].key<L.r[k].key)	k=j;// k 指向此趟排序中关键字最小的记录 
    		if(k!=i)	//交换 r[i] 与 r[k] 
    		{	//在 i 所指的元素不是最小纪录的情况下 
    			//int t;
    			L.r[0]=L.r[i];
    			L.r[i]=L.r[k];
    			L.r[k]=L.r[0];
    		}
    	}
    }
    int main()
    {
    	SqList L;
    	int n;
    	cout<<"请输入记录的个数："<<endl;
    	cin>>n;
    	for(int i=1;i<=n;i++)
    		cin>>L.r[i].key;
    	L.length=n;
    	for(int i=1;i<=L.length;i++)
    		cout<<L.r[i].key<<"  ";
    	cout<<endl;
    	SelectSort(L);
    	for(int i=1;i<=L.length;i++)
    		cout<<L.r[i].key<<"  ";
    	cout<<endl;
    	return 0;
    }

*  ### 运行结果： ###

### 例如：输入   6  （记录个数） ###

###            12    3    4     77    80     20 ###

### 输出为 ###

###  12    3    4     77    80     20（原序列） ###

###   3     4    12    20    77    80      ###

## **另一种实现直接选择排序的源代码（不用结构体，用数组实现）：** ##

#include<iostream>
    using namespace std;
    int s[10000];
    int main()
    {
    	int n,i,j;
    	cout<<"请输入记录的个数："<<endl;
    	cin>>n;
    	for(i=1;i<=n;i++)
    		cin>>s[i];
    	for(i=1;i<n;i++)
    	{
    		int k=i;
    		for(j=i+1;j<=n;j++)
    		{
    			if(s[j]<s[k])
    				k=j;
    		}
    		if(k!=i)
    		{
    			int t;
    			t=s[i];
    			s[i]=s[k];
    			s[k]=t;
    		}
    	}
    	for(i=1;i<=n;i++)
    		cout<<s[i]<<"  ";
    	cout<<endl;
    	return 0;
    }

### 运行结果和上面第一种方法一样。 ###