欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

小甲鱼 排序算法 快速排序

程序员文章站 2022-03-02 08:13:23
...

小甲鱼 排序算法 快速排序

 

#include <stdio.h>

//交换 
void swap(int k[], int low, int high)
{
	int temp;
	
	temp = k[low];
	k[low] = k[high];
	k[high] = temp;
}

//计算基准点的函数
//把将所有小于基准点的所有元素放在基准点的左边
//把将所有大于基准点的所有元素放在基准点的右边
int Partition(int k[], int low, int high)
{
	//low和high这里是指针 
	int point;
	
	point = k[low];//基准点定位第一个元素
	
	//当退出这个循环时,low和high接触在一块 
	while (low < high)
	{
		//比较右边 
		while (low < high && k[high] >= point)
		{
			high--;	
		}
		//比较右边,如果比基准点少,把基准点传过去,把小的数传进来 
		swap(k, low, high);//需要移动,交换,low相当于point基准点 
		
		//比较左边 
		while (low < high && k[low] <= point)
		{
			low++;//指向下一个 
		}
		//如果出了循环,出现左边的大于基准点,该与基准点进行交换 
		swap(k, low, high);//需要移动,交换 
	}
	
	return low;//返回中间点 
}

//low起始位置,high结束位置 
void QSort(int k[], int low, int high)
{
	int point;//基准点 
	
	//左边的指针和右边的指针都会移动,当指针重叠的时候,进行一轮比较了 
	if (low < high)
	{
		point = Partition(k, low, high);//基准点的定位 
		
		QSort(k, low, point-1);//对左边进行递归调用 
		
		QSort(k, point+1, high);//对右边进行递归调用  
	}
}

//外层函数,封装 
void QuickSort(int k[], int n)
{
	//实际的操作函数
	//参数:数组,初始位置,最大元素的位置 
	QSort(k, 0, n-1);
	
}

int main(void)
{
	int i, a[10] = {5, 2, 6, 0, 3, 9, 1, 7, 4, 8};
	
	QuickSort(a, 10);
	
	printf("排序后的结果是:");
	for(i = 0; i < 10; i++)
	{
		printf("%d", a[i]);
	}
	printf("\n\n");
	
	return 0;
}

 

相关标签: 快速排序

上一篇: Java-快速排序

下一篇: 快速排序