首页 > 其他分享 >数据结构——快速排序

数据结构——快速排序

时间：2024-11-11 22:19:13浏览次数：3  
标签：排序 return int mid right key 数据结构 快速 left

目录

一、排序思想

二、代码实现

（一）hoare版

1、原版——固定选key

2、随机选key、三数取中选key

（二）挖坑法

（三）前后指针法

（四）小区间优化

（五）非递归写法

一、排序思想

任取待排序元素序列中的某元素作为基准值，按照该基准值将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后左右两子序列重复该过程，直到所有元素都排列在相应位置上为止。

二、代码实现

下列所有代码示例均是排成升序。

注：

快排在对存在大量相同的数据排序时，效率很低，这种情况三路划分可以解决，感兴趣的朋友可以自行了解，这里不作介绍。

（一）hoare版

1、原版——固定选key

缺点：

固定位置选key，在数据有序或几乎有序时容易栈溢出。

注：

选最左边元素为key，最右边先开始选数


选最右边元素为key，最左边先开始选数

#include<stdio.h>

void Print(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;
}

//haore
void QuickSort1(int* a, int left, int right)
{
	if (left >= right)
	{
		return;
	}
	int begin = left;
	int end = right;
	int keyi = left;
	while (left < right)
	{
		//右边找小
		while (left < right && a[right] >= a[keyi])
		{
			right--;
		}
		//左边找大
		while (left < right && a[left] <= a[keyi])
		{
			left++;
		}
		Swap(&a[left], &a[right]);
	}
	Swap(&a[left], &a[keyi]);
	keyi = left;
	//begin keyi-1  keyi  key+1 end
	QuickSort1(a, begin, keyi - 1);
	QuickSort1(a, keyi+1, end);

}

int main()
{
	int arr[10] = { 9,8,7,6,5,4,3,2,1,0 };

	QuickSort1(arr, 0, sizeof(arr) / sizeof(arr[0]) - 1);
	Print(arr, 10);

	return 0;
}

2、随机选key、三数取中选key

思想较之于原版并没有本质变化，只是优化了选key的方式。

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

//打印
void Print(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;
}

//三数取中
int Midnum(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;
		}
	}

}

//快排(升序)——hoare(优化选key)
void QuickSort(int* a,int left,int right)
{
	if (left >= right)
	{
		return;
	}
	int begin = left;
	int end = right;
	//随机选key
	/*int ran = left + rand() % (right - left);
	Swap(&a[left], &a[ran]);
	int keyi = left;*/
	
	//三数取中选key
	int mid = Midnum(a,left, right);
	Swap(&a[left], &a[mid]);
	int keyi = left;
	while (left < right)
	{
		//右边找小
		while (left < right && a[right] >= a[keyi])
		{
			right--;
		}
		//左边找大
		while (left < right && a[left] <= a[keyi])
		{
			left++;
		}
		//找到交换
		Swap(&a[left], &a[right]);
	}
	//将key移至中间
	Swap(&a[left], &a[keyi]);
	//更新keyi
	keyi = left;
	//递归 [begin,keyi-1] keyi [keyi+1,end]
	QuickSort(a, begin, keyi - 1);
	QuickSort(a, keyi + 1, end);
}

int main()
{
	int arr[10] = { 9,8,7,6,5,4,3,2,1,0 };
	QuickSort(arr, 0, sizeof(arr) / sizeof(arr[0])-1);
	Print(arr, 10);

	return 0;
}

（二）挖坑法

思想：

将选定的key存起来，原本key的位置就空出来成为一个坑位，然后将找到的符合要求的元素填入坑内，该元素原本所在的位置成为新的坑位，循环往复。

其实就是一个不断填坑造坑的过程。

#include<stdio.h>

//打印
void Print(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;
}

//三数取中
int GetMidnum(int* a, int left, int right)
{
	int mid = (right - left) / 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//a[left]<a[mid]
	{
		if (a[mid] < a[right])
		{
			return mid;
		}
		else if (a[left] > a[right])
		{
			return left;
		}
		else
		{
			return right;
		}
	}
}


//快排(升序)——挖坑法
void QuickSort3(int* a, int left, int right)
{
	if (left >= right)
	{
		return;
	}
	int begin = left, end = right;
	int mid = GetMidnum(a, left, right);
	Swap(&a[left], &a[mid]);
	int key = a[left];
	int hole = left;
	while (left < right)
	{
		//右边找小
		while (left < right && a[right] >= key)
		{
			right--;
		}
		a[hole] = a[right];
		//更新坑位
		hole = right;
		//左边找大
		while (left < right && a[left] <= key)
		{
			left++;
		}
		a[hole] = a[left];
		//更新坑位
		hole = left;
	}
	a[hole] = key;
	//[begin,hole-1] hole [hole+1,end]
	QuickSort3(a, begin, hole - 1);
	QuickSort3(a, hole+1, end);
}

int main()
{
	int arr[] = { 9,8,7,6,5,4,3,2,1,0 };
	QuickSort3(arr, 0, sizeof(arr) / sizeof(arr[0]) - 1);
	Print(arr, sizeof(arr) / sizeof(arr[0]));

	return 0;
}

