Java十大排序算法怎么實現(xiàn)

本篇內(nèi)容介紹了“Java十大排序算法怎么實現(xiàn)”的有關(guān)知識，在實際案例的操作過程中，不少人都會遇到這樣的困境，接下來就讓小編帶領(lǐng)大家學(xué)習(xí)一下如何處理這些情況吧！希望大家仔細(xì)閱讀，能夠?qū)W有所成！

排序算法的穩(wěn)定性：

        假定在待排序的記錄序列中，存在多個具有相同的關(guān)鍵字的記錄，如果排序以后，保證這些記錄的相對次序保持不變，即在原序列中，a[i]=a[j]，且 a[i] 在 a[j] 之前，排序后保證 a[i] 仍在 a[j] 之前，則稱這種排序算法是穩(wěn)定的；否則稱為不穩(wěn)定的。

一.選擇排序

每次從待排序的元素中選擇最小的元素，依次和第1、2、3...位置的元素進(jìn)行交換。這樣在數(shù)組前面的部分形成有序區(qū)域。每進(jìn)行一次交換，有序區(qū)域長度加一。

public static void selectionSort(int[] arr){
    //細(xì)節(jié)一：這里可以是arr.length也可以是arr.length-1
    for (int i = 0; i < arr.length-1 ; i++) {
        int mini = i;
        for (int j = i+1; j < arr.length; j++) {
            //切換條件，決定升序還是降序
            if(arr[mini]>arr[j]) mini =j;
        }
        swap(arr,mini,i);
    }
}

二.冒泡排序

        依次比較相鄰的兩個數(shù)，如果順序錯誤就把他們交換過來，這樣的話，每一輪比較下來都可以把最大的數(shù)放到它應(yīng)該在的位置。（就像是把最大的氣泡冒到最上層一樣）

         這里解釋一下順序錯誤的含義。我們按照按升序排序，后面的值應(yīng)該大于等于前面的值，如果不滿足的話，就交換。

public static void bubbleSort(int[] arr){
    for (int i = 0; i < arr.length-1; i++) {
        //記錄本次有沒有進(jìn)行交換的操作
        boolean flag = false;
        //保存在頭就動頭，保存在尾就動尾
        for(int j =0 ; j < arr.length-1-i ; j++){
            //升序降序選擇地
            if(arr[j] > arr[j+1])
            {
                swap(arr,j,j+1);
                flag = true;
            }
        }
        //如果本次沒有進(jìn)行交換操作，表示數(shù)據(jù)已經(jīng)有序
        if(!flag){break;} //程序結(jié)束
    }
}

三.插入排序

        插入排序其實可以理解為我們玩撲克時摸牌的過程，我們在摸牌的時候手里的牌總是有序的，每摸一張牌，就把這張牌插到它應(yīng)該在的位置。等所有的牌都摸完了以后，全部的牌就都有序了。

 思考：數(shù)組前面形成了有序區(qū)域，那我查找當(dāng)前數(shù)字應(yīng)該插入位置的時候，用二分進(jìn)行，是不是就可以把插入排序的復(fù)雜度優(yōu)化到O(nlogn)了呀？

        二分倒是可以log的復(fù)雜度找到位置。 關(guān)鍵是如果用數(shù)組存儲的話，插入的時候數(shù)據(jù)后移還是O(n)的復(fù)雜度。如果用鏈表的話，找到位置插入是O(1)的了，但是鏈表也沒辦法二分呀。

public static void insertSort(int[] arr){
        //從第二個數(shù)開始，把每個數(shù)依次插入到指定的位置
        for(int i = 1 ; i < arr.length ; i++)
        {
            int key = arr[i];
            int j = i-1;
            //大的后移操作
            while(j >= 0 && arr[j] > key)
            {
                arr[j+1] = arr[j];
                j--;
            }
            arr[j+1] = key;
        }
    }

四.希爾排序

        希爾排序是Donald Shell于1959年提出的一種排序算法，是對直接插入排序的改進(jìn)之后的高效版本。 希爾排序需要準(zhǔn)備一組數(shù)據(jù)作為增量序列。

