数据结构与算法——排序算法—（4）选择排序

柔情只为你懂 2022-03-16 09:16 244阅读 0赞

**1.4 选择排序**（Selection Sort）是一种简单直观的排序算法。它的基本思想是：首先在未排序的数列中找到最小的元素，然后将其存放着数列的起始位置；接着，在从剩余未排序的元素中继续寻找最小的元素，然后放到以排序序列的末尾。直至所有元素均排序完毕。

//首先是自己琢磨的代码

//选择排序
    void selectionSort(int a[], int len)
    {
    	for (int i = 0; i < len; ++i)
    	{
    		int minVal = a[i];//找出每次循环序列的最小值
    		int minIndex = i;
    		for (int j = i; j < len; ++j)
    		{
    			if (a[j] < minVal)
    			{
    				minVal = a[j];
    				minIndex = j;
    			}
    
    		}
    		int temp = a[i];
    		a[i] = a[minIndex];
    		a[minIndex] = temp;
    
    	}
    
    }

//网上的优化代码

//选择排序优化
    void selectionSortBetter(int a[], int len)
    {
    	for (int i = 0; i < len; ++i)
    	{
    		//				(1)删除最小值，用a[minIndex]代替
    		int minIndex = i;//找出每次循环序列的最小值的位置 
    		for (int j = i+1; j < len; ++j)//(2)j = i+1,原来是j=i,此时j == i == minIndex; 自己与自己就不用比较了
    		{
    			if (a[j] < a[minIndex])
    			{
    				minIndex = j;//(1)用位置替代val
    			}
    
    		}
    		if (i != minIndex)//(3)最小值位置与i相等时，交换无意义
    		{
    			int temp = a[i];
    			a[i] = a[minIndex];
    			a[minIndex] = temp;
    		}
    	}
    }

选择排序的时间复杂度和稳定性：

**时间复杂度**：  
假设被排序的数列中有n个数，(n-1)+(n-2)+….+2+1 = n(n-1) /2。因此，时间复杂度为O(n2)。

**稳定性**： 不稳定