当前位置:   article > 正文

数据结构从入门到精通——直接选择排序

数据结构从入门到精通——直接选择排序


前言

直接选择排序是一种简单的排序算法。它的工作原理是每一次从未排序部分选出最小(或最大)的一个元素,存放到排序序列的起始位置,然后再从剩余未排序元素中继续寻找最小(或最大)元素,然后放到已排序序列的末尾。以此类推,直到所有元素均排序完毕。这种算法的时间复杂度为O(n^2),其中n是待排序元素的数量,因此在处理大数据集时效率较低。然而,它的实现简单,对于小规模的数据排序是一个不错的选择。


一、选择排序的基本思想:

每一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,直到全部待排序的数据元素排完 。

选择排序的基本思想是从未排序的序列中找到最小(或最大)的元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(或最大)元素,然后放到已排序序列的末尾。以此类推,直到所有元素均排序完毕。

这种排序算法的优点在于其实现过程相对简单,对于小规模的数据排序,其效率是可以接受的。然而,选择排序也存在明显的缺点。由于其每次都需要从未排序的元素中找到最小(或最大)的元素,这导致算法的时间复杂度为O(n^2),其中n为待排序元素的数量。这意味着当处理大规模数据时,选择排序的性能可能会变得非常低下。

在实际应用中,选择排序往往不是最优的选择,特别是对于大规模数据的排序。更高效的排序算法,如快速排序、归并排序、堆排序等,在处理大规模数据时,通常会有更好的性能表现。

但是,选择排序的思想在某些特定情境下仍然有其应用价值。例如,在某些需要稳定排序且数据量较小的场景中,选择排序可以作为一个简单且有效的解决方案。此外,选择排序的思想也可以作为其他更复杂排序算法的基础,帮助理解和学习更高级的排序算法。

总的来说,选择排序的基本思想虽然简单,但其性能上的局限性使得它在实际应用中并不常见。然而,这并不意味着它没有价值,通过深入理解和应用选择排序的思想,我们可以更好地理解排序算法的本质,并为学习更高级的排序算法打下坚实的基础。

二、直接选择排序

  • 在元素集合array[i]--array[n-1]中选择关键码最大(小)的数据元素
  • 若它不是这组元素中的最后一个(第一个)元素,则将它与这组元素中的最后一个(第一个)元素交换
  • 在剩余的array[i]--array[n-2](array[i+1]--array[n-1])集合中,重复上述步骤,直到集合剩余1个元素

直接选择排序是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,直到全部待排序的数据元素排完。

首先,我们假设有一个无序的整数列表,我们想要通过直接选择排序将其按升序排列。算法的工作流程可以分为以下几个步骤:

  1. 找到最小(大)元素:在列表中找到最小(大)的元素。这个步骤通常涉及遍历整个列表,比较每个元素的值。
  2. 交换位置:一旦找到最小(大)元素,将其与列表的第一个元素交换位置。这样,最小(大)的元素就被放到了它应该在的位置。
  3. 移除已排序元素:从列表中移除已排序的第一个元素(现在是最小(大)元素),然后对剩余的元素重复上述两个步骤。
  4. 重复过程:继续这个过程,每次从剩余的未排序元素中找到最小(大)元素,并将其与未排序部分的第一个元素交换。
  5. 结束条件:当整个列表都被排序时,算法结束。

直接选择排序的时间复杂度是O(n^2),其中n是列表的长度。这是因为它包含两个嵌套循环:一个用于找到最小(大)元素,另一个用于遍历整个列表。尽管这种排序方法在处理小型或中型列表时可能是有效的,但对于大型列表,更高效的排序算法(如快速排序、归并排序或堆排序)通常是更好的选择。

然而,直接选择排序有一个显著的优点,那就是它的实现相对简单,对于初学者来说是一个很好的学习工具。通过理解这个算法,可以对排序的基本概念有一个直观的认识,从而为学习更复杂的排序算法打下基础。

在实际应用中,直接选择排序可能不是最优选择,但它在教育、演示和教学方面仍然具有很高的价值。此外,对于某些特定类型的数据集(如部分有序的数据集),直接选择排序的性能可能会比其他算法更好。

三、直接选择排序的特性总结:

  1. 直接选择排序思考非常好理解,但是效率不是很好。实际中很少使用
  2. 时间复杂度:O(N^2)
  3. 空间复杂度:O(1)
  4. 稳定性:不稳定

直接选择排序的特性总结起来,主要是其直观易懂、原地排序和不稳定排序的特点。

直接选择排序是一种简单直观的排序算法,其基本原理是每一次从未排序的部分选出最小(或最大)的一个元素,存放到排序序列的起始位置。它的操作过程是从左到右逐个选择剩余元素中的最小者,并将其与未排序部分的第一个元素交换。这种选择过程一直持续到未排序部分为空,排序也就完成了。因此,直接选择排序的直观性是其显著特点之一,使得初学者容易理解和实现。

