• 均按從小到大排列

• k代表數(shù)值中的”數(shù)位”個(gè)數(shù)

• n代表數(shù)據(jù)規(guī)模

• m代表數(shù)據(jù)的最大值減最小值　

穩(wěn)定性：穩(wěn)定排序算法會(huì)讓原本有相等鍵值的紀(jì)錄維持相對(duì)次序。也就是如果一個(gè)排序算法是穩(wěn)定的，當(dāng)有兩個(gè)相等鍵值的紀(jì)錄R和S，且在原本的列表中R出現(xiàn)在S之前，在排序過(guò)的列表中R也將會(huì)是在S之前。

概述

　　冒泡排序通過(guò)重復(fù)地走訪過(guò)要排序的數(shù)列，一次比較兩個(gè)元素，如果他們的順序錯(cuò)誤就把他們交換過(guò)來(lái)，直到?jīng)]有再需要交換的元素為止（對(duì)n個(gè)項(xiàng)目需要O(n^2)的比較次數(shù)）。這個(gè)算法的名字由來(lái)是因?yàn)樵叫〉脑貢?huì)經(jīng)由交換慢慢“浮”到數(shù)列的頂端。

實(shí)現(xiàn)步驟

1. 比較相鄰的元素。如果第一個(gè)比第二個(gè)大，就交換他們兩個(gè)?！?/p>

2. 對(duì)每一對(duì)相鄰元素做同樣的工作，從開始第一對(duì)到結(jié)尾的最后一對(duì)。這步做完后，最后的元素會(huì)是最大的數(shù)。

3. 針對(duì)所有的元素重復(fù)以上的步驟，除了最后一個(gè)。

4. 持續(xù)每次對(duì)越來(lái)越少的元素重復(fù)上面的步驟，直到?jīng)]有任何一對(duì)數(shù)字需要比較?！?/p>

　　冒泡排序?yàn)橐涣袛?shù)字進(jìn)行排序的過(guò)程　

實(shí)現(xiàn)性能

• 最差時(shí)間復(fù)雜度

O(n^2)

• 最優(yōu)時(shí)間復(fù)雜度

O(n)　

• 平均時(shí)間復(fù)雜度

O(n^2)

• 最差空間復(fù)雜度

總共O(n)，需要輔助空間O(1)

Java實(shí)現(xiàn)

public static void main(String[] args) {
        int[] number = {95,45,15,78,84,51,24,12};
        bubble_sort(number);
        for(int i = 0; i < number.length; i++) {
            System.out.print(number[i] + " ");
            }
    }
    public static void bubble_sort(int[] arr) {
            int  temp, len = arr.length;
            for (int i = 0; i < len - 1; i++)
                for (int j = 0; j < len - 1 - i; j++)
                    if (arr[j] > arr[j + 1]) {
                        temp = arr[j];
                        arr[j] = arr[j + 1];
                        arr[j + 1] = temp;
                }
        }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

選擇排序

　　常用的選擇排序方法有簡(jiǎn)單選擇排序和堆排序，這里只說(shuō)簡(jiǎn)單選擇排序，堆排序后面再說(shuō)。

簡(jiǎn)單選擇排序

　　設(shè)所排序序列的記錄個(gè)數(shù)為n，i　取　1,2,…,n-1　。
　　從所有n-i+1個(gè)記錄（Ri,Ri+1,…,Rn）中找出排序碼最小（或最大）的記錄，與第i個(gè)記錄交換。執(zhí)行n-1趟 后就完成了記錄序列的排序。

以排序數(shù)組｛3，2，1，4，6，5｝為例

簡(jiǎn)單選擇排序性能

　　在簡(jiǎn)單選擇排序過(guò)程中，所需移動(dòng)記錄的次數(shù)比較少。最好情況下，即待排序記錄初始狀態(tài)就已經(jīng)是正序排列了，則不需要移動(dòng)記錄?！?
　　最壞情況下，即待排序記錄初始狀態(tài)是按第一條記錄最大，之后的記錄從小到大順序排列，則需要移動(dòng)記錄的次數(shù)最多為3（n-1）。

　　簡(jiǎn)單選擇排序過(guò)程中需要進(jìn)行的比較次數(shù)與初始狀態(tài)下待排序的記錄序列的排列情況無(wú)關(guān)。
　　當(dāng)i=1時(shí)，需進(jìn)行n-1次比較；當(dāng)i=2時(shí)，需進(jìn)行n-2次比較；依次類推，共需要進(jìn)行的比較次數(shù)是(n-1)+(n-2)+…+2+1=n(n-1)/2，即進(jìn)行比較操作的時(shí)間復(fù)雜度為O(n^2)，進(jìn)行移動(dòng)操作的時(shí)間復(fù)雜度為O(n)?！?/p>

　　簡(jiǎn)單選擇排序是不穩(wěn)定排序。

簡(jiǎn)單選擇排序Java實(shí)現(xiàn)

