排序算法：简单选择排序算法实现及分析

╰+哭是因爲堅強的太久メ 2022-05-31 10:52 241阅读 0赞

# 简单选择排序算法介绍 #

**简单选择排序（Simple Selection Sort）就是通过n-1次关键字排序之间的比较，从n-i+1个记录中选择关键字最小的记录，并和第i（1<=i<=n）记录交换**。这是一般书上的定义。**实际上选择排序，就是每一轮选者一个最值出来，然后在剩下的数据中又选择一个最值出来，直到数据被选择完毕。这就是所谓的简单选择排序算法。**

# 简单选择排序算法实现 #

在下面代码中，**每一轮内循环完毕，记录最值下标，然后和起始值进行比较，如果不一样才交换值**。

**记录最值下标才是最好的选择，**以前在**某些书上看到的，靠 ，直接在内层循环中交换值！这样效率肯定打折扣**。

**注意：内层循环的起始位置为i+1 哟!**

//选择排序 核心是记录最值下标
    void SelectSort_Up(int *arr, int length)
    {
    	for (int i = 0; i < length-1; i++)
    	{
    		int index = i;//记录最值下标
    		for (int j = i + 1; j < length; j++)
    		{
    			//升序
    			if (arr[index] > arr[j])
    			{
    				index = j;
    			}
    		}
    		if (i != index)
    		{
    			Swap(&arr[i], &arr[index]);
    		}
    	}
    }

# 简单选择排序算法复杂度分析 #

如果数组中有**n个数据**，外层的

第1轮循环是arr\[0\] 和arr\[1\] ...arr\[n-1\] 进行比较，次数为n-1 次，arr\[0\]放最值。

第2轮循环是arr\[1\] 和 arr\[2\]...arr\[n-1\] 进行比较，次数为n-2次，arr\[1\]放第二个最值。

所以不难得出它的比较的次数是n-1 + n-2 + n-3 + ....1 = n\*（n-1）/2 。

时间复杂度为 = n^2/2- n/2 = n^2 ,**O（n^2）**。

# 完整代码 #

#define _CRT_SECURE_NO_WARNINGS
    #include <stdio.h>
    #include <stdlib.h>
    #include <time.h>
    #define MAXSIZE 10
    
    //交换值
    void Swap(int* a, int* b)
    {
    	int temp = *a;
    	*a = *b;
    	*b = temp;
    }
    
    //选择排序 核心是记录最值下标
    void SelectSort_Up(int *arr, int length)
    {
    	for (int i = 0; i < length-1; i++)
    	{
    		int index = i;//记录最值下标
    		for (int j = i + 1; j < length; j++)
    		{
    			//升序
    			if (arr[index] > arr[j])
    			{
    				index = j;
    			}
    		}
    		if (i != index)
    		{
    			Swap(&arr[i], &arr[index]);
    		}
    	}
    }
    //选择排序 核心是记录最值下标
    void SelectSort_Down(int *arr, int length)
    {
    	for (int i = 0; i < length - 1; i++)
    	{
    		int index = i;//记录最值下标
    		for (int j = i + 1; j < length; j++)
    		{
    			//降序
    			if (arr[index] < arr[j])
    			{
    				index = j;
    			}
    		}
    		if (i != index)
    		{
    			Swap(&arr[i], &arr[index]);
    		}
    	}
    }
    //打印数组元素
    void PrintArr(int* arr, int length)
    {
    	for (int i = 0; i < length; i++)
    	{
    		printf("%d ", arr[i]);
    	}
    	printf("\n");
    	return;
    }
    
    
    int main(int argc, char *argv[])
    {
    	srand((size_t)time(NULL));//设置随机种子
    	int arr[MAXSIZE] = { 0 };
    	//给每个元素设置一个随机值
    	for (int i = 0; i < MAXSIZE; i++)
    	{
    		arr[i] = rand() % 11;
    	}
    	printf("排序前:\n");
    	PrintArr(arr, MAXSIZE);
    	printf("升序:\n");
    	SelectSort_Up(arr,MAXSIZE);
    	PrintArr(arr, MAXSIZE);
    	printf("降序:\n");
    	SelectSort_Down(arr, MAXSIZE);
    	PrintArr(arr, MAXSIZE);
    	return 0;
    }

# 运行结果检测 #

![20180222163436772][]

[20180222163436772]: /images/20220531/56b2460d0d8d46b1a5659c685c87ab45.png