回顾快速排序

快速排序

快速排序的核心:

找到一个key

通常左边的数比key小,右边的数比key大。

找key通常有三种方法:

1.

挖坑法:

 

代码实现:

//
int _pivot(int* a, int left, int right)
{
	int begin = left, end = right;
	int index = get_mid(a, left, right);
	swap(a[index], a[begin]);
	int key = a[begin];
	int pivot = begin;
	while (begin < end)
	{
		while (begin < end && a[end] >= key)
		{
			--end;
		}
		//swap(a[end], a[pivot]);
		a[pivot] = a[end];
		pivot = end;
		while (begin < end && a[begin] <= key)
		{
			++begin;
		}
		//swap(a[begin], a[pivot]);
		a[pivot] = a[begin];
		pivot = begin;
	}
	//swap(a[begin], a[pivot]);
	pivot = begin;
	a[pivot] = key;
	return pivot;
}

 该代码的注意点为:

如果a[begin]或a[end]与key相等时,key原来在key的那边,while循环后key还在原来那边。

swap交换是错误的例子。

pivot是坑,a[pivot]是图里面类似于马赛克的位置(a[pivot]是空),所以不能是交换,应该是赋值。

左右指针法:(最左侧的一列是其示例图)

 图中代码有本质差别,图一正确(左)。

 

 先end--

后end--

二者有质的区别,完全不同

前后指针法:

 

 

找到key之后的核心:

 

相关推荐

  1. 快速排序回顾及相关题型

    2024-04-03 09:02:04       30 阅读
  2. 回顾冒泡排序

    2024-04-03 09:02:04       10 阅读
  3. 快速排序

    2024-04-03 09:02:04       21 阅读
  4. 排序算法——快速排序

    2024-04-03 09:02:04       27 阅读
  5. 排序算法——快速排序

    2024-04-03 09:02:04       28 阅读

最近更新

  1. FFT快速傅里叶变换音频分析

    2024-04-03 09:02:04       0 阅读
  2. 基于单片机雨天自动关窗器的设计

    2024-04-03 09:02:04       0 阅读
  3. 基础矩阵和本质矩阵

    2024-04-03 09:02:04       0 阅读
  4. 水气表CJ/T188协议学习及实例

    2024-04-03 09:02:04       0 阅读
  5. 基于springboot的教学资源库源码数据库

    2024-04-03 09:02:04       0 阅读
  6. flink mysql数据表同步SQL CDC

    2024-04-03 09:02:04       0 阅读
  7. 【QT进阶】Qt http编程之json解析的简单介绍

    2024-04-03 09:02:04       0 阅读
  8. 从0开始深入理解Spring(1)--SpringApplication构造

    2024-04-03 09:02:04       0 阅读

热门阅读

  1. Amazon API Gateway 配置自定义域名

    2024-04-03 09:02:04       5 阅读
  2. FPGA在深度学习领域的应用的优势

    2024-04-03 09:02:04       8 阅读
  3. 安装编译cpprest sdk

    2024-04-03 09:02:04       4 阅读
  4. SSH中私钥和公钥的使用

    2024-04-03 09:02:04       6 阅读
  5. Echart(多雷达图展示)

    2024-04-03 09:02:04       5 阅读
  6. openmmlab系列框架多GPU训练

    2024-04-03 09:02:04       5 阅读
  7. 练气第六天

    2024-04-03 09:02:04       4 阅读
  8. openGauss 分布式分析能力

    2024-04-03 09:02:04       9 阅读
  9. PostCSS安装与使用技术详解

    2024-04-03 09:02:04       4 阅读