数据结构(快速排序——递归实现)
程序员文章站
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;
}