public static void main(String[] args) {
        int[] number = {3,1,2,8,4,5,24,12};
        SimpleSort(number);
        for(int i = 0; i < number.length; i++) {
            System.out.print(number[i] + " ");
            }
    }
public static void SimpleSort(int[] arr) {
            int length=arr.length;
            int temp;
            for(int i=0;i<length-1;i++){
                int min=i;
                for(int j=i+1;j<length;j++){ //尋找最小的數(shù)
                    if(arr[j]<arr[min]){
                        min =j;
                    }
                }
                if(min!=i){
                     temp = arr[min];
                     arr[min]=arr[i];
                     arr[i]=temp;
                }
            }
        }   
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

概述

　　希爾排序法(縮小增量法) 屬于插入類排序，是將整個(gè)無(wú)序列分割成若干小的子序列分別進(jìn)行插入排序的方法。

　　把記錄按下標(biāo)的一定增量分組，對(duì)每組使用直接插入排序算法排序；隨著增量逐漸減少，每組包含的關(guān)鍵詞越來(lái)越多，當(dāng)增量減至1時(shí)，整個(gè)文件恰被分成一組，算法便終止。

希爾排序是基于插入排序的以下兩點(diǎn)性質(zhì)而提出改進(jìn)方法的：

• 插入排序在對(duì)幾乎已經(jīng)排好序的數(shù)據(jù)操作時(shí)，效率高，即可以達(dá)到線性排序的效率。

• 但插入排序一般來(lái)說(shuō)是低效的，因?yàn)椴迦肱判蛎看沃荒軐?shù)據(jù)移動(dòng)一位。

實(shí)現(xiàn)過(guò)程

　　先取一個(gè)正整數(shù)d1小于n，把所有序號(hào)相隔d1的數(shù)組元素放一組，組內(nèi)進(jìn)行直接插入排序；然后取d2小于d1，重復(fù)上述分組和排序操作；直至di=1，即所有記錄放進(jìn)一個(gè)組中排序?yàn)橹埂?/p>

　　例如，假設(shè)有這樣一組數(shù)[ 13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10 ]，如果我們以步長(zhǎng)為5開始進(jìn)行排序，我們可以通過(guò)將這列表放在有5列的表中來(lái)更好地描述算法，這樣他們就應(yīng)該看起來(lái)是這樣：

13 14 94 33 82
25 59 94 65 23
45 27 73 25 39
10

然后我們對(duì)每列進(jìn)行排序：

10 14 73 25 23
13 27 94 33 39
25 59 94 65 82
45

　　將上述四行數(shù)字，依序接在一起時(shí)我們得到：[ 10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45 ].這時(shí)10已經(jīng)移至正確位置了，然后再以3為步長(zhǎng)進(jìn)行排序：

10 14 73
25 23 13
27 94 33
39 25 59
94 65 82
45

排序之后變?yōu)椋?/p>

10 14 13
25 23 33
27 25 59
39 65 73
45 94 82
94

最后以1步長(zhǎng)進(jìn)行排序（此時(shí)就是簡(jiǎn)單的插入排序了）。

實(shí)現(xiàn)效率

　　希爾排序是一個(gè)不穩(wěn)定的排序，其時(shí)間復(fù)雜度受步長(zhǎng)（增量）的影響。

　　空間復(fù)雜度：?。?1)

　　時(shí)間復(fù)雜度：　平均 O(n^1.3)
　　　　　　　　　最好　O(n)
　　　　　　　　　最壞　O(n^2)

Java實(shí)現(xiàn)

public static void shellSort(int[] a) {
        int gap = 1, i, j, len = a.length;
        int temp;//插入排序交換值的暫存
        //確定初始步長(zhǎng)
        while (gap < len / 3){
            gap = gap * 3 + 1;
        }
        for (; gap > 0; gap /= 3){//循環(huán)遍歷步長(zhǎng)，最后必為1
            for (i = gap; i < len; i++) {//每一列依次向前做插入排序
                temp = a[i];
                //每一列中在a[i]上面且比a[i]大的元素依次向下移動(dòng)
                for (j = i - gap; j >= 0 && a[j] > temp; j -= gap){
                    a[j + gap] = a[j];
                }
                //a[i]填補(bǔ)空白，完成一列中的依次插入排序
                a[j + gap] = temp;
            }
        }   
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

１.概述

　　歸并排序，是創(chuàng)建在歸并操作上的一種有效的排序算法該算法是采用分治法（Divide and Conquer）的一個(gè)非常典型的應(yīng)用，且各層分治遞歸可以同時(shí)進(jìn)行。

　　即先使每個(gè)子序列有序，再將兩個(gè)已經(jīng)排序的序列合并成一個(gè)序列的操作。若將兩個(gè)有序表合并成一個(gè)有序表，稱為二路歸并。

例如：

設(shè)有數(shù)列{6，202，100，301，38，8，1}
初始狀態(tài)：6,202,100,301,38,8，1
第一次歸并后：{6,202},{100,301},{8,38},{1}，比較次數(shù)：3；
第二次歸并后：{6,100,202,301}，{1,8,38}，比較次數(shù)：4；
第三次歸并后：{1,6,8,38,100,202,301},比較次數(shù)：4；
總的比較次數(shù)為：3+4+4=11,；
逆序數(shù)為14；

　　　　　　歸并排序示意圖

２.效率

　　歸并排序速度僅次于快速排序，為穩(wěn)定排序算法（即相等的元素的順序不會(huì)改變），一般用于對(duì)總體無(wú)序，但是各子項(xiàng)相對(duì)有序的數(shù)列.　

　　時(shí)間復(fù)雜度為O(nlogn) 　
　　
　　空間復(fù)雜度為 O(n)　

歸并排序比較占用內(nèi)存，但卻是一種效率高且穩(wěn)定的算法。

3.迭代實(shí)現(xiàn)

3.１實(shí)現(xiàn)原理

①申請(qǐng)空間，使其大小為兩個(gè)已經(jīng)排序序列之和，該空間用來(lái)存放合并后的序列

②設(shè)定兩個(gè)指針，最初位置分別為兩個(gè)已經(jīng)排序序列的起始位置

③比較兩個(gè)指針?biāo)赶虻脑?，選擇相對(duì)小的元素放入到合并空間，并移動(dòng)指針到下一位置

