鲜于言悠905

鲜于言悠905

关注
发信
关注(28)粉丝(399)

数据结构从入门到精通——快速排序

前言

快速排序是一种高效的排序算法，通过选取一个“基准”元素，将数组分为两部分：比基准小的元素和比基准大的元素，然后递归地对这两部分进行排序，从而实现对整个数组的排序。该算法平均时间复杂度为O(nlogn)，最坏情况下为O(n²)，但由于实际应用中很少出现最坏情况，因此快速排序仍然是一种广泛使用的排序算法。

一、快速排序的基本思想

数据结构从入门到精通——快速排序-LMLPHP

快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

快速排序的基本思想是采用分治策略，通过选取一个“基准”元素，将待排序的数组分为两个子数组，一个子数组的元素都比基准元素小，另一个子数组的元素都比基准元素大，然后对这两个子数组递归地进行快速排序，从而达到对整个数组排序的目的。

在快速排序的具体实现中，通常选择数组中的一个元素作为基准元素，然后将数组中的其他元素与基准元素进行比较，根据比较结果将元素放到两个子数组中。这个过程可以通过使用双指针技术来实现，一个指针从数组的开头开始向右移动，另一个指针从数组的末尾开始向左移动，当左指针指向的元素小于等于基准元素，且右指针指向的元素大于等于基准元素时，交换这两个元素的位置。当左指针移动到右指针的位置时，整个数组就被划分为了两个子数组。

接下来，对这两个子数组分别进行快速排序。递归地调用快速排序函数，传入子数组的首尾指针作为参数，直到整个数组都被排序完毕。

快速排序的时间复杂度在最坏情况下为O(n²)，即当每次选取的基准元素都是当前数组中的最小或最大元素时，会导致每次划分得到的子数组大小相差很大，从而使得递归树的深度很大，排序效率降低。然而，在实际应用中，由于快速排序的随机性，其平均时间复杂度为O(nlogn)，因此在实际应用中具有很高的效率。

此外，快速排序是一种原地排序算法，只需要常数级别的额外空间，因此在处理大规模数据时具有很大的优势。同时，快速排序也是一种不稳定的排序算法，即相等的元素在排序后可能会改变它们的相对位置。

综上所述，快速排序是一种基于分治策略的排序算法，通过递归地将数组划分为子数组并对其进行排序，实现了对整个数组的排序。虽然在最坏情况下其时间复杂度可能达到O(n²)，但在实际应用中其平均时间复杂度为O(nlogn)，具有很高的效率。同时，快速排序也是一种原地、不稳定的排序算法，适用于处理大规模数据。

常见方式

将区间按照基准值划分为左右两半部分的常见方式有

  1. hoare版本
    数据结构从入门到精通——快速排序-LMLPHP

  2. 挖坑法
    数据结构从入门到精通——快速排序-LMLPHP

  3. 前后指针版本
    数据结构从入门到精通——快速排序-LMLPHP

通用模块

/ 假设按照升序对array数组中[left, right)区间中的元素进行排序
void QuickSort(int array[], int left, int right)
{
 	if(right - left <= 1)
	return;
 
 	// 按照基准值对array数组的 [left, right)区间中的元素进行划分
 	int div = partion(array, left, right);
 
 	// 划分成功后以div为边界形成了左右两部分 [left, div) 和 [div+1, right)
 	// 递归排[left, div)
 	QuickSort(array, left, div);
 
 	// 递归排[div+1, right)
 	QuickSort(array, div+1, right);
}

二、快速排序的特性总结

  1. 快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序
  2. 时间复杂度：O(N*logN)
    数据结构从入门到精通——快速排序-LMLPHP
  3. 空间复杂度：O(logN)
  4. 稳定性：不稳定

快速排序是一种高效的排序算法，其最显著的特点是其“分而治之”的策略。它的基本思想是通过一个分割操作，将待排序的序列划分为两个子序列，其中一个子序列的所有元素都比另一个子序列的所有元素要小，然后再对这两个子序列分别进行快速排序，从而达到整个序列有序的目的。

