快速排序算法 -- 深入研究

发布于:2025-02-11 ⋅ 阅读:(43) ⋅ 点赞:(0)

一 .  快排性能的关键点分析

快排性能的关键点分析 : 决定快排性能的关键点是每次单趟排序后 , key 对数组的分割 , 如果每次选key 基本二分居中,那么快排的递归树就是颗均匀的满二叉树,性能最佳。但是实际中虽然不可能每次都是二分居中,但是性能也还是可控的。但是如果出现每次选到的最小值/最大值,划分为0个和N-1个子问题时,时间复杂度会退化,时间复杂度为O(N^2) , 数组有序的时候会出现这样的问题 , 可以使用 三数取中 或者 随机选key 解决这个问题 , 但是还是有一些情景没有解决(有大量重复的数据) 

//数组中有多个与key相等的值
int a[] = {6,1,7,6,6,6,4,9}
int a[] = {3,2,3,3,3,3,3,2}

//数组全部是相同的值
int a[] = {2,2,2,2,2,2,2,2}
以下是《算法导论》书籍中给出的hoare和lomuto给出的快排的单趟排序的伪代码:

二 . 三路划分基本思路:

 当面对有大量跟key相同的值时 , 三路划分的核心思想有点类似hoare的左右指针 和 lumuto 的前后指针的结合 。 核心思想是把数组中的数据分成三段

【比key小的值】 【与key相等的值】 【比key大的值】

所以,称之为三路划分法 !

1 . key 默认取 left 位置的值

2 . left 指向区间最左边 , right 指向区间最右边 , cur指向left + 1 的位置

3 . cur 遇到比key小的值后 , left 与 cur交换 , left++ , cur--

4 . cur 遇到比key大的值后 , right 与 cur交换 ,right--

5 . cur遇到跟key相等的值后 , cur++

6 . 直到 cur > right 结束

 

三 . hoare和lomuto和三路划分单趟排序代码分析:

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include<string.h>
void PrintArray(int* a, int n)
{
	for (int i = 0; i < n; ++i)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
}
void Swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
// hoare
// [left, right]
int PartSort1(int* a, int left, int right)
{
	int keyi = left;
	++left;
	while (left <= right)//left和right相遇的位置的值⽐基准值要⼤
	{
		//right找到⽐基准值⼩或等
		while (left <= right && a[right] > a[keyi])
		{
			right--;
		}
		//left找到⽐基准值⼤或等
		while (left <= right && a[left] < a[keyi])
		{
			left++;
		}
		//right left
		if (left <= right)
		{
			Swap(&a[left++], &a[right--]);
		}

	}
	 //right keyi交换
		 Swap(&a[keyi], &a[right]);
	
		 return right;	
}
// 前后指针
int PartSort2(int* a, int left, int right)
{
	 int prev = left;
	 int cur = left + 1;
	 int keyi = left;
	 while (cur <= right)
		 {
		 if (a[cur] < a[keyi] && ++prev != cur)
			 {
			 Swap(&a[prev], &a[cur]);
			 }
		
			 ++cur;
		 }
	
		 Swap(&a[prev], &a[keyi]);
	 keyi = prev;
	 return keyi;
	 }

 typedef struct
{
	 int leftKeyi;
	 int rightKeyi;
}KeyWayIndex;

// 三路划分
 KeyWayIndex PartSort3Way(int* a, int left, int right)
{
	 int key = a[left];
	
		 // left和right指向就是跟key相等的区间
		// [开始, left-1][left, right][right+1, 结束]
		 int cur = left + 1;
	while (cur <= right)
		 {
		 // 1、cur遇到⽐key⼩,⼩的换到左边,同时把key换到中间位置
		// 2、cur遇到⽐key⼤,⼤的换到右边
		if (a[cur] < key)
			{
			Swap(&a[cur], &a[left]);
			 ++cur;
			++left;
			 }
		else if (a[cur] > key)
			{
			Swap(&a[cur], &a[right]);
			 --right;
			}
		 else
		{
			 ++cur;
		 }
		
	}
	
	 KeyWayIndex kwi;
	 kwi.leftKeyi = left;
	 kwi.rightKeyi = right;
	 return kwi;
 }

