快速排序的实现和分析

快速排序的实现和分析

第一篇正式的文章

想来想去,第一篇正式的文章,还是写一个前一段时间学算法的时候实现的基本的排序算法中的快速排序吧!

快速排序

1. 介绍

快速排序是三大基本排序中的冒泡排序的高级算法,采用了分置和递归的思想来处理排序功能,是最好的内排序之一。

2. 冒泡排序

冒泡排序是交换排序中的基本算法,这个排序比较简单,在我大一下半学年的c语言程序设计和大二上半学期的java程序设计中都有涉及到这个问题。

思想

冒泡排序的思想是依次比较相邻的两个数,将比较小的数放在前面,较大的数放在后面,即可实现冒泡排序。
在具体实现中使用了双层循环实现这个算法,外层循环代表当前的这个数,而内层循环代表其他后面的数来和这个数比较。

代码块

public class BubblingSort {
	public static void main(String[] args) {
		// 无序数组
		int[] array = { 12, 6, 31, 45, 0, 32, 55, 11, 22, 33 };
		// 直接插入排序
		bubblingSort(array);
		// 输出排序结果
		System.out.println(Arrays.toString(array));
	}
	public static void bubblingSort(int[] ary) {
		// 外循环
		for (int i = 0; i < ary.length; i++) {
			// 内循环
			for (int j = i; j < ary.length; j++) {
				if (ary[i] > ary[j]) {
					int temp = ary[i];
					ary[i] = ary[j];
					ary[j] = temp;
				}
			}
		}
	}
}

时间复杂度分析

由于冒泡排序使用了双重循环时间复杂度也比较好算,很明显是o(n^2)。

3.快速排序思想

快速排序的思想分为三个步骤:

  1. 先从数列中驱逐一个数作为基准数,基准数可以是任何一个数列中的数,为了简易操作一半都是选择第一个数作为基准数。

  2. 将比这个数大的数全部放在右边,小于或等于这个数的数全部放在左边(以升序为例的)。这个步骤是分治的过程。

  3. 再对左区间和右区间分别再执行第一部和第二部,直到区间只有一个数,数列就自然有序了。这个步骤是递归的过程。

4. 具体实现

步骤分析

对照思想来整理代码实现的步骤,首先定义这个快速排序的方法名称为quickSort。

分析需求,这个方法肯定需要待排序的数列的参数。

还需要对这个数列的那些区域进行排序的信息,因为后面需要用到递归所以对区域的起点和终点需要定义为参数。

这样就,明确了quickSort方法需要的参数,我们可以这样定义:

代码块

public static void quickSort(int[] ary, int low, int height) {}

继续分析需求,我们这个quickSort方法的功能是什么呢?

答案是:用来对序列(ary)进行排序,然后我们就根据思想中的来继续往下实现代码。

这里为了简便我们再提取一个方法divsion,这个方法用来干什么?这个方法用来执行第一步和第二部的功能,完成分置,这个方法肯定也需要序列,分置的起点和终点.
还有一点是这里我们让division方法返回一个int类型的数这个数代表本次次分置完成后的基准数的索引,方便我们继续递归进行剩下的排序和分置。
我们这样定义这个方法:

代码块

public static int division(int[] ary, int low, int height) {}

两个方法里的ary,都代表待排序序列,而low,和height代表排序的起点和终点或者分置的起点和终点。

我们先来将quickSort中的代码补全,这代表了思想中第三部的实现:

quickSort需要实现的功能很简单:
第一步: 对传进来的形参先进行分置
第二部: 对分置后的左区域进行quickSort排序
第二部: 对分置后的右区域进行quickSort排序

代码块

public static void quickSort(int[] ary, int low, int height) {
	if (low < height) {
		// 1. 对传进来的形参先进行分置,这个mid就是左区域和右区域的分界点
		int mid = division(ary, low, height);
		// 2. 对分置后的左区域进行quickSort排序
		quickSort(ary, low, mid - 1);
		// 3.对分置后的右区域进行quickSort排序
		quickSort(ary, mid + 1, height);
	}
}

完成了quickSort方法,我们来继续完成division方法,这个方法代表思想中的,第一步和第二部。

这个方法的实现是整个快速排序的核心内容,接下来会尽可能详细的展示分置的过程->图解。

这里我们假设演绎第一次也就是最外层的分置.
设数组为:ary = { 12, 6, 31, 45, 0, 32, 55, 11, 22, 33 };

图示

  1. 选取基准数mid,默认为了简单就选择第一个

quickSort01

  1. 左面有空位置就那右面的数进行判断,右面就反之亦然。
    判断右面的数数和基准数,如果右面的数(以下就称之为指针指向的数)小,则需要将右面这个数放到左面,正好放在第一个空间中。
    反之没有基准数大就不换位置,但是指针要指向右面的下一个数也就是22。
    很显然这里33<12我们只需要将指针往下挪一格便可。