④重復(fù)步驟③直到某一指針到達(dá)序列尾

⑤將另一序列剩下的所有元素直接復(fù)制到合并序列尾

3.２Java代碼

public static void main(String[] args) {
        int [] arr ={6,5,3,1,8,7,2,4};
        merge_sort(arr);
        for(int i : arr){
            System.out.println(i);
        }
    }
public static void merge_sort(int[] arr) {
        int len = arr.length;
      //用于合并的臨時(shí)數(shù)組
        int[] result = new int[len];
        int block, start;

      //兩兩合并后塊大小變大兩倍 (注意最后一次block等于len)
        for(block = 1; block <=len ; block *= 2) {
            //把整個(gè)數(shù)組分成很多個(gè)塊，每次合并處理兩個(gè)塊
            for(start = 0; start <len; start += 2 * block) {
                int low = start;
                int mid = (start + block) < len ? (start + block) : len;
                int high = (start + 2 * block) < len ? (start + 2 * block) : len;
                //兩個(gè)塊的起始下標(biāo)及結(jié)束下標(biāo)
                int start1 = low, end1 = mid;
                int start2 = mid, end2 = high;
                //開始對(duì)兩個(gè)block進(jìn)行歸并排序
                while (start1 < end1 && start2 < end2) {
                result[low++] = arr[start1] < arr[start2] ? arr[start1++] : arr[start2++];
                }
                while(start1 < end1) {
                result[low++] = arr[start1++];
                }
                while(start2 < end2) {
                result[low++] = arr[start2++];
                }
            }
         //每次歸并后把結(jié)果result存入arr中，以便進(jìn)行下次歸并
        int[] temp = arr;
        arr = result;
        result = temp;
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

4.遞歸實(shí)現(xiàn)

4.１實(shí)現(xiàn)原理

假設(shè)序列共有n個(gè)元素

①將序列每相鄰兩個(gè)數(shù)字進(jìn)行歸并操作，形成floor(n/2)個(gè)序列，排序后每個(gè)序列包含兩個(gè)元素。

②將上述序列再次歸并，形成floor(n/4)個(gè)序列，每個(gè)序列包含四個(gè)元素

③重復(fù)步驟②，直到所有元素排序完畢

4.２Java代碼

public static void main(String[] args) {
        int [] arr ={6,5,3,1,8,7,2,4};
        int len = arr.length;
        int[] reg = new int[len];
        merge_sort_recursive(arr,reg,0,len-1);
        for(int i : arr){
            System.out.println(i);
        }
    }
static void merge_sort_recursive(int[] arr, int[] reg, int start, int end) {
        if (start >= end)
            return;
        int len = end - start, mid = (len >> 1) + start;
        int start1 = start, end1 = mid;
        int start2 = mid + 1, end2 = end;
        //遞歸到子序列只有一個(gè)數(shù)的時(shí)候，開始逐個(gè)返回
        merge_sort_recursive(arr, reg, start1, end1);
        merge_sort_recursive(arr, reg, start2, end2);       
        //-------合并操作，必須在遞歸之后（子序列有序的基礎(chǔ)上）----
        int k = start;
        while (start1 <= end1 && start2 <= end2)
reg[k++] = arr[start1] < arr[start2] ? arr[start1++] : arr[start2++];
        while (start1 <= end1)
            reg[k++] = arr[start1++];
        while (start2 <= end2)
            reg[k++] = arr[start2++];
        //借用reg數(shù)組做合并，然后把數(shù)據(jù)存回arr中
        for (k = start; k <= end; k++)
            arr[k] = reg[k];
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

基本思想

　　快速排序（Quicksort）是對(duì)冒泡排序的一種改進(jìn)，又稱劃分交換排序（partition-exchange sort。

　　快速排序使用分治法（Divide and conquer）策略來(lái)把一個(gè)序列（list）分為兩個(gè)子序列（sub-lists）。

步驟為：

①．從數(shù)列中挑出一個(gè)元素，稱為”基準(zhǔn)”（pivot）

②．重新排序數(shù)列，所有元素比基準(zhǔn)值小的擺放在基準(zhǔn)前面，所有元素比基準(zhǔn)值大的擺在基準(zhǔn)的后面（相同的數(shù)可以到任一邊）。在這個(gè)分區(qū)結(jié)束之后，該基準(zhǔn)就處于數(shù)列的中間位置。這個(gè)稱為分區(qū)（partition）操作。

③．遞歸地（recursive）把小于基準(zhǔn)值元素的子數(shù)列和大于基準(zhǔn)值元素的子數(shù)列排序

使用快速排序法對(duì)一列數(shù)字進(jìn)行排序的過(guò)程

排序效率

　　在平均狀況下，排序n個(gè)項(xiàng)目要Ο(n log n)次比較。在最壞狀況下則需要Ο(n2)次比較，但這種狀況并不常見。事實(shí)上，快速排序通常明顯比其他Ο(n log n)算法更快，因?yàn)樗膬?nèi)部循環(huán)（inner loop）可以在大部分的架構(gòu)上很有效率地被實(shí)現(xiàn)出來(lái)。

最差時(shí)間復(fù)雜度 Ο(n^2)　

最優(yōu)時(shí)間復(fù)雜度 Ο(n log n)　

平均時(shí)間復(fù)雜度Ο(n log n)　

最差空間復(fù)雜度 根據(jù)實(shí)現(xiàn)的方式不同而不同

Java實(shí)現(xiàn)

public static void main(String[] args) {
        int [] arr = {8,1,0,4,6,2,7,9,5,3};
        quickSort(arr,0,arr.length-1);
        for(int i :arr){
            System.out.println(i);
        }
    }
    public static void quickSort(int[]arr,int low,int high){
         if (low < high) {     
             int middle = getMiddle(arr, low, high);     
              quickSort(arr, low, middle - 1);            
             quickSort(arr, middle + 1, high);            
          }  
    }
    public static int getMiddle(int[] list, int low, int high) {     
        int tmp = list[low];    
        while (low < high) {     
            while (low < high && list[high] >= tmp) {     
                high--;     
            }     
            list[low] = list[high];   
            while (low < high && list[low] <= tmp) {     
                low++;     
            }     
            list[high] = list[low];   
        }     
       list[low] = tmp;           
       return low;                   
    } 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

運(yùn)行結(jié)果：

分析：

?。笧橹兄?，紅色箭頭表示low，綠色箭頭表示high

①?gòu)膆igh開始向前掃描到第一個(gè)比８小的值與８交換。

