排序算法

常用排序算法總結(jié)(一)
找出數(shù)組中出現(xiàn)次數(shù)最多的那個(gè)數(shù)——主元素問(wèn)題

Arrays.sort() 對(duì)基本類(lèi)型用快速排序，非基本類(lèi)型用歸并排序，是因?yàn)榛绢?lèi)型不需要穩(wěn)定性的排序，他們的相同值是無(wú)差別的。
Collections.sort()使用的Arrays.sort()

  1. 堆排序
    堆排序是一種選擇排序，整體主要由構(gòu)建初始堆+交換堆頂元素和末尾元素并重建堆兩部分組成。
    其中構(gòu)建初始堆經(jīng)推導(dǎo)復(fù)雜度為O(n)，在交換并重建堆的過(guò)程中，需交換n-1次，
    而重建堆的過(guò)程中，根據(jù)完全二叉樹(shù)的性質(zhì)，[log2(n-1),log2(n-2)...1]逐步遞減，近似為nlogn。
    所以堆排序時(shí)間復(fù)雜度一般認(rèn)為就是O(nlogn);
    最壞最好都是O(nlogn);
    輔助空間O(1);
    不穩(wěn)定;

  2. 快速排序
    快速排序每次遞歸取一個(gè)標(biāo)準(zhǔn)值，根據(jù)它來(lái)劃分序列，劃分總的再遞歸劃分左右序列。
    時(shí)間復(fù)雜度是O(nlogn);
    最好是O(nlogn);
    最壞是O(n^2);倒序，此時(shí)需要隨機(jī)取標(biāo)準(zhǔn)值p。
    因?yàn)檫f歸劃分序列，所以輔助空間O(logn)~O(n)
    不穩(wěn)定

  3. 歸并排序
    歸并排序，遞歸平分序列到最底層（最底層只有一個(gè)數(shù)默認(rèn)是排好序的），然后歸并左右序列。
    時(shí)間復(fù)雜度是O(nlogn);
    最好最壞都是O(nlogn);
    輔助空間O(n);
    穩(wěn)定

  1. 直接選擇排序
    暴力排序，每次遍歷數(shù)組選出一個(gè)最大值
    最好最壞都是O(n^2)
    輔助空間O(1);
    不穩(wěn)定;

  2. 直接插入排序
    外循環(huán)從左到右i，
    內(nèi)循環(huán)比較當(dāng)前值和后面的值，小于就交換（可以保存當(dāng)前值，然后把要交換的值直接右移一位，不用真的去交換），否則退出循環(huán)
    0到i始終有序
    最好O(n)
    最壞O(n^2)
    平均O(n^2)
    輔助空間O(1)
    穩(wěn)定

    • 改進(jìn)：二分插入排序，如果比較的代價(jià)比交換的代價(jià)大的話(huà)，就可以使用這個(gè)算法減少比較次數(shù)，最優(yōu)O(nlogn);
      二分法在左邊序列中定位當(dāng)前值要插入的位置，把該位置右邊的值都向右移動(dòng)一個(gè)位置，插入。

  3. 冒泡排序
    外循環(huán)從大到小 j
    內(nèi)循環(huán)從0到j(luò)，當(dāng)前值和前面的值比較，大于就交換。
    每次內(nèi)循環(huán)結(jié)束最大值都會(huì)浮到最上方。
    最壞是O(n^2);
    設(shè)一個(gè)標(biāo)記標(biāo)記內(nèi)循環(huán)有沒(méi)交換過(guò)，可以把最優(yōu)時(shí)間復(fù)雜度降到O(n);
    穩(wěn)定;

    • 改進(jìn)：雞尾酒排序（定向冒泡排序）， 與冒泡排序不同在從低到高然后從高到低。以序列(2,3,4,5,1)為例，雞尾酒排序只需要訪(fǎng)問(wèn)一次序列就可以完成排序，但如果使用冒泡排序則需要四次。但是在亂數(shù)序列的狀態(tài)下，雞尾酒排序與冒泡排序的效率都很差勁。
void CocktailSort(int A[], int n)
{
    int left = 0;                            // 初始化邊界
    int right = n - 1;
    while (left < right)
    {
        for (int i = left; i < right; i++)   // 前半輪,將最大元素放到后面
        {
            if (A[i] > A[i + 1])
            {
                Swap(A, i, i + 1);
            }
        }
        right--;
        for (int i = right; i > left; i--)   // 后半輪,將最小元素放到前面
        {
            if (A[i - 1] > A[i])
            {
                Swap(A, i - 1, i);
            }
        }
        left++;
    }
}
  1. 希爾排序
  2. 基數(shù)排序（桶排序？）
  3. 計(jì)數(shù)排序？

堆排序

package sort;

import java.util.Arrays;

/**
 * 堆排序是一種選擇排序，整體主要由構(gòu)建初始堆+交換堆頂元素和末尾元素并重建堆兩部分組成。
 * 其中構(gòu)建初始堆經(jīng)推導(dǎo)復(fù)雜度為O(n)，在交換并重建堆的過(guò)程中，需交換n-1次，
 * 而重建堆的過(guò)程中，根據(jù)完全二叉樹(shù)的性質(zhì)，[log2(n-1),log2(n-2)...1]逐步遞減，近似為nlogn。
 * 所以堆排序時(shí)間復(fù)雜度一般認(rèn)為就是O(nlogn);
 * 最壞最好都是O(nlogn);輔助空間O(1);不穩(wěn)定；
 */
public class HeapSort {
    public static void main(String []args){
        int []arr = {9,10,7,6,5,4,3,2,1};
        sort(arr);
        System.out.println(Arrays.toString(arr));//[1, 2, 3, 4, 5, 6, 7, 9, 10]
    }
    public static void sort(int[] arr) {
        //先構(gòu)建大頂堆 O(n)
        //從最后一個(gè)非葉子節(jié)點(diǎn)開(kāi)始 length/2-1
        //從下至上，從右到左
        for(int i =arr.length/2-1;i>=0;i--) {
            adjustHeap(arr,i,arr.length);
        }
        //調(diào)整堆結(jié)構(gòu)，交換堆頂元素與末尾元素
        for(int i=arr.length-1;i>0;i--) {
            swap(arr,0,i);
            adjustHeap(arr,0,i);
        }

    }
    /**
     * 調(diào)整最大堆
     * 堆大小小于等于3的可以當(dāng)做是最大堆，所以構(gòu)建最大堆時(shí)可以調(diào)用這個(gè)方法從下到上調(diào)整
     * 循環(huán)子層直到子節(jié)點(diǎn)不大于父節(jié)點(diǎn)。
     * @param arr 數(shù)組
     * @param i 父節(jié)點(diǎn)
     * @param length 要調(diào)整的數(shù)組長(zhǎng)度，0~length-1
     */
    public static void adjustHeap(int[] arr,int i,int length){
        //如果子結(jié)點(diǎn)大于父結(jié)點(diǎn)的話(huà)，交換兩者的位置，又因?yàn)榻粨Q之后又要判斷下一層的父結(jié)點(diǎn)和子節(jié)點(diǎn)
        //所以可以先把當(dāng)前節(jié)點(diǎn)存起來(lái)，等到都比較好位置調(diào)好后，再把這個(gè)數(shù)值放在可以覆蓋的節(jié)點(diǎn)上。
        //i的左子節(jié)點(diǎn)是2i+1
        int temp = arr[i];
        for(int k=2*i+1;k<length;k=2*k+1) {//一層層往下判斷，直到父結(jié)點(diǎn)大于子節(jié)點(diǎn)
            if(k+1<length && arr[k]<arr[k+1]){//如果左子節(jié)點(diǎn)小于右子結(jié)點(diǎn)，k指向右子結(jié)點(diǎn)
                k++;//k指向最大的子結(jié)點(diǎn)
            }
            if(arr[k]>temp) {//如果子結(jié)點(diǎn)大于父結(jié)點(diǎn)的話(huà)，將子結(jié)點(diǎn)賦給父結(jié)點(diǎn)
                arr[i]=arr[k];
                i=k;//繼續(xù)下一層的判斷，下一層的父結(jié)點(diǎn)還是temp
            }else {
                break;//如果子結(jié)點(diǎn)小于等于父結(jié)點(diǎn)的話(huà)，就不需要再調(diào)整堆了
            }
        }
        arr[i]=temp;
    }
    public static void swap(int[] arr,int a,int b) {
        int temp=arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }
}

快速排序

package sort;

import java.util.Arrays;
import java.util.Random;
import java.util.Stack;

/**
 * 快速排序每次遞歸取一個(gè)標(biāo)準(zhǔn)值，根據(jù)它來(lái)劃分序列，劃分總的再遞歸劃分左右序列。
 * 時(shí)間復(fù)雜度是O(nlogn);
 * 最好是O(nlogn);
 * 最壞是O(n^2);倒序，此時(shí)需要隨機(jī)取標(biāo)準(zhǔn)值p。
 * 因?yàn)檫f歸劃分序列，所以輔助空間O(logn)？？
 */
public class QucikSort {

    public static void main(String []args){
        int []arr = {9,10,7,6,5,4,3,2,1};
        sort(arr,0,arr.length-1);
        System.out.println(Arrays.toString(arr));
    }

    /**
     * 從上到下遞歸，先劃分總的，再劃分左右序列
     * @param arr
     * @param start
     * @param end
     */
    public static void sort(int[] arr,int start,int end) {
        if(start>=end){
            return;
        }
        int i = partition(arr,start,end);
        sort(arr,start,i-1);
        sort(arr,i+1,end);

    }
    //非遞歸實(shí)現(xiàn)，用棧存start和end
    public static void sortStack(int[] arr){
        Stack<Integer> stack = new Stack<Integer>();
        stack.push(0);
        stack.push(arr.length-1);
        while (!stack.isEmpty()){
            int end = stack.pop();
            int start = stack.pop();
            int i = partition(arr,start,end);
            if(start<i-1){
                stack.push(start);
                stack.push(i-1);
            }
            if(end>i+1){
                stack.push(i+1);
                stack.push(end);
            }
        }
    }

    /**
     * 根據(jù)選定的標(biāo)準(zhǔn)p來(lái)劃分序列，小于p的放左邊，大于p的放右邊，p在中間
     * 頭尾指針實(shí)現(xiàn)
     * @param arr 待劃分?jǐn)?shù)組
     * @param start 要開(kāi)始劃分的下標(biāo)
     * @param end 結(jié)束劃分的下標(biāo)
     * @return 返回最后p所在的下標(biāo)
     */
    private static int partition(int[] arr,int start,int end){
        if(start>=end){
            return start;
        }
        int ran = (int)(Math.random()*(end-start+1))+start;//隨機(jī)取標(biāo)準(zhǔn)值p
        swap(arr,ran,start);

        int p = arr[start];
        int i = start; // 兩個(gè)指針，右邊指針先開(kāi)始移動(dòng)，碰到小于p的數(shù)時(shí)把它放到左邊指針的位置；然后開(kāi)始移動(dòng)左指針，操作相反；兩指針輪流移動(dòng)直到i>=j。
        int j = end;
        while(i<j){
            while (i<j&&arr[j]>=p){
                j--;
            }
            arr[i]=arr[j];
            while (i<j&&arr[i]<=p){
                i++;
            }
            arr[j]=arr[i];
        }
        arr[i]=p;
        return i;
    }
    private static void swap(int[] arr,int a,int b){
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }
}

歸并排序

package sort;

import java.util.Arrays;

/**
 * 歸并排序，遞歸平分序列到最底層（最底層只有一個(gè)數(shù)默認(rèn)是排好序的），然后歸并左右序列
 * 時(shí)間復(fù)雜度是O(nlogn);
 * 最好最壞都是O(nlogn);
 * 輔助空間O(n);
 * 穩(wěn)定
 */
public class MergeSort {

    public static void main(String []args){
        int []arr = {9,10,7,6,5,4,3,2,1};
//        sort(arr,0,arr.length-1);
        sortIteration(arr);
        System.out.println(Arrays.toString(arr));
    }

    //非遞歸實(shí)現(xiàn)
    public static void sortIteration(int[] arr){
        //從底到上
        int left;
        int mid;
        int right;
        for(int i=1;i<arr.length;i*=2) {//子序列大小，每輪乘2
            left = 0;
            while(left+i<arr.length) {//后一個(gè)子序列存在的話(huà)，歸并兩個(gè)序列
                mid = left+i-1;
                right = mid+i;
                right = right<arr.length?right:arr.length-1;
                merge(arr,left,mid,right);
                left = right+1;
            }
        }
    }
    public static void sort(int[] arr,int start,int end) {
        if(start>=end){
            return;
        }
        int h = (start+end)/2;
        sort(arr,start,h);
        sort(arr,h+1,end);
        merge(arr,start,h,end);

    }
    private static void merge(int[] arr,int start,int h,int end){
        int i = start;//左序列，start~h
        int j = h+1;//有序列，h+1~end
        int[] aux = new int[end-start+1];//輔助數(shù)組
        int k = 0;
        while (i<=h&&j<=end){
            while (i<=h&&j<=end&&arr[i]<=arr[j]) {
                aux[k++]=arr[i++];
            }
            while (i<=h&&j<=end&&arr[j]<arr[i]) {
                aux[k++]=arr[j++];
            }
        }
        while (i<=h){
            aux[k++]=arr[i++];
        }
        while (j<=end){
            aux[k++]=arr[j++];
        }
        System.arraycopy(aux,0,arr,start,aux.length);
    }

    private static void swap(int[] arr,int a,int b){
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }
}

代碼戳這里

最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀(guān)點(diǎn)，簡(jiǎn)書(shū)系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

友情鏈接更多精彩內(nèi)容