算法 - 选择排序(Select_Sort)

发布于:2023-02-09 ⋅ 阅读:(734) ⋅ 点赞:(0)

在写选择排序的代码之前,我们先对选择排序的排序原理进行梳理:

选择排序中一共要对三个下标进行操作,分别是i,j,k(当然你也可以自行设置),第一个循环为i对整个序列的遍历,i下标也是从序列中的第一个元素开始,将i下标所对应的元素赋值给k下标,第二个循环为j下标(i的后一位元素)对i后面的元素进行遍历,j下标对应的是i+1号元素,后面的元素如果小于i下标对应的元素,将k下标迁移过去,如果还有发现有更小的元素,继续将k下标迁移过去,直到找到剩下元素中最小的元素,并将k下标对应的元素与i下标对应的元素进行互换,也就是将最小的元素放到前面,循环执行次过程,并且每次执行i和j下标都向前移一位,直到排序完成。

如上图,我在这里给出了一组数据:

int ar = {55,23,87,62,16};

 

在选择排序中,存在三个持续变更的下标,在这里分别为:i下标,j下标(总是指向 i 的后一位元素,也就是i + 1),k下标(用于临时存储数据的下标)。

用选择排序方法排序上面的5个整数的过程为:

一:i下标指向55,将i下标的值赋值给k下标(k = i),j下标指向23,k下标指向23,但是后面的16小于23,所以ar[k] = 16,现在将ar[k] 与ar[i]互换,此时元素的顺序为:15,55,23,87,62

二:现在i和j下标向后偏移一位,i下标指向55,k下标指向55,j下标指向23,23小于55,小于87,小于62,于是ar[k] = 23,交换ar[k]和ar[i],此时元素的顺序为:16,23,55,87,62

三:此时i和j下标向后再偏移一位,i下标指向55,k下标指向55,j下标指向87,55为接下来三个元素中最小的元素,所以元素顺序不动,此时元素的顺序为16,23,55,87,62

四:此时i和j下标向后再偏移一位,i下标指向87,k下标指向87,j下标指向62,此时元素中未进行排序的只有两个元素,只需将剩下的两个元素进行比较即可,62 < 87,所以ar[k] = 62 ,将ar[k] 与ar[i]进行交换,此时元素的顺序为:16,23,55,62,87

五:排序完成。 

将思路代码化:

#include<stdio.h>
#include<iostream>
#include<stdlib.h>
#include<assert.h>
#include<time.h>
#define MAXSIZE 12
void initar(int *ar,int len)
{
	assert(ar != nullptr);
	for(int i = 0;i < len;i++){
		ar[i] = rand() % 20;
	}
}
void showar(int *ar,int len)
{
	assert(ar != nullptr);
	for(int i = 0;i < len;i++){
		printf("%d ",ar[i]);
	}
	printf("\n--------------------------\n");
}
void swap(int *ar,int index1,int index2)
{
	int temp = ar[index1];
	ar[index1] = ar[index2];
	ar[index2] = temp;
}
void Select_sort(int *ar,int len)
{
    assert(ar != nullptr && len >= 0);
    for(int i = 0;i < len;i++){
        int k = i;
        for(int j = i + 1;j < len;j++){
            if(ar[j] < ar[k]){
                k = j;
            }
        }
        swap(ar,i,k);
    }
}
int main()
{
	srand((unsigned int)time(NULL));
	int ar[MAXSIZE];
	initar(ar,MAXSIZE);
	printf("原始数据为:\n");
	showar(ar,MAXSIZE);
	printf("经过选择排序后的数据为:\n");
	Select_sort(ar,MAXSIZE);
	showar(ar,MAXSIZE);
	return 0;
}

随机生成12个小于20的数,运行结果为:

输出完成

如图所示,选择排序执行完成,十二个元素排序完成。 

本文含有隐藏内容,请 开通VIP 后查看