八大排序之选择排序

柔情只为你懂 2022-05-16 00:36 156阅读 0赞

##### 思想： #####

每一趟都从待排序的数列中选择一个最大（最小）的，放在数列的最后一个位置（或起始位置）直到全部待排序的数据元素排完。 选择排序是不稳定的排序方法。

##### 图解： #####

例：9 5 3 4 6 2 8 1 7 0  
![这里写图片描述][70]

#include <stdio.h>
    #include <string.h>
    
    void Swap(int *p1, int *p2)
    {
    	int tmp = *p1;
    	*p1 = *p2;
    	*p2 = tmp;
    }
    
    void select_sort(int arr[], int len)
    {
    	for (int i = 0; i < len - 1; i++) //表示趟数
    	{
    		int maxPos = 0;
    		for (int j = 1; j < len - i; j++)
    		{
    			if (arr[j] > arr[maxPos])
    			{
    				maxPos = j;
    			}
    		}
    		if (maxPos != len - 1 - i) //如果最大的元素就是在最后位置，就不用交换
    		{
    			Swap(arr + maxPos, arr + (len - 1 - i));
    		}
    	}
    }
    
    int main()
    {
    	int arr[] = { 9,5,3,4,6,2,8,1,7,0 };
    	int len = sizeof(arr) / sizeof(arr[0]);
    	select_sort(arr, len);
    	for (int i = 0; i < len; i++)
    	{
    		printf("%d ", arr[i]);
    	}
    	system("pause");
    	return 0;
    }

##### 优化： #####

选择排序的每一趟记录最大值，我们是不是可以在一趟中，把最小值和最大值都记录下来，这样就可以只完成一半的工作

![这里写图片描述][70 1]

void Swap(int *p1, int *p2)
    	{
    		int tmp = *p1;
    		*p1 = *p2;
    		*p2 = tmp;
    	}
    	
    	void select_sort(int arr[], int len)
    	{
    		int left = 0;
    		int right = len - 1;
    		while (left < right)
    		{
    			int minPos = left;
    			int maxPos = left;
    			for (int i = left; i < len - left; i++)
    			{
    				if (arr[i] < arr[minPos])
    				{
    					minPos = i;
    				}
    				if (arr[i] > arr[maxPos])
    				{
    					maxPos = i;
    				}
    			}
    			//这个if是为了判断第一个元素是不是最大的，因为如果第一个元素是最大的，会将最大的元素换位置
    			//比如，上述中的第一步，9是最大的，如果9和0换位置，但maxPos仍然是0，这是第一个元素就变为了0，
    			//maxPos却没有发生变化，再将最大的元素和最后一个元素换位置，就会是0和最后一个元素换位置，而不是最大的元素
    			//所以这种情况就要先将换后的位置赋值给maxPos
    			Swap(arr + minPos, arr + left);
    			if (maxPos == left)
    			{
    				maxPos = minPos;
    			}
    			Swap(arr + maxPos, arr + right);
    			left++;
    			right--;
    		}
    	}

###### 时间复杂度： O(n^2) ######

[70]: /images/20220516/72eac324fbfa4e7a8624a92b6cff1a5a.png
[70 1]: /images/20220516/4ee944521708423eace0efd7bd97113b.png