這組數(shù)據(jù)需要滿足以下三個條件：

1. 數(shù)據(jù)遞減排列

2. 數(shù)據(jù)中的最大值小于待排序數(shù)組的長度

3. 數(shù)據(jù)中的最小值是1。

        只要滿足上述要求的數(shù)組都可以作為增量序列，但是不同的增量序列會影響到排序的效率。這里我們用{5,3,1}作為增量序列來進(jìn)行講解

 實現(xiàn)優(yōu)化的原因：減少數(shù)據(jù)量，使O(n)和O(n^2)的差距并不大

public static void shellSort(int[] arr){
        //分塊處理
        int gap = arr.length/2; //增量
        while(1<=gap)
        {
            //插入排序：只不過是與增量位交換
            for(int i = gap ; i < arr.length ; i++)
            {
                int key = arr[i];
                int j = i-gap;
                while(j >= 0 && arr[j] > key)
                {
                    arr[j+gap] = arr[j];
                    j-=gap;
                }
                arr[j+gap] = key;
            }
            gap = gap/2;
        }
    }

五.堆排序

是一棵完全二叉樹，分為大根堆、小根堆兩種

可以O(shè)(1)取最大/小值，可以O(shè)(logn)刪除最大/小值，可以O(shè)(logn)插入元素

MIN-HEAPIFY（i）操作：

我們假設(shè)完全二叉樹中某節(jié)點 i 的左子樹和右子樹都滿足小根堆的性質(zhì)，假設(shè) i 節(jié)點的左孩子是 left_i，i 節(jié)點的右孩子是 rig?t_i。那如果 a[i] 大于 a[left_i] 或 a[rig?t_i] 的話，那以 i 節(jié)點為根節(jié)點的整棵子樹就不滿足小根堆的性質(zhì)了，我們現(xiàn)在要進(jìn)行一個操作：把以 i 為根節(jié)點的這棵子樹調(diào)整成小根堆。

//堆排序
    public static void heapSort(int[] arr){
        //開始調(diào)整的位置為最后一個葉子節(jié)點
        int start = (arr.length - 1)/2;
        //從最后一個葉子節(jié)點開始遍歷，調(diào)整二叉樹
        for (int i = start; i >= 0 ; i--){
            maxHeap(arr, arr.length, i);
        }
 
        for (int i = arr.length - 1; i > 0; i--){
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;
            maxHeap(arr, i, 0);
        }
    }
 
    //將二叉樹調(diào)整為大頂堆
    public static void maxHeap(int[] arr, int size, int index){
        //建立左子節(jié)點
        int leftNode = 2 * index + 1;
        //建立右子節(jié)點
        int rightNode = 2 * index + 2;
 
        int maxNode = index;
        //左子節(jié)點的值大于根節(jié)點時調(diào)整
        if (leftNode < size && arr[leftNode] > arr[maxNode]){
            maxNode = leftNode;
        }
        //右子節(jié)點的值大于根節(jié)點時調(diào)整
        if (rightNode < size && arr[rightNode] > arr[maxNode]){
            maxNode = rightNode;
        }
        if (maxNode != index){
            int temp = arr[maxNode];
            arr[maxNode] = arr[index];
            arr[index] = temp;
            //交換之后可能會破壞原來的結(jié)構(gòu)，需要再次調(diào)整
            //遞歸調(diào)用進(jìn)行調(diào)整
            maxHeap(arr, size, maxNode);
        }
    }

我使用的是大根堆，排序的過程歸根下來就是：先左底根后右底根（看自己怎么寫）->每個根向上在向下。（左右上下）

六.歸并排序

        歸并排序是分治法的典型應(yīng)用，先來介紹一下分治法，分治法是把一個復(fù)雜的問題分成兩個或更多的相同或相似的子問題，再把子問題分成更小的子問題……直到最后子問題規(guī)模很小可以直接求解，再將子問題的解進(jìn)行合并來得到原問題的解。

        歸并排序分解子問題的過程就是每一次把數(shù)組分成2份，直到數(shù)組的長度為1（因為只有一個數(shù)字的數(shù)組是有序的）。然后再將相鄰的有序數(shù)組合并成一個有序數(shù)組。直到全部合到一起，整個數(shù)組就排序完畢了。 現(xiàn)在要解決的問題就是如何把兩個有序的數(shù)組合并成一個有序的數(shù)組。其實就是每次比較兩個數(shù)組當(dāng)前最小的兩個元素，哪個小就選哪個

