如何利用java實作排序演算法

不穩定排序

選擇排序： 
  經過第一輪比較得到的最小的記錄，與第一個記錄的位置交換， 然後對不包括第一個記錄以外的記錄進行第二輪比較，得到的最小記錄與第二個記錄交換 
  時間複雜度：O(n^2) 
  空間複雜度：O(1)

    public static void selectSort(int[] arr){        
    if (arr == null || arr.length == 0)            
    return;        
    int len = arr.length;        
    for (int i = 0; i < len; i++) {            
        int min = arr[i];            
        int index = i;            
        for (int j = i+1; j < len; j++) {                
        if (arr[j] < min) {                    
            min = arr[j];
          index = j;
          }
       }
       arr[index] = arr[i];
       arr[i] = min;
     }
    }

快速排序： 
 對於一組給定的記錄，每一趟排序後，將原先序列分成兩部分，其中前一部分的所有記錄均比後一部分的所有記錄小，然後再依序對前後兩部分記錄進行快速排序 
 時間複雜度：O(nlogn)  最壞：O(n^2) 
 空間複雜度：O(nlogn)

    public int Partition(int[] a,int start,int end){        int std = a[start];
        while (start < end){
             while(start < end && a[end] >= std)                 
             end--;
             a[start] = a[end];
             while(start < end && a[start] <= std)                 
             start++;
             a[end] = a[start];
        }
        a[start] = std;
        return start;
    }
    public void quickSort(int[] a,int start,int end){        
            if(start >= end){
            return;
        }
        int index = Partition(a,start,end);
        quickSort(a,start,index-1);
        quickSort(a,index+1,end);
    }

堆排序：完全二元樹 
 將二元樹調整為大頂堆，然後將堆的最後一個元素與堆頂元素（即二元樹的根結點）進行交換後，堆的最後一個元素即為最大記錄；接著將前n-1個元素調整為大頂堆，再將堆頂元素與當前堆的最後一個元素進行交換後得到次大的記錄重複該過程直到調整的堆中只剩一個元素為止，該元素即為最小記錄，此時可得到一個有序序列 
 時間複雜度：O(nlogn) 
 空間複雜度：O(1)

   public void HeapSort(int[] a){        
            for (int i = a.length/2 - 1; i >= 0 ; i--) {
            HeapAdjust(a,i,a.length-1);
        }        
        for (int i = a.length - 1; i >= 0; i--) {
            swap(a,0,i);
            HeapAdjust(a,0,i-1);
        }
    }    
    private void swap(int[] a, int i, int j) {        
            int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }    
    public void HeapAdjust(int[] arr,int s,int len){        
            int tmp = arr[s];        
            for (int i = s * 2 + 1; i < len ; i = i * 2 + 1) {            
                    if (i < len && arr[i] < arr[i+1]){
                i++;
            }            
            if (tmp > arr[i])                
            break;
            arr[s] = arr[i];
            s = i; //s记录被替换的子结点的索引
        }
        arr[s] = tmp;
    }

穩定排序

直接插入排序： 
 第一個記錄可以看作是自成一個有序序列，其餘記錄稱為無序序列。接著從第二個記錄開始，按照記錄的大小依序將目前處理的記錄插入之前的有序序列中，直到最後一個記錄插入到有序序列中為止 
 時間複雜度：O(n^2)
 空間複雜度：O(1)

    public static void insertSort(int[] arr){        
            if (arr == null || arr.length == 0)            
            return;        
            int len = arr.length;        
            for (int i = 1; i < len; i++) {            
            int curr = arr[i];            
            int j = i;            
            if (arr[j-1] > curr){                
                while (j > 0 && arr[j-1]> curr){
                arr[j] = arr[j-1];
                j--;
                }
            }
          arr[j] = curr;
        }
    }

冒泡排序：
從第一個記錄開始依序對相鄰的兩個記錄進行比較，當前面的記錄大於後面的記錄時，交換位置，進行一輪比較和換位後，n個記錄中最大的記錄將位於第n位，然後對前面的n-1個記錄進行第二輪比較，重複該過程直到進行比較的記錄只剩下一個為止
 時間複雜度：O(n^2)
 空間複雜度：O(1)

    public void bubbleSort(int[] arr){        
            boolean flag = true;        
            for (int i = 0; i < arr.length && flag; i++) {
            flag = false;            
            for (int j = 0; j < arr.length - i - 1; j++) {                
                    if (arr[j] > arr[j+1]){
                flag = true;
                swap(arr,j,j+1);
                }
            }
        }
    }    
    private void swap(int[] arr, int j, int i) {        
            int tmp = arr[j];
        arr[j] = arr[i];
        arr[i] = tmp;
    }

歸併排序：歸：遞歸，並：分開的資料有序合併
將每兩個相鄰的長度為1的子序列進行歸併，得到n/2個長度為2或1的有序子數列，再將兩兩歸併，反覆執行此過程，直到得到一個有序序列
 時間複雜度：O(nlogn)
 空間複雜度：O(n)

   public static void mergeSort(int[] arr,int begin,int end){        
              int mid = (begin+end)/2;        
              if (begin < end){
            mergeSort(arr,begin,mid);
            mergeSort(arr,mid+1,end);
            Merge(arr,begin,end,mid);
        }
    }    
    public static void Merge(int[] arr,int begin,int end,int mid){        
            int[] temp = new int[end-begin+1];        
            int i = begin;        
            int j = mid+1;        
            int k=0;        
            while (i <= mid && j <= end){            
            if (arr[i] < arr[j]){
                temp[k++] = arr[i++];
            }else{
                temp[k++] = arr[j++];
            }
        }        
        while (i <= mid){
            temp[k++] = arr[i++];
        }        
        while (j <= end){
            temp[k++] = arr[j++];
        }        
        for (int m = 0;m < temp.length;m++){
            arr[m+begin] = temp[m];
        }
    }

以上是如何利用java實作排序演算法的詳細內容。更多資訊請關注PHP中文網其他相關文章！