快速排序的高效性主要得益于其内部循环可以在大部分的实际情况下将元素放到最终的位置上，这被称为“原地排序”，因为它只需要常量级的额外空间来存放辅助信息。然而，这也带来了一个潜在的问题，即在最坏情况下，当输入序列已经有序或者逆序时，快速排序的时间复杂度会退化到O(n^2)，这是因为分割操作会导致不平衡的子序列划分。

快速排序的另一个重要特性是其不稳定性。这意味着在排序过程中，相等的元素可能会改变它们的相对顺序。这通常不会影响到排序结果的正确性，但在某些特定的应用场景下，如需要保持元素原始顺序的排序，就需要选择其他稳定的排序算法。

综上所述，快速排序是一种强大而灵活的排序工具，其“分而治之”的策略和原地排序的特性使其在许多情况下都成为首选的排序算法。然而，为了充分发挥其性能优势，也需要对其潜在的缺点有所了解，并采取相应的策略进行规避。

三、三种快速排序的动画展示

  1. hoare版本快速排序的动画展示
    Hoare版本快速排序的动画展示揭示了该排序算法的工作原理。在动画中，初始未排序的数组被选取一个基准值（pivot），然后将数组分为两部分：小于基准值的元素和大于基准值的元素。这个过程通过不断调整基准值的位置，使得数组逐渐变得有序。动画清晰展示了分区过程以及递归地对子数组进行相同操作的步骤，直到整个数组完全排序。整个过程直观展示了快速排序算法的高效性和稳定性。

    hoare——快速排序

  2. 挖坑法快速排序的动画展示
    挖坑法快速排序是一种排序算法的可视化展现。它展示了如何通过不断挖坑、填坑的过程，将数组分为两部分，使得左边的元素都比右边的元素小，从而实现快速排序。动画中，可以看到随着排序的进行，数组被逐渐整理成有序状态。

挖坑法——快速排序

  1. 前后指针快速排序的动画展示
    该段话介绍了前后指针快速排序的动画展示。其核心在于，通过动画形式直观地展示了前后指针快速排序的过程。该算法利用两个指针，以找到需要交换的元素对，并进行交换。通过重复此过程，最终实现数组的排序。动画演示使得这一过程更加直观易懂。

前后指针——快速排序

四、hoare版本快速排序的代码展示

普通版本

void Swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
void QuickSort(int* a, int left, int right)//hoare
{
	// 区间只有一个值或者不存在就是最小子问题
	if (left >= right)
		return;
		int begin = left, end = right;
		int keyi = left;
		while (left < right)
		{
			// right先走，找小
			while (left < right && a[right] >= a[keyi])
			{
				--right;
			}

			// left再走，找大
			while (left < right && a[left] <= a[keyi])
			{
				++left;
			}

			Swap(&a[left], &a[right]);
		}

		Swap(&a[left], &a[keyi]);
		keyi = left;
		// [begin, keyi-1]keyi[keyi+1, end]
		QuickSort(a, begin, keyi - 1);
		QuickSort(a, keyi + 1, end);
}

这段代码是实现了经典的快速排序（QuickSort）算法，使用了Hoare版本的分区（partitioning）策略。快速排序是一种非常高效的排序算法，平均时间复杂度为O(nlogn)。下面我将对代码进行逐行分析：

  1. void QuickSort(int* a, int left, int right)：定义了一个名为QuickSort的函数，它接受三个参数：一个整数数组的指针a，以及要排序的区间的左右端点left和right。

  2. if (left >= right) return;：如果区间内只有一个元素或者没有元素（即left大于或等于right），那么就没有排序的必要，函数直接返回。

  3. int begin = left, end = right;：定义了两个变量begin和end，分别初始化为区间的左右端点。这两个变量将用于后续的递归调用。

  4. int keyi = left;：定义了一个变量keyi，并初始化为区间的左端点。keyi将作为基准（pivot）值，用于划分数组。

  5. while (left < right)：主循环，当left小于right时继续执行循环体。

  6. 接下来的两个while循环用于调整数组元素的位置，使得比a[keyi]小的元素都在它的左边，比它大的元素都在它的右边。

    • 第一个while循环：从右向左遍历数组，找到第一个小于a[keyi]的元素，right的数值就是此时的下标。
    • 第二个while循环：从左向右遍历数组，找到第一个大于a[keyi]的元素，left的数值就是此时的下标。

  7. Swap(&a[left], &a[right]);：交换a[left]和a[right]两个元素的位置。

  8. Swap(&a[left], &a[keyi]);：将基准值a[keyi]放到正确的位置上，即它左边的所有元素都小于它，右边的所有元素都大于它。此时，left所指向的位置就是keyi的正确位置。

  9. QuickSort(a, begin, keyi - 1);：对基准值左边的子区间进行递归排序。

  10. QuickSort(a, keyi + 1, end);：对基准值右边的子区间进行递归排序。