另一个特性是原地排序,这意味着直接选择排序不需要额外的存储空间来进行排序,它直接在原始数组上进行操作,改变了原始数组的顺序。这一特性使得它在处理内存受限的场景时非常有用。

然而,直接选择排序也是一种不稳定的排序算法。稳定性是指如果两个元素的键值相等,那么在排序之后它们的相对位置不会改变。由于直接选择排序在每次选择最小(或最大)元素进行交换时,可能会改变相等元素的原始相对位置,因此它不具备稳定性。

总的来说,直接选择排序是一种简单直观、原地进行的排序算法,但它是不稳定的。在实际应用中,根据数据的特性和排序要求,可能需要选择更合适的排序算法。例如,对于大规模数据集,直接选择排序的效率可能较低,因为它需要多次遍历和交换操作。而对于小规模数据集或者对稳定性要求不高的场景,直接选择排序则是一个简单有效的选择。

四、直接选择排序的动画展示

直接选择排序是一种简单的排序算法。它通过每次从未排序部分选择最小(或最大)元素,与未排序部分的第一个元素交换位置,从而达到排序的目的。在动画展示中,可以看到每次选择的最小(或最大)元素逐步“冒泡”到已排序部分的末尾,直到整个序列有序。这种排序方法的时间复杂度为O(n^2),适用于小规模数据的排序。

选择排序

五、直接选择排序的代码展示

test.c

#include<stdio.h>
#include<stdlib.h>
#include<time.h>

void SelectSort(int* a, int n);
void PrintArray(int* a, int n);
void Swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
void TestSelectSort()
{
	int a[] = { 5, 13, 9, 16, 12, 4, 7, 1, 28, 25, 3, 9, 6, 2, 4, 7, 1, 8 };
	//int a[] = { 5, 3, 9, 6, 2, 4, 7, 1, 8 };
	PrintArray(a, sizeof(a) / sizeof(int));

	SelectSort(a, sizeof(a) / sizeof(int));

	PrintArray(a, sizeof(a) / sizeof(int));
}


