Java實現(xiàn)常見的排序算法的示例代碼

更新時間：2022年10月17日 11:46:58 作者：時間郵遞員

這篇文章主要為大家詳細(xì)介紹了Java實現(xiàn)常見的排序算法（選擇排序、插入排序、希爾排序等）的相關(guān)資料，文中的示例代碼講解詳細(xì)，感興趣的可以了解一下

一、優(yōu)化后的冒泡排序

package com.yzh.sort;
/*
冒泡排序
 */
@SuppressWarnings({"all"})
public class BubbleSort {

    public static void BubbleSort(int[]a){
        for (int i = 0; i <a.length-1 ; i++) {
            boolean flag=true;
            for (int j = 0; j <a.length-i-1 ; j++) {
                if(a[j]>a[j+1]){
                    int temp=a[j];
                    a[j]=a[j+1];
                    a[j+1]=temp;
                    flag=false;
                }
            }
            if(flag) break;
        }
    }

}

二、選擇排序

package com.yzh.sort;
@SuppressWarnings({"all"})
public class SelectSort {

    public static void SelectSort(int[]a) {
        for (int i = 0; i < a.length - 1; i++) {
            int index = i;//標(biāo)記為待比較的數(shù)
            for (int j = i + 1; j < a.length; j++) { //然后從后面遍歷與第一個數(shù)比較
                if (a[j] < a[index]) {  //如果小,就交換最小值
                    index = j;//保存最小元素的下標(biāo)
                }
            }
            //找到最小值后，將最小的值放到第一的位置，進(jìn)行下一遍循環(huán)
            int temp = a[index];
            a[index] = a[i];
            a[i] = temp;
        }
    }
}

三、插入排序

package com.yzh.sort;
@SuppressWarnings({"all"})
/*
插入排序
 */
public class InsertSort {

    public static void InsertSort(int[]a){
        for (int i = 0; i < a.length; i++) {
            //定義待插入的數(shù)
            int insertValue=a[i];
            //找到待插入數(shù)的前一個數(shù)的下標(biāo)
            int insertIndex=i-1;
            while (insertIndex>=0 && insertValue <a[insertIndex]) {//拿a[i]前面的數(shù)比較
                a[insertIndex+1]=a[insertIndex];
                insertIndex--;
            }
            a[insertIndex+1]=insertValue;
        }
    }
}

四、希爾排序

package com.yzh.sort;

/*
希爾排序
 */
@SuppressWarnings({"all"})
public class ShellSort {

    public static void ShellSort(int[] a){
        for (int gap=a.length / 2; gap > 0; gap = gap / 2) {
            //將整個數(shù)組分為若干個子數(shù)組
            for (int i = gap; i < a.length; i++) {
                //遍歷各組的元素
                for (int j = i - gap; j>=0; j=j-gap) {
                    //交換元素
                    if (a[j]>a[j+gap]) {
                        int temp=a[j];
                        a[j]=a[j+gap];
                        a[j+gap]=temp;
                    }
                }
            }
        }
    }
}

五、快速排序

package com.yzh.sort;
@SuppressWarnings({"all"})
/*
隨機(jī)化快速排序
 */
public class QuickSort {

    public static void QuickSort(int[] arr,int low,int high){
        int i,j,temp,t;
        if(low>=high){
            return;
        }
        i=low;
        j=high;
        //temp就是基準(zhǔn)位
        temp = arr[low];
        while (i<j) {
            //先看右邊，依次往左遞減
            while (temp<=arr[j]&&i<j) {
                j--;
            }
            //再看左邊，依次往右遞增
            while (temp>=arr[i]&&i<j) {
                i++;
            }
            //如果滿足條件則交換
            if (i<j) {
                t = arr[j];
                arr[j] = arr[i];
                arr[i] = t;
            }
        }
        //最后將基準(zhǔn)為與i和j相等位置的數(shù)字交換
        arr[low] = arr[i];
        arr[i] = temp;
        //遞歸調(diào)用左半數(shù)組
        QuickSort(arr, low, j-1);
        //遞歸調(diào)用右半數(shù)組
        QuickSort(arr, j+1, high);
    }
}

六、隨機(jī)化快速排序

package com.yzh.sort;

import java.util.Random;
import java.util.Scanner;

@SuppressWarnings({"all"})
public class RandQuickSort {

    public static void randsort(int[] arr, int left, int right) {
        if(left>=right)
            return;
        Random random = new Random();
        int randIndex = random.nextInt(right-left)+left;  //選取隨機(jī)主元
        //把隨機(jī)主元放到數(shù)組尾部
        int temp = arr[randIndex];
        arr[randIndex] = arr[right];
        arr[right] = temp;
        //數(shù)組中元素與主元比較
        int i = left-1;//注意
        for(int j = left;j<=right;j++) {
            if(arr[j]<arr[right]) {
                i++;
                int temp1 = arr[i];
                arr[i] = arr[j];
                arr[j] = temp1;
            }
        }
        //最后把主元放到適當(dāng)位置
        int temp2 = arr[i+1];
        arr[i+1] = arr[right];
        arr[right] = temp2;

        randsort(arr,left,i);
        randsort(arr,i+2,right);
    }
}