（三）前后指针法

思想：

1、cur找到比key小的值，++prev，cur和prev位置的值交换，++cur
2、cur找到比key大的值，++cur

循环往复

其实就是将比key大的值向右扔，将比key小的值向左扔。

注：

1、prev要么紧跟着cur
2、prev要么跟cur中间间隔着比key大的一段值区间

#include<stdio.h>

//打印
void Print(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;
}

//三数取中
int GetMidnum(int* a, int left, int right)
{
	int mid = (right - left) / 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//a[left]<a[mid]
	{
		if (a[mid] < a[right])
		{
			return mid;
		}
		else if (a[left] > a[right])
		{
			return left;
		}
		else
		{
			return right;
		}
	}
}

//快排——前后指针法
void QuickSort4(int* a, int left, int right)
{
	if (left >= right)
	{
		return;
	}
	int mid = GetMidnum(a, left, right);
	Swap(&a[left], &a[mid]);
	int keyi = left;
	int prev = left;
	int cur = left + 1;
	while (cur <= right)
	{
		if (a[cur] < a[keyi] && cur != ++prev)
		{
			Swap(&a[cur], &a[prev]);
		}
		cur++;
	}
	//a[prev]永远都比a[keyi]小
	Swap(&a[prev], &a[keyi]);
	//更新keyi
	keyi = prev;
	//[left,keyi-1] keyi [keyi+1,right]
	QuickSort4(a, left, keyi - 1);
	QuickSort4(a, keyi+1, right);
}

int main()
{
	int arr[] = { 9,8,7,6,5,4,3,2,1,0,11,13,14};
	QuickSort4(arr, 0, sizeof(arr) / sizeof(arr[0]) - 1);
	Print(arr, sizeof(arr) / sizeof(arr[0]));

	return 0;
}

（四）小区间优化

①主要针对递归层数太多的情况。

②小区间优化需要用到直接插入排序，不了解的朋友可以先移步直接插入排序

#include<stdio.h>
#include"InsertSort.h"

//打印
void Print(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;
}

//三数取中
int GetMidnum(int* a, int left, int right)
{
	int mid = (right - left) / 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//a[left]<a[mid]
	{
		if (a[mid] < a[right])
		{
			return mid;
		}
		else if (a[left] > a[right])
		{
			return left;
		}
		else
		{
			return right;
		}
	}
}

//快排——前后指针法
int _QuickSort5(int* a, int left, int right)
{
	int mid = GetMidnum(a, left, right);
	Swap(&a[left], &a[mid]);
	int keyi = left;
	int prev = left;
	int cur = left + 1;
	while (cur <= right)
	{
		if (a[cur] < a[keyi] && cur != ++prev)
		{
			Swap(&a[cur], &a[prev]);
		}
		cur++;
	}
	//a[prev]永远都比a[keyi]小
	Swap(&a[prev], &a[keyi]);
	//更新keyi
	keyi = prev;
	return keyi;
}

void QuickSort5(int* a, int left, int right)
{
	if (left >= right)
	{
		return;
	}

	if (right - left + 1 > 10)
	{
		int keyi = _QuickSort5(a, left, right);
		//[left,keyi-1] keyi [keyi+1,right]
		QuickSort5(a, left, keyi - 1);
		QuickSort5(a, keyi + 1, right);
	}
	//小区间优化
	else
	{
		IsertSort(a+left, right - left + 1);
	}
}

int main()
{
	int arr[] = { 9,8,7,6,5,4,3,2,1,0,11,2,4,45,33 };
	QuickSort5(arr, 0, sizeof(arr) / sizeof(arr[0]) - 1);
	Print(arr, sizeof(arr) / sizeof(arr[0]));

	return 0;
}

（五）非递归写法

此处是用栈来辅助改成循环，需要用到栈。

思想：

①将初始区间入栈

②从栈中取一段区间进行单趟快排并分割

③将分割出的子区间入栈（区间内元素数量>=2）

#include<stdio.h>
#include"Stack.h"

//打印
void Print(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;
}

//三数取中
int GetMidnum(int* a, int left, int right)
{
	int mid = (right - left) / 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//a[left]<a[mid]
	{
		if (a[mid] < a[right])
		{
			return mid;
		}
		else if (a[left] > a[right])
		{
			return left;
		}
		else
		{
			return right;
		}
	}
}

//快排——前后指针法
int _QuickSort6(int* a, int left, int right)
{
	int mid = GetMidnum(a, left, right);
	Swap(&a[left], &a[mid]);
	int keyi = left;
	int prev = left;
	int cur = left + 1;
	while (cur <= right)
	{
		if (a[cur] < a[keyi] && cur != ++prev)
		{
			Swap(&a[cur], &a[prev]);
		}
		cur++;
	}
	//a[prev]永远都比a[keyi]小
	Swap(&a[prev], &a[keyi]);
	//更新keyi
	keyi = prev;
	return keyi;
}

