当前位置:首页 > 开发 > 编程语言 > Java > 正文

java 快速排序分析

发表于: 2013-03-20   作者:blackproof   来源:转载   浏览次数:
摘要: 快速排序:   1.实现   2.复杂度   1.java 快速排序实现:   package com.sort; import java.util.ArrayList; public class QuickSort { private int getMiddle(ArrayList<Integer> list,int

快速排序:

  1.实现

  2.复杂度

 

1.java 快速排序实现:

 

package com.sort;

import java.util.ArrayList;

public class QuickSort {
	private int getMiddle(ArrayList<Integer> list,int start,int end){
		int i = start;
		int j = end;
		Integer temp = list.get(start);//需要中间变量,或是每次替换时进行twiceswap
		while(i<j){
			while(temp<list.get(j)&&i<j)
				j--;
			if(i<j){
				list.set(i, list.get(j));
				i++;
			}
			while(list.get(i)<temp&&i<j)
				i++;
			if(i<j){
				list.set(j, list.get(i));
				j--;
			}
		}
		list.set(i, temp);//最后i=j
		return i;
	}
	
	private void quickSort(ArrayList<Integer> list,int start,int end){
		if(start<end){
			int middle = getMiddle(list, start, end);
			quickSort(list, start, middle-1);
			quickSort(list, middle+1, end);
		}
	}
	
	public void quickSort(ArrayList<Integer> list){
		this.quickSort(list, 0, list.size()-1);
	}
	
	public static void main(String[] args) {
		ArrayList<Integer> list = new ArrayList<Integer>();
		list.add(7);
		list.add(2);
		list.add(3);
		list.add(8);
		list.add(3);
		list.add(6);
		list.add(10);
		list.add(100);
		list.add(9);
		list.add(77);
		list.add(34);
		list.add(20);
		new QuickSort().quickSort(list);
		QuickSort.print(list);
	}
	
	public static void print(ArrayList<Integer> list){
		for (Integer integer : list) {
			System.out.print(integer+",");
		}
		System.out.println();
	}

}

1.实现中注意的事情,至少是我碰到的,需要一个中间变量进行比较,或是在交换的时候,进行两次交换,就是两个值互换位置 。可以尝试这样的用例100 77 34 20.

2.每一次的拆分,就已经确定了一个位置(并且将值分为两半,一半大,一半小),不要将middle也带入下一次的排序

 

 

2.快速排序复杂度分析:

 

快速排序的最佳情况:分割递归为平衡树,

这样分解次数为log2n

在第i次分解,需要比较n/(2^i)

通过运算推导

T(1) = 0;
T(n) <= 2T(n/2) + n;
T(n) <= 2(2T(n/4) + n/2) + n=4T(n/4)+2n
T(n) <= 8T(n/8)+3n
T(n) <= (log2n)^2T(1)+(log2n)n (因为分解log2n次)
T(n) <= nlog2n

 所以快速排序最佳复杂度为nlog2n

 

快速排序的最差情况:序列为正序或逆序,在分割后产生斜树,

这样要分解次数为n-1次,

在第i次分解后,需要比较n-i次

通过运算推导

n-1+n-2+n-3....+1=n(n-1)/2

 索引快速排序的最差复杂度为n^2

 

 

快速排序的平均复杂度:

设分解的关键字为k,则(1<=k<=n)

通过运算推导为nlogn

 

 

 

 

 

 

java 快速排序分析

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
Java快速排序算法分析 基本思想:通过一趟排序将待排序记录分割成独立的两部分,其中一部分记录的关
开篇 在实际的过程中,总需要对一些数据进行排序,在众多的排序算法中,快速排序是较为常用的排序算
开篇 在实际的过程中,总需要对一些数据进行排序,在众多的排序算法中,快速排序是较为常用的排序算
近最研究元素排序,稍微总结一下,以后继承补充: 近最决议天每学点数据结构与算法,写客博来促督自
说来感到惭愧,昨天看别人的博客上面一一讲了一些算法,其实这些算法在大学都学过,不过几乎全部忘
1)基本思想:选择一个基准元素,通常选择第一个元素或者最后一个元素,通过一趟扫描,将待排序列分成
快速排序 作者:Legend QQ:158067568 快排是分治法的一个应用,快排主要是通过一个设定枢轴,然后
说来感到惭愧,昨天看别人的博客上面一一讲了一些算法,其实这些算法在大学都学过,不过几乎全部忘
说来感到惭愧,昨天看别人的博客上面一一讲了一些算法,其实这些算法在大学都学过,不过几乎全部忘
部分内容摘自:http://zh.wikipedia.org/wiki/%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F 快速排序步骤
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号