排序之选择排序

我不是女神ヾ 2022-05-24 23:05 141阅读 0赞

> # 选择排序简介 #

选择排序（Selection sort）是一种简单直观的[排序算法][Link 1]。它的工作原理是每一次从待排序的[数据元素][Link 2]中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。 选择排序是不稳定的排序方法。

> # 选择排序的基本思想 #

一个长度为N的待排序列，先找出 (0，N-1)区间内最小的数，放在第一位，再找出(2，N-1)区间内最小的数放在第二位，如此反复直至排序结束。

> # 时间复杂度 #

O(n\*n)

> # 稳定性 #

选择排序是给每个位置选择当前元素最小的，比如给第一个位置选择最小的，在剩余元素里面给第二个元素选择第二小的，依次类推，直到第n-1个元素，第n个元素不用选择了，因为只剩下它一个最大的元素了。那么，在一趟选择，如果一个元素比当前元素小，而该小的元素又出现在一个和当前元素相等的元素后面，那么交换后稳定性就被破坏了。比较拗口，举个例子，序列5 8 5 2 9，我们知道第一遍选择第1个元素5会和2交换，那么原序列中两个5的相对前后顺序就被破坏了，所以选择排序是一个不稳定的排序算法。

#include <iostream>
    #include <cstdlib>
    #include <ctime>
    using namespace std;
    
    void SelectionSort(int num[],int N)        //选择排序
    {
    	for(int i = 0; i < N - 1; i++)          //遍历数组     
    	{
    		int min = i;                        
    		for(int j = i + 1; j < N; j++)      //找出最小数
    		{
    			if(num[min] > num[j])
    			{
    				min = j;
    			}
    		}
    		if(min != i)                        //若是min是最小值的下标切不等于i则交换
    		{
    			int temp = num[min];
    			num[min] = num[i];
    			num[i] = temp;
    		}
    	}
    }
    
    void print(int num[], int N)
    {
    	int i = 0;
    	while(i < N) cout << num[i++] << " ";
    	
    	cout << endl;
    } 
    
    int main()
    {
    	srand((unsigned)time(NULL));
    	int N;
    	while(cin >> N)	    
    	{
    		int num[N];
    		for(int i = 0; i < N; i++)        //生成一个长度为N的随机数列
    		{                            
    			num[i] = rand() % 65536;
    		}
    		print(num,N);                    //打印排序前数列
    		SelectionSort(num,N);            //进行选择排序 
    		print(num,N);                    //打印排序后数列
    	}
    	
    	return 0;
    }

[Link 1]: https://baike.baidu.com/item/%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95/5399605
[Link 2]: https://baike.baidu.com/item/%E6%95%B0%E6%8D%AE%E5%85%83%E7%B4%A0/715313