//快排——非递归形式
void QuickSort6(int* a, int left, int right)
{
	ST st;
	StackInit(&st);
	//将初始区间入栈
	StackPush(&st, right);
	StackPush(&st, left);
	while (!Empty(&st))
	{
		int begin = StackTop(&st);
		StackPop(&st);
		int end = StackTop(&st);
		StackPop(&st);
		//分割母区间
		int keyi = _QuickSort6(a, begin, end);
		
		//[begin,keyi-1]  keyi  [keyi+1,end]
		//将子区间入栈(元素>=2)
		if (keyi + 1 < end)//此处别误写成循环，会栈溢出
		{
			StackPush(&st, end);
			StackPush(&st, keyi+1);
		}
		if (begin < keyi - 1)
		{
			StackPush(&st, keyi - 1);
			StackPush(&st, begin);
		}
	}

	StackDestroy(&st);
}

int main()
{
	int arr[] = { 9,7,8,5,4,6,3,1,2,0 };
	QuickSort6(arr, 0, sizeof(arr) / sizeof(arr[0]) - 1);
	Print(arr, sizeof(arr) / sizeof(arr[0]));

	return 0;
}

感谢阅读，本文如有疏漏不当之处，烦请各位指正。

标签：排序,return,int,mid,right,key,数据结构,快速,left
From： https://blog.csdn.net/2301_81298637/article/details/143652805

相关文章

  • C++数据结构实验题目解析
    目录题目:考点分析：难点1：就地逆置步骤：代码实现：核心代码详细解释：难点2：①非递减链表，②删除相同元素代码详解①：代码详解②：完整代码：大家好，今天我就来给大家分析一下我上期分享的题目的详细解析，编程的能力都是逐步提升的，但是思维的锻炼可以提前进行，这样有助于我们以后自......
  • 郝玩的数据结构1——单调栈，单调队列
    栈和队列是很郝咏的Stl，那么，我们手搓——用数组模拟故事背景：辣鸡老o在学单调栈&单调队列——我栈top为栈顶，易得出出栈即top--，入栈++top=(ovo)......——完全不会讲，那么上马：点击查看代码#include<bits/stdc++.h>usingnamespacestd;constintN=114514;intstk[N],top=0;......
  • 力扣 170. 两数之和 III - 数据结构设计 two-sum III
    数组系列力扣数据结构之数组-00-概览力扣.53最大子数组和maximum-subarray力扣.128最长连续序列longest-consecutive-sequence力扣.1两数之和N种解法two-sum力扣.167两数之和IItwo-sum-ii力扣.170两数之和IIItwo-sum-iii力扣.653两数之和IVtwo-sum-IV力......
  • python算法之最low三人组之一——————选择排序
    之前讲过了冒泡排序，我们再聊一聊最low三人组中的选择排序，选择排序的基本思想是：遍历整个序列，选取其中一个最小的数取出来，然后再次遍历除了刚刚选出来的最小的数的序列中最小的数现在让我们看看代码实现importrandomdefselect_sort(li):new_li=[]foriinrange(l......
  • 快速排序，思路总结与实现
    思路找基准值(pivot)pivot=startorend比基准值小的放左边，大的放右边实现双指针，left从左到右找比基准值大的元素，right从右到左找比基准值小的元素找到后交换left和right指针的内容直到left=right这是递增排序，递减排序情况相反如果pivot=start，则右指针先动，否......
  • 快速掌握封装，继承及多态
    目录1.封装1.1封装的语法1.2访问修饰限定符*包1.包的使用2.自定义包3.包访问权限（只在包内访问）4.常用的包2.继承2.1继承的语法(子类和父类)2.2在子类中访问父类1.子类与访问父类成员名字不同2.子类与访问父类成员同名---super*如何访问同名时的父......
  • 推荐一款快速启动工具：Glary Quick Startup
    GlaryQuickStartup是一款快速启动工具，减缓PC加载速度，顾名思义，它是一个快速简单的启动管理器，专门设计用于通过延迟某些程序在系统启动后自动启动，或删除不必要的程序在系统启动时抢夺资源来启动自己，从而加快Windows启动。快速启动用于安排自动启动程序并为系统启动提供足够的......
  • 算法学习—归并排序
    1.算法介绍 归并算法是一种由冯·诺伊曼发明的分治算法，相较于普通排序算法时间复杂度较低，运行效率高。通常情况下，归并算法的时间复杂度为O(nlogn)。2.算法思想以及大致步骤 归并算法主要运用到了分治以及归并的思想，主要步骤如下：首先将一个无序数组分为n个有序的单个数......
  • 算法学习—快速排序
    1.算法介绍   快速排序算法是一种高效排序算法，效率相比普通排序算法较高，通常情况下时间复杂度为O(nlogn)，但在最坏情况下时间复杂度会提高到O(n^2)2.算法思想和大致步骤 快速排序算法主要用到了二分和递归的思想，主要有三个步骤：（1）在数组中选取一个元素作为基准值(pivot)......
  • 十大经典排序算法-插入排序
    插入排序的代码实现虽然没有冒泡排序和选择排序那么简单粗暴，但它的原理应该是最容易理解的了，因为只要打过扑克牌的人都应该能够秒懂。插入排序是一种最简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99