排序算法之选择排序

我不是女神ヾ 2022-09-25 15:20 195阅读 0赞

先看一下下面这张图

![Center][]

下面分析选择排序：

选择排序第一次从头遍历n个元素，找到最大（最小）的元素并放到最后。

第二次从头遍历n-1个元素，同样找到最大的元素，放到n-2（即第n-1个元素）的位置。

以此下去，直到只剩下第一个元素，排序结束。

选择排序简单粗暴，实现起来比较容易，外层循环控制已经排好序的个数，内层循环遍历前n个元素找到最大元素放到n-1位置。

也正是因为它的简单粗暴，它的时间复杂度比较高，外层循环需要O(n)，内层循环也要O(n)，所以时间复杂度为O(n2)。无论初始数组是否有序，内层循环都需要遍历n个元素，所以其最好最坏平均情况下的时间复杂度都是O(n2)。

由于不需要额外的辅助空间，其空间复杂度为O(1)，即常量复杂度。

选择排序内层循环开始时取第一个元素为最大元素，后续元素如果有比其大的则替换它，找到最大元素后与最后一个元素进行交换，这样最后一个元素就被提到前面来了，可能会破坏稳定性（如855，把8和第二个5交换后，第二个5就被交换到第一个5前面了），所以这个元素有可能被放到本来在其后面的跟其一样大的元素后面，所以选择排序是不稳定的。

AS3代码：

/**
    		 * 选择排序
    		 * 外层循环控制当前已排好多少个元素
    		 * 内层循环遍历还未排的元素
    		 */
    		private function SelectSort(arr:Array):void{
    			var inx:uint,temp:Number;
    			//外层循环从0到n-2,共n-1次循环，第n次循环时只剩下一个元素没必要再排了
    			for(var i:uint=0;i<arr.length-1;i++){
    				//默认取第一元素作为最大元素
    				inx=0;
    				//内层循环从1到n-1-i，共n-i个元素，因为已经后i个元素已经排好，所以只需要排前n-i个元素即可
    				for(var j:uint=1;j<arr.length-i;j++){
    					if(arr[j]>=arr[inx]){
    						inx=j;
    					}
    				}
    				if(inx!=arr.length-1-i){
    					temp=arr[inx];
    					arr[inx]=arr[arr.length-1-i];
    					arr[arr.length-1-i]=temp;
    				}
    			}
    		}
    		/**
    		 * 选择排序
    		 * 外层循环控制从哪个元素开始遍历
    		 * 内层循环遍历这些元素并把最小元素放到最前
    		 */
    		private function SelectSort2(arr:Array):void{
    			var inx:uint,temp:Number;
    			//开始遍历坐标为0到n-2，n-1为最后一个元素，不需要再作遍历
    			for(var i:uint=0;i<arr.length-1;i++){
    				//默认取第一个元素为最小元素
    				inx=i;
    				//从待排元素第二个位置开始遍历
    				for(var j:uint=i+1;j<arr.length;j++){
    					if(arr[j]<arr[inx]){
    						inx=j;
    					}
    				}
    				if(inx!=i){
    					temp=arr[inx];
    					arr[inx]=arr[i];
    					arr[i]=temp;
    				}
    			}
    		}

c++代码：

/**
    * 选择排序
    * 每次遍历找到最小（大）的元素，遍历n-1次
    * 最好、最坏、平时时间复杂度O(n2)
    * 空间复杂度O(n)
    * 不稳定，每次找到最小（大）元素后都要与端点进行交换，会破坏端点元素的稳定性
    * @param arr 目标数组
    * @param n 数组个数
    * @param false表示从小到大排序 true表示从大到小排序
    */
    template<class T>
    void selectSort(T* arr, int n, bool reserve)
    {
    	int inx;
    	//外层循环n-1次
    	for (int i = 0; i < n - 1; i++)
    	{
    		inx = 0;
    		//内层循环n-i次，已经排好i个元素了
    		for (int j = 1; j < n - i; j++)
    		{
    			if ((arr[j] > arr[inx]) ^ reserve)
    			{
    				inx = j;
    			}
    		}
    		//找到的元素与最后一个元素交换
    		if (inx != n - i - 1)
    		{
    			arr[inx] += arr[n - 1 - i];
    			arr[n - 1 - i] = arr[inx] - arr[n - 1 - i];
    			arr[inx] = arr[inx] - arr[n - 1 - i];
    		}
    	}
    }

总结，选择排序时间复杂度为O(n2),空间复杂度为O(1)，不具备稳定性。

[Center]: /images/20220717/4a8e56d499ce4252a911bff646f20d12.png