②從low向后掃描第一比8大的值與8交換。

③重復(fù)①②過(guò)程只到，high=low完成一次快速排序，然后遞歸子序列。

淺析堆

　　堆排序(Heapsort)是指利用堆這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計(jì)的一種排序算法，它是選擇排序的一種?？梢岳?strong>數(shù)組的特點(diǎn)快速定位指定索引的元素。堆分為大根堆和小根堆，是完全二叉樹。大根堆的要求是每個(gè)節(jié)點(diǎn)的值都不大于其父節(jié)點(diǎn)的值。

　　由于堆中每次都只能刪除第0個(gè)數(shù)據(jù)，通過(guò)　取出第０個(gè)數(shù)據(jù)再執(zhí)行堆的刪除操作、重建堆（實(shí)際的操作是將最后一個(gè)數(shù)據(jù)的值賦給根結(jié)點(diǎn)，然后再?gòu)母Y(jié)點(diǎn)開始進(jìn)行一次從上向下的調(diào)整。），然后再取，如此重復(fù)實(shí)現(xiàn)排序。

堆的操作：

在堆的數(shù)據(jù)結(jié)構(gòu)中，堆中的最大值總是位于根節(jié)點(diǎn)。堆中定義以下幾種操作：

• 最大堆調(diào)整（Max_Heapify）：將堆的末端子節(jié)點(diǎn)作調(diào)整，使得子節(jié)點(diǎn)永遠(yuǎn)小于父節(jié)點(diǎn)

• 創(chuàng)建最大堆（Build_Max_Heap）：將堆所有數(shù)據(jù)重新排序

• 堆排序（HeapSort）：移除位在第一個(gè)數(shù)據(jù)的根節(jié)點(diǎn)，并做最大堆調(diào)整的遞歸運(yùn)算

堆的存儲(chǔ)：

通常堆是通過(guò)一維數(shù)組來(lái)實(shí)現(xiàn)的。在數(shù)組起始位置為0的情形中：

• 父節(jié)點(diǎn)i的左子節(jié)點(diǎn)在位置(2*i+1);　

• 父節(jié)點(diǎn)i的右子節(jié)點(diǎn)在位置(2*i+2);

• 子節(jié)點(diǎn)i的父節(jié)點(diǎn)在位置floor((i-1)/2);　

