排序总结之快速排序

简介:

快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下,排序 n 个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n2)次比较,但这种状况并不常见。事实上,快速排序通常明显比其他Ο(n log n) 算法更快,因为它的内部循环(inner loop)可以在大部分的架构上很有效率地被实现出来。快速排序使用分治法(Divide and conquer)策略来把一个串行(list)分为两个子串行(sub-lists)。

步骤:

1 ,从数列中挑出一个元素,称为 "基准"

2 ,重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分区退出之后,该基准就处于数列的中间位置。这个称为分区(partition)操作。

3 ,递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序。

递归的最底部情形,是数列的大小是零或一,也就是永远都已经被排序好了。虽然一直递归下去,但是这个算法总会退出,因为在每次的迭代(iteration)中,它至少会把一个元素摆到它最后的位置去。

复杂度:

数据结构 不定
最差时间复杂度
最优时间复杂度
平均时间复杂度
最差空间复杂度 根据实现的方式不同而不同

空间复杂度:被快速排序所使用的空间,依照使用的版本而定。使用原地(in-place)分区的快速排序版本,在任何递归调用前,仅会使用固定的额外空间。然而,如果需要产生O(log n)嵌套递归调用,它需要在他们每一个存储一个固定数量的信息。因为最好的情况最多需要O(log n)次的嵌套递归调用,所以它需要O(log n)的空间。最坏情况下需要O(n)次嵌套递归调用,因此需要O(n)的空间。

java code:

package com.lxz.sort;

import java.util.Arrays;

public class QuickSortDemo {
	// 快速排序在交换元素时会导致相等元素相对位置改变所以是不稳定的
	private void quickSort(int[] a, int left, int right) {
		if (left < right) {
			int mid = getMid(a, left, right);
			// int mid = getMid1(a, left, right);
			quickSort(a, left, mid - 1);
			quickSort(a, mid + 1, right);
		}
	}

	// 双指针单侧向右移动交换。
	private int getMid1(int[] a, int left, int right) {
		int origin = a[left];
		int pos = left;
		for (int j = left + 1; j <= right; j++) {
			if (a[j] <= origin) {
				pos++;
				if (pos != j) {// 如果不等则前面遍历过的元素有小于origin的
					int temp = a[j];
					a[j] = a[pos];
					a[pos] = temp;
				}
			}
		}
		a[left] = a[pos];
		a[pos] = origin;
		return pos;
	}

	// 双指针两端向中间移动交换
	private int getMid(int[] a, int left, int right) {
		int temp = a[left];
		while (left < right) {// 这里有等号会导致死循环
			while (left < right && temp <= a[right])
				// left <= right等号会导致java.lang.ArrayIndexOutOfBoundsException
				right--;
			a[left] = a[right];
			while (left < right && a[left] <= temp)
				left++;
			a[right] = a[left];
		}
		a[left] = temp;
		return left;
	}
	public static void main(String[] args){
		QuickSortDemo qsd = new QuickSortDemo();
		int b[] = { 49, 38, 65, 97, 76, 13, 27, 49, 78, 34, 12, 64, 5, 4, 62,
				99, 98, 54, 56, 17, 18, 23, 34, 15, 35, 25, 53, 51 };
		// int b[] = { 8, 9, 6, 3, 4, 5, 2, 1, 7, 2, 12, 11, 15, 1 };
		qsd.quickSort(b, 0, b.length - 1);
		System.out.println(Arrays.toString(b));
	}
}

参考文献:http://zh.wikipedia.org/wiki/%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F

排序总结之快速排序,布布扣,bubuko.com

时间: 05-13

排序总结之快速排序的相关文章

排序算法 之 快速排序

快速排序是基于分治思想的一种排序算法,就像该方法的名字一样,速度比较快,所以叫做快速排序:它的平均时间复杂度为O(N*logN),最坏时间复杂度为O(n2),由于快速排序在序列元素数量多的时候速度比较快,所以很多语言内置的排序方法也是用快速排序实现的.快速排序也有很多优化的版本,比如在排序时基数的选择等等-下面就说一下一般的快速排序的实现. 基本思想: 快速排序的基本思想就是,先从待排序的序列中任选一个元素作为基数,然后将序列中的其他小于基数的元素放在基数的左边,大于或等于基数的元素放在基数的右

18. 蛤蟆的数据结构进阶十八排序实现之快速排序