quickSort02

  1. 重复第2部即可,指针指向的数与基准数比较,很显然还是22>12,那么指针继续往后移到11上面,这时候就不一样了,11<12,我们需要将11放在左面的空间里,然后指针从空间的位置后移一位

quickSort03

  1. 继续用指针指向的数和基准数进行比较,6<12,放在左边所以不用移动位置,只需要将指针往后移动一位就可以。继续比较31>12,则需要将31移动到右边,此时右边正好有空间存放31。移动完成后指针变为右边31位置的下一个位置。

quickSort04

  1. 继续重复之前的步骤,55,32都比12大所以全部是放在右边,只需要往下移动指针,到指针指向0<12,把0放在左边空的位置,指针指向45。

quickSort05

  1. 继续重复之前的步骤,45>12,将45移动到右边空位置上,指针后移。

quickSort06

但是这时候就出问题了,我们能发现这时候其实分置已经结束了,但是我们怎么来判断分置是否结束呢?为了解决这个问题我们必须设置两个指针,分别代表左区域和右区域和基准数比较的数,当这个两个指针指向的索引相同了当然也就是分置结束的时候了。

  1. 最后只需要将最后空下来的位置放入基准数,然后返回两个指针中的其中一个就可以了(两指针是相同的)。

quickSort07

division方法代码实现

根据刚才的图解分析我们很容易就能写出division方法的代码了

public static int division(int[] ary, int low, int height) {
	// 基准数
	int mid = ary[low];
	// 代表空位置是在左边还是右边
	boolean flag = true;
	// low是左指针,height是右指针
	while (low != height) {
		// 判断是左边有空位置还是右边
		if (flag) {
			// 右指针指向的数是否比基准数的小
			if (ary[height] <= mid) {
				// 放进空位置
				ary[low] = ary[height];
				// 倒置flag表示空位置在右边
				flag = false;
				// 左指针移动
				low++;
			} else {
				// 右指针指向的数比基准数大,只需挪动指针
				height--;
			}
		} else {
			// 左指针指向的数是否比基准数大
			if (ary[low] > mid) {
				// 放进空位置
				ary[height] = ary[low];
				// 倒置flag表示空位置在左边
				flag = true;
				// 右指针移动
				height--;
			} else {
				// 左指针指向的数比基准数打,只需要挪动指针
				low++;
			}
		}
	}
	// 最后的空位置,放基准数
	ary[low] = mid;
	// 返回一个指针即可,两个指针是相同的
	return low;
}

整体优化

思路,为了使使用quickSort方法的体验最优化,我们暴露给外界的方法最好只需要传入一个数组即可。所以我们把quickSort方法和division方法设置为private不让外界访问。

暴露一个重载的quickSort(int[] ary)方法给外界使用。
这样我们的最终代码就为:

public class QuickSort {
	public static void main(String[] args) {
		// 无序数组
		int[] array = { 12, 6, 31, 45, 0, 32, 55, 11, 22, 33 };
		// 快速排序
		quickSort(array);
		// 输出排序结果
		System.out.println(Arrays.toString(array));
	}
	// 暴露给外界的方法入口
	public static void quickSort(int[] ary) {
		int low = 0;
		int height = ary.length - 1;
		quickSort(ary, low, height);
	}
	private static void quickSort(int[] ary, int low, int height) {
		if (low < height) {
			int mid = division(ary, low, height);
			quickSort(ary, low, mid - 1);
			quickSort(ary, mid + 1, height);
		}
	}
	private static int division(int[] ary, int low, int height) {
		int mid = ary[low];
		boolean flag = true;
		while (low != height) {
			if (flag) {
				if (ary[height] <= mid) {
					ary[low] = ary[height];
					flag = false;
					low++;
				} else {
					height--;
				}
			} else {
				if (ary[low] > mid) {
					ary[height] = ary[low];
					flag = true;
					height--;
				} else {
					low++;
				}
			}
		}
		ary[low] = mid;
		return low;
	}
}

5.复杂度分析

由于我的实力有限,复杂度的学习并不是很好。这里就只写结论了。QAQ

时间复杂度

最坏情况:o(n^2)
最好情况:o(nlog2n)

空间复杂度

o(log2n)

6.稳定性

结论:快速排序不稳定
现在先直接记住结论以后有时间系统的分析复杂度和稳定性问题。


这是第一篇正式的记录我学习的笔记的技术博客,以后也会系统学习和分析复杂度的问题,和分析其他的排序算法(比如:希尔排序,归并排序..),并比较他们的优缺。


Copyright: 采用 知识共享署名4.0 国际许可协议进行许可

Links: https://www.byfree.top/archives/qurcksortimplements