`

java排序

阅读更多

纯粹个人的笔记,看到hadoop中的quickSort和headSort,发现原来的好东西都付之东流了,在此记一下下

 

------------------------------------

前几种,冒泡,标记都不适合实际使用,或是只用在部分排序上

堆排序实质是将树变为符合规则的大/小顶树,循环从下向上,递归从顶到下进行交换;建堆和排序两个过程都是在进行此操作

冒泡  

  一种实现可以:for 向后 for 内部向前

  for(out = nElens-1;out>0;out--)

     for(int i=0;i<out;i++)

          if(a[i]>a[out])swap();

 

--------------------------------------

选择   冒泡的变形,使用标志,而不是替换,在内部结束时进行替换

  一种实现可以:for 向前 for 内部向前

   for(out=0;n<nElens-1;out++)

      min = out;

      for(int i=0;i<n;i++)

          if(a[min]>a[i])min = i;

      swap()

 

--------------------------------------

插入   跟前边有序列比较,找到合适的位置,进行错位

for(int out = 1; n< nElens; out++)

   item = a[out];

   int in = out;

   while(in > 0 && a[in] > item)

        a[out] = a[out-1];in--;

   a[in] = item;

 

--------------------------------------

希尔 插入排序的改变,先进行分组,组内进行插入排序,知道分组数为1为止

 

        int j;  

        for(int gap = data.length / 2; gap > 0; gap /= 2){  

            for(int i = gap; i < data.length; i++){  

                Comparable temp = data[i];  

                for(j = i; j >= gap && temp.compareTo(data[j - gap]) < 0; j -= gap){  

                    data[j] = data[j - gap];  

                }  

 

                data[j] = temp;  

            }  

        }  

 

--------------------------------------

转: http://blog.csdn.net/forrestgtju/article/details/7848829

快速   分区,递归在分区,每次分区确定一个基数位置,并将队列分两半

         分区算法的一种实现:设left为基数位置,想跟right比较,再跟left比较,当left>=right,结束,并将基数放在left上int AdjustArray(int s[], int l, int r) //返回调整后基准数的位置  

{  
    int i = l, j = r;  
    int x = s[l]; //s[l]即s[i]就是第一个坑  
    while (i < j)  
    {  
        // 从右向左找小于x的数来填s[i]  
        while(i < j && s[j] >= x)   
            j--;    
        if(i < j)   
        {  
            s[i] = s[j]; //将s[j]填到s[i]中,s[j]就形成了一个新的坑  
            i++;  
        }  
  
        // 从左向右找大于或等于x的数来填s[j]  
        while(i < j && s[i] < x)  
            i++;    
        if(i < j)   
        {  
            s[j] = s[i]; //将s[i]填到s[j]中,s[i]就形成了一个新的坑  
            j--;  
        }  
    }  
    //退出时,i等于j。将x填到这个坑中。  
    s[i] = x;  
  
    return i;  
} 

另一种实现快速排序,其实理论上都一样:

             int left = i; 

        int right =j; 
        int temp = 0; 
        boolean r_or_l = true; 
        if(left>=right){ 
            return; 
        } 
        while(left<right){ 
            if(nums[left]>nums[right]){ 
                temp = nums[left]; 
                nums[left] = nums[right]; 
                nums[right] = temp; 
                r_or_l = r_or_l?false:true; 
            } 
            if(r_or_l){ 
                right--; 
            } else { 
                left++; 
            } 
        }     
        left-=1; 
        right+=1; 
        System.out.println(right+" "+left); 

        quickSort(nums, 0, left); 
        quickSort(nums, right, j); 

最后在贴一版hadoop中实现的quickSort(他好像还想用堆排序,最后给give up了,不太清楚是没写完,还是写坏了) 

 

private static void sortInternal(final IndexedSortable s, int p, int r,
      final Progressable rep, int depth) {
    if (null != rep) {
      rep.progress();
    }
    while (true) {
    if (r-p < 13) {
      for (int i = p; i < r; ++i) {
        for (int j = i; j > p && s.compare(j-1, j) > 0; --j) {
          s.swap(j, j-1);
        }
      }
      return;
    }
    if (--depth < 0) {
      // give up
      alt.sort(s, p, r, rep);
      return;
    }

    // select, move pivot into first position
    fix(s, (p+r) >>> 1, p);
    fix(s, (p+r) >>> 1, r - 1);
    fix(s, p, r-1);

    // Divide
    int i = p;
    int j = r;
    int ll = p;
    int rr = r;
    int cr;
    while(true) {
      while (++i < j) {
        if ((cr = s.compare(i, p)) > 0) break;
        if (0 == cr && ++ll != i) {
          s.swap(ll, i);
        }
      }
      while (--j > i) {
        if ((cr = s.compare(p, j)) > 0) break;
        if (0 == cr && --rr != j) {
          s.swap(rr, j);
        }
      }
      if (i < j) s.swap(i, j);
      else break;
    }
    j = i;
    // swap pivot- and all eq values- into position
    while (ll >= p) {
      s.swap(ll--, --i);
    }
    while (rr < r) {
      s.swap(rr++, j++);
    }

    // Conquer
    // Recurse on smaller interval first to keep stack shallow
    assert i != j;
    if (i - p < r - j) {
      sortInternal(s, p, i, rep, depth);
      p = j;
    } else {
      sortInternal(s, j, r, rep, depth);
      r = i;
    }
    }
  }

 

--------------------------------------

堆排序

堆排序 获得最大或最小元素,即为根元素;移除根元素,将最底元素移动至根位置。

重组树(移动新节点,最大根数要与最大子节点交换位置,反之亦然),然后递归

 

void HeapSort(SeqIAst R)
   { //对R[1..n]进行堆排序,不妨用R[0]做暂存单元
    int i;
    BuildHeap(R); //将R[1-n]建成初始堆
    for(i=n;i>1;i--){ //对当前无序区R[1..i]进行堆排序,共做n-1趟。
      R[0]=R[1];R[1]=R[i];R[i]=R[0]; //将堆顶和堆中最后一个记录交换
     Heapify(R,1,i-1); //将R[1..i-1]重新调整为堆,仅有R[1]可能违反堆性质
     } //endfor
   } //HeapSort

 

--------------------------------------

基数排序 (出自java算法和数据结构)

基数排序 是把关键字拆分 然后进行排序。一般从各位开始,按照各位分10组,从0到9。以此遍历各个位,并且以后的分组内部顺序要满足上边的顺序。输出结果可显示为:

421 240 035 532 305 430 124

(240 430) (421) (532) (124) (035 305)

(305) (421 124) (430 532 035) (240)

(035) (124) (240) (305) (421 430) (532)

 

 

---------------------------------------------------------

 

加个折半查找,呵呵

int i = (low+high)/2

if(item=a[i]) re i;

if(item>a[i])

 re find(a,i,high)

else

 re find(a,low,i)

------------------

while(low<high)

    int i = (low+high)/2

    if(item = a[i])

        break;

    if(item>a[i]) 

         low = i;

    else

         high = 1;

 

 

 

 

 

 

 

分享到:
评论

相关推荐

    java排序.txt

    根据提供的文件信息,我们可以归纳出以下关于Java排序的相关知识点: ### 一、文件基本信息 - **文件名**:`java排序.txt` - **文件描述**:该文本文件主要介绍了几种常用的Java排序算法,并通过示例代码展示了...

    java排序算法使用及场景说明

    Java 排序算法使用及场景说明 本文档主要介绍了 Java 排序算法的使用和场景说明,包括了五个实践场景的解决方案。 Scenario 1: 找出两个文件共同的 URL 在这个场景中,我们有两个文件 a 和 b,每个文件中存放了 ...

    java排序代码大全

    根据给定文件中的标题“Java排序代码大全”以及描述与标签中的关键词如“Java排序”、“排序大全”和“算法”,本文将详细解读文件中所包含的几种排序算法的实现方式,并结合具体代码进行深入分析。 ### 快速排序...

    java排序大全(含各种排序算法)

    Java排序算法是编程中基础且重要的概念,它们用于组织数组或列表中的元素,使其按照特定顺序排列。在本文中,我们将探讨几种常见的排序算法的Java实现,包括插入排序、冒泡排序、选择排序、Shell排序、快速排序、...

    Java排序算法详细整理

    【Java排序算法详细整理】 在计算机科学中,排序算法是用于对一组数据进行排列的算法。在Java中,实现各种排序算法有助于理解数据结构和算法的原理,同时也能提高编程能力。以下是对Java中常见的几种排序算法的详细...

    面向对象java排序包

    【面向对象Java排序包】是基于Java编程语言设计的一个专门用于处理排序问题的软件组件。这个包充分体现了面向对象的设计原则,将数据结构、算法和业务逻辑封装在独立的对象中,提高了代码的可读性和可维护性。它不仅...

    java排序简单介绍

    Java排序是程序开发中常见的一种任务,主要用于对数据集合进行有序排列。在Java中,有多种内置和自定义的排序算法可供选择,每种都有其特定的适用场景和性能特点。下面将详细介绍几种常见的Java排序方法。 1. **...

    Java排序算法大全

    Java排序算法大全是一份专为Java开发者准备的学习资源,涵盖了各种经典的排序算法,旨在帮助初学者和有经验的程序员深入理解排序的原理和实现。排序是计算机科学中的基础且重要的概念,它在数据处理、数据库操作、...

    JAVA排序汇总 各种排序

    在Java编程语言中,排序是数据处理中非常基础且重要的操作。本文将全面解析Java中的各种排序算法,帮助你理解并掌握它们的核心概念、实现方式以及适用场景。 1. 冒泡排序(Bubble Sort) 冒泡排序是最简单的排序...

    Java排序算法源代码

    本资源“Java排序算法源代码”提供了一系列经典的排序算法实现,包括冒泡排序、插入排序、选择排序、希尔排序和快速排序,全部用Java语言编写。这些算法对于学习和理解排序原理以及优化代码性能至关重要。 1. **...

    java排序大全.txt

    java排序算法大全 为了便于管理,先引入个基础类: 一 插入排序 二 冒泡排序 三,选择排序 四 Shell排序 五 快速排序 六 归并排序 等等

    java排序可视化页面

    Java排序可视化页面是一种用于教学和理解排序算法的强大工具。它通过图形化的方式展示了排序过程,使得用户能够直观地看到冒泡排序、选择排序和插入排序这三种基础排序算法的工作原理。接下来,我们将深入探讨这些...

    java 排序 面试题

    ### Java排序方法面试知识点详解 在Java编程领域中,排序算法是面试中常见的技术考察点之一。本篇文章将深入分析几种基本的排序算法,并通过具体的Java代码示例来阐述每种算法的特点及其应用场景。 #### 1. 插入...

    面试笔试必用-必须掌握的Java排序算法

    Java排序算法是编程面试和笔试中常见的考察点,掌握这些算法对于提升编程能力和解决实际问题至关重要。本篇文章将深入探讨几种主要的Java排序算法及其特点。 1. **插入排序** - **直接插入排序**:将每个元素依次...

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

    这个"Java排序算法包"提供了对多种排序算法的支持,并且允许用户根据自己的需求自定义比较条件,使得排序功能更加灵活。 1. **排序算法基础**: - 排序是指将一组数据按照特定的顺序进行排列的过程。常见的排序...

    Java排序Java排序.doc

    Java排序是程序设计中常见的操作,它涉及到一系列的算法,用于对数组或列表中的元素进行升序或降序排列。本文主要介绍几种经典的排序算法,包括插入排序、交换排序、选择排序、归并排序和基数排序,并分析了如何根据...

    java代码-使用java解决java排序之-快速排序的问题的源代码

    java代码-使用java解决java排序之-快速排序的问题的源代码 ——学习参考资料:仅用于个人学习使用!

    Java排序(带图形界面)

    执行语句:java sort &lt;输入方式&gt; &lt;图形界面/非图形界面选择&gt; &lt;待排序数列&gt; 例: java sort 0 643 323 12 3 523 23 //命令行输入数据并排序 java sort 1 1 //非图形界面下手动输入数据并排序 java sort 1 2 //手动...

Global site tag (gtag.js) - Google Analytics