当前位置:网站首页>让你理解选择排序(C语言)

让你理解选择排序(C语言)

2022-06-11 11:41:00 Butayarou

【引入】
选择排序,原理就是将当前的单个数据(设为cur)依次与其后的所有数据进行比较后,选择其后数据中的最值与cur进行位置交换。然后将下标+1(变更cur),重复上述操作,直至所有元素排序完毕。

可以说,从理解上,选择排序是一种比较简单直观的排序算法。

【手工演示】
让我们来打一下草稿演示一下:
在这里插入图片描述

从上面的草稿,我们可以知道一共需交换[元素个数减1]次(即len-1),每次交换前找后面的数依次比较,符合条件的会执行交换操作。

【代码实现】
将上面的想法转换为代码如下:

void SelectionSort(int arr[], int len)
{
    
     for(int i=0; i<len-1; i++)   //共需交换len-1次
     {
    
        int min = i; 
        for(int j=i+1; j<len; j++)   //找出后面整数中的最值
        {
    
            if(a[j] < a[min])  /* 按照 所需条件 进行排序 */
            {
    
                min = j;       /* 更新最值的下标 */
            }
        }
        int tmp = arr[j];   // 借助临时变量将两个数据交换
        arr[j] = arr[j+1];    
        arr[j+1] = tmp;
     }
}

时间复杂度:在这里插入图片描述

但是不足的是,选择排序的稳定性不好。
比如,对于4 9 4 1 7,如果我们选择升序排序的话,第一遍选择第一个元素4会和1交换,那么原序列中两个4的相对前后顺序就被破坏了。

【简单优化】

void Swap(int* p1,int* p2)
{
    
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}

void SelectSort(int* a, int n)
{
    
	int begin = 0, end = n - 1;  //用双指针
	while (begin < end)
	{
    
		int mini = begin, maxi = begin;
		for (int i = begin; i <= end; i++)
		{
    
			if (a[i] < a[mini])  //找最小值的下标
			{
    
				mini = i;
			}
			if (a[i] > a[maxi])  //找最大值的下标
			{
    
				maxi = i;
			}
		}

		Swap(&a[begin], &a[mini]);  //交换值
		if (begin == maxi)  //修正
		{
    
			maxi = mini;
		}
		Swap(&a[end], &a[maxi]);  //交换值

		begin++;
		end--;
	}
}

这个也比较容易理解,让双指针分别指着一头一尾,两指针在移动过程中逐渐向中间靠拢。
这里对修正作一下说明:如果 begin 和 maxi 指向同一个元素,那么 begin 与 mini 交换值后,mini 指向的值便是交换值前 maxi 指向的值。

更多文章:
让你搞懂冒泡排序(C语言)

原网站

版权声明
本文为[Butayarou]所创,转载请带上原文链接,感谢
https://blog.csdn.net/m0_59938453/article/details/120916540