public static void mergeSort(int[] arr, int low, int high){
        int middle = (high + low)/2;
        if (low < high){
            //遞歸排序左邊
            mergeSort(arr, low, middle);
            //遞歸排序右邊
            mergeSort(arr, middle +1, high);
            //將遞歸排序好的左右兩邊合并
            merge(arr, low, middle, high);
        }
 
    }
 
    public static void merge(int[] arr, int low, int middle, int high){
        //存儲歸并后的臨時數(shù)組
        int[] temp = new int[high - low + 1];
        int i = low;
        int j = middle + 1;
        //記錄臨時數(shù)組中存放數(shù)字的下標(biāo)
        int index = 0;
        while (i <= middle && j <= high){
            if (arr[i] < arr[j]){
                temp[index] = arr[i];
                i++;
            } else {
                temp[index] = arr[j];
                j++;
            }
            index++;
        }
        //處理剩下的數(shù)據(jù)
        while (j <= high){
            temp[index] = arr[j];
            j++;
            index++;
        }
        while (i <= middle){
            temp[index] = arr[i];
            i++;
            index++;
        }
        //將臨時數(shù)組中的數(shù)據(jù)放回原來的數(shù)組
        for (int k = 0; k < temp.length; ++k){
            arr[k + low] = temp[k];
        }
    }

七.快速排序

        快速排序的工作原理是：從待排序數(shù)組中隨便挑選一個數(shù)字作為基準(zhǔn)數(shù)，把所有比它小的數(shù)字放在它的左邊，所有比它大的數(shù)字放在它的右邊。然后再對它左邊的數(shù)組和右邊的數(shù)組遞歸進(jìn)行這樣的操作。

        全部操作完以后整個數(shù)組就是有序的了。 把所有比基準(zhǔn)數(shù)小的數(shù)字放在它的左邊，所有比基準(zhǔn)數(shù)大的數(shù)字放在它的右邊。這個操作，我們稱為“劃分”(Partition)。

	//快速排序
	public static void QuickSort1(int[] arr, int start, int end){
		int low = start, high = end;
		int temp;
		if(start < end){
		    int guard = arr[start];
			while(low != high){
				while(high > low && arr[high] >= guard) high--;
				while(low < high && arr[low] <= guard) low++;
				if(low < high){
					temp = arr[low];
					arr[low] = arr[high];
					arr[high] = temp;
				}
			}
			arr[start] = arr[low];
			arr[low] = guard;
			QuickSort1(arr, start, low-1);
			QuickSort1(arr, low+1, end);
		}
	}
	
	//快速排序改進(jìn)版(填坑法)
	public static void QuickSort2(int[] arr, int start, int end){
		int low = start, high = end;
		if(start < end){
		while(low != high){
	    	int guard = arr[start];//哨兵元素
			while(high > low && arr[high] >= guard) high--;
			arr[low] = arr[high];
			while(low < high && arr[low] <= guard) low++;
			arr[high] = arr[low];
		}
		arr[low] = guard;
		QuickSort2(arr, start, low-1);
		QuickSort2(arr, low+1, end);
	}
}

八.鴿巢排序

        計算一下每一個數(shù)出現(xiàn)了多少次。舉一個例子，比如待排序的數(shù)據(jù)中1出現(xiàn)了2次，2出現(xiàn)了0次，3出現(xiàn)了3次，4出現(xiàn)了1次，那么排好序的結(jié)果就是{1.1.3.3.3.4}。

