十大排序算法网站首页 学无止境

十大排序算法

wjfdsklfdkfksd 2024-06-17 06:01:02

简介十大排序算法

十大排序算法的时间复杂度

1.冒泡排序

步骤:从头元素开始比较每一对相邻元素，如果第1个比第2个大，就交换它们的位置，执行完一轮，最末尾的那个元素就是最大的元素

1.1冒泡算法

void BubbleSort(int arr[], size_t length)
{
	for (int end = length-1; end > 0; --end)//
	{
		for (int begin = 0; begin < end; ++begin)
		{
			if (arr[begin] > arr[begin +1])
			{
				int tmp = arr[begin];
				arr[begin] = arr[begin + 1];
				arr[begin + 1] = tmp;
			}
		}
	}
}

1.2优化1:如果已经完全有序，可以提前结束比较

void BubbleSort(int arr[], size_t length)
{
	for (int end = length - 1; end > 0; --end)//
	{
		bool bSorted = true;
		for (int begin = 0; begin < end; ++begin)
		{
			if (arr[begin] > arr[begin + 1])
			{
				int tmp = arr[begin];
				arr[begin] = arr[begin + 1];
				arr[begin + 1] = tmp;
				bSorted = false;
			}	
		}
		if (bSorted == true) break;//已经完全有序
	}
}

1.3 优化2:如果序列尾部已经局部有序，可以记录最后一次交换的位置，减少比较次数

尾部提前有序的情况

//冒泡排序的优化  如果序列尾部已经局部有序，可以记录最后一次交换的位置，减少比较次数
void BubbleSort(int arr[], size_t length)
{
	for (int end = length - 1; end > 0; --end)//
	{
		//为数组完全有序做准备的，只进行一次外循环就退出
		int iLastSortIndex = 1;
		for (int begin = 0; begin < end; ++begin)
		{
			if (arr[begin] > arr[begin + 1])
			{
				int tmp = arr[begin];
				arr[begin] = arr[begin + 1];
				arr[begin + 1] = tmp;
				iLastSortIndex = begin;//记录一下最后一次比较的位置
			}
		}
		end = iLastSortIndex;
	}
}

最坏,平均时间复杂度:O(n^2)
最好时间复杂度:O(n)经过一轮循环，如果是完全有序，可以提前退出。

算法稳定性

如果两个相等的元素，在排序前后的相对位置保持不变，就是稳定。
冒牌算法是稳定的排序算法，注意不要将 > 写成 >=

2.选择排序

执行流程：. 从序列中找到最大的那个元素，然后与最末尾的元素交换位置,最末尾的元素就是最大的元素

void  selectSort(int arr[], size_t length)
{
	for (int end = length - 1; end > 0; --end)//
	{
		int maxIndex = 0;
		for (int begin = 0; begin < end; ++begin)
		{
			if (arr[maxIndex] < arr[begin])
				maxIndex = begin;
		}
		//跟结尾进行交换
		int temp = arr[maxIndex];
		arr[maxIndex] = arr[end];
		arr[end] = temp;
	}
}