七、歸并排序

package com.yzh.sort;

@SuppressWarnings({"all"})
/*
歸并排序
 */
public class MergeSort {

    private static void mergesort(int[] a, int left, int right, int[] temp) {
        //分解
        if (left<right) {
            int mid=((right-left)>>1)+left;
            //向左遞歸進(jìn)行分解
            mergesort(a, left, mid, temp);
            //向右遞歸進(jìn)行分解
            mergesort(a, mid+1, right, temp);
            //每分解一次便合并一次
            merge(a,left,right,mid,temp);
        }
    }

    private static void merge(int[] a, int left, int right, int mid, int[] temp) {
        int i=left; //初始i，左邊有序序列的初始索引
        int j=mid+1;//初始化j，右邊有序序列的初始索引（右邊有序序列的初始位置即中間位置的后一位置）
        int t=0;//指向temp數(shù)組的當(dāng)前索引，初始為0

        //先把左右兩邊的數(shù)據(jù)（已經(jīng)有序）按規(guī)則填充到temp數(shù)組
        //直到左右兩邊的有序序列，有一邊處理完成為止
        while (i<=mid && j<=right) {
            //如果左邊有序序列的當(dāng)前元素小于或等于右邊的有序序列的當(dāng)前元素，就將左邊的元素填充到temp數(shù)組中
            if (a[i]<=a[j]) {
                temp[t++]=a[i++];
            }else {
                //反之，將右邊有序序列的當(dāng)前元素填充到temp數(shù)組中
                temp[t++]=a[j++];
            }
        }
        //把剩余數(shù)據(jù)的一邊的元素填充到temp中
        while (i<=mid) {
            //此時說明左邊序列還有剩余元素
            //全部填充到temp數(shù)組
            temp[t++]=a[i++];
        }
        while (j<=right) {
            //此時說明左邊序列還有剩余元素
            //全部填充到temp數(shù)組
            temp[t++]=a[j++];
        }
        //將temp數(shù)組的元素復(fù)制到原數(shù)組
        t=0;
        int tempLeft=left;
        while (tempLeft<=right) {
            a[tempLeft++]=temp[t++];
        }
    }
}

八、可處理負(fù)數(shù)的基數(shù)排序

package com.yzh.sort;

public class RadixSort{

    public static void main(String[] args) {
        int[]a={-2,-1,-6,3,5,1,2,88,-1,99,100,21};
        RadixSort(a);
        for (int x : a) {
            System.out.print(x+" ");
        }
        System.out.println();
    }


    public static int[] RadixSort(int[] arr){
        //最大值，用來計算需要找多少次
        int max = Integer.MIN_VALUE;
        //用來判斷是否是負(fù)數(shù)
        int min = Integer.MAX_VALUE;
        //從該數(shù)組中找到最大\最小值
        for (int i = 0; i < arr.length; i++) {
            max = Math.max(max, arr[i]);
            min = Math.min(min, arr[i]);
        }
        //如果最小值小于0，那么把每個數(shù)都減去最小值，這樣可以保證最小的數(shù)是0
        if (min<0) {
            for (int i = 0; i < arr.length; i++) {
                arr[i] -= min;
            }
            //max也要處理
            max -= min;
        }
        //計算最大值有幾位數(shù)
        int maxLength = (max+"").length();
        //定義十個桶，每個桶就是一個一維數(shù)組
        int[][] bucket = new int[10][arr.length];
        //記錄每個桶中實際存放了多少個數(shù)據(jù)
        int[] bucketElementCount = new int[10];
        //根據(jù)最大長度數(shù)，決定比較次數(shù)
        for (int i = 0 ,n = 1 ; i < maxLength ; i++,n*=10) {
            //每一個數(shù)字分別計算余數(shù)
            for (int j = 0; j < arr.length ; j++) {
                int value = arr[j]/n % 10;
                //把當(dāng)前遍歷的數(shù)放到指定的位置
                bucket[value][bucketElementCount[value]] = arr[j];
                //該位置加一，為下一個值進(jìn)來做準(zhǔn)備
                bucketElementCount[value]++;
            }
            //記錄arr的位置
            int index = 0;
            //遍歷取出第n次排序的值，等于0的不需要取
            for (int j = 0; j < bucketElementCount.length ; j++) {
                if (bucketElementCount[j]!=0){
                    //遍歷取出數(shù)據(jù)并放到原來的arr中
                    for (int k = 0; k < bucketElementCount[j]; k++) {
                        arr[index] = bucket[j][k];
                        index++;
                    }
                }
                //把數(shù)量置為零，因為還有n輪
                bucketElementCount[j] = 0;
            }
        }
        //把排序好的arr重新加上減去的值
        if (min<0){
            for (int i = 0; i < arr.length ; i++) {
                arr[i] += min;
            }
        }
        return arr;
    }

}

以上就是Java實現(xiàn)常見的排序算法的示例代碼的詳細(xì)內(nèi)容，更多關(guān)于Java排序算法的資料請關(guān)注腳本之家其它相關(guān)文章！

您可能感興趣的文章: