选择排序

选择排序

全栈程序员-站长 • 2021年12月7日上午8:00 • 未分类 • 阅读 35

大家好，又见面了，我是全栈君，祝每个程序员都可以多学几门语言。

昨日写完冒泡排序，和大多数人的感觉一样，太简单，丝毫没有挑战性。但楼主是一个追求踏实平稳的人，希望地基坚固，也为方便后面学习和研究更加高深的算法。但在研究效率上还有待提高，楼主一定好好努力。今天将会写完选择排序和插入排序，本文主在选择排序。

一. 算法描写叙述

选择排序：比方在一个长度为N的无序数组中，在第一趟遍历N个数据，找出当中最小的数值与第一个元素交换，第二趟遍历剩下的N-1个数据，找出当中最小的数值与第二个元素交换……第N-1趟遍历剩下的2个数据，找出当中最小的数值与第N-1个元素交换，至此选择排序完毕。

以以下5个无序的数据为例：

56 12 80 91 20（文中仅细化了第一趟的选择过程）

第1趟：12 56 80 91 20

选择排序

第2趟：12 20 80 91 56

第3趟：12 20 56 91 80

第4趟：12 20 56 80 91

二. 算法分析

平均时间复杂度：O(n2)

空间复杂度：O(1) (用于交换和记录索引)

稳定性：不稳定（比方序列【5， 5， 3】第一趟就将第一个[5]与[3]交换，导致第一个5挪动到第二个5后面）

三. 算法实现

//交换data1和data2所指向的整形
void DataSwap(int* data1, int* data2)
{
	int temp = *data1;
	*data1 = *data2;
	*data2 = temp;
}

/********************************************************
*函数名称：SelectionSort
*參数说明：pDataArray 无序数组；
*		   iDataNum为无序数据个数
*说明：    选择排序
*********************************************************/
void SelectionSort(int* pDataArray, int iDataNum)
{
	for (int i = 0; i < iDataNum - 1; i++)    //从第一个位置開始
	{
		int index = i;
		for (int j = i + 1; j < iDataNum; j++)    //寻找最小的数据索引 
			if (pDataArray[j] < pDataArray[index])
				index = j;

		if (index != i)    //假设最小数位置变化则交换
			DataSwap(&pDataArray[index], &pDataArray[i]);
	}
}

发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/118370.html原文链接：https://javaforall.net