排序算法入门之简单选择排序

本是古典何须时尚 2022-05-26 12:07 217阅读 0赞

# 简单选择排序 #

简单选择排序是最简单直观的一种算法，基本思想为每一趟从待排序的数据元素中选择最小（或最大）的一个元素作为首元素，直到所有元素排完为止，简单选择排序是不稳定排序。

在算法实现时，每一趟确定最小元素的时候会通过不断地比较交换来使得首位置为当前最小，交换是个比较耗时的操作。其实我们很容易发现，在还未完全确定当前最小元素之前，这些交换都是无意义的。我们可以通过设置一个变量min，每一次比较仅存储较小元素的数组下标，当轮循环结束之后，那这个变量存储的就是当前最小元素的下标，此时再执行交换操作即可。代码实现很简单，一起来看下。

简单选择排序通过上面优化之后，无论数组原始排列如何，比较次数是不变的；对于交换操作，在最好情况下也就是数组完全有序的时候，无需任何交换移动，在最差情况下，也就是数组倒序的时候，交换次数为n-1次。综合下来，时间复杂度为O(n2)

其中注意两个数交换方法：

一.建立临时变量

1.普通的方法：

思路简介：建立一个临时变量，通过temp=a,a=b,b=temp来实现交换。

缺点：这只是一种假交换，由于这只是在函数内部临时变量间的交换，所以当函数退出，函数栈帧被释放，原本的值并没有交换。

具体方法：

int swap(int m,int n)

int  z=m;                                                            //通过建立z这个临时变量来交换\_x,\_y  
                                       m=n;  
                                       n=z;  
                                      printf("%d %d",m,n);  
                                      return 0;

2.指针的方法：

思路简介：取两个数的地址，在swap方法中再用指针指向地址交换，这时候为数值交换（函数调用结束后原空间的值也得到了交换）。

具体方法：

int swap(int \*\_x,int \*\_y)                                     //主函数中把两个数的地址传过来  
                                  \{  
                                       int  tmp = \*\_x;                                                  //定义中间变量 然后交换两个数  
                                       \*\_x = \*\_y;  
                                      \*\_y = tmp;  
                                      printf("%d %d",\*\_x,\*\_y);  
                                   \}

代码如下：

<pre name="code" class="cpp">#include <iostream>  
    void swap0(int a,int b)  
    {  
        int temp;  
        temp=a;  
        a=b;  
        b=temp;  
    } 
    
    void swap0(int &a,int &b)  
    {  
        int temp;  
        temp=a;  
        a=b;  
        b=temp;  
    } 
    
    void swap2(int *a ,int *b)  
    {  
        int temp;  
        temp=*a;  
        *a=*b;  
        *b=temp;  
    }  
      
    int main()  
    {  
        using namespace std;  
        int s1,s2;  
        cin>>s1;  
        cin>>s2;  
        swap0(s1,s2);  
        cout<<s1<<" ";  
        cout<<s2<<endl;  
        swap2(&s1,&s2);  
        cout<<s1<<" ";  
        cout<<s2<<endl;  
        swap1(s1,s2);
        cout<<s1<<" ";  
        cout<<s2; 
    	return 0;
    }

总结：void swap0(int a,int b)  按值传递，这只是一种假交换，由于这只是在函数内部临时变量间的交换，所以当函数退出，函数栈帧(栈中变量使用结束后，自动擦除)被释放，原本的值并没有交换。

而void swap1(int &a,int &b) 按引用传值，是实参的两个变量的别名，这时候的交换，实质上也就是实参发生交换

void swap2(int \*a,int \*b) 按指针传递，将实参的地址传给形参的两个变量

![70][]

![70 1][]

方法2 不用中间变量

直接交换，不利用中间变量：
    #include<iostream>
    using namespace std;
    int main()
    {
        int a,b;
        cout<<"Please input two numbers:"<<endl;
        cin>>a>>b;
        a = a + b;         //但是加法可能会最终导致溢出
        b = a - b;
        a = a - b;
    
        cout<<"After changing:"<<endl;
        cout<<a<<" "<<b<<endl;
    
        system("pause");
        return 0;
    }

或者采用“异或”：
    
    #include<iostream>
    using namespace std;
    int main()
    {
        int a,b;
        cout<<"Please input two numbers:"<<endl;
        cin>>a>>b;
        a = a^b;
        b = a^b;
        a = a^b;
        // b ^= a ^= b ^= a; // 可以简写
    
        cout<<"After changing:"<<endl;
        cout<<a<<" "<<b<<endl;
    
        system("pause");
        return 0;
    }

采用指针，并且不用临时变量：
    
    #include<iostream>
    using namespace std;
    
    void change(int *a, int *b)  
    {  
        *a = *a + *b;    //这里同理也可以换成“异或”
        *b = *a - *b;  
        *a = *a - *b;  
    }
    int main()
    {
        int a,b;
        cout<<"Please input two numbers:"<<endl;
        cin>>a>>b;
        change(&a,&b);
    
        cout<<"After changing:"<<endl;
        cout<<a<<" "<<b<<endl;
    
        system("pause");
        return 0;
    }

在C++中支持模板操作，所以可以利用这个写一个通用的change操作：
    
    #include<iostream>
    using namespace std;
    
    template <class T>
    void change(T &a,T &b)
    {
        T ch;
        ch = a;
        a = b;
        b = ch;
    }
    
    int main()
    {
        int a,b;
        cout<<"Please input two numbers:"<<endl;
        cin>>a>>b;
        change(a,b);
    
        cout<<"After changing:"<<endl;
        cout<<a<<" "<<b<<endl;
    
        system("pause");
        return 0;
    }

简单排序代码：

#include <iostream>
    
    using namespace std;
    
    /*
    将这个过程量化：假设有n个元素，需要确定的下标有0到n-1。最后一个元素无需比较。假设当前需要确定的下标为i，则将min初
    
    始化为i，然后将min处的元素依次与后面n-1-i个元素相比较，min每次指向较小元素。
    */
    void swap01(int *array, int a, int b)
    {
    	array[a] = array[a] + array[b];
    	array[b] = array[a] - array[b];
    	array[a] = array[a] - array[b];
    }
    
    void selectSort(int *arry,int length)
    {
    	int i, j, min = 0;
    	for ( i = 0; i < length - 1; i++)//最后一个元素无需比较
    	{
    		min = i;
    		for ( j = i + 1; j < length; j++)
    		{
    			if (arry[min] > arry[j])//如果有小于当前最小值的关键字
    			{
    				min = j;//将此关键字的下标赋值给min
    			}
    		}
    		if (i != min)
    		{
    			swap01(arry, i, min);
    		}
    	}
    }
    int main()
    {
    	int array[9] = { 9, 1, 5, 8, 3, 7, 4, 6, 2 };
    	int array_length = sizeof(array) / sizeof(array[0]);
    
    	selectSort(array,array_length);
    
    	for (int i = 0; i < array_length; i++)
    	{
    		cout << array[i] << endl;
    	}
    
    	system("pause");
    	return 0;
    }

参考[经典排序算法之简单选择排序][Link 1]

[70]: /images/20220526/a63a26b2e5c3483a8c318c0b9fc03837.png
[70 1]: /images/20220526/af8460a68b45475f8242ef451a61dec7.png
[Link 1]: https://blog.csdn.net/hulifangjiayou/article/details/47321309