这段代码实现了快速排序的基本思想：选择一个基准值，通过一趟排序将数组分成两部分，其中一部分的所有数据都比另一部分的所有数据要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

优化版本

为什么要优化快速排序代码

优化快速排序代码的目的是提高排序算法的性能，使其更快地完成排序任务。快速排序是一种高效的排序算法，但在某些情况下，原始的快速排序算法可能会比较慢或占用更多的内存。通过对代码进行优化，可以减少不必要的比较和交换操作，以提高算法的效率。

以下是一些常见的优化快速排序代码的方法：

  1. 选取合适的枢轴元素：枢轴元素的选择对快速排序的性能影响很大。选择一个合适的枢轴元素可以减少比较和交换的次数。常用的选择方法有随机选择、中位数选择和三数取中等。

  2. 使用插入排序：对于小规模的子数组，使用插入排序可能比快速排序更高效。当子数组的规模小于某个阈值时，可以切换到插入排序来提高性能。

  3. 优化递归调用：快速排序是一个递归算法，递归调用会带来一定的性能开销。可以考虑使用尾递归或迭代来替代递归调用，以减少函数调用的开销。

  4. 避免重复比较：在递归过程中，可能会重复比较相同的元素，这是不必要的。可以通过增加判断条件来避免重复比较，以提高性能。

总之，通过优化快速排序代码，可以加快排序算法的执行速度，减少不必要的开销，提高算法的效率。

三数取中法

三数取中法是一种排序算法中的选择方法，用于快速排序等算法中选取基准元素。它选取待排序数组中第一个、中间和最后一个元素中的中值作为基准，以保证基准元素的选择相对均匀，从而提高排序效率。这种方法在处理大量数据时表现优秀，能有效减少比较和交换次数，提高排序速度。

int GetMidi(int* a, int left, int right)
{
	int mid = (left + right) / 2;
	if (a[left] < a[mid])
	{
		if (a[mid] < a[right])
		{
			return mid;
		}
		else if (a[left] > a[right])
		{
			return left;
		}
		else return right;
	}
	else
	{
		if (a[mid] > a[right])
		{
			return mid;
		}
		else if (a[left] < a[right])
		{
			return left;
		}
		else
		{
			return right;
		}
	}
}

这段代码是一个函数，函数名为GetMidi，接受一个int类型的数组a和两个整型参数left和right。

函数的作用是找到数组a中的一个索引值，使得该索引值对应的元素值是数组中的"中间值"。"中间值"的定义是当数组a按照升序排列时，它的前半部分元素值都小于它，后半部分元素值都大于它。

函数首先计算mid值，即left和right的中间值。然后通过对比a[left]、a[mid]和a[right]的值，来确定mid值是否满足"中间值"的条件。

具体判断逻辑如下：

  • 首先判断a[left]和a[mid]的大小关系。
    • 若a[left] < a[mid]，则继续判断a[mid]和a[right]的大小关系。
      • 若a[mid] < a[right]，则返回mid。
      • 若a[left] > a[right]，则返回left。
      • 若以上条件均不满足，则返回right。
    • 若a[left] ≥ a[mid]，则继续判断a[mid]和a[right]的大小关系。
      • 若a[mid] > a[right]，则返回mid。
      • 若a[left] < a[right]，则返回left。
      • 若以上条件均不满足，则返回right。

