`
jbm3072
  • 浏览: 211232 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

Java Arrays 快速排序算法的实现

阅读更多

我们知道Java在排序上分别使用了快速排序和合并排序。下面我们就研究一下这两种排序。

本节先分析快速排序,我们以Int数组的排序为例。

 

Java的排序算法是这样子的:

方法声明如下:

sort1(int x[], int off, int len)

对于数组个数小于7的情况下,使用插入排序:

if (len < 7) {

    for (int i=off; i<len+off; i++)

for (int j=i; j>off && x[j-1]>x[j]; j--) //

    swap(x, j, j-1); //交换 x[j]x[j-1]

    return;

}

如果大于7的话,则使用快速排序。在教科书上,快速排序一般使用的是最后一个元素作为分割元素。

Java 实现上,在寻找分割值时,则使用的下面的算法:

// Choose a partition element, v

int m = off + (len >> 1);       // Small arrays, middle element

if (len > 7) {

    int l = off;

    int n = off + len - 1;

    if (len > 40) {        // Big arrays, pseudomedian of 9

int s = len/8;

l = med3(x, l,     l+s, l+2*s);

m = med3(x, m-s,   m,   m+s);

n = med3(x, n-2*s, n-s, n);

    }

    m = med3(x, l, m, n); // Mid-size, med of 3

}

int v = x[m];

如果长度小于等于40的话,去 最左边,最右边和中间的元素的中间数作为分割元素;

如果大于40的话,分割元素,则去9个元素的中间数。

 

找到中间元素后,将数组分成:v* (<v)* (>v)* v*这样的形式。

 

int a = off, b = a, c = off + len - 1, d = c;

//a 起始位置,c结束位置

//b 起始位置变量,d结束位置变量

 

while(true) {

    while (b <= c && x[b] <= v) {

if (x[b] == v)

    swap(x, a++, b);

b++;

    }

    while (c >= b && x[c] >= v) {

if (x[c] == v)

    swap(x, c, d--);

c--;

    }

    if (b > c)

break;

    swap(x, b++, c--);

}

 

上述的算法和教科书的快速排序算法是一样的。分别从两端大于v的数,和小于v的数。如果找到,交换一下,例如[1239----------3987]的数组,如果分割元素是4,则会变成[1233-----9887]。如果数等于分割元素,则会放到开头或者结尾,最终形成v* (<v)* (>v)* v* 的数据形式。

接下来则是对数据进行调换,形成(<v)*v*(>v)*的结构:

int s, n = off + len;

s = Math.min(a-off, b-a  );  vecswap(x, off, b-s, s);

s = Math.min(d-c,   n-d-1);  vecswap(x, b,   n-s, s);

b是中间位置。vecswap是对象量进行的调换。a-off边是等于v的元素个数。b-a表示<v的个数。s表示要交换的个数。然后交换一下即可。

 

接下来递归调用快排算法:

如上,b-a表示<v的个数,现在小于v的数都已经挪到了左侧,只需调用一下排序,对前b-a的数据进行排序和后d-c的数据进行排序即可。

if ((s = b-a) > 1)

    sort1(x, off, s);

if ((s = d-c) > 1)

    sort1(x, n-s, s);

    }

 

总结:

  1.  对于小于7的元素使用插入排序;
  2. 选择中间元素有学问;
  3. 对等于v的数据进行的特殊处理。
1
0
分享到:
评论

相关推荐

    Java实现快速排序算法(源代码)

    ### Java实现快速排序算法知识点详解 #### 一、快速排序的基本概念 快速排序是一种非常高效且广泛应用的排序算法,最早由C.A.R. Hoare在1960年提出。其核心思想是采用分治法策略,通过一次排序操作将待排序的数据...

    java十二种排序算法实现源代码(类)

    在Java中实现这些排序算法,通常会用到`Arrays`类中的`sort()`方法,以及自定义的比较器`Comparator`。通过编写不同的比较逻辑,可以实现各种排序需求。此外,理解这些算法的工作原理,有助于在实际开发中选择最合适...

    java 8种排序算法

    在Java中,这些排序算法都可以用代码实现,可以通过`java.util.Arrays.sort()`方法使用内置的快速排序或归并排序,也可以自定义排序逻辑。在`AllSort`这个压缩包中,可能包含了这八种排序算法的Java实现代码,通过...

    JAVA实现快速排序

    基准关键字的选取是决定快速排序算法的关键,常用的基准关键字的选取方式包括: * 三者取中:将序列首、尾和中间位置上的记录进行比较,选择三者中值作为基准关键字。 * 取left和right之间的一个随机数,用n[m]作为...

    Java直接插入排序算法源码

    总的来说,Java中的直接插入排序算法是一个直观易懂的排序方法,虽然在效率上不敌更高级的排序算法,但它在理解和实现上相对简单,对于初学者来说是很好的学习材料。通过阅读和实践这个源代码,你可以深入理解排序...

    常见的八大排序算法及其JAVA实现

    本篇文章将深入探讨八大常见的排序算法,并提供它们在Java语言中的具体实现。这八大排序算法包括冒泡排序、选择排序、插入排序、希尔排序、归并排序、快速排序、堆排序以及计数排序。 1. 冒泡排序(Bubble Sort):...

    java实现快速排序

    在`springboot-quick`这个压缩包文件中,可能包含了一个使用SpringBoot构建的示例项目,演示了如何在实际应用中集成和使用快速排序算法。这个项目可以作为一个学习和实践快速排序的好资源,同时展示了如何将算法应用...

    Java各种排序算法代码

    了解和掌握这些排序算法的原理和实现方式,不仅有助于编写高效的排序代码,还能帮助我们在面对实际问题时选择最合适的解决方案。在学习过程中,可以结合实际例子,通过编写代码来加深理解,同时通过分析时间复杂度和...

    Java-各种排序算法

    这里我们将深入探讨几种常见的Java排序算法,包括冒泡排序、堆排序、插入排序、合并排序、快速排序以及选择排序和希尔排序。 1. **冒泡排序**:冒泡排序是最基础的排序算法之一,它通过重复遍历待排序数组,比较...

    基于Java的不同排序算法的实现及其性能比较

    Java提供了`java.util.Arrays.sort()`方法,内部实现了TimSort,这是一种混合排序算法,结合了插入排序和归并排序的优点,能在很多情况下提供良好的性能。 总的来说,理解并熟练掌握不同的排序算法对于提升程序的...

    Java排序算法实现:冒泡与选择排序示例代码

    Java排序算法实现主要涉及到两种经典的算法:冒泡排序和选择排序。这两种算法都是基于比较的排序方法,适用于小规模或教学目的的数据排序。 **冒泡排序(Bubble Sort)** 是一种简单直观的排序算法,其核心思想是...

    最快的排序算法 java最快的排序-在Java中对列表进行排序的最快方法,排序算法数据结构

    例如,在有大量元素需要排序的情况下,可以使用高效的快速排序算法;在需要稳定的排序结果时,可以使用归并排序或插入排序等稳定排序算法。 在上述代码中,使用了 ServerInfoComparator 类来实现自定义的比较器,该...

    Java排序算法包 支持自定义比较条件

    - Java排序算法包可能包含了上述的多种排序算法实现,用户可以根据数据规模、数据特点以及性能要求选择合适的算法。 - 如果需要排序的对象有复杂的比较规则,自定义`Comparator`是一个很好的解决方案。 总的来说...

    java 8大排序算法

    在Java编程语言中,排序算法是数据结构与算法...在实际编程中,Java集合框架中的`Collections.sort()`和`Arrays.sort()`方法已经为我们提供了排序功能,但了解底层的排序算法原理,有助于我们更好地理解和优化代码。

    排序算法的Java实现

    在编程领域,排序算法是计算机科学中的核心概念,特别是在数据结构和算法分析中。...在实际开发中,还可以考虑结合Java的内置排序函数`Arrays.sort()`,它使用了一种高效的混合排序算法,可以处理各种数据类型。

    排序算法-基于Java实现的排序算法之BozoSort实现.zip

    它可以让我们深刻理解为什么我们需要高效的排序算法,比如快速排序、归并排序、堆排序等,它们在时间复杂度上有着显著的优势。同时,BozoSort也提醒我们,在编程实践中,应优先考虑算法的效率,尤其是在处理大数据时...

    java四大排序算法总结.zip

    同时,现代Java库(如`Arrays.sort()`方法)通常使用更高级的排序算法,如TimSort,它结合了稳定的排序和插入排序的特性,能在大多数情况下提供良好的性能。 总的来说,理解和掌握这些基础排序算法是每个Java程序员...

    java实现常见的集中排序算法

    在Java中,我们可以使用ArrayUtils、Collections等工具类进行排序,例如`Arrays.sort()`和`Collections.sort()`,它们内部使用了高效的排序算法,如TimSort,是混合排序算法,结合了插入排序和归并排序的优点,对小...

    常用排序算法分析与实现(Java版)

    ### 常用排序算法分析与实现(Java版) #### 插入排序 **1. 直接插入排序** 直接插入排序是一种简单的排序方法,它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并...

    JAVA排序汇总 java应用中一些比较经典的排序算法

    在Java中实现这些排序算法时,通常会使用数组作为数据结构,通过定义辅助方法如`swap()`来进行元素交换,`printArray()`用于输出排序结果。例如,`bubbleSort()`函数展示了冒泡排序的具体实现,根据参数`sortType`...

Global site tag (gtag.js) - Google Analytics