排序算法 Java實現代碼

openkk 12年前發布 | 54K 次閱讀 Java 算法
JAVA下面的堆排序冒泡排序法選擇排序法快速排序法插入排序法折半插入排序法希爾排序法歸并排序法
/*
 

@param <T>
*/
public class Sort<T extends Comparable<T>> {
 //交換索引i和索引j的值
 private void swap(T[] data,int i,int j){

 T tmp;
 tmp = data[i];
 data[i] = data[j];
 data[j] = tmp;

}
//-----堆排序 時間復雜度O(nlogn)-----
 public void heapSort(T[] data) {

 int arrayLength = data.length;
 // 循環建堆
 for (int i = 0; i < arrayLength - 1; i++) {
     // 建堆
     builMaxdHeap(data, arrayLength - 1 - i);
     // 交換堆頂和最后一個元素
     swap(data, 0, arrayLength - 1 - i);
     //System.out.println(java.util.Arrays.toString(data));
 }

}
// 對data數組從0到lastIndex建大頂堆
 private void builMaxdHeap(T[] data, int lastIndex) {

 // 從lastIndex處節點（最后一個節點）的父節點開始
 for (int i = (lastIndex - 1) / 2; i >= 0; i--) {
     // k保存當前正在判斷的節點
     int k = i;
     // 如果當前k節點的子節點存在
     while (k * 2 + 1 <= lastIndex) {
         // k節點的左子節點的索引
         int biggerIndex = 2 * k + 1;
         // 如果biggerIndex小于lastIndex，即biggerIndex + 1
         // 代表的k節點的右子節點存在
         if (biggerIndex < lastIndex) {
             // 如果右子節點的值較大
             if (data[biggerIndex].compareTo(data[biggerIndex + 1]) < 0) {
                 // biggerIndex總是記錄較大子節點的索引
                 biggerIndex++;
             }
         }
         // 如果k節點的值小于其較大子節點的值
         if (data[k].compareTo(data[biggerIndex]) < 0) {
             // 交換它們
             swap(data, k, biggerIndex);
             // 將biggerIndex賦給k，開始while循環的下一次循環，
             // 重新保證k節點的值大于其左、右子節點的值。
             k = biggerIndex;
         } else {
             break;
         }
     }
 }

}
//-----冒泡排序法 時間復雜度O(n^2)-----
 public void bubbleSort(T[] data){

 int i,j;
 for(i=0;i<data.length-1;i++){
     for(j=0;j<data.length-i-1;j++){
         //排序之前[9, -16*, 21, 23, -30, -49, 21*, 30, 30]
         //排序之后[-49, -30, -16*, 9, 21, 21*, 23, 30, 30]
         if(data[j].compareTo(data[j+1]) > 0){
             swap(data,j+1,j);
         }
     }
 }

}
//-----選擇排序法 時間復雜度O(n^2)-----
 public void selectSort(T[] data){

 int i,j;    

 for(i=0;i<data.length-1;i++){
     for(j=i+1;j<data.length;j++){
         //排序之前[9, -16*, 21, 23, -30, -49, 21*, 30, 30]
         //排序之后[-49, -30, -16*, 9, 21, 21*, 23, 30, 30]
         if (data[i].compareTo(data[j]) > 0){
             swap(data,i,j);
         }
     }
 }

}
//-----快速排序法  時間復雜度為O(log2n)-----
 public void quickSort(T[] data){

 subQuickSort(data,0,data.length-1);

}
private void subQuickSort(T[] data,int start,int end){

 if( start < end ){
     //以第一個元素作為分界值
     T base = data[start];
     //i從左邊開始搜索大于分界值元素的索引
     int i = start;
     //j從右邊開始搜索小于分界值元素的索引
     int j = end + 1;
     //排序之前[9, -16*, 21, 23, -30, -49, 21*, 30, 30]
     //排序之后[-30, -16*, -49, 9, 21*, 21, 23, 30, 30]
     while(true){
         //左邊跳過比base小的元素
         while(i < end && data[++i].compareTo(base) <= 0);
         //右邊跳過比base大的元素
         while(j > start && data[--j].compareTo(base) >= 0);

         if(j > i){
             swap(data,i,j);
         }else{
             break;
         }
     }
     //將分界值還原
     swap(data,start,j);

     //遞歸左邊序列
     subQuickSort(data,start,j-1);
     //遞歸右邊序列
     subQuickSort(data,j+1,end);
     // System.out.println(  Arrays.toString(data) );
 }

}
//-----插入排序法 時間復雜度O(n^2)-----
 public void insertSort(T[] data){

 int arrayLength = data.length;

 for(int i=1;i<arrayLength;i++){
     //當整體后移時保證data[i]的值不會丟失
     T tmp = data[i];
     //i索引處的值已經比前面所有值都大,表明已經有序,無需插入
     //i-1處索引之前的數值已經有序,i-1處索引處元素的值也是最大值
     if(data[i].compareTo(data[i-1]) < 0){
         int j = i-1;
         //整體后移一個
         while(j>=0 && data[j].compareTo(tmp) > 0){
             data[j+1] = data[j];
             j--;
         }
     data[j+1] = tmp;
     // System.out.println(  Arrays.toString(data) );
     }
 }

}
//-----折半插入排序法 時間復雜度-----
 public void binaryInsertSort(T[] data) {

 int arrayLength = data.length;

 for (int i = 1; i < arrayLength; i++) {
     if (data[i - 1].compareTo(data[i]) > 0) {
         // 緩存i處的元素值
         T tmp = data[i];

         // 記錄搜索范圍的左邊界
         int low = 0;
         // 記錄搜索范圍的右邊界
         int high = i - 1;

         while (high >= low) {
             // 記錄中間位置
             int mid = (high + low) / 2;
             // 比較中間位置數據和i處數據大小，以縮小搜索范圍

             if (tmp.compareTo(data[mid]) > 0) {
                 low = mid + 1;
             } else {
                 high = mid - 1;
             }
         }
         // 將low~i處數據整體向后移動1位
         for (int j = i; j > low; j--) {
             data[j] = data[j - 1];
         }
         data[low] = tmp;

     }
     //System.out.println(  Arrays.toString(data) );
 }

}
//-----希爾排序法 時間復雜度O(nlogn)O(n^2)具體看h的值-----
 public void shellSort(T[] data){

 int arrayLength = data.length;
 //h保存可變增量

 int h = 1;
 while(h<=arrayLength/3){
     h = h * 3 + 1;
     //System.out.println("h="+h);
 }

 while(h > 0){
     //System.out.println(Arrays.toString( data )+"h="+h);

     for(int i=h;i<arrayLength;i++){
         //當整體后移時,保證data[i]的值不丟失
         T tmp = data[i];
         //i索引處的值已經比前面所有的值大
         //(i-1索引之前的值已經有序的,i-1索引處元素的值就是最大值)
         if(data[i].compareTo(data[i-h]) < 0){
             int j = i-h;
             //整體后移一格
             while(j>=0 && data[j].compareTo(tmp) > 0){
                 data[j+h] = data[j];
                 j-=h;
             }

             //最后將tmp值插入合適的位置
             data[j+h] = tmp;
         }
     }
     h = (h-1)/3;
 }


}
//-----歸并排序法 時間復雜度為O(nlog2n)-----
 public void mergeSort(T[] data){

 subMergeSort(data,0,data.length-1);

}
private void subMergeSort(T[] data,int left,int right){

 if(right > left){
     //找出中間索引
     //System.out.println(  Arrays.toString(data) );
     int center = (left + right)/2;
     //對左邊數組進行遞歸
     subMergeSort(data,left,center);
     //對右邊數組進行遞歸
     subMergeSort(data,center+1,right);
     //合并
     merge(data,left,center,right);
 }

}
@SuppressWarnings("unchecked")
 private void merge(T[] data, int left, int center, int right) {

 Object[] tmpArr = new Object[data.length];
 int mid = center + 1;
 // third記錄中間處索引
 int third = left;
 int tmp = left;

 while (left <= center && mid <= right) {
     // 從兩個數組中取出最小的放入中間數組
     if (data[left].compareTo(data[mid]) <= 0) {
         tmpArr[third++] = data[left++];
     } else {
         tmpArr[third++] = data[mid++];
     }
 }

 // 剩余部分依次放入中間數組
 while (mid <= right) {
     tmpArr[third++] = data[mid++];
 }
 while (left <= center) {
     tmpArr[third++] = data[left++];
 }

 // 將中間數組的內容復制拷回原數組
 // (原left~right范圍內德內容被復制回原數組)
 while (tmp <= right) {
     data[tmp] = (T) tmpArr[tmp++];
 }


}



/*public static void main(String[] args){
    DataWarp[] dataWarp = {
        new DataWarp(9,""),
        new DataWarp(-16,"*"),
        new DataWarp(21,""),
        new DataWarp(23,""),
        new DataWarp(-30,""),
        new DataWarp(-49,""),
        new DataWarp(21,"*"),
        new DataWarp(30,""),
        new DataWarp(56,""),
        new DataWarp(40,""),
        new DataWarp(430,""),
        new DataWarp(-67,""),
        new DataWarp(56,""),
        new DataWarp(-87,""),
        new DataWarp(26,""),
        new DataWarp(92,""),
        new DataWarp(30,"")
    };

    DataWarp[] dataWarp2 = {
            new DataWarp(9,""),
            new DataWarp(-16,"*"),
            new DataWarp(21,""),
            new DataWarp(23,""),
            new DataWarp(-30,""),
            new DataWarp(-49,""),
            new DataWarp(21,"*"),
            new DataWarp(30,""),
            new DataWarp(56,""),
            new DataWarp(40,""),
            new DataWarp(430,""),
            new DataWarp(-67,""),
            new DataWarp(56,""),
            new DataWarp(-87,""),
            new DataWarp(26,""),
            new DataWarp(92,""),
            new DataWarp(30,"")
        };

    System.out.println( "排序之前" + Arrays.toString(dataWarp) );

    Sort<DataWarp> sort = new Sort<DataWarp>();
    sort.mergeSort(dataWarp);
    sort.shellSort(dataWarp2);

    System.out.println( "排序之后" + Arrays.toString(dataWarp) );
    System.out.println( "排序之后" + Arrays.toString(dataWarp2) );

}*/

}</pre>
本文由用戶 openkk 自行上傳分享，僅供網友學習交流。所有權歸原作者，若您的權利被侵害，請聯系管理員。
轉載本站原創文章，請注明出處，并保留原始鏈接、圖片水印。
本站是一個以用戶分享為主的開源技術平臺，歡迎各類分享！
本文地址：http://www.baiduhome.net/lib/view/open1345733835985.html
Java 算法
排序算法 Java實現代碼

相關經驗

相關資訊

相關文檔

目錄
