7种排序算法

7种排序算法

package com.org.momo.排序算法;
public class Sort { 
 public static void displayData(int[] data) { 
 for (int d : data) { 
   System.out.print(d + " "); 
  }
  System.out.println(""); 
 } 

 /** 
  * 快速排序:时间复杂度O(nlogn)，最坏时间复杂度O(n2)，平均时间复杂度O(nlogn)，算法不具稳定性 
        思想: 
       基于冒泡排序,取第一个作为关键值a,用a与后面开始往前比较,遇到比a小
       的则交换,依然乘此关键值为a,再用a与第一个数开始向后比较,遇到比a大的则
       交换,最终的关键值将依然是最初的第一个元素的值,用此值将此无序序列分成两
       部分,比它小的都在它前面,大的都在后面,然后用递归将前面和后面的分别用快
       速排序进行处理,得到最终的有序序列. 
  */ 
 public static void quickSort(int[] src, int begin, int end) { 
  if (begin < end) { 
   int key = src[begin]; 
   int i = begin; 
   int j = end;  

   while (i < j) { 
    while (i < j && src[j] > key) { 
     j--; 
    } 
    if (i < j) { 
     src[i] = src[j]; 
     i++; 
    } 

    while (i < j && src[i] < key) { 
     i++; 
    } 
    if (i < j) { 
     src[j] = src[i]; 
     j--; 
    }
   } 
   src[i] = key;
   quickSort(src, begin, i - 1); 
   quickSort(src, i + 1, end); 
  } 
 } 

 
/** 
* 冒泡排序算法：时间复杂度O(n2)，算法具有稳定性，堆排序和快速排序算法不具
   有稳定性，即排序后相同元素的顺序会发生变化 
   思想:  
 n个数,将第一个和第二个进行比较,将大的放在第二个位置,再将第二个和第
  三比较,大的放在第三个位置,依次向后比较,比较n-1次,将最大的放在最后(n的位
  置),然后再从第一个开始比较,比较n-2次,这次把最大的放到第n-1个位置,然后再
  来回比较.遵循第i次遍历就从第一个数开始比较n-i次,将最后的值放在第n-i+1
  的位置.    
*/ 
 public static void bubbleSort(int[] src) { 
  if (src.length > 0) { 
   int length = src.length; 
   for (int i = 1; i < length; i++) { 
    for (int j = 0; j < length - i; j++) { 
     if (src[j] > src[j + 1]) { 
      int temp = src[j]; 
      src[j] = src[j + 1]; 
      src[j + 1] = temp; 
     } 
    } 
   } 
  } 
 } 
 
 
 /** 
  * 插入排序:适用于少量数据的排序，时间复杂度O(n2)，是稳定的排序算法，原地排序 
  * 将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序，
  */ 
 public static void insertSort(int[] a) { 
  int length = a.length; 
 
  for (int i = 1; i < length; i++) { 
   int temp = a[i]; 
   int j = i; 
   for (; j > 0 && a[j - 1] > temp; j--) { 
    a[j] = a[j - 1]; 
   } 
   a[j] = temp; 
  } 
 } 

 
 /** 
  * 归并排序算法:稳定排序，非原地排序，空间复杂度O(n)，时间复杂度O(nlogn) 
  * 将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。
  * 然后再把有序子序列合并为整体有序序列。
  */ 
 public static void mergeSort(int a[], int low, int high) { 
  if (low < high) { 
   mergeSort(a, low, (low + high) / 2); 
   mergeSort(a, (low + high) / 2 + 1, high); 
   merge(a, low, (high + low) / 2, high); 
  } 
  } 

