首页 > 代码库 > 排序(5)---------快速排序(C语言实现)

排序(5)---------快速排序(C语言实现)

继shell发明了shell排序过后呢,各位计算机界的大牛们又开始不爽了,为什么他能发明,我就不能发明呢。于是又有个哥们蹦出来了。哎。。。那么多排序,就木有一个排序是中国人发明的。顺便吐槽一下,一百年的天朝的历史书里还在吹,祖冲之第一个发现圆周率,领先世界一千多年......


快速排序使用分治法(Divide and conquer)策略来把一个串行(list)分为两个子串行(sub-lists)。
步骤为:

1,从数列中挑出一个元素,称为 "基准",
2,重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分区退出之后,该基准就处于数列的中间位置。这个称为分区操作。
3,递归地把小于基准值元素的子数列和大于基准值元素的子数列排序。
4,递归的最底部情形,是数列的大小是零或一,也就是永远都已经被排序好了。虽然一直递归下去,但是这个算法总会退出,因为在每次的迭代中,它至少会把一个元素摆到它最后的位置去。


①先假定序列的第一个元素为标志位,从第一位到最后一直与标志位进行比较,比标志位小的全部移到标志位的左边,比标志位大的全部移到标志位的右边

②对标志位左边的进行步骤①操作,右边亦是,形成新的两个标志位,依次递归下去


源代码:

#include "stdafx.h"
#include <stdlib.h>

void swap(int arr[],int i, int j) //交换
{
	int temp = arr[i];
	arr[i] = arr[j];
	arr[j] = temp;
}


int getPoint(int arr[],int low ,int  high)
{
	int res = arr[low];   //第一次假定第一个元素即为标志点
	while (low < high)
	{
		while ((low < high) && (arr[high] >= res))
		{
			high--;
		}
		swap(arr,low,high);
		
		while ((low < high) && (arr[low] <= res))
		{
			low++;
		}
		swap(arr,low,high);
	}

	return low;
}

void QSort(int arr[],int low ,int high)
{
	if (low < high)
	{
		int lowIndex = getPoint(arr, low, high);

		QSort(arr, low,lowIndex-1);
		QSort(arr, lowIndex+1,high);
	}
}

void Quick_Sort(int arr[], int low, int high)
{
	QSort(arr, low, high-1);
}


int main(void)
{
	int arr[10];
	
	for ( int i=0; i<10; i++)  //初始化数据
	{
		arr[i] = rand()%33;  //随机生成数据
	}
	printf("Before sort:\n");  //打印排序前的数据
	for (int i = 0; i < 10; i++)
	{
		printf("%d ",arr[i]);
	}

	//开始排序
	Quick_Sort(arr,0,10);


	printf("\nAfter sort:\n"); //打印排序后的数据
	for (int i = 0; i < 10; i++)
	{
		printf("%d ",arr[i]);
	}
	system("pause");
	return 0;
}

运行结果:

Before sort:
8 20 31 1 29 16 27 21 1 11
After sort:
1 1 8 11 16 20 21 27 29 31 请按任意键继续. . .


如有错误,望不吝指出。