Java代碼實(shí)現(xiàn)

public class HeapSort {
    private static int[] sort = new int[]{1,0,10,20,3,5,6,4,9,8,12,17,34,11};
    public static void main(String[] args) {
        buildMaxHeapify(sort);
        heapSort(sort);
        print(sort);
    }

    private static void buildMaxHeapify(int[] data){
        //沒有子節(jié)點(diǎn)的才需要?jiǎng)?chuàng)建最大堆，從最后一個(gè)的父節(jié)點(diǎn)開始
        int startIndex = getParentIndex(data.length - 1);
        //從尾端開始創(chuàng)建最大堆，每次都是正確的堆
        for (int i = startIndex; i >= 0; i--) {
            maxHeapify(data, data.length, i);
        }
    }

    /**
     * 創(chuàng)建最大堆
     * @param data
     * @param heapSize需要?jiǎng)?chuàng)建最大堆的大小，一般在sort的時(shí)候用到，因?yàn)樽疃嘀捣旁谀┪玻┪簿筒辉贇w入最大堆了
     * @param index當(dāng)前需要?jiǎng)?chuàng)建最大堆的位置
     */
    private static void maxHeapify(int[] data, int heapSize, int index){
        // 當(dāng)前點(diǎn)與左右子節(jié)點(diǎn)比較
        int left = getChildLeftIndex(index);
        int right = getChildRightIndex(index);

        int largest = index;
        if (left < heapSize && data[index] < data[left]) {
            largest = left;
        }
        if (right < heapSize && data[largest] < data[right]) {
            largest = right;
        }
        //得到最大值后可能需要交換，如果交換了，其子節(jié)點(diǎn)可能就不是最大堆了，需要重新調(diào)整
        if (largest != index) {
            int temp = data[index];
            data[index] = data[largest];
            data[largest] = temp;
            maxHeapify(data, heapSize, largest);
        }
    }

    /**
     * 排序，最大值放在末尾，data雖然是最大堆，在排序后就成了遞增的
     * @param data
     */
    private static void heapSort(int[] data) {
        //末尾與頭交換，交換后調(diào)整最大堆
        for (int i = data.length - 1; i > 0; i--) {
            int temp = data[0];
            data[0] = data[i];
            data[i] = temp;
            maxHeapify(data, i, 0);
        }
    }

    /**
     * 父節(jié)點(diǎn)位置
     * @param current
     * @return
     */
    private static int getParentIndex(int current){
        return (current - 1) >> 1;
    }

    /**
     * 左子節(jié)點(diǎn)position注意括號(hào)，加法優(yōu)先級(jí)更高
     * @param current
     * @return
     */
    private static int getChildLeftIndex(int current){
        return (current << 1) + 1;
    }

    /**
     * 右子節(jié)點(diǎn)position
     * @param current
     * @return
     */
    private static int getChildRightIndex(int current){
        return (current << 1) + 2;
    }

    private static void print(int[] data){
        for (int i = 0; i < data.length; i++) {
            System.out.print(data[i] + " |");
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93

1.概念

桶排序（Bucket sort）或所謂的箱排序，是一個(gè)排序算法。

　　假設(shè)有一組長(zhǎng)度為N的待排關(guān)鍵字序列K[1….n]。首先將這個(gè)序列劃分成M個(gè)的子區(qū)間(桶) 。然后基于某種映射函數(shù) ，將待排序列的關(guān)鍵字k映射到第i個(gè)桶中(即桶數(shù)組B的下標(biāo) i) ，那么該關(guān)鍵字k就作為B[i]中的元素。接著對(duì)每個(gè)桶B[i]中的所有元素進(jìn)行比較排序(可以使用快排)。然后依次枚舉輸出B[0]….B[M]中的全部?jī)?nèi)容即是一個(gè)有序序列。

桶排序的步驟：

①設(shè)置一個(gè)定量的數(shù)組當(dāng)作空桶子。

②尋訪序列，并且把項(xiàng)目一個(gè)一個(gè)放到對(duì)應(yīng)的桶子去。

③對(duì)每個(gè)不是空的桶子進(jìn)行排序。

④從不是空的桶子里把項(xiàng)目再放回原來(lái)的序列中。

２.性能

數(shù)據(jù)結(jié)構(gòu) 數(shù)組　
最差時(shí)間復(fù)雜度 　 O(n^2)
平均時(shí)間復(fù)雜度 　O(n+k)
最差空間復(fù)雜度　O(n*k)

　　平均情況下桶排序以線性時(shí)間運(yùn)行，桶排序是穩(wěn)定的，排序非?？?但是同時(shí)也非常耗空間,基本上是最耗空間的一種排序算法。

　　對(duì)N個(gè)關(guān)鍵字進(jìn)行桶排序的時(shí)間復(fù)雜度分為兩個(gè)部分：

①循環(huán)計(jì)算每個(gè)關(guān)鍵字的桶映射函數(shù)，這個(gè)時(shí)間復(fù)雜度是O(N)。

②利用先進(jìn)的比較排序算法對(duì)每個(gè)桶內(nèi)的所有數(shù)據(jù)進(jìn)行排序，其時(shí)間復(fù)雜度為 ∑ O(Ni*logNi) 。其中Ni 為第i個(gè)桶的數(shù)據(jù)量。

　　很顯然，第②部分是桶排序性能好壞的決定因素。盡量減少桶內(nèi)數(shù)據(jù)的數(shù)量是提高效率的唯一辦法(因?yàn)榛诒容^排序的最好平均時(shí)間復(fù)雜度只能達(dá)到O(N*logN)了)。因此，我們需要盡量做到下面兩點(diǎn)：　　

