疯狂java


您现在的位置: 疯狂软件 >> 新闻资讯 >> 正文

八大排序算法-java实现


 

   

  public class Sort {

  //1.直接插入排序

  public void insertSort(int[] A)

  {

  int n = A.length;

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

  {

  int x = A[i];

  int j = i - 1 ;

  while(j >= 0 && A[j] >= x)

  {

  A[j+1] = A[j];

  j--;

  }

  A[j+1] = x ;

  }

  }

  //2.希尔排序

  public void shellSort(int[] A)

  {

  int n = A.length ;

  int d = n/2 ;

  while(d >= 1)

  {

  for(int x = 0 ; x < d ; x++)

  {

  for(int i = x+d ; i < n ; i += d )

  {

  int temp = A[i];

  int j = i - d ;

  while(j >= 0 && A[j] > temp)

  {

  A[j+d] = A[j];

  j = j - d ;

  }

  A[j+d] = temp ;

  }

  }

  d = d >> 1 ;

  }

  }

  //3.冒泡排序

  public void bubbleSort(int[] A)

  {

  int n = A.length ;

  for(int j = n - 1 ; j > 0 ; j--)

  {

  boolean isBalance = true ;

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

  {

  if(A[i] > A[i+1])

  {

  int temp = A[i] ;

  A[i]= A[i+1] ;

  A[i+1] = temp ;

  isBalance = false ;

  }

  }

  if(isBalance)

  break ;

  }

  }

  //4.快速排序

  public int partion(int[] data , int start , int end)

  {

  int random = (int)(Math.random() * (end - start)) + start ;

  exechange(data, random, end);

  int x = data[end] ;

  int index = start - 1 ;

  for(int j = start ; j < end ; j++)

  {

  if(data[j] < x)

  {

  index++ ;

  exechange(data, index, j);

  }

  }

  exechange(data, index+1, end);

  return index + 1 ;

  }

  public void exechange(int[] data , int i , int j )

  {

  int temp = data[i];

  data[i] = data[j] ;

  data[j] = temp ;

  }

  public void quickSort(int[] data , int start , int end)

  {

  if(start < end)

  {

  int r = partion(data, start, end);

  quickSort(data, start, r - 1 );

  quickSort(data, r + 1, end);

  }

  }

  //5简单选择排序

  public void selectSort(int[] A)

  {

  int length = A.length ;

  for(int i = 0 ; i < length - 1 ; i ++){

  int k = i ;

  for(int j = i + 1 ; j < length ; j ++ ){

  if(A[j] < A[k]) k = j ;

  }

  if(k != i) {

  int temp = A[i] ;

  A[i] = A[k];

  A[k] = temp ;

  }

  }

  }

  //6.堆排序

  public void max_heapfiy(int[] A , int i , int heap_size){

  int largest ;

  int left = 2 * i ;

  int right = 2 * i + 1 ;

  if(left <= heap_size - 1 && A[left] > A[i])

  largest = left ;

  else largest = i ;

  if(right <= heap_size - 1 && A[right] > A[largest])

  largest = right ;

  if(largest != i ){

  int temp = A[i] ;

  A[i] = A[largest] ;

  A[largest] = temp ;

  max_heapfiy(A,largest,heap_size);

  }

  }

  public void build_max_heap(int[] A){

  int heap_size = A.length ;

  for(int i = A.length / 2 ; i >= 0 ; i--)

  max_heapfiy(A,i,heap_size);

  }

  public void heap_sort(int[] A){

  int heap_size = A.length ;

  build_max_heap(A);

  for(int i = A.length - 1 ; i >= 1 ; i--){

  int temp = A[i] ;

  A[i] = A[0] ;

  A[0] = temp ;

  heap_size-- ;

  max_heapfiy(A,0,heap_size);

  }

  }

  //7.归并排序

  public void merge(int[] A , int first , int mid , int last )

  {

  int[] tempArray = new int[A.length];

  int indexA = first ;

  int indexB = mid + 1 ;

  int tempIndex = first ;

  while(indexA <= mid && indexB <= last)

  {

  if(A[indexA] <= A[indexB])

  tempArray[tempIndex++] = A[indexA++];

  else

  tempArray[tempIndex++] = A[indexB++];

  }

  while(indexA <= mid) tempArray[tempIndex++] = A[indexA++];

  while(indexB <= last) tempArray[tempIndex++] = A[indexB++];

  for(int i = first ; i <= last ; i++)

  {

  A[i] = tempArray[i];

  }

  }

  public void mergerSort(int[] A , int first , int last)

  {

  if(first < last)

  {

  int mid = (first + last)/2 ;

  mergerSort(A, first, mid);

  mergerSort(A, mid + 1, last);

  merge(A, first, mid, last);

  }

  }

  //8基数排序

  public void radixSort(int[] A , int maxRadix)

  {

  int m = 1 ;

  int times = 1 ;

  int[][] temp = new int[10][A.length];

  int[] indexArray = new int[10];

  while(times <= maxRadix)

  {

  for(int i = 0 ; i < A.length ; i++)

  {

  if(A[i] < m)

  temp[0][indexArray[0]++] = A[i];

  else

  {

  int les = (A[i]/m)%10 ;

  temp[les][indexArray[les]++] = A[i];

  }

  }

  m = m * 10 ;

  collectionElement(A,temp,indexArray);

  times++;

  }

  }

  public void collectionElement(int[] A , int[][] temp , int[] indexArray)

  {

  int index = 0 ;

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

  {

  for(int j = 0 ; j < indexArray[i] ; j++)

  {

  A[index++] = temp[i][j];

  }

  indexArray[i] = 0 ;

  }

  }

  }