教程集 > 脚本编程 > java > 正文 Java数据排序几种算法(堆排序插入排序快速排序)

Java数据排序几种算法(堆排序插入排序快速排序)

发布时间：2016-10-23 编辑：jiaochengji.com

教程集为您提供Java数据排序几种算法(堆排序插入排序快速排序)等资源，欢迎您收藏本站，我们将为您提供最新的Java数据排序几种算法(堆排序插入排序快速排序)资源

Java数据排序几种算法了，包括有堆排序插入排序快速排序了，这三种排序算法也是我们工作中常用到的，下面整理了几个例子。

堆排序算法

核心思想：用数组来表示完全二叉树，然后逐步把这个二叉树由半堆变成堆。经过不断转化，整个二叉树的根节点的值必然是最大的，然后把这个最大值放到二叉树最后的(数组的最后)。以后再进行堆化的过程时候，就可以忽略这个元素。不断的重复将最大值放到数组后面，二叉树区间越来越小，直到只剩一个元素，就表示堆排序完成了。

import java.util.*;

public class HeapSort{

public static void main(String[] args){
  int arr[] = {20,40,30,10,90,70};    // 原始数组
  heapsort( arr , arr.length ); //   进行堆排序
        System.out.println(Arrays.toString(arr));   //打印排序好后的数组
}

public static void heapsort(int heap[] , int n){
  //   n表示heap[]中有多个少元素
  //   数组heap表示的是从索引0到lastIndex之间的堆
  for ( int rootIndex = n/2-1; rootIndex >= 0; rootIndex-- ){ // 索引rootIndex处的节点是半堆的根
   reheap(heap,rootIndex,n-1); //重建堆和排序
    System.out.println(Arrays.toString(heap) "for1"); //   跟踪数组变化

  }
  swap(heap,0,n-1);   //将最大的元素放到最后面，这样下面继续排序，就可以忽视这个节点了
   System.out.println(Arrays.toString(heap) "swap");
  //逐渐删除堆的规模
  for (int lastIndex = n-2 ; lastIndex >=0 ; lastIndex--){ //
   reheap(heap, 0 , lastIndex); //重建堆和排序
   System.out.println(Arrays.toString(heap) "for"); //   跟踪数组变化
   swap(heap,0,lastIndex);     //   交换
     System.out.println(Arrays.toString(heap) "swap2"); //   跟踪数组变化
  }

}

private static void reheap(int heap[] , int BrootIndex , int BlastIndex){
  // 索引BrootIndex处的节点是半堆的根

  boolean done = false;
  int tmp = heap[BrootIndex];   //   将半堆的根的值保存到临时变量tmp中
  int leftChildIndex = 2* BrootIndex 1; //半堆的根的左子节点
  // int counter = 0 统计while执行的次数;
  while (!done && (leftChildIndex <= BlastIndex)){   // 通过左子节点索引是否大于BlastIndex来判断g半堆的根节点是否有左子节点
   int largerChildIndex = leftChildIndex;    //
   int rightChildIndex = leftChildIndex 1 ;   // 半堆的根的右子节点

//   判断半堆的根是否有右子节点
   if ((rightChildIndex <= BlastIndex ) && (heap[rightChildIndex] > heap[largerChildIndex]) ){
    largerChildIndex = rightChildIndex;
   }

   if (tmp < heap[largerChildIndex] ){ //   当半堆的根的值小于其子节点中的最大值，则将该子节点移动到半堆的根
    // 将左子节点的值给半堆根节点
    heap[BrootIndex] = heap[largerChildIndex];
    //除了上面要交换子左子节点与根节点的值之外，还要将他们的索引也互换
    BrootIndex = largerChildIndex;
    leftChildIndex = 2*BrootIndex 1;
    // System.out.println("跟踪BrootIndex 在if的值：" BrootIndex); //

   }
   else
    done = true; //   关键的地方：用done来判断是否已经将半堆转化为堆
    // counter ; 统计while执行的次数
  }

  // 将半堆的根的值给新的左子节点
  heap[BrootIndex] = tmp ;

   // System.out.println(Arrays.toString(heap) "while"); //   跟踪数组变化

}
public static void swap( int heap[] , int a , int n){
   int temp;
   temp = heap[a];
   heap[a] = heap[n];
   heap[n] = temp;

}

直接插入排序算法

public class InsertionSort{
public static void main(String[] args){
  int arr[]=new int[]{20,40,90,30,80,70,50};
  System.out.println("原始数组为:");
  for(int x : arr){                         //打印排序前的数组；
   System.out.print(x "＼t");
  }
  int i;
  int j;
  int tmp;
  for(i = 1;i<arr.length;i ){
   tmp = arr[i];
              //这段表示前后两个元素 A与B，B的值放到tmp中，当A值比tmp大的时候，前面的元素即A，往后移动一个位置到B的位置。
   for(j=i-1;j>=0 && arr[j]>tmp; j--){
    arr[j 1] = arr[j];    //相邻两个元素都用j来表示即arr[j]和arr[j 1],所以才有 j=i-1
   }
   arr[j 1] = tmp;
  }

  System.out.println("直接插入排序后的数组：");
  for(int x : arr){
   System.out.print(x "＼t");
  }
}

快速排序算法

核心思想：选中数组中的一个元素作为支点，将比它大的数放到它的右边，比它小的数放到它的左边。那么放完一趟后，这个支点所在的位置就是整个数组排序后的这个元素所在位置。依次递归的将数组用支点分成两段，重复这上面的步骤了，就完成了对整个数组的排序。支点选择为数组第一个元素。

import java.util.*;;

public class QuickSort
{
public static void QuickSort(int[] arr){
System.out.println("跟踪过程：");
    qsort(arr, 0, arr.length-1);

}
private static void qsort(int[] arr, int left, int right){
    if (left < right){
        int pivot=partition(arr, left, right);        //将数组分为两部分
        qsort(arr, left, pivot-1);                   //递归排序左子数组
        qsort(arr, pivot 1, right);                  //递归排序右子数组

    }
}
private static int partition(int[] arr, int left, int right){
    int pivot = arr[left];     //枢轴记录
    while (left<right){
        while (left<right && arr[right]>=pivot) --right;
        arr[left]=arr[right];             //交换比枢轴小的记录到左端

  System.out.println(Arrays.toString(arr));

        while (left<right && arr[left]<=pivot) left;
        arr[right] = arr[left];           //交换比枢轴小的记录到右端

  System.out.println(Arrays.toString(arr));

    }
    //扫描完成，枢轴到位
    arr[left] = pivot;
    //返回的是枢轴的位置
    return left;
}
   public static void main(String[] args)
   {
int Arr[] = new int[]{3,5,0,4,6,1,2,4};
      QuickSort(Arr);

   System.out.println("排序完成后的数组：");
      for (int i=0 ; i < Arr.length ; i ) System.out.print(Arr[i] " ");
      System.out.println();
   }
}

您可能感兴趣的文章：
php实用快速排序算法的实例代码
 javascript常见排序算法实现代码
 javascript排序算法代码解析
 PHP学习之插入排序的实现
 python常见的排序算法有哪些?
java排序算法
 php 插入排序程序代码
 Java数据排序几种算法(堆排序插入排序快速排序)
php基础算法有哪几种
 php 数组排序方法分享(冒泡排序、选择排序)

上一篇：java快速排序算法与冒泡排序算法比较下一篇：非常全面jsp页面的for循环示例程序

[关闭]

Java数据排序几种算法(堆排序插入排序快速排序)

最近更新

浏览排行

Java数据排序几种算法(堆排序 插入排序 快速排序)

最近更新

浏览排行

Java数据排序几种算法(堆排序插入排序快速排序)