① 映射函數(shù)f(k)能夠?qū)個(gè)數(shù)據(jù)平均的分配到M個(gè)桶中，這樣每個(gè)桶就有[N/M]個(gè)數(shù)據(jù)量。　
　　
②盡量的增大桶的數(shù)量。極限情況下每個(gè)桶只能得到一個(gè)數(shù)據(jù)，這樣就完全避開了桶內(nèi)數(shù)據(jù)的“比較”排序操作。 當(dāng)然，做到這一點(diǎn)很不容易，數(shù)據(jù)量巨大的情況下，f(k)函數(shù)會(huì)使得桶集合的數(shù)量巨大，空間浪費(fèi)嚴(yán)重。這就是一個(gè)時(shí)間代價(jià)和空間代價(jià)的權(quán)衡問(wèn)題了。

3.java實(shí)現(xiàn)

　　對(duì)０～１之間的一組浮點(diǎn)數(shù)進(jìn)行升序排序：

BucketSort.Java

public class BucketSort  {
    /** 
     * 對(duì)arr進(jìn)行桶排序，排序結(jié)果仍放在arr中 
     */  
    public static void bucketSort(double arr[]){  
  //-------------------------------------------------分桶-----------------------------------------------      
        int n = arr.length;  
        //存放桶的鏈表
        ArrayList bucketList[] = new ArrayList [n];  
        //每個(gè)桶是一個(gè)list，存放此桶的元素   
        for(int i =0;i<n;i++){  
            //下取等
            int temp = (int) Math.floor(n*arr[i]);  
            //若不存在該桶，就新建一個(gè)桶并加入到桶鏈表中
            if(null==bucketList[temp])  
                bucketList[temp] = new ArrayList();  
            //把當(dāng)前元素加入到對(duì)應(yīng)桶中
            bucketList[temp].add(arr[i]);            
        }  
//-------------------------------------------------桶內(nèi)排序-----------------------------------------------    
        //對(duì)每個(gè)桶中的數(shù)進(jìn)行插入排序   
        for(int i = 0;i<n;i++){  
            if(null!=bucketList[i])  
                insert(bucketList[i]);  
        }  
//-------------------------------------------------合并桶內(nèi)數(shù)據(jù)-----------------------------------------------    
        //把各個(gè)桶的排序結(jié)果合并   
        int count = 0; 
        for(int i = 0;i<n;i++){  
            if(null!=bucketList[i]){  
                Iterator iter = bucketList[i].iterator();  
                while(iter.hasNext()){  
                    Double d = (Double)iter.next();  
                    arr[count] = d;  
                    count++;  
                }  
            }  
        }  
    }  

