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

数据结构(快速排序——递归实现)

程序员文章站 2022-06-04 10:32:53
...

快速排序

快速排序由C. A. R. Hoare在1962年提出。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。

时间复杂度:O(nlogn)

空间复杂度:O(logn)

稳定性:不稳定

排序过程如图所示:

数据结构(快速排序——递归实现)
上图是进行一趟快速排序的过程

图示的意思是
1.先在整个待排序序列中选择一个基准数据,一般常用的就是第一个数据
2 i,j:
i从前向后 j从后向前 当i<j的时候
(1)从后向前找第一个比基准小的数据(i<j),找到后将其放到i位置
(2)从前向后找第一个比基准大的数据(i<j),找到后将其放到j位置
3.将基准值放到i位置
4.基准将数据序列划分成左右两部分,当左右两部分数据量大于1时,递归处理左右部分

我们来举个例子

例如:5、4、9、6、7、2、8

我们先将待排序的数组的第一个数字5定位关键字
定义i,j分别赋值为第一个数字和最后一个数字的下标,然后开始排序
第一趟排序
j下标的数字8和关键字5比较,由于大于关键字,8>5,所以 j-1,j继续与关键字比较,小于关键字,2<5,所以将2赋值给i下标的变量,然后i++,i与关键字比较,4<5,继续i++,i与关键字比较,9>5,所以将9赋值给j下标的变量,j-1,j与关键字比较,7>5,j-1,j与关键字比较,6>5,j-1,这时 i !< j 所以第一趟排序结束
排序结果:2、4、5、6、7、9、8
我们可以发现虽然现在的数据还不是很有顺序,但关键字5之前都比关键字小,关键字5之后都比关键字大
此时我们将数组分成两部分
【1】2、4
【2】6、7、9、8
继续让这两部分进行上述的排序,直至有序

参考代码

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define LENGTH 15        //待排序的数字个数

int GetWidth(int arr[],int left,int right)    //一次排序
{
	int tmp = arr[left];
	while(left<right)
	{
		while(left<right)
		{
			if(arr[right]>tmp)
			{
				right--;
			}
			else
			{
				arr[left] = arr[right];
				left++;
				break;
			}
		}
		while(left<right)
		{
			if(arr[left]<tmp)
			{
				left++;
			}
			else
			{
				arr[right] = arr[left];
				right--;
				break;
			}
		}
	}
	arr[left] = tmp;
	return left;
}

void OneQuick(int *arr,int left,int right)
{
	int width = GetWidth(arr,left,right);

	if((width-left)>1)
	{
		OneQuick(arr,left,width-1);
	}
	if((right-width)>1)
	{
		OneQuick(arr,width+1,right);
	}
}

void QuickSort(int *arr,int len)     //快速排序(递归实现)
{
	OneQuick(arr,0,len-1);
}

void ShowSort(int arr[],int len)     //打印
{
	for(int i=0;i<len;i++)
	{
		printf("%3d  ",arr[i]);
	}
	printf("\n");
}

int main()
{
	srand((unsigned int)time(NULL));

	int arr[LENGTH];

	for(int i=0;i<LENGTH;i++)
	{
		arr[i] = rand()%100;   //获得随机数
	}
	ShowSort(arr,LENGTH);

	QuickSort(arr,LENGTH);

	ShowSort(arr,LENGTH);
	return 0;
}