算法导论 之 快速排序[C语言]

一、算法实现

快速排序的时间复杂度为O（n^2），但其通常是用于排序的最佳的使用选择，这是因为其平均性能相当好：期望的运行时间为O（nlgn）。其实现的算法如下：

int quick_sort(int *array, int low, int high)
{
	int idx = 0;

	if(low < high)
	{
		idx = partition(array, low, high);

		quick_sort(array, low, idx-1);
		quick_sort(array, idx+1, high);
	}

	return 0;
}

int partition(int *array, int low, int high)
{
	array[0] = array[low]; /* array[0]作为临时交换空间 */
	while(high > low)
	{
		while((array[high]>=array[0]) && (high>low)) { high--; }

		array[low] = array[high];
		left++;

		while((array[low]<=array[0]) && (high>low)) { low++; }

		array[high] = array[low];
		right--;
	}

	array[low] = array[0];

	return low;
}

二、函数调用

void print(int *array, int low, int high)
{
	int idx = low;
	char msg[1024] = {0}, str[128] = {0};

	while(idx <= max)
	{
		sprintf(str, "array[%d]=%d ", idx, array[idx]);
		strcat(msg, str);
		idx++;
	}
	fprintf(stdout, "%s\n", msg);
}

int main(void)
{
	int array[] = {-1, 9, 8, 7, 30, 5, 4, 3, -2, 1, 0};

	quick_sort(array, 1, 10);

	print(array, 1, 10);

	return 0;
}