常見排序算法之選擇排序

1.直接選擇排序

直接選擇排序和直接插入排序類似，都將數(shù)據(jù)分為有序區(qū)和無序區(qū)，所不同的是直接插入排序是將無序區(qū)的第一個元素直接插入到有序區(qū)以形成一個更大的有序區(qū)，而直接選擇排序是從無序區(qū)選一個最小的元素直接放到有序區(qū)的最后。

設數(shù)組為a[0…n-1]。

1.      初始時，數(shù)組全為無序區(qū)為a[0..n-1]。令i=0

2.      在無序區(qū)a[i…n-1]中選取一個最小的元素，將其與a[i]交換。交換之后a[0…i]就形成了一個有序區(qū)。

3.      i++并重復第二步直到i==n-1。排序完成

這里直接給出一種比較優(yōu)化的直接選擇排序，每次遍歷選出最大值和最小值

void SelectSort(int* a, size_t n)  //選擇排序優(yōu)化版
{
	assert(a);

	for (int left = 0, right = n - 1; left < right; ++left, --right)
	{
		int min = left;
		int max = right;

		for (int i = left; i <= right; ++i)
		{
			if (a[i] < a[min])
				min = i;
			else if (a[i] > a[max])
				max = i;
		}

		if (min != left)
		{
			std::swap(a[min], a[left]);

			if (max == left)
			{
				max = min;
			}
		}
		if (max != right)
		{
			std::swap(a[max], a[right]);
		}

	}
}

2.堆排序

將待排序的數(shù)組建立一個大堆，每次將堆頂?shù)脑厝〕龇旁跀?shù)組的最后一個位置上，再對數(shù)組的長度減1，然后對堆進行調(diào)整，使之仍然是一個大堆，直到堆的長度為1，將此元素放在數(shù)組的起始位置，排序完成。

void AdjustDown(int* a, size_t size, size_t root)
{
	assert(a);

	int child = root * 2 + 1;
	while (child < size)
	{
		if (child+1 < size && a[child + 1] > a[child])
		{
			++child;
		}
		if (a[child] > a[root])
		{
			std::swap(a[child], a[root]);
			root = child;
			child = root * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

void HeapSort(int* a, size_t n)
{
	assert(a);
	for (int i = (n-2)/2; i >=0 ; --i)
	{
		AdjustDown(a, n, i);  //建（大）堆
	}

	for (int i = n - 1; i > 0; --i)  //這樣寫比較好
	{
		std::swap(a[0], a[i]);
		AdjustDown(a, i - 1, 0);
	}

}