    /** 
     * 用插入排序?qū)γ總€(gè)桶進(jìn)行排序 
     * 從小到大排序
     */  
    public static void insert(ArrayList list){  

        if(list.size()>1){  
            for(int i =1;i<list.size();i++){  
                if((Double)list.get(i)<(Double)list.get(i-1)){  
                    double temp = (Double) list.get(i);  
                    int j = i-1;  
                    for(;j>=0&&((Double)list.get(j)>(Double)list.get(j+1));j--)  
                        list.set(j+1, list.get(j));  //后移
                    list.set(j+1, temp);  
                }  
            }  
        } 
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

測(cè)試代碼：

public static void main(String[] args) {
        double arr [] ={0.21,0.23,0.76,0.12,0.89};
        BucketSort.bucketSort(arr);
        for(double a:arr){
            System.out.println(a);
        }
    }
1
2
3
4
5
6
7
1
2
3
4
5
6
7

輸出結(jié)果：

原理

　　基數(shù)排序（Radix sort）是一種非比較型整數(shù)排序算法，其原理是將整數(shù)按位數(shù)切割成不同的數(shù)字，然后按每個(gè)位數(shù)分別比較。由于整數(shù)也可以表達(dá)字符串（比如名字或日期）和特定格式的浮點(diǎn)數(shù)，所以基數(shù)排序也不是只能使用于整數(shù)。

　　將所有待比較數(shù)值（正整數(shù)）統(tǒng)一為同樣的數(shù)位長(zhǎng)度，數(shù)位較短的數(shù)前面補(bǔ)零。然后，從最低位開始，依次進(jìn)行一次排序。這樣從最低位排序一直到最高位排序完成以后，數(shù)列就變成一個(gè)有序序列。

效率

　　基數(shù)排序的時(shí)間復(fù)雜度是O(k·n)，其中n是排序元素個(gè)數(shù)，k是數(shù)字位數(shù)。注意這不是說(shuō)這個(gè)時(shí)間復(fù)雜度一定優(yōu)于O(n·log(n))，k的大小取決于數(shù)字位的選擇和待排序數(shù)據(jù)所屬數(shù)據(jù)類型的全集的大??；k決定了進(jìn)行多少輪處理，而n是每輪處理的操作數(shù)目。

　　基數(shù)排序基本操作的代價(jià)較小，k一般不大于logn，所以基數(shù)排序一般要快過(guò)基于比較的排序，比如快速排序。

　　最差空間復(fù)雜度是O(k·n)

Java實(shí)現(xiàn)

　　現(xiàn)在有數(shù)組：278，109，63,930,589,184,505,269,8,83　。根據(jù)各位數(shù)將數(shù)組劃分為10個(gè)鏈表(當(dāng)然其中的某些鏈表可能不含有元素)
　　
第一次分配：

0:930
1:
2:
3:63,83
4:184
5:505
6：
7:
8:278,8
9:109,589,269

第一次收集后的數(shù)組：

930,63,83,184,505，278,8,109,589,269

第二次分配：

0:505,8,109
1:
2:
3:930
4:
5:
6：63,269
7:278
8:83,184，589
9:

第二次收集后的數(shù)組：

505,8,109，930，63,269，278，83,184，589

第三次分配：

0:8,63,83
1:109,184
2:278,269
3:
4:
5:505,589
6:
7:
8:
9:930

最后得到序列：

8,63,83,109,184，269,278,505,589,930

基數(shù)排序其實(shí)是利用多關(guān)鍵字先達(dá)到局部有序，再調(diào)整達(dá)到全局有序。

代碼實(shí)現(xiàn)：

public class Test {
    public static void main(String[] args) {

        int[] array = {278,109,63,930,589,184,505,269,8,83};  
        radixSort(array);  
        for(double a : array){
            System.out.println(a);
        }
    }
public static void radixSort(int[] array){

        //------------------------------------------確定排序的趟數(shù)----------------------------------
        int max=array[0];
        for(int i=1;i<array.length;i++){
            if(array[i]>max){
                max=array[i];
            }
        }
        int time=0;
        while(max>0){
            max/=10;
            time++;
        }
        //----------------------------------------初始化10個(gè)鏈表用戶分配時(shí)暫存-------------------------------
        List<List<Integer>> list=new ArrayList<List<Integer>>();
        for(int i=0;i<10;i++){
            List<Integer> item=new ArrayList<Integer>();
            list.add(item);
        }

        //-----------------------------------------進(jìn)行time次分配和收集-------------------------------------
      for(int i=0;i<time;i++){
            //分配元素;
            for(int j=0;j<array.length;j++){
                int index = array[j]%(int)Math.pow(10, i+1)/(int)Math.pow(10, i);
                list.get(index).add(array[j]);
            }
            //收集元素;
            int count=0;
            for(int k=0;k<10;k++){
                if(list.get(k).size()>0){
                    for(int a : list.get(k)){
                        array[count]=a;
                        count++;
                    }
                    //清除數(shù)據(jù)，以便下次收集
                    list.get(k).clear();
                }
            }
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

運(yùn)行結(jié)果：

概述

　　將一個(gè)數(shù)據(jù)插入到已經(jīng)排好序的有序數(shù)據(jù)中，從而得到一個(gè)新的、個(gè)數(shù)加一的有序數(shù)據(jù)，算法適用于少量數(shù)據(jù)的排序，是穩(wěn)定的排序方法。

　　插入排序又分為　直接插入排序　和 折半插入排序。

直接插入排序

　　把待排序的紀(jì)錄按其關(guān)鍵碼值的大小逐個(gè)插入到一個(gè)已經(jīng)排好序的有序序列中，直到所有的紀(jì)錄插入完為止，得到一個(gè)新的有序序列。

Java實(shí)現(xiàn)

    public static void insertSort(int a[]){  
        int j;       //當(dāng)前要插入值的位置  
        int preJ;     //依次指向j前的位置  
        int key;       //后移時(shí)來(lái)暫存要插入的值

        //從數(shù)組的第二個(gè)位置開始遍歷值  
        for(j=1;j<a.length;j++){  
            key=a[j];  
            preJ=j-1;  
            //a[preJ]比當(dāng)前值大時(shí)，a[preJ]后移一位  
            while(preJ>=0 && a[preJ]>key){  
                a[preJ+1]=a[preJ]; //將a[preJ]值后移   

     //這里注意:  a[preJ+1]=a[j]=key,把插入值已經(jīng)存在了 key中
    //等于說(shuō), 留出來(lái)一個(gè)空白位置來(lái)實(shí)現(xiàn)依次后移（不會(huì)造成數(shù)據(jù)丟失問(wèn)題）

                preJ--;         //preJ前移  
            }
            //找到要插入的位置或已遍歷完成（(preJ=0）
            a[preJ+1]=key;    //將當(dāng)前值插入 空白位置
        }  
    } 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

　
　　備注很清楚，我就不多說(shuō)了．．．．

效率分析

　　空間復(fù)雜度O(1) 　
　　
　　平均時(shí)間復(fù)雜度O(n^2)

最差情況：反序，需要移動(dòng)n*(n-1)/2個(gè)元素 ，運(yùn)行時(shí)間為O(n^2)。
　　
最好情況：正序，不需要移動(dòng)元素，運(yùn)行時(shí)間為O(n)．

折半插入排序　

　　直接插入排序中要把插入元素與已有序序列元素依次進(jìn)行比較，效率非常低?！?
　　
　　折半插入排序,使用使用折半查找的方式尋找插入點(diǎn)的位置, 可以減少比較的次數(shù),但移動(dòng)的次數(shù)不變, 時(shí)間復(fù)雜度和空間復(fù)雜度和直接插入排序一樣，在元素較多的情況下能提高查找性能。

Java實(shí)現(xiàn)

private static void binaryInsertSort(int[] a)  
    {  
        //從數(shù)組的第二個(gè)位置開始遍歷值    
        for(int i = 1; i < a.length; i++)  {  
            int key = a[i];           //暫存要插入的值    
            int pre = 0;              //有序序列開始和結(jié)尾下標(biāo)申明
            int last = i - 1;       
        // 折半查找出插入位置 a[pre]
            while(pre <= last)  {  
                int mid = (pre + last) / 2;                
                if(key < a[mid])  {  
                    last = mid - 1;  
                } else {  
                    pre = mid + 1;  
                }  
            }  
     //a[i]已經(jīng)取出來(lái)存放在key中，把下標(biāo)從pre + 1到 i-1的元素依次后移
            for(int j = i; j >= pre + 1; j--)  {  
                a[j] = a[j - 1];  
            }  
            //把值插入空白位置
            a[pre] = key;            
        }  
    } 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

直接插入排序是，比較一個(gè)后移一個(gè)；
折半插入排序是，先找到位置，然后一起移動(dòng)；

1. 快排的partition函數(shù)

　　作用：給定一個(gè)數(shù)組arr[]和數(shù)組中任意一個(gè)元素a，重排數(shù)組使得a左邊都小于它，右邊都不小于它。

// A[]為數(shù)組，start、end分別為數(shù)組第一個(gè)元素和最后一個(gè)元素的索引
 // povitIndex為數(shù)組中任意選中的數(shù)的索引
static int partition(int A[], int start, int end, int pivotIndex){
    int i = start, j = end, pivot = A[pivotIndex];
    swap<int>(A[end], A[pivotIndex]);
    while(i < j){
        while(i < j && A[i] <= pivot) ++i;
        while(i < j && A[j] >= pivot) --j;
        if(i < j) swap<int>(A[i], A[j]);
    }
    swap<int>(A[end], A[i]);
    return i;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
1
2
3
4
5
6
7
8
9
10
11
12
13

2. 冒泡排序的改進(jìn)

思路：

①、加一個(gè)標(biāo)志位，當(dāng)某一趟冒泡排序沒有元素交換時(shí)，則冒泡結(jié)束，元素已經(jīng)有序，可以有效的減少冒泡次數(shù)。

  /** 
     * 引入標(biāo)志位，默認(rèn)為true 
     * 如果前后數(shù)據(jù)進(jìn)行了交換，則為true，否則為false。如果沒有數(shù)據(jù)交換，則排序完成。 
     */  
    public static int[] bubbleSort(int[] arr){  
        boolean flag = true;  
        int n = arr.length;  
        while(flag){  
            flag = false;  
            for(int j=0;j<n-1;j++){  
                if(arr[j] >arr[j+1]){  
                    //數(shù)據(jù)交換  
                    int temp = arr[j];  
                    arr[j] = arr[j+1];  
                    arr[j+1] = temp;  
                    //設(shè)置標(biāo)志位  
                    flag = true;  
                }  
            }  
            n--;  
        }  
        return arr;  
    }  
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

②、記錄每一次元素交換的位置，當(dāng)元素交換的位置在第0個(gè)元素時(shí)，則排序結(jié)束。

3.快排優(yōu)化

① 快速排序在處理小規(guī)模數(shù)據(jù)時(shí)的表現(xiàn)不好，這個(gè)時(shí)候可以改用插入排序。

②對(duì)于一個(gè)每個(gè)元素都完全相同的一個(gè)序列來(lái)講，快速排序也會(huì)退化到 O(n^2)。要將這種情況避免到，可以這樣做：

　　在分區(qū)的時(shí)候，將序列分為 3 堆，一堆小于中軸元素，一堆等于中軸元素，一堆大于中軸元素，下次遞歸調(diào)用快速排序的時(shí)候，只需對(duì)小于和大于中軸元素的兩堆數(shù)據(jù)進(jìn)行排序，中間等于中軸元素的一堆已經(jīng)放好。