189 8069 5689
Java排序算法
成都网站建设、成都做网站介绍好的网站是理念、设计和技术的结合。创新互联公司拥有的网站设计理念、多方位的设计风格、经验丰富的设计团队。提供PC端+手机端网站建设，用营销思维进行网站设计、采用先进技术开源代码、注重用户体验与SEO基础，将技术与创意整合到网站之中，以契合客户的方式做到创意性的视觉化效果。
1）分类：
1）插入排序（直接插入排序、希尔排序）
2）交换排序（冒泡排序、快速排序）
3）选择排序（直接选择排序、堆排序）
4）归并排序
5）分配排序（箱排序、基数排序）
所需辅助空间最多：归并排序
所需辅助空间最少：堆排序
平均速度最快：快速排序
不稳定：快速排序，希尔排序，堆排序。
1）选择排序算法的时候
1.数据的规模 ； 2.数据的类型 ； 3.数据已有的顺序
一般来说，当数据规模较小时，应选择直接插入排序或冒泡排序。任何排序算法在数据量小时基本体现不出来差距。 考虑数据的类型，比如如果全部是正整数，那么考虑使用桶排序为最优。 考虑数据已有顺序，快排是一种不稳定的排序（当然可以改进），对于大部分排好的数据，快排会浪费大量不必要的步骤。数据量极小，而起已经基本排好序，冒泡是最佳选择。我们说快排好，是指大量随机数据下，快排效果最理想。而不是所有情况。
3）总结：
——按平均的时间性能来分：
1）时间复杂度为O(nlogn)的方法有：快速排序、堆排序和归并排序，其中以快速排序为最好；
2）时间复杂度为O(n2)的有：直接插入排序、起泡排序和简单选择排序，其中以直接插入为最好，特 别是对那些对关键字近似有序的记录序列尤为如此；
3）时间复杂度为O(n)的排序方法只有，基数排序。
当待排记录序列按关键字顺序有序时，直接插入排序和起泡排序能达到O(n)的时间复杂度;而对于快速排序而言，这是最不好的情况，此时的时间性能蜕化为O(n2)，因此是应该尽量避免的情况。简单选择排序、堆排序和归并排序的时间性能不随记录序列中关键字的分布而改变。
——按平均的空间性能来分（指的是排序过程中所需的辅助空间大小）：
1） 所有的简单排序方法(包括：直接插入、起泡和简单选择)和堆排序的空间复杂度为O(1)；
2） 快速排序为O(logn )，为栈所需的辅助空间;
3） 归并排序所需辅助空间最多，其空间复杂度为O(n );
4）链式基数排序需附设队列首尾指针，则空间复杂度为O(rd )。
——排序方法的稳定性能：
1） 稳定的排序方法指的是，对于两个关键字相等的记录，它们在序列中的相对位置，在排序之前和 经过排序之后，没有改变。
2） 当对多关键字的记录序列进行LSD方法排序时，必须采用稳定的排序方法。
3） 对于不稳定的排序方法，只要能举出一个实例说明即可。
4） 快速排序，希尔排序和堆排序是不稳定的排序方法。
4）插入排序：
包括直接插入排序，希尔插入排序。
直接插入排序： 将一个记录插入到已经排序好的有序表中。
1, sorted数组的第0个位置没有放数据。
2，从sorted第二个数据开始处理：
如果该数据比它前面的数据要小，说明该数据要往前面移动。
首先将该数据备份放到 sorted的第0位置当哨兵。
然后将该数据前面那个数据后移。
然后往前搜索，找插入位置。
找到插入位置之后讲 第0位置的那个数据插入对应位置。
O(n*n), 当待排记录序列为正序时，时间复杂度提高至O(n)。
希尔排序（缩小增量排序 diminishing increment sort）：先将整个待排记录序列分割成若干个子序列分别进行直接插入排序，待整个序列中的记录基本有序时，再对全体记录进行一次直接插入排序。
面试穿什么，这里找答案！
插入排序Java代码：
public class InsertionSort {
// 插入排序：直接插入排序 ，希尔排序
public void straightInsertionSort(double [] sorted){
int sortedLen= sorted.length;
for(int j=2;jsortedLen;j++){
if(sorted[j]sorted[j-1]){
sorted[0]= sorted[j];//先保存一下后面的那个
sorted[j]=sorted[j-1];// 前面的那个后移。
int insertPos=0;
for(int k=j-2;k=0;k--){
if(sorted[k]sorted[0]){
sorted[k+1]=sorted[k];
}else{
insertPos=k+1;
break;
}
}
sorted[insertPos]=sorted[0];
}
}
}
public void shellInertionSort(double [] sorted, int inc){
int sortedLen= sorted.length;
for(int j=inc+1;jsortedLen;j++ ){
if(sorted[j]sorted[j-inc]){
sorted[0]= sorted[j];//先保存一下后面的那个
int insertPos=j;
for(int k=j-inc;k=0;k-=inc){
if(sorted[k]sorted[0]){
sorted[k+inc]=sorted[k];
//数据结构课本上这个地方没有给出判读，出错：
if(k-inc=0){
insertPos = k;
}
}else{
insertPos=k+inc;
break;
}
}
sorted[insertPos]=sorted[0];
}
}
}
public void shellInsertionSort(double [] sorted){
int[] incs={7,5,3,1};
int num= incs.length;
int inc=0;
for(int j=0;jnum;j++){
inc= incs[j];
shellInertionSort(sorted,inc);
}
}
public static void main(String[] args) {
Random random= new Random(6);
int arraysize= 21;
double [] sorted=new double[arraysize];
System.out.print("Before Sort:");
for(int j=1;jarraysize;j++){
sorted[j]= (int)(random.nextDouble()* 100);
System.out.print((int)sorted[j]+" ");
}
System.out.println();
InsertionSort sorter=new InsertionSort();
// sorter.straightInsertionSort(sorted);
sorter.shellInsertionSort(sorted);
System.out.print("After Sort:");
for(int j=1;jsorted.length;j++){
System.out.print((int)sorted[j]+" ");
}
System.out.println();
}
}
面试穿什么，这里找答案！
5）交换排序：
包括冒泡排序，快速排序。
冒泡排序法：该算法是专门针对已部分排序的数据进行排序的一种排序算法。如果在你的数据清单中只有一两个数据是乱序的话，用这种算法就是最快的排序算法。如果你的数据清单中的数据是随机排列的，那么这种方法就成了最慢的算法了。因此在使用这种算法之前一定要慎重。这种算法的核心思想是扫描数据清单，寻找出现乱序的两个相邻的项目。当找到这两个项目后，交换项目的位置然后继续扫描。重复上面的操作直到所有的项目都按顺序排好。
快速排序：通过一趟排序，将待排序记录分割成独立的两个部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。具体做法是：使用两个指针low,high, 初值分别设置为序列的头，和序列的尾，设置pivotkey为第一个记录，首先从high开始向前搜索第一个小于pivotkey的记录和pivotkey所在位置进行交换，然后从low开始向后搜索第一个大于pivotkey的记录和此时pivotkey所在位置进行交换，重复知道low=high了为止。
交换排序Java代码：
public class ExchangeSort {
public void BubbleExchangeSort(double [] sorted){
int sortedLen= sorted.length;
for(int j=sortedLen;j0;j--){
int end= j;
for(int k=1;kend-1;k++){
double tempB= sorted[k];
sorted[k]= sorted[k]sorted[k+1]?
sorted[k]:sorted[k+1];
if(Math.abs(sorted[k]-tempB)10e-6){
sorted[k+1]=tempB;
}
}
}
}
public void QuickExchangeSortBackTrack(double [] sorted,
int low,int high){
if(lowhigh){
int pivot= findPivot(sorted,low,high);
QuickExchangeSortBackTrack(sorted,low,pivot-1);
QuickExchangeSortBackTrack(sorted,pivot+1,high);
}
}
public int findPivot(double [] sorted, int low, int high){
sorted[0]= sorted[low];
while(lowhigh){
while(lowhigh sorted[high]= sorted[0])--high;
sorted[low]= sorted[high];
while(lowhigh sorted[low]=sorted[0])++low;
sorted[high]= sorted[low];
}
sorted[low]=sorted[0];
return low;
}
public static void main(String[] args) {
Random random= new Random(6);
int arraysize= 21;
double [] sorted=new double[arraysize];
System.out.print("Before Sort:");
for(int j=1;jarraysize;j++){
sorted[j]= (int)(random.nextDouble()* 100);
System.out.print((int)sorted[j]+" ");
}
System.out.println();
ExchangeSort sorter=new ExchangeSort();
// sorter.BubbleExchangeSort(sorted);
sorter.QuickExchangeSortBackTrack(sorted, 1, arraysize-1);
System.out.print("After Sort:");
for(int j=1;jsorted.length;j++){
System.out.print((int)sorted[j]+" ");
}
System.out.println();
}
}
6）选择排序：
分为直接选择排序， 堆排序
直接选择排序：第i次选取 i到array.Length-1中间最小的值放在i位置。
堆排序：首先，数组里面用层次遍历的顺序放一棵完全二叉树。从最后一个非终端结点往前面调整，直到到达根结点，这个时候除根节点以外的所有非终端节点都已经满足堆得条件了，于是需要调整根节点使得整个树满足堆得条件，于是从根节点开始，沿着它的儿子们往下面走（最大堆沿着最大的儿子走，最小堆沿着最小的儿子走）。 主程序里面，首先从最后一个非终端节点开始调整到根也调整完，形成一个heap， 然后将heap的根放到后面去（即：每次的树大小会变化，但是 root都是在1的位置，以方便计算儿子们的index，所以如果需要升序排列，则要逐步大顶堆。因为根节点被一个个放在后面去了。 降序排列则要建立小顶堆）
代码中的问题： 有时候第2个和第3个顺序不对（原因还没搞明白到底代码哪里有错）
选择排序Java代码：
public class SelectionSort {
public void straitSelectionSort(double [] sorted){
int sortedLen= sorted.length;
for(int j=1;jsortedLen;j++){
int jMin= getMinIndex(sorted,j);
exchange(sorted,j,jMin);
}
}
public void exchange(double [] sorted,int i,int j){
int sortedLen= sorted.length;
if(isortedLen jsortedLen ij i=0 j=0){
double temp= sorted[i];
sorted[i]=sorted[j];
sorted[j]=temp;
}
}
public int getMinIndex(double [] sorted, int i){
int sortedLen= sorted.length;
int minJ=1;
double min= Double.MAX_VALUE;
for(int j=i;jsortedLen;j++){
if(sorted[j]min){
min= sorted[j];
minJ= j;
}
}
return minJ;
}
public void heapAdjust(double [] sorted,int start,int end){
if(startend){
double temp= sorted;
// 这个地方jend与课本不同，j=end会报错：
for(int j=2*start;jend;j *=2){
if(j+1end sorted[j]-sorted[j+1]10e-6){
++j;
}
if(temp=sorted[j]){
break;
}
sorted=sorted[j];
start=j;
}
sorted=temp;
}
}
public void heapSelectionSort(double [] sorted){
int sortedLen = sorted.length;
for(int i=sortedLen/2;i0;i--){
heapAdjust(sorted,i,sortedLen);
}
for(int i=sortedLen;i1;--i){
exchange(sorted,1,i);
heapAdjust(sorted,1,i-1);
}
}
public static void main(String [] args){
Random random= new Random(6);
int arraysize=9;
double [] sorted=new double[arraysize];
System.out.print("Before Sort:");
for(int j=1;jarraysize;j++){
sorted[j]= (int)(random.nextDouble()* 100);
System.out.print((int)sorted[j]+" ");
}
System.out.println();
SelectionSort sorter=new SelectionSort();
// sorter.straitSelectionSort(sorted);
sorter.heapSelectionSort(sorted);
System.out.print("After Sort:");
for(int j=1;jsorted.length;j++){
System.out.print((int)sorted[j]+" ");
}
System.out.println();
}
}
面试穿什么，这里找答案！
7）归并排序：
将两个或两个以上的有序表组合成一个新的有序表。归并排序要使用一个辅助数组，大小跟原数组相同，递归做法。每次将目标序列分解成两个序列，分别排序两个子序列之后，再将两个排序好的子序列merge到一起。
归并排序Java代码：
public class MergeSort {
private double[] bridge;//辅助数组
public void sort(double[] obj){
if (obj == null){
throw new NullPointerException("
The param can not be null!");
}
bridge = new double[obj.length]; // 初始化中间数组
mergeSort(obj, 0, obj.length - 1); // 归并排序
bridge = null;
}
private void mergeSort(double[] obj, int left, int right){
if (left right){
int center = (left + right) / 2;
mergeSort(obj, left, center);
mergeSort(obj, center + 1, right);
merge(obj, left, center, right);
}
}
private void merge(double[] obj, int left,
int center, int right){
int mid = center + 1;
int third = left;
int tmp = left;
while (left = center mid = right){
// 从两个数组中取出小的放入中间数组
if (obj[left]-obj[mid]=10e-6){
bridge[third++] = obj[left++];
} else{
bridge[third++] = obj[mid++];
}
}
// 剩余部分依次置入中间数组
while (mid = right){
bridge[third++] = obj[mid++];
}
while (left = center){
bridge[third++] = obj[left++];
}
// 将中间数组的内容拷贝回原数组
copy(obj, tmp, right);
}
private void copy(double[] obj, int left, int right)
{
while (left = right){
obj[left] = bridge[left];
left++;
}
}
public static void main(String[] args) {
Random random = new Random(6);
int arraysize = 10;
double[] sorted = new double[arraysize];
System.out.print("Before Sort:");
for (int j = 0; j arraysize; j++) {
sorted[j] = (int) (random.nextDouble() * 100);
System.out.print((int) sorted[j] + " ");
}
System.out.println();
MergeSort sorter = new MergeSort();
sorter.sort(sorted);
System.out.print("After Sort:");
for (int j = 0; j sorted.length; j++) {
System.out.print((int) sorted[j] + " ");
}
System.out.println();
}
}
面试穿什么，这里找答案！
8）基数排序：
使用10个辅助队列，假设最大数的数字位数为 x， 则一共做 x次，从个位数开始往前，以第i位数字的大小为依据，将数据放进辅助队列，搞定之后回收。下次再以高一位开始的数字位为依据。
以Vector作辅助队列，基数排序的Java代码：
public class RadixSort {
private int keyNum=-1;
private VectorVectorDouble util;
public void distribute(double [] sorted, int nth){
if(nth=keyNum nth0){
util=new VectorVectorDouble();
for(int j=0;j10;j++){
Vector Double temp= new Vector Double();
util.add(temp);
}
for(int j=0;jsorted.length;j++){
int index= getNthDigit(sorted[j],nth);
util.get(index).add(sorted[j]);
}
}
}
public int getNthDigit(double num,int nth){
String nn= Integer.toString((int)num);
int len= nn.length();
if(len=nth){
return Character.getNumericValue(nn.charAt(len-nth));
}else{
return 0;
}
}
public void collect(double [] sorted){
int k=0;
for(int j=0;j10;j++){
int len= util.get(j).size();
if(len0){
for(int i=0;ilen;i++){
sorted[k++]= util.get(j).get(i);
}
}
}
util=null;
}
public int getKeyNum(double [] sorted){
double max= Double.MIN_VALUE;
for(int j=0;jsorted.length;j++){
if(sorted[j]max){
max= sorted[j];
}
}
return Integer.toString((int)max).length();
}
public void radixSort(double [] sorted){
if(keyNum==-1){
keyNum= getKeyNum(sorted);
}
for(int i=1;i=keyNum;i++){
distribute(sorted,i);
collect(sorted);
}
}
public static void main(String[] args) {
Random random = new Random(6);
int arraysize = 21;
double[] sorted = new double[arraysize];
System.out.print("Before Sort:");
for (int j = 0; j arraysize; j++) {
sorted[j] = (int) (random.nextDouble() * 100);
System.out.print((int) sorted[j] + " ");
}
System.out.println();
RadixSort sorter = new RadixSort();
sorter.radixSort(sorted);
System.out.print("After Sort:");
for (int j = 0; j sorted.length; j++) {
System.out.print((int) sorted[j] + " ");
}
System.out.println();
}
}
//copy而来
给你介绍4种排序方法及源码，供参考
1.冒泡排序
主要思路： 从前往后依次交换两个相邻的元素，大的交换到后面，这样每次大的数据就到后面，每一次遍历，最大的数据到达最后面，时间复杂度是O(n^2)。
public static void bubbleSort(int[] arr){
for(int i =0; i arr.length - 1; i++){
for(int j=0; j arr.length-1; j++){
if(arr[j] arr[j+1]){
arr[j] = arr[j]^arr[j+1];
arr[j+1] = arr[j]^arr[j+1];
arr[j] = arr[j]^arr[j+1];
}
}
}
}
2.选择排序
主要思路：每次遍历序列，从中选取最小的元素放到最前面，n次选择后，前面就都是最小元素的排列了，时间复杂度是O(n^2）。
public static void selectSort(int[] arr){
for(int i = 0; i arr.length -1; i++){
for(int j = i+1; j arr.length; j++){
if(arr[j] arr[i]){
arr[j] = arr[j]^arr[i];
arr[i] = arr[j]^arr[i];
arr[j] = arr[j]^arr[i];
}
}
}
}
3.插入排序
主要思路：使用了两层嵌套循环，逐个处理待排序的记录。每个记录与前面已经排好序的记录序列进行比较，并将其插入到合适的位置，时间复杂度是O(n^2）。
public static void insertionSort(int[] arr){
int j;
for(int p = 1; p arr.length; p++){
int temp = arr[p]; //保存要插入的数据
//将无序中的数和前面有序的数据相比，将比它大的数，向后移动
for(j=p; j0 temp arr[j-1]; j--){
arr[j] = arr[j-1];
}
//正确的位置设置成保存的数据
arr[j] = temp;
}
}
4.希尔排序
主要思路：用步长分组，每个分组进行插入排序，再慢慢减小步长，当步长为1的时候完成一次插入排序， 希尔排序的时间复杂度是：O（nlogn）～O（n2），平均时间复杂度大致是O(n^1.5)
public static void shellSort(int[] arr){
int j ;
for(int gap = arr.length/2; gap 0 ; gap/=2){
for(int i = gap; i arr.length; i++){
int temp = arr[i];
for(j = i; j=gap temparr[j-gap]; j-=gap){
arr[j] = arr[j-gap];
}
arr[j] = temp;
}
}
}
// 排序
public class Array
{
public static int[] random(int n) //产生n个随机数，返回整型数组
{
if (n0)
{
int table[] = new int[n];
for (int i=0; itable.length; i++)
table[i] = (int)(Math.random()*100); //产生一个0～100之间的随机数
return table; //返回一个数组
}
return null;
}
public static void print(int[] table) //输出数组元素
{
if (table!=null)
for (int i=0; itable.length; i++)
System.out.print(" "+table[i]);
System.out.println();
}
public static void insertSort(int[] table) //直接插入排序
{ //数组是引用类型，元素值将被改变
System.out.println("直接插入排序");
for (int i=1; itable.length; i++) //n-1趟扫描
{
int temp=table[i], j; //每趟将table[i]插入到前面已排序的序列中
// System.out.print("移动");
for (j=i-1; j-1 temptable[j]; j--) //将前面较大元素向后移动
{
// System.out.print(table[j]+", ");
table[j+1] = table[j];
}
table[j+1] = temp; //temp值到达插入位置
System.out.print("第"+i+"趟: ");
print(table);
}
}
public static void shellSort(int[] table) //希尔排序
{
System.out.println("希尔排序");
for (int delta=table.length/2; delta0; delta/=2) //控制增量，增量减半，若干趟扫描
{
for (int i=delta; itable.length; i++) //一趟中若干组，每个元素在自己所属组内进行直接插入排序
{
int temp = table[i]; //当前待插入元素
int j=i-delta; //相距delta远
while (j=0 temptable[j]) //一组中前面较大的元素向后移动
{
table[j+delta] = table[j];
j-=delta; //继续与前面的元素比较
}
table[j+delta] = temp; //插入元素位置
}
System.out.print("delta="+delta+" ");
print(table);
}
}
private static void swap(int[] table, int i, int j) //交换数组中下标为i、j的元素
{
if (i=0 itable.length j=0 jtable.length i!=j) //判断i、j是否越界
{
int temp = table[j];
table[j] = table[i];
table[i] = temp;
}
}
public static void bubbleSort(int[] table) //冒泡排序
{
System.out.println("冒泡排序");
boolean exchange=true; //是否交换的标记
for (int i=1; itable.length exchange; i++) //有交换时再进行下一趟，最多n-1趟
{
exchange=false; //假定元素未交换
for (int j=0; jtable.length-i; j++) //一次比较、交换
if (table[j]table[j+1]) //反序时，交换
{
int temp = table[j];
table[j] = table[j+1];
table[j+1] = temp;
exchange=true; //有交换
}
System.out.print("第"+i+"趟: ");
print(table);
}
}
public static void quickSort(int[] table) //快速排序
{
quickSort(table, 0, table.length-1);
}
private static void quickSort(int[] table, int low, int high) //一趟快速排序，递归算法
{ //low、high指定序列的下界和上界
if (lowhigh) //序列有效
{
int i=low, j=high;
int vot=table[i]; //第一个值作为基准值
while (i!=j) //一趟排序
{
while (ij vot=table[j]) //从后向前寻找较小值
j--;
if (ij)
{
table[i]=table[j]; //较小元素向前移动
i++;
}
while (ij table[i]vot) //从前向后寻找较大值
i++;
if (ij)
{
table[j]=table[i]; //较大元素向后移动
j--;
}
}
table[i]=vot; //基准值的最终位置
System.out.print(low+".."+high+", vot="+vot+" ");
print(table);
quickSort(table, low, j-1); //前端子序列再排序
quickSort(table, i+1, high); //后端子序列再排序
}
}
public static void selectSort(int[] table) //直接选择排序
{
System.out.println("直接选择排序");
for (int i=0; itable.length-1; i++) //n-1趟排序
{ //每趟在从table[i]开始的子序列中寻找最小元素
int min=i; //设第i个数据元素最小
for (int j=i+1; jtable.length; j++) //在子序列中查找最小值
if (table[j]table[min])
min = j; //记住最小元素下标
if (min!=i) //将本趟最小元素交换到前边
{
int temp = table[i];
table[i] = table[min];
table[min] = temp;
}
System.out.print("第"+i+"趟: ");
print(table);
}
}
private static void sift(int[] table, int low, int high) //将以low为根的子树调整成最小堆
{ //low、high是序列下界和上界
int i=low; //子树的根
int j=2*i+1; //j为i结点的左孩子
int temp=table[i]; //获得第i个元素的值
while (j=high) //沿较小值孩子结点向下筛选
{
if (jhigh table[j]table[j+1]) //数组元素比较（改成为最大堆）
j++; //j为左右孩子的较小者
if (temptable[j]) //若父母结点值较大（改成为最大堆）
{
table[i]=table[j]; //孩子结点中的较小值上移
i=j; //i、j向下一层
j=2*i+1;
}
else
j=high+1; //退出循环
}
table[i]=temp; //当前子树的原根值调整后的位置
System.out.print("sift "+low+".."+high+" ");
print(table);
}
public static void heapSort(int[] table)
{
System.out.println("堆排序");
int n=table.length;
for (int j=n/2-1; j=0; j--) //创建最小堆
sift(table, j, n-1);
// System.out.println("最小堆？ "+isMinHeap(table));
for (int j=n-1; j0; j--) //每趟将最小值交换到后面，再调整成堆
{
int temp = table[0];
table[0] = table[j];
table[j] = temp;
sift(table, 0, j-1);
}
}
public static void mergeSort(int[] X) //归并排序
{
System.out.println("归并排序");
int n=1; //已排序的子序列长度，初值为1
int[] Y = new int[X.length]; //Y数组长度同X数组
do
{
mergepass(X, Y, n); //一趟归并，将X数组中各子序列归并到Y中
print(Y);
n*=2; //子序列长度加倍
if (nX.length)
{
mergepass(Y, X, n); //将Y数组中各子序列再归并到X中
print(X);
n*=2;
}
} while (nX.length);
}
private static void mergepass(int[] X, int[] Y, int n) //一趟归并
{
System.out.print("子序列长度n="+n+" ");
int i=0;
while (iX.length-2*n+1)
{
merge(X,Y,i,i+n,n);
i += 2*n;
}
if (i+nX.length)
merge(X,Y,i,i+n,n); //再一次归并
else
for (int j=i; jX.length; j++) //将X剩余元素复制到Y中
Y[j]=X[j];
}
private static void merge(int[] X, int[] Y, int m, int r, int n) //一次归并
{
int i=m, j=r, k=m;
while (ir jr+n jX.length) //将X中两个相邻子序列归并到Y中
if (X[i]X[j]) //较小值复制到Y中
Y[k++]=X[i++];
else
Y[k++]=X[j++];
while (ir) //将前一个子序列剩余元素复制到Y中
Y[k++]=X[i++];
while (jr+n jX.length) //将后一个子序列剩余元素复制到Y中
Y[k++]=X[j++];
}
public static void main(String[] args)
{
// int[] table = {52,26,97,19,66,8,49};//Array.random(9);{49,65,13,81,76,97,38,49};////{85,12,36,24,47,30,53,91,76};//;//{4,5,8,1,2,7,3,6};// {32,26,87,72,26,17};//
int[] table = {13,27,38,49,97,76,49,81}; //最小堆
System.out.print("关键字序列: ");
Array.print(table);
// Array.insertSort(table);
// Array.shellSort(table);
// Array.bubbleSort(table);
// Array.quickSort(table);
// Array.selectSort(table);
// Array.heapSort(table);
// Array.mergeSort(table);
System.out.println("最小堆序列? "+Array.isMinHeap(table));
}
//第9章习题
public static boolean isMinHeap(int[] table) //判断一个数据序列是否为最小堆
{
if (table==null)
return false;
int i = table.length/2 -1; //最深一棵子树的根结点
while (i=0)
{
int j=2*i+1; //左孩子
if (jtable.length)
if (table[i]table[j])
return false;
else
if (j+1table.length table[i]table[j+1]) //右孩子
return false;
i--;
}
return true;
}
}
/*
程序运行结果如下：
关键字序列: 32 26 87 72 26 17 8 40
直接插入排序
第1趟排序: 26 32 87 72 26 17 8 40
第2趟排序: 26 32 87 72 26 17 8 40
第3趟排序: 26 32 72 87 26 17 8 40
第4趟排序: 26 26 32 72 87 17 8 40 //排序算法稳定
第5趟排序: 17 26 26 32 72 87 8 40
第6趟排序: 8 17 26 26 32 72 87 40
第7趟排序: 8 17 26 26 32 40 72 87
关键字序列: 42 1 74 25 45 29 87 53
直接插入排序
第1趟排序: 1 42 74 25 45 29 87 53
第2趟排序: 1 42 74 25 45 29 87 53
第3趟排序: 1 25 42 74 45 29 87 53
第4趟排序: 1 25 42 45 74 29 87 53
第5趟排序: 1 25 29 42 45 74 87 53
第6趟排序: 1 25 29 42 45 74 87 53
第7趟排序: 1 25 29 42 45 53 74 87
关键字序列: 21 12 2 40 99 97 68 57
直接插入排序
第1趟排序: 12 21 2 40 99 97 68 57
第2趟排序: 2 12 21 40 99 97 68 57
第3趟排序: 2 12 21 40 99 97 68 57
第4趟排序: 2 12 21 40 99 97 68 57
第5趟排序: 2 12 21 40 97 99 68 57
第6趟排序: 2 12 21 40 68 97 99 57
第7趟排序: 2 12 21 40 57 68 97 99
关键字序列: 27 38 65 97 76 13 27 49 55 4
希尔排序
delta=5 13 27 49 55 4 27 38 65 97 76
delta=2 4 27 13 27 38 55 49 65 97 76
delta=1 4 13 27 27 38 49 55 65 76 97
关键字序列: 49 38 65 97 76 13 27 49 55 4 //严书
希尔排序
delta=5 13 27 49 55 4 49 38 65 97 76
delta=2 4 27 13 49 38 55 49 65 97 76 //与严书不同
delta=1 4 13 27 38 49 49 55 65 76 97
关键字序列: 65 34 25 87 12 38 56 46 14 77 92 23
希尔排序
delta=6 56 34 14 77 12 23 65 46 25 87 92 38
delta=3 56 12 14 65 34 23 77 46 25 87 92 38
delta=1 12 14 23 25 34 38 46 56 65 77 87 92
关键字序列: 84 12 43 62 86 7 90 91
希尔排序
delta=4 84 7 43 62 86 12 90 91
delta=2 43 7 84 12 86 62 90 91
delta=1 7 12 43 62 84 86 90 91
关键字序列: 32 26 87 72 26 17
冒泡排序
第1趟排序: 26 32 72 26 17 87
第2趟排序: 26 32 26 17 72 87
第3趟排序: 26 26 17 32 72 87
第4趟排序: 26 17 26 32 72 87
第5趟排序: 17 26 26 32 72 87
关键字序列: 1 2 3 4 5 6 7 8
冒泡排序
第1趟排序: 1 2 3 4 5 6 7 8
关键字序列: 1 3 2 4 5 8 6 7
冒泡排序
第1趟排序: 1 2 3 4 5 6 7 8
第2趟排序: 1 2 3 4 5 6 7 8
关键字序列: 4 5 8 1 2 7 3 6
冒泡排序
第1趟排序: 4 5 1 2 7 3 6 8
第2趟排序: 4 1 2 5 3 6 7 8
第3趟排序: 1 2 4 3 5 6 7 8
第4趟排序: 1 2 3 4 5 6 7 8
第5趟排序: 1 2 3 4 5 6 7 8
关键字序列: 38 26 97 19 66 1 5 49
0..7, vot=38 5 26 1 19 38 66 97 49
0..3, vot=5 1 5 26 19 38 66 97 49
2..3, vot=26 1 5 19 26 38 66 97 49
5..7, vot=66 1 5 19 26 38 49 66 97
关键字序列: 38 5 49 26 19 97 1 66
0..7, vot=38 1 5 19 26 38 97 49 66
0..3, vot=1 1 5 19 26 38 97 49 66
1..3, vot=5 1 5 19 26 38 97 49 66
2..3, vot=19 1 5 19 26 38 97 49 66
5..7, vot=97 1 5 19 26 38 66 49 97
5..6, vot=66 1 5 19 26 38 49 66 97
关键字序列: 49 38 65 97 76 13 27 49
0..7, vot=49 49 38 27 13 49 76 97 65
0..3, vot=49 13 38 27 49 49 76 97 65
0..2, vot=13 13 38 27 49 49 76 97 65
1..2, vot=38 13 27 38 49 49 76 97 65
5..7, vot=76 13 27 38 49 49 65 76 97
关键字序列: 27 38 65 97 76 13 27 49 55 4
low=0 high=9 vot=27 4 27 13 27 76 97 65 49 55 38
low=0 high=2 vot=4 4 27 13 27 76 97 65 49 55 38
low=1 high=2 vot=27 4 13 27 27 76 97 65 49 55 38
low=4 high=9 vot=76 4 13 27 27 38 55 65 49 76 97
low=4 high=7 vot=38 4 13 27 27 38 55 65 49 76 97
low=5 high=7 vot=55 4 13 27 27 38 49 55 65 76 97
关键字序列: 38 26 97 19 66 1 5 49
直接选择排序
第0趟排序: 1 26 97 19 66 38 5 49
第1趟排序: 1 5 97 19 66 38 26 49
第2趟排序: 1 5 19 97 66 38 26 49
第3趟排序: 1 5 19 26 66 38 97 49
第4趟排序: 1 5 19 26 38 66 97 49
第5趟排序: 1 5 19 26 38 49 97 66
第6趟排序: 1 5 19 26 38 49 66 97
最小堆
关键字序列: 81 49 76 27 97 38 49 13 65
sift 3..8 81 49 76 13 97 38 49 27 65
sift 2..8 81 49 38 13 97 76 49 27 65
sift 1..8 81 13 38 27 97 76 49 49 65
sift 0..8 13 27 38 49 97 76 49 81 65
13 27 38 49 97 76 49 81 65
sift 0..7 27 49 38 65 97 76 49 81 13
sift 0..6 38 49 49 65 97 76 81 27 13
sift 0..5 49 65 49 81 97 76 38 27 13
sift 0..4 49 65 76 81 97 49 38 27 13
sift 0..3 65 81 76 97 49 49 38 27 13
sift 0..2 76 81 97 65 49 49 38 27 13
sift 0..1 81 97 76 65 49 49 38 27 13
sift 0..0 97 81 76 65 49 49 38 27 13
最大堆
关键字序列: 49 65 13 81 76 27 97 38 49
sift 3..8 49 65 13 81 76 27 97 38 49
sift 2..8 49 65 97 81 76 27 13 38 49
sift 1..8 49 81 97 65 76 27 13 38 49
sift 0..8 97 81 49 65 76 27 13 38 49
97 81 49 65 76 27 13 38 49
sift 0..7 81 76 49 65 49 27 13 38 97
sift 0..6 76 65 49 38 49 27 13 81 97
sift 0..5 65 49 49 38 13 27 76 81 97
sift 0..4 49 38 49 27 13 65 76 81 97
sift 0..3 49 38 13 27 49 65 76 81 97
sift 0..2 38 27 13 49 49 65 76 81 97
sift 0..1 27 13 38 49 49 65 76 81 97
sift 0..0 13 27 38 49 49 65 76 81 97
关键字序列: 52 26 97 19 66 8 49
归并排序
子序列长度n=1 26 52 19 97 8 66 49
子序列长度n=2 19 26 52 97 8 49 66
子序列长度n=4 8 19 26 49 52 66 97
关键字序列: 13 27 38 49 97 76 49 81 65
最小堆序列? true
*/
输入三个数你可以这样
Scanner in=new Scanner(System.in);
int a=in.nextInt();
Scanner in=new Scanner(System.in);
int b=in.nextInt();
Scanner in=new Scanner(System.in);
int c=in.nextInt();
然后对三个数进行比较。
int tmp=0；
if(ab){
tmp=a;
a=b;
b=tmp;
}
if(ac){
tmp=a;
a=c;
c=tmp;
}
if(bc){
tmp=b;
b=c;
c=tmp;
}
System.out.println(a+" "+b+" "+c);
这就可以了，自己想想动动脑子才能灵活运用，如果只是给你代码，你只会复制粘贴。
//从a[index]到a[len]除了a[index]外其它元素满足一个堆，把a[index]调整到合适位置
//这个堆满足父节点孩子结点，且要保证2*index能取到index的左孩子，
public static void adjustHeap(int[] a,int index,int len){
int scn=a[index];
for(int i=2*index;i=m;i*=2){
if(ima[i]a[i+1])i+=1;
if(!a[i]scn)break;
a[index]=a[i];index=i;
}
a[index]=scn;
}
//数组a从a[1]开始存放元素，如果想从a[0]开始则要调整adjustHeap代码，以便满足完全二叉树
//性质，代码未经测试
public static void heapSort(int[] a){
for(int i=(a.length-1)/2;i0;i--)
adjustHeap(a,i,a.length-1);
int tmp;
for(int i=a.length-1;i1;i--){
tmp=a[i];
a[i]=a[1];
a[1]=tmp;
adjustHeap(a,1,i-1);
}
}
import java.util.Arrays;
import java.util.Collection;
public class Demo2 {
public static void main(String[] args) {
// 这是你的三个数
int[] arr = { 12, 32, 18 };
// 两层嵌套循环
for (int i = 0; i arr.length; i++) {
for (int j = 0; j i; j++) {
// 如果后者小于前者，让他们交换位置，一直循环
// 直到每个数字都从头到尾跟数组里的每个数字比较一次
if (arr[i] arr[j]) {
// 这三步就是交换位置，相信聪明的你一定看得懂了
arr[i] = arr[i] + arr[j];
arr[j] = arr[i] - arr[j];
arr[i] = arr[i] - arr[j];
}
}
}
//最后打印出来
for (int i = 0; i arr.length; i++) {
System.out.println(arr[i]);
}
}
}
资料拓展：
Java是一门面向对象编程语言，不仅吸收了C++语言的各种优点，还摒弃了C++里难以理解的多继承、指针等概念，因此Java语言具有功能强大和简单易用两个特征。Java语言作为静态面向对象编程语言的代表，极好地实现了面向对象理论