一起学习交流~

排序-02-选择&冒泡&鸡尾酒排序

算法 laomuji 12个月前 (10-08) 360次浏览 已收录 0个评论

这三个排序原理差不多,所以放在一起讲

一、这三个排序是什么?

这三个排序都是循环里嵌套循环,很浪费时间,但写起来容易,废话不多说,直接贴百度百科的截图.

二、选择排序

选择排序思路

假设有一个数组{3,4,1,42,154,767,2,5}

3414215476725原始
1434215476725
1234215476745
1234215476745
1234154767425
1234576742154
1234542767154
1234542154767

每轮找到最小的值的下标,与开始这一轮的位置的下标进行交换

第一次:找到1最小,1的下标是2,开始位置的下标是0,将这两个下标所表示的值交换

第二次:找到2最小,2的下标是6,开始位置的下标是1,将这两个下标所表示的值交换

第三次:找到3最小,3的下标是2,开始位置的下标是2,将这两个下标所表示的值交换

一共8个数字,通过7轮循环得到正确的排序结果

选择排序代码

#include<iostream>
//选择排序
//记录每次记录最大或最小的下标,循环一次后再进行交换

template<typename T>
void selectSortMin(T nums[],unsigned int size) 
{
	int min,i, j;
	T temp;
	for (i = 0; i < size; i++)
	{
		min = i;//假设当前下标为最小值
		for (j = i + 1; j < size; j++)
		{
			//如果当前值小于最小值,那么当前值就是最小值
			if (nums[j] < nums[min]) min = j;
		}
		temp = nums[i];
		nums[i] = nums[min];
		nums[min] = temp;
	}
}


int main(int argc, char** argv)
{
	int nums[10] = { 3,4,1,42,154,767,2,5};
	selectSortMin(nums, 10);
	for (int i = 0; i < 10; i++)
	{
		std::cout << nums[i] << " ";
	}

}

三、冒泡排序

冒泡排序思路

冒泡排序和选择排序思路很像,就不再画图了

冒泡不是记录最小值的下标,而是若当前值小于开始下标的值,就进行交换

也就是说一次循环里有多次交换

显然,冒泡排序在交换比较浪费时间的时候,比选择排序表现要差一些.

但冒泡排序实现起来几乎是最简单的,所以在数据不多的情况下 冒泡排序很常见

冒泡排序代码

#include<iostream>
//冒泡排序 检测到当前不是最大的就交换,不记录下标
template<class T>
void bubbleSortMin(T nums[], int length)
{
	for (int i = 0; i < length - 1; i++)
	{
		for (int j = i + 1; j < length; j++)
		{
			//如果当前位置的值小于开始位置的值,就进行交换
			if (nums[j] < nums[i]) 
			{
				T temp = nums[j];
				nums[j] = nums[i];
				nums[i] = temp;
			}
		}
	}
}

四、鸡尾酒排序

鸡尾酒排序思路

鸡尾酒排序属于冒泡的优化版本,循环次数只有冒泡排序的一半

思路基本很像

冒泡排序是从头查到尾,一个循环里嵌套一个循环

鸡尾酒排序是一个从头查,一个从尾查,一个循环里嵌套两个循环

鸡尾酒排序代码

//鸡尾酒排序 冒泡排序的优化版本
template<class T>
void cocktailSortMin(T nums[], int length)
{
	//左边开始的位置和右边开始的位置
	int left = 0;
	int right = length - 1;
	//如果 左边和右边没有相遇,就循环
	while (left < right)
	{
		//从左边到右边开始循环,把大的数字往右移动
		for (int i = left; i < right; i++)
		{
			if (nums[i] > nums[i + 1])
			{
				T temp = nums[i];
				nums[i] = nums[i + 1];
				nums[i + 1] = temp;
			}
		}
		right--;//因为右边已经是最大的数字了,所以右边往左边移动

		//再从右边往左边开始循环,把小的数字往左移动
		for (int i = right; i > left; i--)
		{
			if (nums[i] < nums[i - 1])
			{
				T temp = nums[i];
				nums[i] = nums[i - 1];
				nums[i - 1] = temp;
			}
		}
		left++;//因为左边已经是最小的数字了,所以左边往右移动
		
	}
}
喜欢 (0)
订阅评论
提醒
guest
0 评论
内联反馈
查看所有评论