`

java 快速排序分析

阅读更多

快速排序:

  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

 

 

 

 

 

 

0
0
分享到:
评论

相关推荐

    JAVA实现快速排序

    JAVA实现快速排序 快速排序是一种高效的排序算法,它的实现可以分为两个部分:基本思想和复杂度分析。在基本思想中,快速排序采用“分而治之”的思想,把大的拆分为小的,小的拆分为更小的,直到序列中的所有记录均...

    JAVA实现的快速排序

    通过以上分析,我们可以看出这段代码实现了快速排序的基本逻辑,但在实际应用中还需要注意一些细节: - 基准值的选择会影响算法的效率。 - 在极端情况下,如已经排好序的数组,可能会导致快速排序退化为O(n^2)的时间...

    用java实现快速排序

    根据给定文件的信息,本文将围绕“用Java实现快速排序”的主题进行展开,不仅解析标题与描述中的核心知识点,还会对部分代码示例进行解读,最后结合这些信息给出一个完整的快速排序算法实现。 ### 快速排序算法简介...

    快速排序示例代码(JAVA版)

    6. **时间复杂度分析**:在理想情况下,快速排序的平均时间复杂度为O(n log n),最坏情况(已排序数组)为O(n^2),但这种情况很少发生。实际应用中,通过随机选择枢轴可以显著降低最坏情况的发生概率。 7. **空间...

    JAVA快速排序(递归实现与非递归堆栈模拟实现)

    ### JAVA快速排序(递归实现与非递归堆栈模拟实现) #### 一、递归实现的快速排序 快速排序是一种非常高效的排序算法,它的基本思想是通过一趟排序将待排记录分隔成独立的两部分,其中一部分的所有记录都比另一...

    用JAVA语言实现的对数据的快速排序法

    根据给定文件中的标题、描述、标签...综上所述,通过对给定文件的分析,我们不仅理解了如何使用Java实现快速排序算法,还深入了解了该算法的工作原理、性能特点以及优化方法,这对于理解和掌握快速排序具有重要意义。

    排序算法时间复杂度的分析java语言描述

    以下是对选择排序、冒泡排序、归并排序、快速排序和插入排序这五种常见排序算法的详细介绍,以及如何分析它们的时间复杂度。 1. **选择排序(Selection Sort)** - 原理:选择排序是一种简单直观的排序算法,它...

    java实现快速排序小结

    快速排序的时间复杂度分析通常使用主定理。主定理是解决递归问题的一个重要工具,它提供了一种确定递归算法运行时间的方法。在快速排序中,每次划分将问题规模减半,即a=b=2,而PARTITION()操作的时间复杂度为O(n)。...

    JAVA快速排序课程设计

    快速排序是一种高效的排序算法,由英国计算机科学家C. A....通过这个课程设计,学生不仅能够深入理解快速排序算法,还能掌握使用Java进行程序设计和调试的技巧,同时提升分析问题和解决问题的能力。

    冒泡排序、快速排序和二分法查找的分析 Java

    ### 冒泡排序、快速排序和二分法查找的分析:Java实现 #### 冒泡排序(Bubble Sort) 冒泡排序是一种简单的排序算法,它重复地遍历要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。遍历数列...

    java冒泡排序、快速排序、二分查找

    本文将对冒泡排序、快速排序、二分查找进行详细的分析和图解。 冒泡排序 冒泡排序是一种简单的排序算法,通过反复地走访要排序的数列,依次比较相邻的两个元素,如果他们的顺序错误就把他们交换过来,直到没有再...

    Java快速排序源代码

    根据提供的文件信息,我们可以分析出该Java程序主要实现了快速排序算法。下面将对该代码的关键部分进行解析,并从中提炼出相关的IT知识点。 ### 1. 文件输入处理 在`public static int input(int[] num)`方法中,...

    算法实验(java快速排序。归并排序,分治算法,回溯算法,n后问题)

    包括所有算法分析设计的实验(java快速排序。归并排序,分治算法,回溯算法,n后问题)

    JAVA排序算法: 直接插入,希尔排序,选择排序,堆排序,冒泡排序,快速排序,归并排序

    本文将深入探讨Java编程语言中实现的七种主要排序算法:直接插入排序、希尔排序、选择排序、堆排序、冒泡排序、快速排序以及归并排序。每种算法都有其独特性,适用于不同的场景和数据特性。 1. **直接插入排序**:...

    [原]Java 快速排序

    以上就是Java快速排序的基本原理和源码分析。快速排序的平均时间复杂度为O(n log n),在最坏情况下(已经排序或逆序)时间复杂度为O(n^2)。由于其高效的性能和相对简单的实现,快速排序在实际应用中被广泛使用。

    快速排序、归并排序、希尔排序、冒泡排序、选择排序等8中排序方式原理分析java实现

    这里我们将深入探讨快速排序、归并排序、希尔排序、冒泡排序、选择排序以及插入排序这六种经典的排序算法,并通过Java语言来实现它们。 1. **快速排序**:由C.A.R. Hoare在1960年提出,是基于分治策略的一种高效...

    Java各种排序算法

    - **快速排序**:通过一个基准值将待排序序列分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个...

    快速排序 java代码

    在这个Java实现中,我们将详细探讨快速排序的工作原理,以及如何用Java编写快速排序算法。 ### 快速排序概述 快速排序的核心在于“分区”操作,它将一个大数组分成两个子数组,一个子数组的所有元素都比另一个子...

    Java中快速排序算法

    在Java中,快速排序通常通过定义一个基准元素,然后重新排列数组来实现,确保所有小于基准的元素位于其左侧,大于基准的位于右侧。这个过程称为分区操作。接下来,对左右两侧的子数组分别递归地执行相同的操作,直到...

    Java各种排序算法代码.zip

    在Java中,快速排序通常用递归实现。 5. 归并排序(Merge Sort): 归并排序是一种分治策略,将大问题分解为小问题解决。它将数组分为两个子数组,分别进行排序,然后合并成一个有序数组。Java中,归并排序需要额外...

Global site tag (gtag.js) - Google Analytics