void TestPartSort1()
{
	 int a1[] = { 6,1,7,6,6,6,4,9 };
	 int a2[] = { 3,2,3,3,3,3,2,3 };
	 int a3[] = { 2,2,2,2,2,2,2,2 };
	
	PrintArray(a1, sizeof(a1) / sizeof(int));
	 int keyi1 = PartSort1(a1, 0, sizeof(a1) / sizeof(int) - 1);
	 PrintArray(a1, sizeof(a1) / sizeof(int));
	 printf("hoare keyi:%d\n\n", keyi1);
	
	PrintArray(a2, sizeof(a2) / sizeof(int));
	 int keyi2 = PartSort1(a2, 0, sizeof(a2) / sizeof(int) - 1);
	 PrintArray(a2, sizeof(a2) / sizeof(int));
	 printf("hoare keyi:%d\n\n", keyi2);
	 
	 PrintArray(a3, sizeof(a3) / sizeof(int));
	 int keyi3 = PartSort1(a3, 0, sizeof(a3) / sizeof(int) - 1);
	PrintArray(a3, sizeof(a3) / sizeof(int));
	  printf("hoare keyi:%d\n\n", keyi3);
}

void TestPartSort2()
{
	int a1[] = { 6,1,7,6,6,6,4,9 };
	int a2[] = { 3,2,3,3,3,3,2,3 };
	int a3[] = { 2,2,2,2,2,2,2,2 };
	
	PrintArray(a1, sizeof(a1) / sizeof(int));
	int keyi1 = PartSort2(a1, 0, sizeof(a1) / sizeof(int) - 1);
	PrintArray(a1, sizeof(a1) / sizeof(int));
	printf("前后指针 keyi:%d\n\n", keyi1);

	PrintArray(a2, sizeof(a2) / sizeof(int));
	int keyi2 = PartSort2(a2, 0, sizeof(a2) / sizeof(int) - 1);
	PrintArray(a2, sizeof(a2) / sizeof(int));
	printf("前后指针 keyi:%d\n\n", keyi2);

	PrintArray(a3, sizeof(a3) / sizeof(int));
	 int keyi3 = PartSort2(a3, 0, sizeof(a3) / sizeof(int) - 1);
	 PrintArray(a3, sizeof(a3) / sizeof(int));
	 printf("前后指针 keyi:%d\n\n", keyi3);
}

void TestPartSort3()
{
	//int a0[] = { 6,1,2,7,9,3,4,5,10,4 };
	 int a1[] = { 6,1,7,6,6,6,4,9 };
	 int a2[] = { 3,2,3,3,3,3,2,3 };
	 int a3[] = { 2,2,2,2,2,2,2,2 };

	 PrintArray(a1, sizeof(a1) / sizeof(int));
	 KeyWayIndex kwi1 = PartSort3Way(a1, 0, sizeof(a1) / sizeof(int) - 1);
	 PrintArray(a1, sizeof(a1) / sizeof(int));
	 printf("3Way keyi:%d,%d\n\n", kwi1.leftKeyi, kwi1.rightKeyi);
	
	 PrintArray(a2, sizeof(a2) / sizeof(int));
	 KeyWayIndex kwi2 = PartSort3Way(a2, 0, sizeof(a2) / sizeof(int) - 1);
	 PrintArray(a2, sizeof(a2) / sizeof(int));
	 printf("3Way keyi:%d,%d\n\n", kwi2.leftKeyi, kwi2.rightKeyi);
	
	 PrintArray(a3, sizeof(a3) / sizeof(int));
	 KeyWayIndex kwi3 = PartSort3Way(a3, 0, sizeof(a3) / sizeof(int) - 1);
	 PrintArray(a3, sizeof(a3) / sizeof(int));
	 printf("3Way keyi:%d,%d\n\n", kwi3.leftKeyi, kwi3.rightKeyi);
}

int main()
{
	TestPartSort1();
	TestPartSort2();
	TestPartSort3();

return 0;
}

 四 .三种快排单趟排序运⾏结果分析:

从下面的运行结果分析,lomuto的前后指针法,面对key有大量重复时,lomuto划分不是很理想,性能退化,hoare相对还不错,但是大量重复时,没有三路划分快。三路划分算法,把跟key相等的值都划分到了中间,可以很好的解决这里的问题。

6 1 7 6 6 6 4 9
6 1 4 6 6 6 7 9
hoare keyi:3

3 2 3 3 3 3 2 3
3 2 3 2 3 3 3 3
hoare keyi:4

2 2 2 2 2 2 2 2
2 2 2 2 2 2 2 2
hoare keyi:3

6 1 7 6 6 6 4 9
4 1 6 6 6 6 7 9
前后指针 keyi:2

3 2 3 3 3 3 2 3
2 2 3 3 3 3 3 3
前后指针 keyi:2

2 2 2 2 2 2 2 2
2 2 2 2 2 2 2 2
前后指针 keyi:0

6 1 7 6 6 6 4 9
1 4 6 6 6 6 9 7
3Way keyi:2,5

3 2 3 3 3 3 2 3
2 2 3 3 3 3 3 3
3Way keyi:2,7

2 2 2 2 2 2 2 2
2 2 2 2 2 2 2 2
3Way keyi:0,7

