直接选择排序
基本思想:
每一趟(第i趟,i = 0,1,…,n - 2)在后面n - i个待排序的数据元素集合中选出关键码最小的数据元素,作为有序元素序列的第i个元素。待到第n - 2趟做完,待排序元素集合中只剩下1个元素,排序结束
【直接选择排序】
- 在元素集合array[i]-array[n-1]中选择关键码最大(小)的数据元素
- 若它不是这组元素中的最后一个(第一个)元素,则将它与这组元素中的最后一个(第一个)元素交换
- 在剩余的array[i]-array[n-2](array[i+1]-array[n-1])集合中,重复上述步骤,直到集合剩余1元素
具体代码
void Swap(int* left, int* right)
{
int tmp = 0;
tmp = *left;
*left = *right;
*right = tmp;
}
void SelectSort(int arr[], int size)
{
int i = 0;
int j = 0;
for (i = 0; i < size - 1; i++)
{
int maxPos = 0;
for (j = 1; j < size - i; j++)
{
if (arr[j] > arr[maxPos])
maxPos = j;
}
//如果当前最大元素不在最后
if (maxPos != size - i - 1)
Swap(&arr[size - i - 1], &arr[maxPos]);
}
}
这个代码还可以写的更高效点,就是在每一趟中,同时找出最大和最小元素,如果最小元素不在第一个位置,则把它和第一个位置的元素交换,第二趟就是从array[i+1]-array[n-2]区间再寻找最大最小元素了。
但要注意的是,有可能最小元素在最后一个位置,我们先把最大元素与最后一个元素交换,现在最小元素的标记在最后一个元素那,我们再把最小元素与第一个元素交换,就会出现错误,最大元素就会跑到第一个位置去,这时我们就要做相应的操作了。
如果最小元素在最后一个位置,在把最大元素和最后一个位置的元素交换后,最后一个元素(最小元素)跑到最大元素的标记处了,所以要改变最小元素的标记,把它改为此时最大元素的标记。
上图解释吧:
具体代码
void SelectSort_OP(int arr[], int size)
{
int begin = 0;
int end = size - 1;
while (begin < end)
{
int maxPos = begin;
int minPos = begin;
//找最大与最小元素的位置
int i = begin + 1;
while (i <= end)
{
if (arr[i] > arr[maxPos])
maxPos = i;
else if (arr[i] < arr[minPos])
minPos = i;
i++;
}
if (maxPos != end)
Swap(&arr[maxPos], &arr[end]);
if (minPos == end)
minPos = maxPos;
Swap(&arr[minPos], &arr[begin]);
begin++;
end--;
}
}