纯粹个人的笔记,看到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排序的相关知识点: ### 一、文件基本信息 - **文件名**:`java排序.txt` - **文件描述**:该文本文件主要介绍了几种常用的Java排序算法,并通过示例代码展示了...
Java 排序算法使用及场景说明 本文档主要介绍了 Java 排序算法的使用和场景说明,包括了五个实践场景的解决方案。 Scenario 1: 找出两个文件共同的 URL 在这个场景中,我们有两个文件 a 和 b,每个文件中存放了 ...
根据给定文件中的标题“Java排序代码大全”以及描述与标签中的关键词如“Java排序”、“排序大全”和“算法”,本文将详细解读文件中所包含的几种排序算法的实现方式,并结合具体代码进行深入分析。 ### 快速排序...
Java排序算法是编程中基础且重要的概念,它们用于组织数组或列表中的元素,使其按照特定顺序排列。在本文中,我们将探讨几种常见的排序算法的Java实现,包括插入排序、冒泡排序、选择排序、Shell排序、快速排序、...
【Java排序算法详细整理】 在计算机科学中,排序算法是用于对一组数据进行排列的算法。在Java中,实现各种排序算法有助于理解数据结构和算法的原理,同时也能提高编程能力。以下是对Java中常见的几种排序算法的详细...
【面向对象Java排序包】是基于Java编程语言设计的一个专门用于处理排序问题的软件组件。这个包充分体现了面向对象的设计原则,将数据结构、算法和业务逻辑封装在独立的对象中,提高了代码的可读性和可维护性。它不仅...
Java排序是程序开发中常见的一种任务,主要用于对数据集合进行有序排列。在Java中,有多种内置和自定义的排序算法可供选择,每种都有其特定的适用场景和性能特点。下面将详细介绍几种常见的Java排序方法。 1. **...
Java排序算法大全是一份专为Java开发者准备的学习资源,涵盖了各种经典的排序算法,旨在帮助初学者和有经验的程序员深入理解排序的原理和实现。排序是计算机科学中的基础且重要的概念,它在数据处理、数据库操作、...
在Java编程语言中,排序是数据处理中非常基础且重要的操作。本文将全面解析Java中的各种排序算法,帮助你理解并掌握它们的核心概念、实现方式以及适用场景。 1. 冒泡排序(Bubble Sort) 冒泡排序是最简单的排序...
本资源“Java排序算法源代码”提供了一系列经典的排序算法实现,包括冒泡排序、插入排序、选择排序、希尔排序和快速排序,全部用Java语言编写。这些算法对于学习和理解排序原理以及优化代码性能至关重要。 1. **...
java排序算法大全 为了便于管理,先引入个基础类: 一 插入排序 二 冒泡排序 三,选择排序 四 Shell排序 五 快速排序 六 归并排序 等等
Java排序可视化页面是一种用于教学和理解排序算法的强大工具。它通过图形化的方式展示了排序过程,使得用户能够直观地看到冒泡排序、选择排序和插入排序这三种基础排序算法的工作原理。接下来,我们将深入探讨这些...
### Java排序方法面试知识点详解 在Java编程领域中,排序算法是面试中常见的技术考察点之一。本篇文章将深入分析几种基本的排序算法,并通过具体的Java代码示例来阐述每种算法的特点及其应用场景。 #### 1. 插入...
Java排序算法是编程面试和笔试中常见的考察点,掌握这些算法对于提升编程能力和解决实际问题至关重要。本篇文章将深入探讨几种主要的Java排序算法及其特点。 1. **插入排序** - **直接插入排序**:将每个元素依次...
这个"Java排序算法包"提供了对多种排序算法的支持,并且允许用户根据自己的需求自定义比较条件,使得排序功能更加灵活。 1. **排序算法基础**: - 排序是指将一组数据按照特定的顺序进行排列的过程。常见的排序...
Java排序是程序设计中常见的操作,它涉及到一系列的算法,用于对数组或列表中的元素进行升序或降序排列。本文主要介绍几种经典的排序算法,包括插入排序、交换排序、选择排序、归并排序和基数排序,并分析了如何根据...
java代码-使用java解决java排序之-快速排序的问题的源代码 ——学习参考资料:仅用于个人学习使用!
执行语句:java sort <输入方式> <图形界面/非图形界面选择> <待排序数列> 例: java sort 0 643 323 12 3 523 23 //命令行输入数据并排序 java sort 1 1 //非图形界面下手动输入数据并排序 java sort 1 2 //手动...