这段代码的时间复杂度是O(1)，因为只是进行有限次的比较和赋值操作，不涉及循环。

优化代码

void Swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
void QuickSort(int* a, int left, int right)//hoare
{
	// 区间只有一个值或者不存在就是最小子问题
	if (left >= right)
		return;
	//优化,也可以不加
	if (right - left + 1 < 10)
	{
		InsertSort(a + left, right - left + 1);//直接插入排序，也可以换成其他排序
		return;
	}
	else
	{
		int begin = left, end = right;

		
		//优化，三数取中法
		int midi = GetMidi(a, left, right);
		Swap(&a[left], &a[midi]);
		int keyi = left;
		while (left < right)
		{
			// right先走，找小
			while (left < right && a[right] >= a[keyi])
			{
				--right;
			}

			// left再走，找大
			while (left < right && a[left] <= a[keyi])
			{
				++left;
			}

			Swap(&a[left], &a[right]);
		}

		Swap(&a[left], &a[keyi]);
		keyi = left;

		// [begin, keyi-1]keyi[keyi+1, end]
		QuickSort(a, begin, keyi - 1);
		QuickSort(a, keyi + 1, end);
	}
	
}

该代码实现了快速排序算法。

函数Swap用于交换两个指针所指向的值。

函数QuickSort是快速排序的主函数，它接受一个整型数组a、左右边界left和right作为参数。在函数中，首先判断区间的大小，如果区间只有一个值或者不存在，则直接返回。如果区间大小小于10，则使用插入排序进行排序，否则进行快速排序。

在快速排序的过程中，选择一个基准值（这里使用三数取中法选择基准值的索引），并将该基准值与左边界的值进行交换。然后，使用左右两个指针分别从左右两边开始向中间遍历，找到左边大于基准值的元素和右边小于基准值的元素，然后交换这两个元素的位置。最后将基准值与左指针的值进行交换，完成一次划分。

然后，将左边和右边的子数组进行递归调用快速排序，直到区间大小为1或不存在，完成整个排序过程。

总结起来，这段代码实现了一个使用了优化的快速排序算法，其中使用了三数取中法选择基准值和插入排序来优化小区间的排序。

五、挖坑法快速排序的代码展示

void Swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
void Quick1Sort(int* a, int left, int right)
{
	// 区间只有一个值或者不存在就是最小子问题
	if (left >= right)
		return;
	//优化,也可以不加
	if (right - left + 1 < 10)
	{
		InsertSort(a + left, right - left + 1);
		return;
	}
	int keyi = left, begin = left, end = right;
	int tmp = a[keyi];
	while (left < right)
	{
		// right先走，找小
		while (left < right && a[right] >= a[keyi])
		{
			--right;
		}
		Swap(&a[keyi], &a[right]);
		keyi = right;
		// left再走，找大
		while (left < right && a[left] <= a[keyi])
		{
			++left;
		}
		Swap(&a[keyi], &a[left]);
		keyi = left;
	}
	Swap(&a[keyi], &tmp);
	// [begin, keyi-1]keyi[keyi+1, end]
	Quick1Sort(a, begin, keyi - 1);
	Quick1Sort(a, keyi + 1, end);
}

这段代码实现了快速排序的挖坑算法。函数Quick1Sort接收一个整型数组a，以及数组的左右边界left和right。函数的作用是对数组a的[left, right]区间进行快速排序。

快速排序的基本思想是选取一个基准元素，将数组分为两个部分，一部分是小于等于基准元素的元素，另一部分是大于基准元素的元素。然后分别对这两部分递归进行快速排序，直到区间只有一个元素或者为空。