//鴿巢排序
    public static void PigeonholeSort(int[] arr){
        //獲取最大值
        int k = 0;
        for (int i = 0; i < arr.length; i++) {
            k = Math.max(k,arr[i]);
        }
        //創(chuàng)建計數(shù)數(shù)組并且初始化為0
        int[] cnt = new int[k+10];
        for(int i = 0 ; i <= k ; i++) { cnt[i]=0; }
        for(int i = 0 ; i < arr.length ;i++) { cnt[arr[i]]++; }
        int j = 0;
        for(int i = 0 ; i <=k ; i++)
        {
            while(cnt[i]!=0)
            {
                arr[j]=i;
                j++;
                cnt[i]--;
            }
        }
    }

        鴿巢排序其實算不上是真正意義上的排序算法，它的局限性很大。只能對純整數(shù)數(shù)組進(jìn)行排序，舉個例子，如果我們需要按學(xué)生的成績進(jìn)行排序。是一個學(xué)生+分?jǐn)?shù)的結(jié)構(gòu)那就不能排序了。

九.計數(shù)排序

        先考慮這樣一個事情：如果對于待排序數(shù)據(jù)中的任意一個元素 a[i]，我們知道有 m 個元素比它小，那么我們是不是就可以知道排好序以后這個元素應(yīng)該在哪個位置了呢？（這里先假設(shè)數(shù)據(jù)中沒有相等的元素）。計數(shù)排序主要就是依賴這個原理來實現(xiàn)的。

比如待排序數(shù)據(jù)是{2,4,0,2,4} 先和鴿巢一樣做一個cnt數(shù)組{1,0,2,0,2}                                                                                                                                    0,1,2,3,4

此時cnt[i]表示數(shù)據(jù)i出現(xiàn)了多少次，

然后對cnt數(shù)組做一個前綴和{1,1,3,3,5}    ：0,1,2,3,4

此時cnt[i]表示數(shù)據(jù)中小于等于i的數(shù)字有多少個

十.基數(shù)排序

基數(shù)排序是通過不停的收集和分配來對數(shù)據(jù)進(jìn)行排序的。

• 因為是10進(jìn)制數(shù)，所以我們準(zhǔn)備十個桶來存分配的數(shù)。

• 最大的數(shù)據(jù)是3位數(shù)，所以我們只需要進(jìn)行3次收集和分配。

• 需要先從低位開始收集和分配（不可從高位開始排，如果從高位開始排的話，高位排好的順序會在排低位的時候被打亂，有興趣的話自己手寫模擬一下試試就可以了）

• 在收集和分配的過程中，不要打亂已經(jīng)排好的相對位置

        比如按十位分配的時候，152和155這兩個數(shù)的10位都是5，并且分配之前152在155的前面，那么收集的時候152還是要放在155之前的。

//基數(shù)排序
    public static void radixSort(int[] array) {
        //基數(shù)排序
        //首先確定排序的趟數(shù);
        int max = array[0];
        for (int i = 1; i < array.length; i++) {
            if (array[i] > max) {
                max = array[i];
            }
        }
        int time = 0;
        //判斷位數(shù);
        while (max > 0) {
            max /= 10;
            time++;
        }
        //建立10個隊列;
        List<ArrayList> queue = new ArrayList<ArrayList>();
        for (int i = 0; i < 10; i++) {
            ArrayList<Integer> queue1 = new ArrayList<Integer>();
            queue.add(queue1);
        }
        //進(jìn)行time次分配和收集;
        for (int i = 0; i < time; i++) {
            //分配數(shù)組元素;
            for (int j = 0; j < array.length; j++) {
                //得到數(shù)字的第time+1位數(shù);
                int x = array[j] % (int) Math.pow(10, i + 1) / (int) Math.pow(10, i);
                ArrayList<Integer> queue2 = queue.get(x);
                queue2.add(array[j]);
                queue.set(x, queue2);
            }
            int count = 0;//元素計數(shù)器;
            //收集隊列元素;
            for (int k = 0; k < 10; k++) {
                while (queue.get(k).size() > 0) {
                    ArrayList<Integer> queue3 = queue.get(k);
                    array[count] = queue3.get(0);
                    queue3.remove(0);
                    count++;
                }
            }
 
        }
 
 
    }

“Java十大排序算法怎么實現(xiàn)”的內(nèi)容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業(yè)相關(guān)的知識可以關(guān)注億速云網(wǎng)站，小編將為大家輸出更多高質(zhì)量的實用文章！