快速排序(c语言代码实现)

交换排序：快速排序（不稳定的排序）

快速排序（Quick Sort）是一种常见的排序算法，它采用分治法的思想，对待排序序列进行划分，使得划分出的子序列可以分别进行排序，最终使整个序列有序。快速排序的最好情况下的时间复杂度为：O(nlogn)，最坏时间复杂度：O(n^2)，是一种高效的排序算法。快速排序是所有内部排序算法中平均性能最优的排序算法

快速排序的具体实现：

1. 选择一个基准元素，一般选择第一个元素作为基准元素；
2. 将序列分为两部分，一部分是所有比基准元素小的元素，另一部分是所有比基准元素大的元素；
3. 对两个子序列进行递归排序，直到子序列长度为1，排序完成。

代码如下

int part(int arr[], int low, int high)
{
	int pivot = arr[low];//将当前表中的第一个元素设为枢轴，对表进行划分
	while (low < high)//循环跳出条件
	{
		while (low < high && arr[high] >= pivot)
			--high;
		arr[low] = arr[high];//将比枢轴小的元素移动到左端
		while (low < high && arr[low] <= pivot)
			++low;
		arr[high] = arr[low];//将比枢轴大的元素移动到右端
	}
	arr[low] = pivot;//枢轴元素存放到最终位置
	return low;//返回存放枢轴的最终位置
}
void quicksort(int arr[], int low, int high)
{
	if (low < high)
	{
		int pivot = part(arr, low, high);
		quicksort(arr, low, pivot-1);//依次对两个子表进行递归排序
		quicksort(arr, pivot+1, high);
	}
}

完整测试代码

#include<stdio.h>
int part(int arr[], int low, int high)
{
	int pivot = arr[low];//将当前表中的第一个元素设为枢轴，对表进行划分
	while (low < high)//循环跳出条件
	{
		while (low < high && arr[high] >= pivot)
			--high;
		arr[low] = arr[high];//将比枢轴小的元素移动到左端
		while (low < high && arr[low] <= pivot)
			++low;
		arr[high] = arr[low];//将比枢轴大的元素移动到右端
	}
	arr[low] = pivot;//枢轴元素存放到最终位置
	return low;//返回存放枢轴的最终位置
}
void quicksort(int arr[], int low, int high)
{
	if (low < high)
	{
		int pivot = part(arr, low, high);
		quicksort(arr, low, pivot-1);//依次对两个子表进行递归排序
		quicksort(arr, pivot+1, high);
	}
}
int main()
{
	int i = 0;
	int arr[7] = { 49,38,65,98,76,13,27 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	printf("原始数组为：");
	for (i = 0; i < sz; i++)
	{
		printf("%d ", arr[i]);
	}
	quicksort(arr, 0, sz - 1);
	printf("\n快速排序之后的数组为：");
	for (i = 0; i < sz; i++)
	{
		printf("%d ", arr[i]);
	}
	return 0;
}