代码的具体实现如下：

  1. 如果left大于等于right，则不需要进行排序，直接返回。
  2. 如果区间的长度小于10，使用插入排序进行排序。这是一个优化，当区间长度较小时，插入排序的效率可能更高。
  3. 初始化两个指针keyi、begin和end。keyi指向基准元素，begin和end分别指向区间的左右边界。
  4. 使用tmp保存基准元素的值。
  5. 通过双指针的方式，找到比基准元素小的元素并交换到右侧，再找到比基准元素大的元素并交换到左侧。直到左指针和右指针相遇。此时左指针的位置就是基准元素的最终位置，将基准元素与tmp交换。
  6. 接下来，递归调用Quick1Sort函数对左右两个区间进行排序，左区间是[begin, keyi-1]，右区间是[keyi+1, end]。

六、前后指针快速排序的代码展示

void Quick2Sort(int* a, int left, int right)
{
	if (left >= right)return;
	int prev = left;
	int cur = left + 1;
	int key = left;
	while (cur <= right)
	{
		if (a[cur] < a[key] && ++prev != cur)
			Swap(&a[cur], &a[prev]);
		cur++;
	}
	Swap(&a[key], &a[prev]);
	key = prev;
	Quick2Sort(a, left, key - 1);
	Quick2Sort(a, key + 1, right);
}

这是快速排序的一种常见的排序算法，其基本思想是通过选择一个基准元素，将序列分为两个子序列，其中一个子序列中的元素都小于基准元素，另一个子序列中的元素都大于基准元素，然后对两个子序列递归地进行快速排序。

具体分析代码如下：

  1. 函数定义：void Quick2Sort(int* a, int left, int right)

    • 参数a表示待排序的数组，left和right表示数组的左右边界；
    • 返回类型为void，表示不需要返回排序后的数组。

  2. 判断递归结束条件：if (left >= right) return;

    • 如果左边界大于等于右边界，说明已经排好序或只有一个元素，无需再排序，直接返回。

  3. 初始化变量：

    • int prev = left;：prev表示小于基准元素的最后一个元素的位置，初始化为左边界；
    • int cur = left + 1;：cur表示当前遍历的元素的位置，初始化为左边界加1；
    • int key = left;：key表示基准元素的位置，初始化为左边界。

  4. 遍历数组：

    • while (cur <= right)：循环遍历数组，直到当前元素的位置大于右边界。
    • if (a[cur] < a[key] && ++prev != cur) Swap(&a[cur], &a[prev])：如果当前元素小于基准元素，且prev不等于cur（即有大于基准元素的元素存在），则将当前元素与prev位置上的元素进行交换，并且prev向后移动一位。
    • cur++：将当前元素的位置向后移动一位，继续遍历数组。

  5. 将基准元素放置到正确的位置：

    • Swap(&a[key], &a[prev])：将基准元素与prev位置上的元素进行交换，使得基准元素放置到正确的位置。

  6. 递归调用快速排序：

    • Quick2Sort(a, left, key - 1)：对左边子数组进行快速排序，左边界为left，右边界为key-1；
    • Quick2Sort(a, key + 1, right)：对右边子数组进行快速排序，左边界为key+1，右边界为right。

  7. 整个函数结束。

七、非递归实现快速排序的代码展示

实现栈的非递归需要使用到栈的知识——栈

对栈不理解的可以看我之前写的文章

Stack.h

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
typedef int STDatatype;
typedef struct Stack
{
	STDatatype* a;
	int top;
	int capacity;
}ST;

void STInit(ST* ps);//栈的初始化
void STDestroy(ST* ps);//栈的销毁

//入栈
void STPush(ST* ps,STDatatype x);
//出栈
void STPop(ST* ps);
STDatatype STTop(ST* ps);//返回栈顶元素
int STSize(ST* ps);//返回栈中的元素个数
bool STEmpty(ST* ps);//检测是否为空

Stack.c

#include "Stack.h"

