• • 人阅读

快速排序

快排算法原理比较简单，选定一个值，根据这个值对数组做划分，小的放左边，大的放右边，然后递归划分子数组。

划分函数

int partition(int * a, int low, int high)
{
	int v = a[low];
	int i = low;
	int j = high+1;
	while (i < j)
	{
		// 子循环条件如果是i<j可能会导致j==i时退出，此时不一定a[j]<v
		while (a[++i] < v && i < high);
		while (a[--j] > v && j > low);
		if (i < j) swap(a, i, j);
	}
	// 此时a[j]<v
	swap(a, low, j);
	return j;
}

递归版本

递归版本就直接按照快排原理写代码即可，对外接口是对递归函数的封装。

void qsort(int * a, int low, int high)
{
	if (high - low <= 0) return;
	int j = partition(a, low, high);
	qsort(a, low, j - 1);
	qsort(a, j + 1, high);
}

void quick_sort(int * a, int N)
{
	return qsort(a, 0, N - 1);
}

非递归版本

因为递归调用其实是系统维护的函数调用栈，因此非递归版本我们自己维护栈就好。 下面的实现里直接使用STL的栈，自己构建一个也可以。

void quick_sort_2(int * a, int N)
{
	stack<pair<int, int>> st;
	st.push(make_pair(0, N - 1));
	while (st.size())
	{
		int low = st.top().first;
		int high = st.top().second;
		st.pop();
		if (high - low <= 0) continue;
		int j = partition(a, low, high);
		st.push(make_pair(low, j - 1));
		st.push(make_pair(j + 1, high));
	}
}

堆排序

下沉函数

下沉函数是堆中的关键函数，作用是将一个值下沉到堆中的正确位置。下面是大根堆的下沉函数实现。

void sink(int * a, int k, int N)
{
	while (2 * k < N)
	{
		int j = 2 * k;
		if (j < N && a[j] < a[j + 1]) j++;
		if (a[k] >= a[j]) break;
		swap(a, k, j);
		k = j;
	}
}

构建堆及堆排序

void heap_sort(int * a, int N)
{
	// 构建堆
	for (size_t k = N / 2; k >= 1; k--)
	{
		sink(a, k, N);
	}
	// 不断交换堆顶和堆底，利用堆调整进行排序
	while (N > 1)
	{
		swap(a, 1, N--);
		sink(a, 1, N);
	}
}

测试函数

int main(int argc, char ** argv)
{
	int a[10] = { 1, 2, 4, -4, 5, 66, -5, 7, 8, 22 };
	quick_sort(a, 10);
	heap_sort(a-1, 10);//a[0]用不到
	for (int i = 0; i < 10; ++i) cout << a[i] << " ";
	getchar();
	return 0;
}