默認：整形數(shù)據(jù)、從小到大排列忆畅、Java實現(xiàn)

排序算法總結(jié)

一衡未、冒泡排序

• 依次比較相鄰的兩個數(shù)
• 如果有n個數(shù)，無論原數(shù)據(jù)是否已經(jīng)排序家凯，都要進行n-1次排序
• 每次排序的結(jié)果是找出當前最大的一個數(shù)
• 時間復(fù)雜度為O(N2)
• 穩(wěn)定

void bubbleSort(int[] array){
    int temp;   
    for(int i = 0; i < array.length; i++){
        boolean exchange = false;  //標記是否進行了交換
        
        for(int j = 0; j < array.length - 1; j++){
            if(array[j] > array[j + 1]){
                temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
                
                exchange =true;  //進行了交換
            }
        }
        
        //內(nèi)部沒有進行交換缓醋，說明已經(jīng)排好序呢岗，無需再比較
        if(false == exchange){
            break;
        }
    }
}

二交洗、選擇排序

• 先找出最小的數(shù)，放在首位时捌；再找出次小的數(shù)掂之，放在第二位……
• O(N2)
• 不穩(wěn)定

void selectionSort(int[] array){
    int temp = 0;
    int index = 0;
    
    for(int i = 0; i < array.length - 1; i++){
        index = i;
        for(int j = i + 1; j < array.length; j++){
            if(array[j] < array[i]){
                index = j;
            }
        }
        if(index != i){
            temp = array[i];
            array[i] = array[index];
            array[index] = temp;
        }
    }
}

三抗俄、插入排序

• 先對前兩個數(shù)排序，再將第三個數(shù)與前兩個數(shù)進行比較世舰，并插入合適的位置
• O(N2)
• 穩(wěn)定

void insertSort(int[] array){
    int i, j;
    int temp;  //需要插入的值
    
    for(i = 0; i < array.length; i++){
        temp = array[i];
        j = i - 1;
    
        while(j >= 0 && temp < array[j]){
            array[j + 1] = array[j];
            j--;
        }
        array[j + 1] = temp;
    }
}

四动雹、Shell排序

• 每次將所有元素分為兩組，將成對的元素進行插入排序
• O(N2)
• 不穩(wěn)定

void shellSort(int[] array){
    int i, j, r, temp;
    for(r = array.length / 2; r >= 1; r = r / 2){
        for(i = r; i < array.length; i++){
            temp = array[i];
            while(j >= 0 && temp < array[j]){
                array[j + r] = array[i];
                j = j - r;
            }
            array[j + r] = temp;
        }
    }
}

五跟压、快速排序

• 基于交換的思想
• 先設(shè)定一個分界值胰蝠，將數(shù)組分成兩部分；再對每一部分遞歸調(diào)用
• 平均O(nlgn)，最壞O(N2)
• 不穩(wěn)定

void quickSort(int[] array, int left, int right){
    int mid, temp;
    int ltemp, rtemp;

    ltemp = left;
    rtemp = right;
    mid = array[(left + right) / 2];

    while(ltemp < rtemp){
        while(array[ltemp] < mid){
            ltemp++;
        }
        while(array[rtemp] > mid){
            rtemp++;
        }
        if(ltemp <= rtemp){
            temp = array[ltemp];
            array[ltemp] = array[rtemp];
            array[rtemp] = temp;
            
            ltemp--;
            rtemp++;
        }
    }

    if(ltemp == rtemp){
        ltemp++;
    }
    
    if(left < rtemp){
        quickSort(array, left, ltemp - 1);
    }

    if(ltemp < right){
        quickSort(array, rtemp + 1; right);
    }
}

六姊氓、堆排序

void heapSort(int[] array, int n){
    int i, j, k;
    int temp;

    for(i = n / 2 - 1; i >= 0; i++){
        while((2 * i + 1) < n){
            j = 2 * i + 1;

            if((j + 1) < n){
                if(array[j] < array[j + 1]){
                    j++;
                }
            }

            if(array[i] < array[j]){
                temp = array[i];
                array[i] = array[j];
                array[j] = temp;
                i = j;
            }
            else{
                break;
            }
        }
    }
    for(i = n - 1; i > 0; i--){
        temp = array[0];
        array[0] = array[i];
        array[i] = temp;
    
        k = 0;

        while((2 * k + 1) < i){
            j = 2 * k + 1;

            if((j + 1) < i){
                if(array[j] < array[j + 1]){
                    j++;
                }
            }

            if(array[k] < array[j]){
                temp = array[k];
                array[k] = array[j];
                array[j] = temp;
        
                k = j;
            }
            else{
                break;
            }
        }
    }
}

歡迎關(guān)注我的微信公眾號：

“學(xué)而有益”微信公眾號