常用的排序

不知不觉都过了一年了，只能感叹时光易逝啊。

10号要去软件园那边应聘实习生，所以今天晚上抽点时间复习了一遍常用的排序。

一. 冒泡

void MaoPao(int *nums, int length)
{
	for (int i = length-2; i > 0; i--)
	{
		for (int j = 0; j <= i; j++)
		{
			if (nums[j + 1] < nums[j])
			{
				swap(&nums[j], &nums[j+1]);
			}
		}
	}
}

　　这是最基础也是最容易想到的排序之一。时间(n²)，没啥好说的。

二. 选择

void XuanZhe(int *nums, int length)
{
	int minIndex = 0;
	bool changed = false;
	for (int i = 0; i < length-1; i++)
	{
		changed = false;
		minIndex = i;
		for (int j = i; j < length; j++)
		{
			if (nums[j] < nums[minIndex])
			{
				minIndex = j;
				changed = true;
			}			
		}
		if (changed) 
		{
			swap(&nums[i], &nums[minIndex]);
		}
	}
}

　　在冒泡、选择、插入里，选择排序算不错的了，起码对内存的操作没有其他两个那么频繁。

三. 插入

void ChaRu(int *nums, int length)
{
	for (int i = 1; i < length; i++) 
	{
		for (int j = 0; j < i; j++)
		{
			if (nums[i] < nums[j])
			{
				int temp = nums[i];
				for (int k = i; k > j; k--)
					nums[k] = nums[k - 1];
				nums[j] = temp;
			}
		}
	}
}

　　插入排序的代码让我想起了大一学C语言的灰暗时光。。。

四. 快排

void KuaiPai_DieDai(int *nums, int start, int end)
{
	if (start >= end)
		return;
	int high = end;
	int low = start;
	while (low < high)
	{
		while(nums[high] >= nums[low]&& low < high)
			high--;
		if(low < high)
			swap(&nums[low], &nums[high]);
		while (nums[low] <= nums[high] && low < high)
			low++;
		if (low < high)
			swap(&nums[low], &nums[high]);
	}
	KuaiPai_DieDai(nums, start, low-1);
	KuaiPai_DieDai(nums, high+1, end);
}

　　快排就舒服多了。除了不少的low<high有碍观瞻，不管是复杂度还是代码都算很不错的。

五.归并

void GuiBing_DieDai(int *nums, int start, int end, int* temp)
{
	if (start >= end)
		return;
	int mid = (start + end) / 2;
	GuiBing_DieDai(nums, start, mid, temp);
	GuiBing_DieDai(nums, mid + 1, end, temp);

	int first_low = start;
	int first_high = mid;
	int second_low = mid+1;
	int second_high = end;
	int tempIndex = 0;

	while (first_low <= first_high && second_low <= second_high)
	{
		if (nums[first_low] < nums[second_low] )
		{
			temp[tempIndex++] = nums[first_low];
			first_low++;
		}
		else
		{
			temp[tempIndex++] = nums[second_low];
			second_low++;
		}
	}
	while (first_low <= first_high)
	{
		temp[tempIndex++] = nums[first_low];
		first_low++;
	}
	while (second_low <= second_high)
	{
		temp[tempIndex++] = nums[second_low];
		second_low++;
	}
	for (int i = 0; i < tempIndex; i++)
	{
		nums[start + i] = temp[i];
	}
}

　　归并看起来就不那么舒服了，特别是空间上，除了递归的开销还要加个n。不过好在它是稳定的。

六.堆排序

void HeapAdjust(int *nums, int i, int length)
{
	int max = i;
	int lchild = i * 2 + 1;
	int rchild = i * 2 + 2;
	if (lchild < length && nums[lchild] > nums[max])
	{
		max = lchild;
	}
	if (rchild < length && nums[rchild] > nums[max])
	{
		max = rchild;
	}
	if (max != i)
	{
		int temp;
		temp = nums[i];
		nums[i] = nums[max];
		nums[max] = temp;
		HeapAdjust(nums, max, length);
	}
}
void Dui(int *nums, int length)
{
	for (int i = length / 2 - 1; i >= 0; i--)
	{
		HeapAdjust(nums, i, length);
	}
	for (int i = length - 1; i >= 0; i--)
	{
		swap(&nums[i], &nums[0]);
		HeapAdjust(nums, 0, i);
	}
}

　　第一个for循环构建大顶堆，第二个for循环开始排序。

找实习好难啊。。。