快速排序的深入详解以及java实现

快速排序作为一种高效的排序算法被广泛应用，SUN的JDK中的Arrays.sort 方法用的就是快排。
快排采用了经典的分治思想（divide and conquer）：

Divide：选取一个基元X（一般选取数组第一个元素），通过某种分区操作（partitioning）将数组划分为两个部分：左半部分小于等于X，右半部分大于等于X。
Conquer： 左右两个子数组递归地调用Divide过程。
Combine：快排作为就地排序算法（in place sort），不需要任何合并操作
可以看出快排的核心部分就是划分过程（partitioning）,下面以一个实例来详细解释如何划分数组（图取自于《算法导论》）
初始化：选取基元P=2，就是数组首元素。i=1,j=i+1=2 (数组下标以1开头)
循环不变量：2~i之间的元素都小于或等于P，i+1~j之间的元素都大于或等于P

循环过程：j从2到n，考察j位置的元素，如果大于等于P，就继续循环。如果小于P，就将j位置的元素（不应该出现在i+1~j这个区间）和i+1位置(交换之后仍在i+1~j区间)的元素交换位置，同时将i+1.这样就维持了循环不变量（见上述循环不变量说明）。直到j=n，完成最后一次循环操作。
要注意的是在完成循环后，还需要将i位置的元素和数组首元素交换以满足我们最先设定的要求（对应图中的第i步）。

细心的读者可能会想到另一种更直白的分区方法，即将基元取出存在另一相同大小数组中，遇到比基元小的元素就存储在数组左半部分，遇到比基元大的元素就存储在数组右半部分。这样的操作复杂度也是线性的,即Theta(n)。但是空间复杂度提高了一倍。这也是快排就地排序的优势所在。



代码如下:

public class QuickSort {
    private static void QuickSort(int[] array,int start,int end)
    {
        if(start<end)
        {
            int key=array[start];//初始化保存基元
            int i=start,j;//初始化i,j
            for(j=start+1;j<=end;j++)

if(array[j]<key)//如果此处元素小于基元，则把此元素和i+1处元素交换，并将i加1，如大于或等于基元则继续循环
                {
                    int temp=array[j];
                    array[j]=array[i+1];
                    array[i+1]=temp;
                    i++;
                }

}
            array[start]=array[i];//交换i处元素和基元
            array[i]=key;
            QuickSort(array, start, i-1);//递归调用
            QuickSort(array, i+1, end);

}

}
    public static void main(String[] args)
    {
        int[] array=new int[]{11,213,134,44,77,78,23,43};
        QuickSort(array, 0, array.length-1);
        for(int i=0;i<array.length;i++)
        {
            System.out.println((i+1)+"th:"+array[i]);
        }
    }
}

赞 (0)

