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    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         while (left=pivot) --right;
        arr[left]=arr[right];             //交换比枢轴小的记录到左端
  
  System.out.println(Arrays.toString(arr));
  
        while (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();
   }
}