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

幾大排序算法的Java實現

很多的面試題都問到了排序算法,中間的算法和思想比較重要,這邊我選擇了5種常用排序算法並用Java進行了實現。自己寫一個模板已防以後面試用到。大家可以看過算法之後,自己去實現一下。

1.冒泡排序:大數向下沉,小數向上浮。

package TestProject;
/**
 * 冒泡排序
 * @author xuhui
 *
 */
public class SortAll {
    public static void main(String[] args){
        int[] a = {0,8,1,2,8,6,1};
        bubbleSort(a);
        for(int i=0;i<a.length;i++){
            System.out.print(a[i]+" ");
        }
    }
    public static void bubbleSort(int[] a){
        int len = a.length;//數組長度
        for(int i=0;i<len;i++){//每趟把最大數下沉到數組最後面
            for(int j=0;j<len-1;j++){
                if(a[j+1]<a[j]){//如果數組後面的數比前面的小,則往後換下沉
                    int temp = a[j];
                    a[j] = a[j+1];
                    a[j+1] = temp;
                }
            }
        }
    }
}

1.1冒泡排序的優化一:用一個變量記錄每趟大數下沉的位置,標量值說明該變量後面數組已排序完成。

package TestProject;
/**
 * 冒泡排序優化
 * @author xuhui
 *
 */
public class SortAll {
    public static void main(String[] args){
        int[] a = {0,8,1,2,8,6,1};
        bubbleSort_1(a);
        for(int i=0;i<a.length;i++){
            System.out.print(a[i]+" ");
        }
    }
    public static void bubbleSort_1(int[] a){
        int len = a.length;//數組長度
        int i = len-1;
        while(i>0){
            int pos = 0;
            for(int j=0;j<i;j++){//只需排序a[0,1,...,pos]
                if(a[j]>a[j+1]){
                    int temp = a[j];
                    a[j] = a[j+1];
                    a[j+1] = temp;
                    pos = j;
                }
            }
            i = pos;//下一攤,a[pos+1,...,len-1]已排序好
        }
    }
}

1.2冒泡排序的優化二:將大數向下沉同時小數向下浮。

package TestProject;
/**
 * 冒泡排序優化
 * @author xuhui
 *
 */
public class SortAll {
    public static void main(String[] args){
        int[] a = {0,8,1,2,8,6,1};
        bubbleSort_2(a);
        for(int i=0;i<a.length;i++){
            System.out.print(a[i]+" ");
        }
    }
    public static void bubbleSort_2(int[] a){
        int len = a.length;//數組長度
        int hight = len-1;
        int low = 0;
        while(low<hight){
            for(int i=low;i<hight;i++){//大數下沉
                if(a[i]>a[i+1]){
                    int temp = a[i];
                    a[i] = a[i+1];
                    a[i+1] = temp;
                }
            }
            hight--;//每趟數組大數下沉到無序數組最後面,後面大數已排序好(這地方可以優化,可以每趟給一個變量記錄其最後交換的位置,說明變量後面的數組已排序好)
            for(int i=hight;i>low;i--){//小數上浮
                if(a[i]<a[i-1]){
                    int temp = a[i];
                    a[i] = a[i-1];
                    a[i-1] = temp;
                }
            }
            low++;//每趟數組小數上浮到無序數組最前面,前面的小數已排序好
        }
    }
}

2.插入排序:大致思想就是兩個數組,一個有序數組,一個無序數組,將無序數組插入有序數列中。其中將a[0]看成有序數組,a[1,...,len-1]看成無序數組。

package TestProject;
/**
 * 插入排序
 * @author xuhui
 *
 */
public class SortAll {
    public static void main(String[] args){
        int[] a = {0,8,1,2,8,6,1};
        insertSort(a);
        for(int i=0;i<a.length;i++){
            System.out.print(a[i]+" ");
        }
    }
    public static void insertSort(int[] a){
        int len = a.length;//數組長度
        for(int i=1;i<len;i++){
            int temp = a[i];
            int j;
            for(j=i-1;j>=0;j--){//將a[i]插入a[0,..,i]序列中
                if(a[j]<=temp){
                    break;
                }else{
                    a[j+1]=a[j];//插入有序數組時(從小到大),如果插入的數比當前數小,則向前插入,此時的數向後挪一位
                }        
            }
            a[j+1] = temp;//此時插入數在有序數列的位置
        }
    }
}

3.選擇排序:每趟選擇出最小的數放在數組最前面。

package TestProject;
/**
 * 選擇排序
 * @author xuhui
 *
 */