void STInit(ST* ps)
{
	assert(ps);
	ps->a = NULL;
	ps->capacity = 0;
	ps->top = 0;
}
void STDestroy(ST* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->capacity = 0;
	ps->top = 0;
}
void STPush(ST* ps,STDatatype x)
{
	assert(ps);
	if (ps->top == ps->capacity)
	{
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		STDatatype* p = (STDatatype*)realloc(ps->a, sizeof(STDatatype)*newcapacity);
		if (p == NULL)
		{
			perror("p malloc : ");
			return ;
		}
		ps->a = p;
		ps->capacity = newcapacity;
	}
	ps->a[ps->top] = x;
	ps->top++;
}
void STPop(ST* ps)
{
	assert(ps);
	assert(!STEmpty(ps));
	ps->top--;
}

bool STEmpty(ST* ps)
{
	assert(ps);
	return ps->top == 0;
}
STDatatype STTop(ST* ps)
{
	assert(ps);
	assert(!STEmpty(ps));
	return ps->a[ps->top - 1];
}
int STSize(ST* ps)
{
	assert(ps);
	return ps->top;
}

非递归实现快速排序

void QuickSortNonR(int* a, int left, int right)
{
	ST st;
	STInit(&st);
	STPush(&st, right);
	STPush(&st, left);

	while (!STEmpty(&st))
	{
		int begin = STTop(&st);
		STPop(&st);

		int end = STTop(&st);
		STPop(&st);

		// 单趟
		int keyi = begin;
		int prev = begin;
		int cur = begin + 1;

		while (cur <= end)
		{
			if (a[cur] < a[keyi] && ++prev != cur)
				Swap(&a[prev], &a[cur]);
			++cur;
		}

		Swap(&a[keyi], &a[prev]);
		keyi = prev;

		// [begin, keyi-1] keyi [keyi+1, end] 
		if (keyi + 1 < end)
		{
			STPush(&st, end);
			STPush(&st, keyi + 1);
		}

		if (begin < keyi - 1)
		{
			STPush(&st, keyi - 1);
			STPush(&st, begin);
		}
	}

	STDestroy(&st);
}

这段代码实现的是非递归版本的快速排序算法。

首先，这段代码使用了一个栈结构ST来保存待排序子数组的起始和结束索引。

在主循环中，每次从栈中弹出两个索引，分别表示待排序子数组的起始和结束位置。接下来执行单趟排序，即将子数组中的元素按照基准元素的大小进行分区，使得基准元素左边的元素都小于或等于它，右边的元素都大于它。具体的分区过程使用了prev和cur两个指针，prev指向当前已处理的小于基准元素的最右边的位置，cur从prev+1开始遍历。如果a[cur]小于基准元素，则将它与prev+1位置的元素进行交换，并将prev向右移动一位。最后将基准元素放到prev位置，并用keyi保存基准元素的索引。

接下来，根据keyi的位置，将子数组分成左右两个部分。如果keyi+1小于end，说明右边的子数组还有未排序的元素，将右子数组范围的起始和结束索引入栈。如果begin小于keyi-1，说明左边的子数组还有未排序的元素，将左子数组范围的起始和结束索引入栈。

最后，在主循环结束后，销毁栈结构。

总的来说，这段代码通过栈结构实现了快速排序的非递归版本，避免了递归调用带来的额外开销。

八、快速排序的完整代码

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include "Stack.h"
void PrintArray(int* a, int n);
void QuickSort(int* a, int left, int right);//hoare
void Quick1Sort(int* a, int left, int right);//挖坑法
void Quick2Sort(int* a, int left, int right);//前后指针法
void QuickSortNonR(int* a, int left, int right);// 非递归实现
void InsertSort(int* a, int n)
{
	for (int i = 0; i < n - 1; i++)
	{
		int end = i;
		int tmp = a[end + 1];
		while (end >= 0)
		{
			if (tmp < a[end])
			{
				a[end + 1] = a[end];
				end--;
			}
			else
				break;
		}
		a[end + 1] = tmp;
	}
}


void Swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
void PrintArray(int* a, int n)
{
	for (int i = 0; i < n; i++)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
}
void TestQuickSort()
{
	//int a[] = { 5, 13, 9, 16, 12, 4, 7, 1, 28, 25, 3, 9, 6, 2, 4, 7, 1, 8 };
	int a[] = { 6,1,2,7,9,3,4,5,10,8 };
	//int a[] = { 1,2,3,4,5,6,7,8,9,10,11,12,13,15,17,19};
	PrintArray(a, sizeof(a) / sizeof(int));

	QuickSort(a, 0, sizeof(a) / sizeof(int) - 1);

	PrintArray(a, sizeof(a) / sizeof(int));
}
void TestQuick1Sort()
{
	int a[] = { 5, 13, 9, 16, 12, 4, 7, 1, 28, 25, 3, 9, 6, 2, 4, 7, 1, 8 };
	//int a[] = { 6,1,2,7,9,3,4,5,10,8 };
	//int a[] = { 1,2,3,4,5,6,7,8,9,10,11,12,13,15,17,19};
	PrintArray(a, sizeof(a) / sizeof(int));

	Quick1Sort(a, 0, sizeof(a) / sizeof(int) - 1);

	PrintArray(a, sizeof(a) / sizeof(int));
}
void TestQuick2Sort()
{
	int a[] = { 5, 13, 9, 16, 12, 4, 7, 1, 28, 25, 3, 9, 6, 2, 4, 7, 1, 8 };
	//int a[] = { 6,1,2,7,9,3,4,5,10,8 };
	//int a[] = { 1,2,3,4,5,6,7,8,9,10,11,12,13,15,17,19};
	PrintArray(a, sizeof(a) / sizeof(int));

	Quick2Sort(a, 0, sizeof(a) / sizeof(int) - 1);

	PrintArray(a, sizeof(a) / sizeof(int));
}
void TestQuick3Sort()
{
	int a[] = { 5, 13, 9, 16, 12, 4, 7, 1, 28, 25, 3, 9, 6, 2, 4, 7, 1, 8 };
	//int a[] = { 6,1,2,7,9,3,4,5,10,8 };
	//int a[] = { 1,2,3,4,5,6,7,8,9,10,11,12,13,15,17,19};
	PrintArray(a, sizeof(a) / sizeof(int));

	QuickSortNonR(a, 0, sizeof(a) / sizeof(int) - 1);

	PrintArray(a, sizeof(a) / sizeof(int));
}
int GetMidi(int* a, int left, int right)
{
	int mid = (left + right) / 2;
	if (a[left] < a[mid])
	{
		if (a[mid] < a[right])
		{
			return mid;
		}
		else if (a[left] > a[right])
		{
			return left;
		}
		else return right;
	}
	else
	{
		if (a[mid] > a[right])
		{
			return mid;
		}
		else if (a[left] < a[right])
		{
			return left;
		}
		else
		{
			return right;
		}
	}
}
void QuickSort(int* a, int left, int right)//hoare
{
	// 区间只有一个值或者不存在就是最小子问题
	if (left >= right)
		return;
	//优化,也可以不加
	if (right - left + 1 < 10)
	{
		InsertSort(a + left, right - left + 1);
		return;
	}
	else
	{
		int begin = left, end = right;

		
		//优化，三数取中法
		int midi = GetMidi(a, left, right);
		Swap(&a[left], &a[midi]);
		int keyi = left;
		while (left < right)
		{
			// right先走，找小
			while (left < right && a[right] >= a[keyi])
			{
				--right;
			}

			// left再走，找大
			while (left < right && a[left] <= a[keyi])
			{
				++left;
			}

			Swap(&a[left], &a[right]);
		}

		Swap(&a[left], &a[keyi]);
		keyi = left;

		// [begin, keyi-1]keyi[keyi+1, end]
		QuickSort(a, begin, keyi - 1);
		QuickSort(a, keyi + 1, end);
	}
	
}
void Quick1Sort(int* a, int left, int right)
{
	// 区间只有一个值或者不存在就是最小子问题
	if (left >= right)
		return;
	//优化,也可以不加
	if (right - left + 1 < 10)
	{
		InsertSort(a + left, right - left + 1);
		return;
	}
	int keyi = left, begin = left, end = right;
	int tmp = a[keyi];
	while (left < right)
	{
		// right先走，找小
		while (left < right && a[right] >= a[keyi])
		{
			--right;
		}
		Swap(&a[keyi], &a[right]);
		keyi = right;
		// left再走，找大
		while (left < right && a[left] <= a[keyi])
		{
			++left;
		}
		Swap(&a[keyi], &a[left]);
		keyi = left;
	}
	Swap(&a[keyi], &tmp);
	// [begin, keyi-1]keyi[keyi+1, end]
	Quick1Sort(a, begin, keyi - 1);
	Quick1Sort(a, keyi + 1, end);
}
void Quick2Sort(int* a, int left, int right)
{
	if (left >= right)return;
	int prev = left;
	int cur = left + 1;
	int key = left;
	while (cur <= right)
	{
		if (a[cur] < a[key] && ++prev != cur)
			Swap(&a[cur], &a[prev]);
		cur++;
	}
	Swap(&a[key], &a[prev]);
	key = prev;
	Quick2Sort(a, left, key - 1);
	Quick2Sort(a, key + 1, right);
}
void QuickSortNonR(int* a, int left, int right)
{
	ST st;
	STInit(&st);
	STPush(&st, right);
	STPush(&st, left);

	while (!STEmpty(&st))
	{
		int begin = STTop(&st);
		STPop(&st);

		int end = STTop(&st);
		STPop(&st);

		// 单趟
		int keyi = begin;
		int prev = begin;
		int cur = begin + 1;

		while (cur <= end)
		{
			if (a[cur] < a[keyi] && ++prev != cur)
				Swap(&a[prev], &a[cur]);
			++cur;
		}

		Swap(&a[keyi], &a[prev]);
		keyi = prev;

		// [begin, keyi-1] keyi [keyi+1, end] 
		if (keyi + 1 < end)
		{
			STPush(&st, end);
			STPush(&st, keyi + 1);
		}

		if (begin < keyi - 1)
		{
			STPush(&st, keyi - 1);
			STPush(&st, begin);
		}
	}

	STDestroy(&st);
}
void TestOP()
{
	srand(time(0));
	const int N = 1000000;
	int* a1 = (int*)malloc(sizeof(int) * N);

	for (int i = 0; i < N; ++i)
	{
		a1[i] = rand();
	}
	int begin1 = clock();
	QuickSort(a1,0,N- 1);
	int end1 = clock();
	printf("QuickSort:%d\n", end1 - begin1);
	free(a1);
}
void Test1OP()
{
	srand(time(0));
	const int N = 1000000;
	int* a1 = (int*)malloc(sizeof(int) * N);

	for (int i = 0; i < N; ++i)
	{
		a1[i] = rand();
	}
	int begin1 = clock();
	Quick1Sort(a1, 0, N - 1);
	int end1 = clock();
	printf("Quick1Sort:%d\n", end1 - begin1);
	free(a1);
}
void Test3OP()
{
	srand(time(0));
	const int N = 1000000;
	int* a1 = (int*)malloc(sizeof(int) * N);

	for (int i = 0; i < N; ++i)
	{
		a1[i] = rand();
	}
	int begin1 = clock();
	Quick2Sort(a1, 0, N - 1);
	int end1 = clock();
	printf("Quick2Sort:%d\n", end1 - begin1);
	free(a1);
}
void Test4OP()
{
	srand(time(0));
	const int N = 1000000;
	int* a1 = (int*)malloc(sizeof(int) * N);

	for (int i = 0; i < N; ++i)
	{
		a1[i] = rand();
	}
	int begin1 = clock();
	QuickSortNonR(a1, 0, N - 1);
	int end1 = clock();
	printf("QuickSortNonR:%d\n", end1 - begin1);
	free(a1);
}
int main()
{
	TestQuickSort();
	TestQuick1Sort();
	TestQuick2Sort();
	TestQuick3Sort();
	TestOP();
	Test1OP();
	Test3OP();
	Test4OP();
	return 0;
}

数据结构从入门到精通——快速排序-LMLPHP

03-23 15:25
Powered by LMLPHP ©2024 鲜于言悠905 0.002308