选择排序+快速排序递归版（二）

选择排序

推荐更优化一点的版本：选出最小的数和最左边位置的数交换，选出最大的和最右边的位置的数交换

代码

// 选择排序
void SelectSort(int* a, int n)
{
	int begin = 0, end = n - 1;
	while (begin < end)
	{
		int mint = begin, maxt = begin;
		for (int i = begin + 1; i <= end; ++i)
		{
			if (a[i] < a[mint]) mint = i;
			else if (a[i] > a[maxt]) maxt = i;
		}
		swap(&a[begin], &a[mint]);
		if (a[begin] == a[maxt])
		// 如果maxt和begin位置重叠,begin和mint换了,mint位置的值就是最大的了
		{
			maxt = mint;
		} 
		swap(&a[end], &a[maxt]);
		begin++;
		end--;
	}
}

int main()
{
	int a[] = { 2,32,13,4,4,53,12 };
	int n = sizeof(a) / sizeof(a[0]);
	SelectSort(a, n);
	for (int i = 0; i < n; ++i)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
	return 0;
}

对于if条件那里的解释：

时间复杂度分析:

最好情况是O(N^2) 数组是有序的，也要过一边数组
外面走一遍数组，里面也走一遍数组
最坏情况：O(N^2) 最坏情况也一样

快速排序递归版

快排有三种方法：
1.霍尔排序
2.前后指针
3.挖坑法

1. 左边找大，右边找小，跟key比较大小，（设key是左边第一个位置的数）然后交换，小的放左边，大的放右边
2. 这样快排就类型于一个完全二叉树的结构，左边递归，右边也递归
3. 相遇就停止，让相遇位置的数和最左边的数交换

代码

// 得到的是数是中间大的(下标)
int Getmidi(int* a, int left, int right)
{
	int mid = left + (right - left) / 2;// 防溢出
	// left mid right
	if (a[left] < a[mid])
	{
		if (a[mid] < a[right])
			return mid;
		else if (a[left] > a[right])//left right mid
			return left;
		else
			return right;
	}
	else// mid left
	{
		if (a[right] > a[left])
			return left;
		else if (a[right] < a[mid])
			return mid;
		else
			return right;
	}
}
// 快排
void QuickSort(int* a, int left, int right)
{
	// [0,0] [2,1]保证没有这两种情况
	if (left >= right) return;

	// 小区间优化，小于10个数不用分割区间，再递归
	if ((right - left + 1) < 10)
	{
		// 数组不一定在开头0位置
		InsertSort(a + left, right - left + 1);
	}
	else 
	{
		// 三数取中
		int midi = Getmidi(a, left, right);
		swap(&a[midi], &a[left]);

		int keyi = left;
		int begin = left, end = right;
		while (begin < end)
		{
			// 右边找小
			while (begin < end && a[keyi] <= a[end])
				end--;
			// 左边找大
			while (begin < end && a[keyi] >= a[begin])
				begin++;
			// 交换两个数
			swap(&a[begin], &a[end]);
		}
		// 交换keyi位置的值
		swap(&a[begin], &a[keyi]);
		// [begin,keyi - 1] keyi [keyi + 1,end]
		keyi = begin;
		// 递归左区间和右区间
		QuickSort(a, left,keyi - 1);
		QuickSort(a, keyi + 1, right);
	}
}
// 简单快速排序实现
int main()
{
	// 对三数取中的测试
	/*int a[10] = { 10,2,3,4,2,5,7,8,9,6 };
	int left = 0, right = 9;
	int mid = Getmidi(a, left, right);
	printf("%d\n", mid);*/

	int a[10] = { 1,3,342,3442,3,4,2,3,9,10 };
	
	QuickSort(a, 0, 9);
	for (int i = 0; i < 10; ++i)
	{
		printf("%d ", a[i]);
	}
	printf("\n");

	return 0;
}

时间复杂度分析

有logN层，每层都是N个数(遍历了一遍数组)
时间复杂度O(N*logN)

提问

非常重要

1. int key = a[left]
   swap(&key,&a[begin]) 为什么这样是错的？
   原因是key是局部变量，只是key变成a[begin]的值，而本身数组中的a[left]没有改变
2. 有序的场景为什么快排会溢出？
   <>递归的深度太深会溢出
   <>左边找大找一次就找到了，右边找小要找到他两相遇也找不到小，相当于遍历一遍数组，keyi = begin，少一个数，如此下去就是等差数列，时间复杂度是O(N*N),这样会导致栈溢出
3. 为什么Dubug版本会爆，而release不爆？
   <> 因为Dubug版本下有调试信息，优化不高
   <> 有调试的话，每个栈桢会大些，>= 1万就爆了
   <> release版本无调试，栈桢开得小，可容纳量增大
4. 怎么解决有序的情况（有序的话，时间复杂度为O(N)）？
   <> 选keyi可以解决这种情况
   <> 选keyi的方法：选到中间大的数
   <> 1.随机数选keyi
   <> 2.三数取中，最左边，最右边，中间的三个数取中间大的数（用下标，方便选出来的值和最左边交换，保证逻辑不变）
5. 快排的优化？
   <> 快排的递归类型于完全二叉树，最后几层占总递归数的90%左右
   <> 比如: 对最后五个值的递归进行优化，最后五个值要递归7次
   
   <> 小区间优化，不再递归分割排序，减少递归的次数
   比如：小于10个数就进行插入排序，因为插入排序是小范围排序中最优的（比冒泡，选择好），大于等于10个数就进行快排
6. <> a1[i] = rand() + i; 重复不多
   <> a1[i] = rand(); 重复较多，rand()产生的随机数不重复的有3万多个
7. 为什么相遇位置的数比keyi位置的数小？
   
8. 挖坑法对单趟排序是怎么进行优化的？
   挖坑法没有效率的提升，但是更容易理解
   挖坑发是左边是坑，右边先走找小，值放入左边，然后右边是坑，左边走找大，左边值放入右边，然后左边又是坑，如此类推