 /** 
  * 归并排序辅助方法，合并 
  */ 
 private static void merge(int[] a, int low, int mid, int high) { 
  int[] b = new int[high - low + 1]; 
  int s = low; 
  int t = mid + 1; 
  int k = 0; 
  while (s <= mid && t <= high) { 
   if (a[s] <= a[t]) 
    b[k++] = a[s++]; 
   else 
    b[k++] = a[t++]; 
  } 
  while (s <= mid) 
   b[k++] = a[s++]; 
  while (t <= high) 
   b[k++] = a[t++]; 
  for (int i = 0; i < b.length; i++) { 
   a[low + i] = b[i]; 
  } 
 } 


/** 
  * 选择排序:分为简单选择排序、树形选择排序(锦标赛排序)、堆排序 此算法为简单选择排序 
  * 每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，
  * 直到全部待排序的数据元素排完。 选择排序是不稳定的排序方法。
  */ 
 public static void selectSort(int[] a) { 
  int length = a.length; 
  for (int i = 0; i < length; i++) { 
   int minIndex = i;    
   for (int j = i + 1; j < a.length; j++) { 
    if (a[j] < a[minIndex]) { 
     minIndex = j; 
    } 
   }     

   if (minIndex != i) { 
    int temp = a[minIndex]; 
    a[minIndex] = a[i]; 
    a[i] = temp; 
    } 
  } 
 } 

 
 /** 
  * 希尔排序:先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成（n除以d1）个组。
  * 所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，
  * 取第二个增量d2<d1重复上述的分组和排序，
  * 直至所取的增量dt=1(dt<dt-l<…<d2<d1)，
  * 即所有记录放在同一组中进行直接插入排序为止。
  */ 
 public static void shellSort(int[] a) { 
  int temp; 
  for (int k = a.length / 2; k > 0; k /= 2) { 
   for (int i = k; i < a.length; i++) { 
    for (int j = i; j >= k; j -= k) { 
     if (a[j - k] > a[j]) { 
      temp = a[j - k]; 
      a[j - k] = a[j]; 
      a[j] = temp; 
     } 
    } 
   } 
  } 
 } 


 /** 
  * 堆排序:最坏时间复杂度O(nlog2n)，平均性能接近于最坏性能。由于建初始堆
所需的比较次数多，故堆不适合记录较少的比较 堆排序为原地不稳定排序 
  */ 
 public static void heapSort(int[] array) { 
  for (int i = 1; i < array.length; i++) { 
   makeHeap(array, i); 
  } 
  
  for (int i = array.length - 1; i > 0; i--) { 
   int temp = array[i]; 
   array[i] = array[0]; 
   array[0] = temp; 
   rebuildHeap(array, i); 
  } 
 } 

 /** 
  * 堆排序辅助方法---创建堆 
  */ 
 private static void makeHeap(int[] array, int k) { 
  int current = k; 
  while (current > 0 && array[current] > array[(current - 1)  
- 6 - 2]) { 
   int temp = array[current]; 
   array[current] = array[(current - 1) / 2]; 
   array[(current - 1) / 2] = temp; 
   current = (current - 1) / 2; 
  } 
 } 


 /** 
  * 堆排序辅助方法---堆的根元素已删除，末尾元素已移到根位置，开始重建 
  */ 
 private static void rebuildHeap(int[] array, int size) { 
  int currentIndex = 0; 
  int right = currentIndex * 2 + 2; 
  int left = currentIndex * 2 + 1; 
  int maxIndex = currentIndex; 
  boolean isHeap = false; 
  while (!isHeap) { 
   if (left < size && array[currentIndex] < array[left]) { 
    maxIndex = left; 
   } 
   if (right < size && array[maxIndex] < array[right]) { 
    maxIndex = right; 
   } 
   if (currentIndex == maxIndex) { 
    isHeap = true; 
   } else { 
    int temp = array[currentIndex]; 
    array[currentIndex] = array[maxIndex]; 
    array[maxIndex] = temp; 
    currentIndex = maxIndex; 
    right = currentIndex * 2 + 2; 
    left = currentIndex * 2 + 1; 
   } 
  } 
 } 

 
 public static void main(String[] args) { 
  int data[] = { 2,8,-2,10,0,6,4}; 
  //快速排序
  Sort.displayData(data) ;
  Sort.quickSort(data,0,data.length-1) ;
  Sort.displayData(data) ;

  
  /*  //2.冒泡排序
  Sort.displayData(data); 
  Sort.bubbleSort(data); 
  Sort.displayData(data); */
 }  
 
}