相关推荐

  • Java 快速排序(QuickSort)原理及实现代码

    快速排序(QuickSort )是常用到的效率比较高的一种排序算法,在面试过程中也经常提及.下面就详细讲解一下他的原理.给出一个Java版本的实现. 快速排序思想: 通过对数据元素集合Rn 进行一趟排序划分出独立的两个部分.其中一个部分的关键字比另一部分的关键字小.然后再分别对两个部分的关键字进行一趟排序,直到独立的元素只有一个,此时整个元素集合有序. 快速排序的过程--挖坑填数法(这是一个很形象的名称),对一个元素集合R[ low ... high ] ,首先取一个数(一般是R[low] )做

  • java简单快速排序实例解析

    一.基本概念 找出一个元素(理论上可以随便找一个)作为基准(pivot),然后对数组进行分区操作,使基准左边元素的值都不大于基准值,基准右边的元素值 都不小于基准值,如此作为基准的元素调整到排序后的正确位置.递归快速排序,将其他n-1个元素也调整到排序后的正确位置.最后每个元素都是在排序后的正 确位置,排序完成.所以快速排序算法的核心算法是分区操作,即如何调整基准的位置以及调整返回基准的最终位置以便分治递归. 二.选择基准元 1.固定基准元 如果输入序列是随机的,处理时间是可以接受的.如果数组已

  • 快速排序的原理及java代码实现

    快速排序的原理及java代码实现

    概述 快速排序是由东尼·霍尔所发展的一种排序算法.在平均状况下,排序 n 个项目要Ο(nlogn)次比较.事实上,快速排序通常明显比其他Ο(nlogn) 算法更快,因为它的内部循环(inner loop)可以在大部分的架构上很有效率地被实现出来,并且在大部分真实世界的数据,可以决定设计的选择,减少所需时间的二次方项之可能性. 快速排序,通过一趟排序将待排记录分割成独立的两部分,其中一部分记录的关键字均比另一部分的关键字小,然后分别对这两部分记录继续进行排序,以达到整个序列有序的目的. 形象图示:

  • 快速排序算法原理及java递归实现

    快速排序 对冒泡排序的一种改进,若初始记录序列按关键字有序或基本有序,蜕化为冒泡排序.使用的是递归原理,在所有同数量级O(n longn) 的排序方法中,其平均性能最好.就平均时间而言,是目前被认为最好的一种内部排序方法 基本思想是:通过一躺排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列. 三个指针: 第一个指针称为pivotkey指针(枢轴),第二个指

  • java数组排序示例(冒泡排序、快速排序、希尔排序、选择排序)

    快速排序法主要是运用了Arrays中的一个方法Arrays.sort()实现. 冒泡法是运用遍历数组进行比较,通过不断的比较将最小值或者最大值一个一个的遍历出来. 选择排序法是将数组的第一个数据作为最大或者最小的值,然后通过比较循环,输出有序的数组. 插入排序是选择一个数组中的数据,通过不断的插入比较最后进行排序. 复制代码 代码如下: package com.firewolf.sort; public class MySort { /**  * @param args  */ public s

  • java 合并排序算法、冒泡排序算法、选择排序算法、插入排序算法、快速排序算法的描述

    算法是在有限步骤内求解某一问题所使用的一组定义明确的规则.通俗点说,就是计算机解题的过程.在这个过程中,无论是形成解题思路还是编写程序,都是在实施某种算法.前者是推理实现的算法,后者是操作实现的算法. 一个算法应该具有以下五个重要的特征: 1.有穷性: 一个算法必须保证执行有限步之后结束: 2.确切性: 算法的每一步骤必须有确切的定义: 3.输入:一个算法有0个或多个输入,以刻画运算对象的初始情况: 4.输出:一个算法有一个或多个输出,以反映对输入数据加工后的结果.没有输出的算法是毫无意义的:

  • 图文讲解Java中实现quickSort快速排序算法的方法

    图文讲解Java中实现quickSort快速排序算法的方法

    相对冒泡排序.选择排序等算法而言,快速排序的具体算法原理及实现有一定的难度.为了更好地理解快速排序,我们仍然以举例说明的形式来详细描述快速排序的算法原理.在前面的排序算法中,我们以5名运动员的身高排序问题为例进行讲解,为了更好地体现快速排序的特点,这里我们再额外添加3名运动员.实例中的8名运动员及其身高信息详细如下(F.G.H为新增的运动员): A(181).B(169).C(187).D(172).E(163).F(191).G(189).H(182) 在前面的排序算法中,这些排序都是由教练主

  • java实现快速排序算法

    java实现快速排序算法

    1.算法概念. 快速排序(Quicksort)是对冒泡排序的一种改进.由C. A. R. Hoare在1962年提出. 2.算法思想. 通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列. 3.实现思路. ①以第一个关键字 K 1 为控制字,将 [K 1 ,K 2 ,-,K n ] 分成两个子区,使左区所有关键字小于等于 K 1 ,右区所有关键字大于

  • Java中的数组排序方式(快速排序、冒泡排序、选择排序)

    1.使用JavaApi文档中的Arrays类中的sort()进行快速排序 复制代码 代码如下: import java.util.Arrays; public class TestOne{ public static void main(String [] args){ int [] array={2,0,1,4,5,8}; Arrays.sort(array);//调用Arrays的静态方法Sort进行排序,升序排列 for(int show:array){ System.out.printl

  • Java实现快速排序算法(Quicktsort)

    快速排序算法介绍快速排序和归并排序都使用分治法来设计算法,区别在于归并排序把数组分为两个基本等长的子数组,分别排好序之后还要进行归并(Merge)操作,而快速排序拆分子数组的时候显得更有艺术,取一个基准元素,拆分之后基准元素左边的元素都比基准元素小,右边的元素都不小于基准元素,这样只需要分别对两个子数组排序即可,不再像归并排序一样需要归并操作.基准元素的选取对算法的效率影响很大,最好的情况是两个子数组大小基本相当.为简单起见,我们选择最后一个元素,更高级的做法可以先找一个中位数并把中位数与最后一

随机推荐