数据结构之排序4---（中位数和顺序统计学，希尔排序）

中位数和顺序统计学

• 中位数和顺序统计学
• 0、在一个由n个元素组成的集合中，第i个顺序统计量是该集合中第i小的元素
• 1、中位数是它所在集合的“中点元素”；当n为奇数时，中位数是唯一的，出现在i=(n+1)/2处；当n为偶数时，存在两个中位数，分别出现在i=n/2处和i=n/2+1处
• 2、找出集合中的最大和最小元素需要比较多少次？
• 找出集合中的最大元素的比较上界是n-1次，最小元素也是一样
• 3、如果要找出最大和最小元素，看起来需要2n-2次；事实上至多3(n/2)次比较就足以同时找到最大和最小元素：
• 成对的处理元素，先将一对元素互相比较，然后把较小的与当前最小元素比较，把较大的与当前最大元素比较，因此每两个元素需要比较3次
• 如何设定当前最大和最小值的初始值依赖于n是奇数还是偶数；如果n是奇数，就将最大值和最小值都设为第一个元素的值，然后成对的处理余下的元素；如果n是偶数，就对前两个元素做一次比较，以决定最大值和最小值的初值，然后如同n是奇数的情况一样，成对的处理余下的元素
• 4、期望情况为线性时间的选择：
• 期望时间复杂度：O(n)
• 最坏时间复杂度：O(n*n) 

情况好的情况： 

int Partition1(int ary[], int left, int right)    //快排的划分函数
{
	int i = left - 1;
	for (int j = left; j < right; ++j)
		if (ary[j] <= ary[right])
		{
			++i;
			swap(ary[i], ary[j]);
		}
	swap(ary[i + 1], ary[right]);
	return i + 1;
}
int RandomizedPartition(int ary[], int left, int right)    //快排的随机划分
{
	srand((unsigned)time(NULL));
	int rdm = rand() % (right - left) + left;
	swap(ary[right], ary[rdm]);
	return Partition1(ary, left, right);
}
int RandomizedSelect(int ary[], int left, int right, int i)
{                        //返回的是第i小的元素
	if (left == right)
		return ary[left];
	int rdm = RandomizedPartition(ary, left, right);    //rdm是划分之后主元的下标
	int k = rdm - left + 1;    //k是主元在当前区间中的第几个
	if (i == k)    //如果当前主元的位置k等于i，那么k对应的下标r就是所求元素的下标
		return ary[rdm];
	else if (i < k)
		return RandomizedSelect(ary, left, rdm - 1, i);
	else
		return RandomizedSelect(ary, rdm + 1, right, i - k);
	//为什么i-k ?
	//因为已经知道有k个元素（即ary[left..rdm]中的所有元素）小于ary[left..right]
	//中的第i小元素，所以所求元素必是ary[rdm+1..right]中的第i-k小的元素
}


void testRandomizedSelect()
{
	int a[10] = { 0,45,57,89,100,70,35,39,20,53 };
	for (int i = 1; i < 11; ++i)
	{
		cout << "第" << i << "小的数为：";
		cout << RandomizedSelect(a, 0, 9, i) << endl;
	}

}

 结果：

结果：
第1小的数为：0
第2小的数为：20
第3小的数为：35
第4小的数为：39
第5小的数为：45
第6小的数为：53
第7小的数为：57
第8小的数为：70
第9小的数为：89
第10小的数为：100

情况最坏的情况：

//最坏情况
int SelectPartition(int ary[], int left, int right, int pivot)
{
	int i = left - 1, j;
	for (j = left; j <= right; ++j)
		if (ary[j] == pivot)    //找到pivot的下标
			break;
	swap(ary[j], ary[right]);
	for (j = left; j < right; ++j)
		if (ary[j] <= pivot)
		{
			++i;
			swap(ary[i], ary[j]);
		}
	swap(ary[i + 1], ary[right]);
	return i + 1;
}
void InsertionSort(int ary[], int left, int right)
{
	for (int i = left + 1; i <= right; ++i)
	{
		int t = ary[i];
		int j = i - 1;
		while (j >= left && ary[j] > t)    //注意：略做修改，是j>=left
		{
			ary[j + 1] = ary[j];
			--j;
		}
		ary[j + 1] = t;
	}
}
int Select(int ary[], int left, int right, int i)
{                        //返回的是第i小的元素
	if (right - left < 5)
	{
		InsertionSort(ary, left, right);
		return ary[left + i];
	}
	int l, r;
	for (int j = 0; j < (right - left + 5) / 5; ++j)
	{
		l = left + j * 5,    //确定分组的left
			r = (left + j * 5 + 4) > right ? right : left + j * 5 + 4;    //确定分组的right
		InsertionSort(ary, l, r);    //排序当前分组
		swap(ary[left + j], ary[l + (r - l) / 2]);    //将各分组的中位数依次交换到前面
	}
	l = left;
	r = left + (right - left) / 5;    //定位移动之后的最右边中位数的位置，中位数的区间
	int pivot = Select(ary, l, r, (r - l) / 2);    //中位数的中位数
	int m = SelectPartition(ary, left, right, pivot);    //用中位数来划分
	int x = m - left;    //左边m-left个元素，右边right-m-1个元素，中间的是划分元素
	if (i == x)
		return ary[m];
	else if (i < x)
		return Select(ary, left, m - 1, i);
	else
		return Select(ary, m + 1, right, i - x - 1);
}

void testSelect()
{
	int a[10] = { 0,45,57,89,100,70,35,39,20,53 };
	for (int i = 0; i < 10; ++i)
	{
		cout << "第" << i << "小的数为：";
		cout << Select(a, 0, 9, i) << endl;
	}
}

结果：

结果：
第1小的数为：0
第2小的数为：20
第3小的数为：35
第4小的数为：39
第5小的数为：45
第6小的数为：53
第7小的数为：57
第8小的数为：70
第9小的数为：89
第10小的数为：100

希尔排序

• 希尔排序
• 将无序数组分割为若干个子序列。
• 子序列不是逐段分割的，而是相隔特定的增量的子序列。
• 对各个子序列进行插入排序；然后再选择一个更小的增量。
• 再将数组分割为多个子序列进行排序......最后选择增量为1。
• 即使用直接插入排序，使最终数组成为有序。
• 耗费的时间是O(n^2)
• 希尔排序是插入排序的高级版

 排序过程：

void ShellSort(int r[], int n)
{
	int i;
	int d;
	int j;
	for (d = n / 2; d >= 1; d = d / 2)            //以增量为d进行直接插入排序
	{
		for (i = d + 1; i < n; i++)
		{
			r[0] = r[i];                 //暂存被插入记录
			for (j = i - d; j > 0 && r[0] < r[j]; j = j - d)
				r[j + d] = r[j];       //记录后移d个位置
			r[j + d] = r[0];
		}
	}
	for (i = 1; i < n; i++)
		cout << r[i] << " ";
}

void testShellSort()
{
	int array[10] = { 0,6,1,2,4,7,8,9,3,5 };
	cout << "arr is old :";
	for (int i = 1; i < 10; i++)
	{
		cout << array[i] << " ";
	}
	cout << endl;
	ShellSort(array, 10);  //排序后
	cout << endl;
	cout << "arr is new :";
	for (int i = 1; i < 10; i++)
	{
		cout << array[i] << " ";
	}
	cout << endl;
}

结果：

结果：
arr is old :6 1 2 4 7 8 9 3 5
1 2 3 4 5 6 7 8 9
arr is new :1 2 3 4 5 6 7 8 9