歡迎來到Linux教程網
Linux教程網
Linux教程網
Linux教程網
您现在的位置: Linux教程網 >> UnixLinux >  >> Linux編程 >> Linux編程

冒泡、插入、歸並、堆排序、快速排序的Java實現代碼

冒泡、插入、歸並、堆排序、快速排序的Java實現代碼,詳細過程就不表了,看代碼吧

import java.util.Arrays;

public class Sort {

   
    static int swapTimes=0;
    public static void main(String[] args) {
        int[] numbers = { 7, 6, 5, 3, 1, 8, 9, 7, 1, 2 ,5};
        //*** BubbleSort Test ***
        //bubbleSort(numbers);
       
        //*** InsertSort Test ***
        //insertSort(numbers);
       
        //*** MergeSort Test ***
        //mergeSort(numbers);
       
        //*** HeapSort Test ***
        //heapSort(numbers);
       
        //*** QuickSort Test ***
       
        quickSort(numbers);
        System.out.println("result:"+Arrays.toString(numbers));

    }

    /*
    * 插入排序
    */
    public static void insertSort(int[] numbers) {
        System.out.println("InsertSort:"+Arrays.toString(numbers));
        if (numbers == null) {
            System.out.println("Invalid input!");
            return;
        }
        for (int i = 1; i < numbers.length; i++) {
            int temp=numbers[i];
            int j=i-1;
            for (; j >= 0&&numbers[j]>temp; j--) { //這個數大於比較數,就把這個數右移
                numbers[j + 1] = numbers[j];
                System.out.println(Arrays.toString(numbers)+"---temp="+temp);
            }
            numbers[j+1]=temp;    //把比較數賦值到正確位置
            System.out.println(Arrays.toString(numbers));
        }
    }

    /*
    * 冒泡排序
    */
    public static void bubbleSort(int[] numbers) {
        System.out.println("BubbleSort:");
        if (numbers == null) {
            System.out.println("Invalid input!");
            return;
        }
        for (int i = numbers.length - 1; i > 0; i--) {
            for (int j = 0; j < i; j++) {
                if (numbers[j] > numbers[j + 1]) {
                    swap(numbers, j, j + 1);
                }
            }
        }
        System.out.println("result:");
    }
    /*
    * 歸並排序
    */
    public static void mergeSort(int[] numbers){
        if(numbers==null){
            System.out.println("Invalid input!");
            return;
        }
        mergeSort(numbers,0,numbers.length-1);
    }
   
    private static void mergeSort(int[] numbers, int start, int end) {
        if(start>=end){
            return;
        }
        int mid=(start+end)>>1;
        mergeSort(numbers, start, mid);
        mergeSort(numbers, mid+1, end);
        merge(numbers,start,mid,end);
        System.out.println(Arrays.toString(numbers)+"---mid="+mid);
    }
    /*
    * 合並兩個有序數組
    */
    private static void merge(int[] numbers, int start, int mid, int end) {
        int leftLength=mid-start+1;
        int rightLength=end-mid;
        int[] leftNumbers=new int[leftLength];
        int[] rightNumbers=new int[rightLength];
        for (int i = 0; i < leftLength; i++) {//將左邊的元素賦給left數組
            leftNumbers[i]=numbers[start+i];
        }
        for (int j = 0; j < rightLength; j++) {//同理
            rightNumbers[j]=numbers[mid+j+1];
        }
        int pLeft=0;
        int pRight=0;
        for(int index=start;index<=end;index++){//開始merge左右數組
            if(pLeft==leftLength){    //當left數組合並完了,就直接賦值right數組
                numbers[index]=rightNumbers[pRight++];
            }else if(pRight==rightLength){
                numbers[index]=leftNumbers[pLeft++];
            }else{        //左右數組都沒賦值完,就要比較大小
                if(leftNumbers[pLeft]<=rightNumbers[pRight]){
                    numbers[index]=leftNumbers[pLeft++];
                }else{
                    numbers[index]=rightNumbers[pRight++];
                }
            }
        }
    }
    /*
    * 堆排序
    */
    public static void heapSort(int[] numbers){
        if(numbers==null){
            System.out.println("Invalid input!");
            return;
        }
        int[] heap=buildHeap(numbers);    //構造小頂堆
        System.out.println("build Heap:"+Arrays.toString(heap));
        int index=0;
        while(!isHeapEmpty(heap)){
            //注意,這裡不能在前面的index++,因為會先算左括號內的++,造成傳入的index+1
            numbers[index]=popHeapTop(heap,index++); 
           
        }
    }
    //將堆頂元素pop出來
    private static int popHeapTop(int[] heap,int index) {
        int temp=heap[0];
        int end=heap.length-1-index;
        heap[0]=heap[end];        //將最後一個數移至堆頂
        heap[end]=Integer.MAX_VALUE;
        adjustHeap(heap, 0);    //調整堆
        System.out.println("current Heap:"+Arrays.toString(heap));
        return temp;
    }

    private static boolean isHeapEmpty(int[] heap) {
        if(heap[0]==Integer.MAX_VALUE){
            return true;
        }
        return false;
    }
    /*
    * 構造小頂堆
    */
    private static int[] buildHeap(int[] numbers) {
        int[] heap=new int[numbers.length];
        for(int i=0;i<heap.length;i++){
            heap[i]=numbers[i];
        }
        for(int j=(heap.length>>1)-1;j>=0;j--){ //從有孩子的結點開始,從底向上維護堆
            adjustHeap(heap,j);
        }
        return heap;
    }
    /*
    * 維護堆
    */
    private static void adjustHeap(int[] heap, int j) {
        int left=j<<1;
        int right=(j<<1)+1;
        int largest=j;
        if(left<heap.length            //該左孩子下標必須在數組內
                &&heap[left]!=Integer.MAX_VALUE    //該元素必須未被覆蓋
                &&heap[j]<heap[left]){   
            largest=left;
        }
        if(right<heap.length
                &&heap[right]!=Integer.MAX_VALUE
                &&heap[largest]<heap[right]){
            largest=right;
        }
       
        if(largest!=j){
            swap(heap, j, largest);
            adjustHeap(heap, largest);  //繼續往下調整
        }
       
    }
   
    /*
    * 快速排序
    */
    public static void quickSort(int[] numbers){
        if(numbers==null){
            System.out.println("Invalid input!");
            return;
        }
        System.out.println("QuickSort:");
        quickSort(numbers,0,numbers.length-1);
    }
    private static void quickSort(int[] numbers, int start, int end) {
        if(start<end){
            int mid=patition(numbers,start,end);
            quickSort(numbers, start, mid-1);
            quickSort(numbers, mid+1, end);
        }
       
    }
    /*
    * 選一個數,將小於它的數放在左邊,大於它的放在右邊
    */
    private static int patition(int[] numbers, int start, int end) {
        int small=start-1;
        int index=start;
        int temp=numbers[end]; //選擇數組最後一個元素作為比較數
        while(index<=end){
            if(numbers[index]<temp){
                small++;
                if(index!=small){
                    swap(numbers, small, index);
                }
            }
            index++;
        }
        swap(numbers, small+1, end);
        return small+1;
    }
    /*
    * 交換數組的兩個元素
    */
    private static void swap(int[] numbers, int a, int b) {
        int temp = numbers[a];
        numbers[a] = numbers[b];
        numbers[b] = temp;
        System.out.println("current numbers:" +        //記錄交換次數
                ""+Arrays.toString(numbers)+"----swap times:"+(++swapTimes));
    }
   
   

}

Copyright © Linux教程網 All Rights Reserved