18. 蛤蟆的数据结构进阶十八排序实现之快速排序 本篇名言:"一个人做点好事并不难,难的是一辈子做好事,不做坏事.--毛泽东" 我们最后来看下快速排序,以及各个排序之间的一些信息汇总. 欢迎转载,转载请标明出处:http://blog.csdn.net/notbaron/article/details/47817933 1.  快速排序 快速排序由C. A. R.Hoare在1962年提出.它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分

常用排序算法之——快速排序(C语言+VC6.0平台)

经典排序算法中快速排序具有较好的效率,但其实现思路相对较难理解. #include<stdio.h> int partition(int num[],int low,int high) //以key为基准 将待排数列“高”.“低 ”两部分,“高”部分的所有数据比key大,“低”部分的数据都比key小 { int left,right,key; left=low;right=high;key=num[low]; while(left<right) { while(left<right

常用排序算法之——快速排序

快速排序的原理: 首先找一个标兵值,等于某一个元素值:遍历数组,将数组分为小于标兵值和大于标兵值的两部分:然后分别对两个部分采用快速排序,递归. 分开数组时,维持一个指针,指向已找到小部分的最后一个元素:一个指针用于遍历. 不稳定排序算法.当数组已经有序时,时间复杂度最差,为O(N2),平均.最优情况下都为O(N lgN). 代码如下: 1 #include <iostream> 2 using namespace std; 3 4 template<typename T> 5 v

排序算法系列——快速排序

记录学习点滴 快速排序算法是一种很有趣的算法,短小精悍,性能强劲,对于大部分情况都可以胜任,但对极端环境难以应付. 快速排序我理解为:这是一个“以自我为中心的”+“分治法”思想的算法. 分治法不必多说,化繁为简,那就是逐个击破. 那什么是“以自我为中心”?顾名思义,就是每次都一个“我”,每个人都要围绕“我”行事,比“我”小的都去左边站着,比“我”他大的都去右边站着,而且“我”不去关心每一边都有谁,反正你没“我”大或者小就行.一旦“我”落位了妥帖了,“我”就不动了.然后再在左右两边分别产生新“我”

排序算法之快速排序Java实现

排序算法之快速排序 舞蹈演示排序: 冒泡排序: http://t.cn/hrf58M 希尔排序:http://t.cn/hrosvb  选择排序:http://t.cn/hros6e  插入排序:http://t.cn/hros0W  快速排序:http://t.cn/ScTA1d  归并排序:http://t.cn/Sc1cGZ 快速排序是一个就地排序,分而治之,大规模递归的算法.从本质上来说,它是归并排序的就地版本. 1.快速排序可以由下面四步组成:(1) 如果不多于1个数据,直接返回.(2

经典排序算法之快速排序(C语言版)

快速排序是一种很常用的排序算法. /*  * 快速排序(伪算法) 2016-04-20 23:34:16  * 1.先找到第一个元素的最终位置  * 2.对第一个元素的最终位置之前的元素,进行快速排序.  * 3.对第一个元素的最终位置之后的元素,进行快速排序.  * */ extern void QuickSort(int a[],int low,int high);//第二个参数表示第一个元素的下标,第三个参数表示最后一个元素的下标 extern int FindPos(int a[], i

排序算法之快速排序的随机化版本

4.3 快速排序的随机化版本 这种方法并不是一种全新的排序算法,而是在快速排序的基础上加入随机化的因素,因素,因而仍然将其作为第四种方法(快速排序)的一种补充. 为什么要提出快速排序的随机化版本,主要是对于快速排序法其划分情况的好坏会直接影响排序的效率,而且,快速排序的平均性能较好,所以,加入随机化成分,可以使该算法对于所有输入均能获得较好的平均情况性能. 针对加入随机化的环节,选取的是选取主元的环节,因为主元的选取直接影响快速排序算法的数组划分. C代码实现为: #include <stdio

数据结构实验之排序八:快速排序

数据结构实验之排序八:快速排序 Time Limit: 1000MS Memory Limit: 65536KB Submit Statistic Problem Description 给定N(N≤10^5)个整数,要求用快速排序对数据进行升序排列,注意不得使用STL. Input 连续输入多组数据,每组输入数据第一行给出正整数N(≤10^5),随后给出N个整数,数字间以空格分隔. Output 输出排序后的结果,数字间以一个空格间隔,行末不得有多余空格. Example Input 8 49