public class SortAll {
    public static void main(String[] args){
        int[] a = {0,8,1,2,8,6,1};
        selectSort(a);
        for(int i=0;i<a.length;i++){
            System.out.print(a[i]+" ");
        }
    }
    public static void selectSort(int[] a){
        int len = a.length;
        for(int i=0;i<len;i++){
            int min = selectMin(a,i,len-1);
            int temp = a[min];//將無序數列的最小值換到前面
            a[min] = a[i];
            a[i] = temp;
        }
    }
    public static int selectMin(int[] a,int s,int t){
        int count = s;
        for(int i=s;i<=t;i++){
            if(a[i]<a[count])count=i;
        }
        return count;
    }
}

3.1選擇排序優化一:二元選擇排序,每次將無序數列的最大值換到後面,將最小值換到前面。

package TestProject;
/**
 * 選擇排序
 * @author xuhui
 *
 */
public class SortAll {
    public static void main(String[] args){
        int[] a = {8,1,0,2,8,6,1};
        selectSort(a);
        for(int i=0;i<a.length;i++){
            System.out.print(a[i]+" ");
        }
    }
    public static void selectSort(int[] a){
        int len = a.length;
        int l = 0;
        int h = len-1;
        while(l<h){
            int[] count = selectMinMax(a,l,h);
            int temp = a[count[0]];//將無序數列的最小值換到前面
            a[count[0]] = a[l];
            a[l] = temp;          
            if(count[1]==l){  //count[0]為無序數列的最小值位置,count[1]為無序數列的最大值位置,如果當count[0]挪到l位置時(a[1,..,l-1]為有序序列),可能會出現l位置就是最大值位置
                temp = a[count[0]];
                a[count[0]] = a[h];
                a[h] = temp;
            }else{
                temp = a[count[1]];
                a[count[1]] = a[h];
                a[h] = temp;
            }
            
            l++;
            h--;
        }
    }
    public static int[] selectMinMax(int[] a,int s,int t){
        int[] count = {s,t};//count[0]-min,count[1]-max
        for(int i=s;i<=t;i++){
            if(a[i]<a[count[0]]){
                count[0]=i;
            }
            if(a[i]>a[count[1]]){
                count[1]=i;
            }
        }
        return count;
    }
}

 4.堆排序:首先建立一個最大堆,堆頂元素為最大值,每次將堆頂元素換到數組後面,這樣一次循環就可以得到從小到大的有序數組。

package TestProject;
/**
 * 堆排序
 * @author xuhui
 *
 */
public class SortAll {
    public static void main(String[] args){
        int[] a = {0,8,1,2,8,6,1};
        int len = a.length;
        for(int i=(len/2-1);i>=0;i--){//建立一個最大堆
            maxHeapFixDown(a,i,len);//從有葉子的父節點建立最大堆,從下到上
        }
        for(int i=a.length-1;i>=0;i--){//堆頂元素為堆的最大值,每次把堆頂換到數組後面,一次次循環就使數組變成從小到大排序
            int temp = a[i];
            a[i] = a[0];
            a[0] = temp;
            maxHeapFixDown(a,0,i);
        }
        for(int i=0;i<a.length;i++){
            System.out.print(a[i]+" ");
        }
    }/**
     * 因為我們要從小到大排序,所以需要建立一個最大堆,從i開始到n-1,此時應滿足a[i]>a[i+1,...,n-1]
     */
    public static void maxHeapFixDown(int[] a,int i,int n){
        int temp = a[i];
        int j = 2*i+1;
        while(j<n){
            if((j+1)<n&&a[j]<a[j+1])j++;
            if(a[j]<temp)break;
            a[i] = a[j];
            i=j;
            j=2*j+1;
        }
        a[i] = temp;
    }
}

 5.快速排序:選第一個元素作為基准元素,把小於這個基准元素的值放到前面,把大於這個基准元素的值放到後面。每次這個基准元素的最後位置也就是有序數列最後的位置,

a[0,...,m-1] <a[m]<a[m+1,..,n],再從前面的a[0,...,m-1]進行上面的重復操作即可。

 
package TestProject;
/**
 * 快排
 * @author xuhui
 *
 */
public class SortAll {
    public static void main(String[] args){
        int[] a = {0,8,1,2,8,6,1};
        int len = a.length;
        quickSort(a,0,len-1);
        for(int i=0;i<a.length;i++){
            System.out.print(a[i]+" ");
        }
    } 
    public static void quickSort(int[] a,int s,int t){
        if(s<t){
            int x = a[s];
            int i = s;
            int j = t;
            while(i<j){
                while(i<j&&a[j]>=x)j--;
                int temp = a[i];
                a[i] = a[j];
                a[j] = temp;
                while(i<j&&a[i]<=x)i++;
                temp = a[j];
                a[j] = a[i];
                a[i] = temp;
            }
            quickSort(a,s,i-1);
            quickSort(a,i+1,t);
        }
    }
}

這邊都是自己參照算法描述實現的Java代碼,其中堆排序理解起來會比較困難,裡面可能有一些邊緣條件沒有考慮到,如果有錯請大家積極糾正。

Copyright © Linux教程網 All Rights Reserved