void PrintArray(int* a, int n)
{
	for (int i = 0; i < n; i++)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
}
void TestOP()
{
	srand(time(0));
	const int N = 10000;
	int* a1 = (int*)malloc(sizeof(int) * N);

	for (int i = 0; i < N; ++i)
	{
		a1[i] = rand();
	}


	int begin1 = clock();
	SelectSort(a1, N);
	int end1 = clock();

	
	
	printf("SelectSort:%d\n", end1 - begin1);

	free(a1);
}
void SelectSort(int* a, int n)
{
	for (int k = 0; k < n; k++)
	{
		int max = 0;
		for (int i = 0; i < n - k; i++)
		{
			if (a[i] >= a[max])max = i;
		}
		Swap(&a[n - 1 - k], &a[max]);
	}
	
}
int main()
{
	TestSelectSort();
	TestOP();

	return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75

这段代码实现的是选择排序(Selection Sort)算法,而不是通常的冒泡排序(Bubble Sort)。选择排序是一种简单直观的排序算法,它的工作原理是每一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,直到全部待排序的数据元素排完。

接下来我将逐步解释这段代码:

  1. 函数定义:
void SelectSort(int* a, int n)
  • 1

这是一个名为 SelectSort 的函数,它接受一个整数数组 a 和一个整数 n 作为参数。n 是数组 a 的长度。

  1. 外层循环:for (int k = 0; k < n; k++)

这个循环从 0n-1 迭代,用于确定当前应该放置最小元素的位置。

  1. 初始化 max 变量:int max = 0;

在每次外层循环开始时,max 被初始化为 0。这个变量用于存储当前找到的最小元素的位置。

  1. 内层循环:for (int i = 0; i < n - k; i++)

这个循环从 0n-k-1 迭代。每次迭代,它都会检查从 a[0]a[n-k-1] 的元素,以找到当前最小元素的位置。

  1. 判断并更新最小元素的位置:if (a[i] >= a[max]) max = i;

这个条件检查 a[i] 是否大于或等于 a[max]。如果是,则更新 maxi。注意这里使用了 >= 而不是 >,这意味着如果有多个相同的最小元素,它们都会被正确地处理。

  1. 交换元素:Swap(&a[n - 1 - k], &a[max]);

在内层循环结束后,我们已经找到了从 a[0]a[n-k-1] 中的最小元素,它的位置是 max。现在,我们需要将这个最小元素与当前位置 n-1-k 的元素交换。

整体上,这段代码通过不断地选择并交换最小元素,最终将数组 a 排序为升序。

六、直接选择排序的优化

使用min和max对直接选择排序进行优化可以减少交换的次数。

在原始的直接选择排序算法中,每次迭代会通过查找最小值和最大值的索引来确定需要交换的元素。然后分别进行交换。这样可能会导致不必要的交换操作。

优化的思路是,在每次迭代中,同时查找最小值和最大值的索引,然后将它们记录下来,最后再进行一次交换操作。

具体实现如下:

void SelectSort(int* a, int n)
{
    int begin = 0, end = n - 1;
    while (begin < end)
    {
        int min = begin, max = end;
        for (int i = begin; i <= end; i++)
        {
            if (a[i] <= a[min]) min = i;
            if (a[i] >= a[max]) max = i;
        }

        // 将最小值放到已排序部分的起始位置
        Swap(&a[begin], &a[min]);
        
        // 如果最大值的索引是begin,将最大值的索引更新为min
        if (max == begin) max = min;
        
        // 将最大值放到已排序部分的末尾位置
        Swap(&a[end], &a[max]);
        
        begin++;
        end--;
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25

这样的优化可以减少交换的次数,提高排序的效率。同时,可以确保每次迭代只进行一次交换操作,减少了内存的读写次数,提高了算法的性能。

 if (max == begin) max = min;
  • 1

关于这个代码是为了防止min正好在end,而max正好在begin这种的特殊情况

test.c

#include<stdio.h>
#include<stdlib.h>
#include<time.h>

void SelectSort(int* a, int n);
void PrintArray(int* a, int n);
void Swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
void TestSelectSort()
{
	int a[] = { 5, 13, 9, 16, 12, 4, 7, 1, 28, 25, 3, 9, 6, 2, 4, 7, 1, 8 };
	//int a[] = { 5, 3, 9, 6, 2, 4, 7, 1, 8 };
	PrintArray(a, sizeof(a) / sizeof(int));

	SelectSort(a, sizeof(a) / sizeof(int));

	PrintArray(a, sizeof(a) / sizeof(int));
}


void PrintArray(int* a, int n)
{
	for (int i = 0; i < n; i++)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
}
void TestOP()
{
	srand(time(0));
	const int N = 10000;
	int* a1 = (int*)malloc(sizeof(int) * N);

	for (int i = 0; i < N; ++i)
	{
		a1[i] = rand();
	}


	int begin1 = clock();
	SelectSort(a1, N);
	int end1 = clock();

	
	
	printf("SelectSort:%d\n", end1 - begin1);

	free(a1);
}
void SelectSort(int* a, int n)
{
	int begin = 0, end = n - 1;
	while (begin < end)
	{
		int min = begin, max = end;
		for (int i = begin; i <= end; i++)
		{
			if (a[i] <= a[min])min = i;
			if (a[i] >= a[max])max = i;
		}
		Swap(&a[begin], &a[min]);
		if (max == begin)max = min;
		Swap(&a[end], &a[max]);
		begin++;
		end--;
	}
	
	
}
int main()
{
	TestSelectSort();
	TestOP();

	return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82

这段代码实现的是选择排序算法,用于对数组a中的元素进行排序。传入参数是数组a和数组长度n

代码的主要思路是:通过每一次迭代,从未排序的元素中找到最小值和最大值,并将它们分别放到已排序部分的起始位置和末尾位置。然后缩小未排序部分的范围,再次进行迭代直至完成排序。

  1. 初始化变量begin为数组的起始索引0end为数组的终止索引n-1
  2. 进入循环,判断begin是否小于end。如果是,继续下面的操作;如果不是,说明排序已完成,退出循环。
  3. 在每一次迭代中,定义变量minmax,分别用于记录当前未排序部分的最小值和最大值的索引,初始值分别设为beginend
  4. beginend遍历数组a,找到当前最小值和最大值的索引,更新minmax
  5. 交换最小值和begin位置的元素,使当前最小值放到已排序部分的起始位置。
  6. 如果max等于begin,说明最大值原本就在begin位置,交换后已经移到了最小值应该在的位置,所以需要将max更新为min
  7. 交换最大值和end位置的元素,使当前最大值放到已排序部分的末尾位置。
  8. 完成一次迭代后,已排序部分的范围向两端缩小,begin增加1end减少1
  9. 重复2-8步骤,直到begin不小于end,排序完成。

总结起来,选择排序每次迭代都会确定未排序部分的最小值和最大值的位置,并将它们交换到已排序部分的起始和末尾位置。通过多次迭代,最终达到整个数组的有序状态。

在这里插入图片描述


声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/盐析白兔/article/detail/403615
推荐阅读
相关标签
  

闽ICP备14008679号