五 . 基于三路划分解决算法题

912. 排序数组 - 力扣(LeetCode) 

这个OJ,当我们用快排的时候,lomuto的方法,过不了这个题目,hoare版本可以过这个题目。堆排序和归并和希尔是可以过的,其 他几个O(N^2)也不过了,因为这个题的测试用例中不仅仅有数据很多的大数组,也有⼀些特殊数据的数组,如大量重复数据的数组。堆排序和归并和希尔不是很受数据样本的分布和形态的影响,但是快排会,因为快排要选key,每次key都当趟分割都很偏,就会出现效率退化问题。
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
 void Swap(int* x,int* y)
 {
    int tmp = *x;
    *x = *y;
    *y = tmp;
 }
 void QuickSort(int* arr,int left,int right)
 {
    if(left >= right)
    {
        return ;
    }
    int begin = left;
    int end = right;

    //随机选key
    int randi = left + (rand()%(right-left +1));
    Swap(&arr[left],&arr[randi]);

    int key = arr[left];
    int cur = left+1;
    while(cur <=right)
    {
        if(arr[cur] < key)
        {
            Swap(&arr[cur],&arr[left]);
            left++;
            cur++;
        }
        else if(arr[cur] > key)
        {
            Swap(&arr[cur],&arr[right]);
            right--;
        }
        else
        {
            cur++;
        }
    } 
    QuickSort(arr,begin,left-1);
    QuickSort(arr,right+1,end);

 }
int* sortArray(int* nums, int numsSize, int* returnSize) {
    srand(time(0));
    QuickSort(nums,0,numsSize-1);
    *returnSize = numsSize;
    return nums;
}

六 . 内省排序

introsort 是 introspective sort采用了缩写,他的名字其实表达了他的实现思路,他的思路就是进行自我侦测和反省,快排递归深度太深(sgi stl中使用的是深度为2倍排序元素数量的对数值)那就说明在这种数据序列下,选key出现了问题,性能在快速退化,那么就不要再进行快排分割递归了, 改换为堆排序进行排序。
void HeapSort(int* a, int n)
{
	// 建堆 -- 向下调整建堆 -- O(N)
	for (int i = (n - 1 - 1) / 2; i >= 0; --i)
	{
		AdjustDown(a, n, i);
	}

	// ⾃⼰先实现 -- O(N*logN)
	int end = n - 1;
	while (end > 0)
	{
		Swap(&a[end], &a[0]);
		AdjustDown(a, end, 0);
		--end;
	}
}
void InsertSort(int* a, int n)
{
	for (int i = 1; i < n; i++)
	{
		int end = i - 1;
		int tmp = a[i];
		// 将tmp插⼊到[0,end]区间中,保持有序
		while (end >= 0)
		{
			if (tmp < a[end])
			{
				a[end + 1] = a[end];
				--end;
			}
			else
			{
				break;
			}
		}
		a[end + 1] = tmp;
	}
}
void IntroSort(int* a, int left, int right, int depth, int defaultDepth)
{
	if (left >= right)
		return;

	// 数组⻓度⼩于16的⼩数组,换为插⼊排序,简单递归次数
	if (right - left + 1 < 16)
	{
		InsertSort(a + left, right - left + 1);
		return;
	}
	// 当深度超过2*logN时改⽤堆排序
	if (depth > defaultDepth)
	{
		HeapSort(a + left, right - left + 1);
		return;
	}
	depth++;
	int begin = left;
	int end = right;
// 随机选key
	int randi = left + (rand() % (right - left + 1));
	Swap(&a[left], &a[randi]);
	int prev = left;
	int cur = prev + 1;
	int keyi = left;
	while (cur <= right)
	{
		if (a[cur] < a[keyi] && ++prev != cur)
		{
			Swap(&a[prev], &a[cur]);
		}
		++cur;
	}
	Swap(&a[prev], &a[keyi]);
	keyi = prev;
	// [begin, keyi-1] keyi [keyi+1, end]
	IntroSort(a, begin, keyi - 1, depth, defaultDepth);
	IntroSort(a, keyi + 1, end, depth, defaultDepth);
}
void QuickSort(int* a, int left, int right)
{
	int depth = 0;
	int logn = 0;
	int N = right - left + 1;
	for (int i = 1; i < N; i *= 2)
	{
		logn++;
	}


	// introspective sort -- ⾃省排序
	IntroSort(a, left, right, depth, logn * 2);
}

int* sortArray(int* nums, int numsSize, int* returnSize) {
	srand(time(0));
	QuickSort(nums, 0, numsSize - 1);

	*returnSize = numsSize;
	return nums;
}

网站公告

今日签到

点亮在社区的每一天
去签到