选择排序

选择排序是一种简单排序算法，核心为每次从未排序区间选出最小（大）元素，放到已排序区间的末尾，直至整个序列有序

直接选择排序

将数组分为已排序和未排序区间，每次从未排序区间选出最小（大）元素，交换到已排序区间的末尾，重复该操作直至整个数组有序

选择排序其实就是每遍历一次找出最小值，然后和第一个值做比较，如果小于第一个值就交换位置如果不小于第一个值就继续遍历，第二次遍历的时候找到第二个最小的值再和第二个位置值做比较如果小于第二个位置的值就交换不小于就第三次遍历以此类推

只找最小值排序

void Swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
void SelectSort(int* a, int n)
{
	int begin = 0, end = n - 1; 
	while (begin < end)
	{
		int mini = begin;
		for (int i = begin + 1; i <= end; i++)
		{
			if (a[i] < a[mini])
			{
				mini = i;
			}
		}
		Swap(&a[begin], &a[mini]);
		++begin;
	}
}

我们先找到第一个下标和最后一个下标然后用while循环来判断是否把下标已经走完，我们把第一个下标的值先看为最小的一个值，然后用for循环遍历从第二个下标开始遍历，如果第二个值还小于第一个最小的值那么就把最小值的下标赋值给mini，然后继续循环直到遍历一次所有的值后找到新的最小的那个值就停下来，把最小值的值和最开头值进行交换然后并把指向的下标往前走1

我们来测试一下代码

void TestSelectSort()
{
	int a[] = {9,1,2,5,7,4,6,3,10,8};
	int sc = sizeof(a) / sizeof(a[0]);
	PrintSort(a, sc);
	SelectSort(a, sc);
	PrintSort(a, sc);

}
int main()
{
	TestSelectSort();
	return 0;
}

现在是不是就排序好了，但是如果我们想同时把最小值和最大值都找到，把最小值放在前面，最大值放在后面会怎么样？

找最小值和最大值排序（错误代码）

void Swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
void SelectSort(int* a, int n)
{
	int begin = 0, end = n - 1; 
	while (begin < end)
	{
		int mini = begin,maxi = begin;
		for (int i = begin + 1; i <= end; i++)
		{
			if (a[i] > a[maxi])
			{
				maxi = i;
			}
			if (a[i] < a[mini])
			{
				mini = i;
			}
		}
		Swap(&a[begin], &a[mini]);
		Swap(&a[end], &a[maxi]);
		++begin;
		--end;
	}
}

我们先找到第一个下标和最后一个下标然后用while循环来判断是否把下标已经走完，我们把第一个下标的值先看为最小的一个值，把最后一个下标看成最大的一个值，然后用for循环遍历从第二个下标开始遍历，如果第二个值小于第一个最小的值那么就把最小值的下标赋值给mini，如果第二个值大于最后面的最大值就把最大值的下标赋值给maxi，然后继续循环直到遍历一次所有的值后找到最小值的下标和最大值的下标，把最小的那个值和最开头的值进行交换然后并把指向的下标往前走1，把最大的值和最后面的值交换后把指向最后面的下标往后走-1

现在我们来测试一下代码

void TestSelectSort()
{
	int a[] = {9,1,2,5,7,4,6,3,10,8};
	int sc = sizeof(a) / sizeof(a[0]);
	PrintSort(a, sc);
	SelectSort(a, sc);
	PrintSort(a, sc);

}
int main()
{
	TestSelectSort();
	return 0;
}

这是为什么呢？每一步看似都是对的，但为什么值出错了？这就是每一个初学者都会犯的经典错误，我们来调试一下代码

现在调试走到这里，我们找到了开始的下标和结束的下标和最大值和最小值

这两幅图片就是已经把两个if分支走完了，第一个if没有执行，第二个if里面第二个值小于第一个值，就把i的下标赋值给mini

现在继续

这段代码就是已经把第一趟的最大值和最小值找出来了

那现在我们就交换值，先把最小值和最前面的值交换

看上去好像没有毛病，现在开始第二趟循环

第二趟循环结束

现在开始交换第二小的值和第二个值(前方高能！！！)

看！！！问题就出在这里，我们没有更新下标，导致值被污染了，所以我们要在两个交换函数中写一个判断语句

修改错误代码

	if (begin == maxi)
		{
			maxi = mini;
		}

现在我们测试一下代码

现在就是我们完整的选择排序

选择排序时间复杂度

时间复杂度只关注最高阶项，并忽略常数系数，因此最终时间复杂度为 O(n^2)

堆排序

上期讲过堆排序，这里不多赘述：https://mp.csdn.net/mp_blog/creation/editor/157656814

交换排序

冒泡排序

核心思想

像水里的气泡向上浮一样，通过相邻元素两两比较、交换，每一轮把当前未排序区间里的最大值（或最小值）逐步 “冒泡” 到区间末尾，重复此过程直到整个数组有序

关键步骤

• 外层循环控制排序轮数（共 n-1 轮，n 为数组长度）
• 内层循环逐对比较相邻元素，若前一个比后一个大（升序），则交换位置
• 每轮结束后，末尾的一个元素会确定最终位置，后续轮次无需再比较

void Swap(int* p1, int* p2) 
{
    int tmp = *p1;
    *p1 = *p2;
    *p2 = tmp;
}
void BubbleSort(int* a, int n) 
{
    for (int i = 0; i < n - 1; i++) 
    {
        for (int j = 0; j < n - 1 - i; j++) 
        {
            if (a[j] > a[j + 1]) 
            {
                Swap(&a[j], &a[j + 1]);
            }
        }
    }
}

我们测试一下代码

冒泡排序时间复杂度

• 外层循环轮数：n−1 轮（n 为数组长度）；
• 每轮内层循环比较次数：第 1 轮 n−1 次，第 2 轮 n−2 次，…，第 n−1 轮 1 次；
• 总比较次数：(n−1)+(n−2)+...+1=n(n−1)/2

时间复杂度只关注最高阶项，并忽略常数系数，因此最终时间复杂度为 O(n^2)