排序算法總結

排序算法	平均時間複雜度	最壞時間複雜度	空間複雜度	是否穩定
冒泡排序	O（n2）		O（1）	是
選擇排序				不是
直接插入排序
歸并排序	O(nlogn)		O（n）
快速排序			O（logn）
堆排序
希爾排序		O（ns）
計數排序	O(n+k)
基數排序	O(N∗M)		O(M)

(1)冒泡排序：

是相鄰元素之間的比較和交換，兩重循環O(n2)；是以，如果兩個相鄰元素相等，是不會交換的。是以它是一種穩定的排序方法

void bubble_sort(int array[], int N)
{
    //使用冒泡的方式進行排序
    for(int i=0;i<N;i++){
        for(int j=0;j<N-1-i;j++){
            if(array[j]>array[j+1]){
                int temp=array[j];
                array[j]=array[j+1];
                array[j+1]=temp;
            }
        }
    }
}

優化一

void bubble_sort(int array[], int N)  
{
    //使用冒泡的方式進行排序
    for(int i=0;i<N;i++){
        //有序标記，每一輪的初始值都是true
        bool isSorted=true;
        for(int j=0;j<N-1-i;j++){
            if(array[j]>array[j+1]){
                int temp=array[j];
                array[j]=array[j+1];
                array[j+1]=temp;
                //因為有元素交換，索引數組還不是有序的，标記變為false
                isSorted=false;
            }
        }
        if(isSorted){
            break;
        }
    }

    return 0;
}

(2)選擇排序：

每個元素都與第一個元素相比，産生交換，兩重循環O(n2)；舉個栗子，5 8 5 2 9，第一遍之後，2會與5交換，那麼原序列中兩個5的順序就被破壞了。是以不是穩定的排序算法

操作方法：

第一趟，從n 個記錄中找出關鍵碼最小的記錄與第一個記錄交換；

第二趟，從第二個記錄開始的n-1 個記錄中再選出關鍵碼最小的記錄與第二個記錄交換；

以此類推.....

第i 趟，則從第i 個記錄開始的n-i+1 個記錄中選出關鍵碼最小的記錄與第i 個記錄交換，

直到整個序列按關鍵碼有序。

void print(int a[], int n ,int i){
    cout<<"第"<<i+1 <<"趟 : ";
    for(int j= 0; j<8; j++){
        cout<<a[j] <<"  ";
    }
    cout<<endl;
}
/**
 * 數組的最小值
 *
 * @return int 數組的鍵值
 */
int SelectMinKey(int a[], int n, int i)
{
    int k = i;
    for(int j=i+1 ;j< n; ++j) {
        if(a[k] > a[j]) k = j;
    }
    return k;
}
 
/**
 * 選擇排序
 *
 */
void selectSort(int a[], int n){
    int key, tmp;
    for(int i = 0; i< n; ++i) {
        key = SelectMinKey(a, n,i);           //選擇最小的元素
        if(key != i){
            tmp = a[i];  a[i] = a[key]; a[key] = tmp; //最小元素與第i位置元素互換
        }
        print(a,  n , i);
    }
}
改進法：
void selectSort(int a[],int len) {
        int i,j,min,max,tmp;  
        for(i=0; i<len/2; i++){  // 做不超過n/2趟選擇排序 
            min = max = i;  
            for(j=i+1; j<=len-1-i; j++){  
                //分别記錄最大和最小關鍵字記錄位置
                if(a[j] > a[max]){  
                    max = j;  
                    continue;  
                }  
                if(a[j] < a[min]){  
                    min = j;  
                }  
            }  
            //該交換操作還可分情況讨論以提高效率
            if(min != i){//當第一個為min值，不用交換  
                tmp=a[min];  a[min]=a[i];  a[i]=tmp;  
            }  
            if(min == len-1-i && max == i)//當第一個為max值，同時最後一個為min值，不再需要下面操作  
                continue;  
            if(max == i)//當第一個為max值，則交換後min的位置為max值  
                max = min;  
            if(max != len-1-i){//當最後一個為max值，不用交換  
                tmp=a[max];  a[max]=a[len-1-i];  a[len-1-i]=tmp;  
            }
            print(a,len, i);            
        }  
 }
 
int main(){
    int a[8] = {3,1,5,7,2,4,9,6};
    cout<<"初始值：";
    for(int j= 0; j<8; j++){
        cout<<a[j] <<"  ";
    }
    cout<<endl<<endl;
    selectSort(a, 8);
    print(a,8,8);
}

(3)插入排序：

時間複雜度：O（n^2）

插入排序是在一個已經有序的小序列的基礎上，一次插入一個元素。剛開始這個小序列隻包含第一個元素，事件複雜度O(n2)。比較是從這個小序列的末尾開始的。想要插入的元素和小序列的最大者開始比起，如果比它大則直接插在其後面，否則一直往前找它該插入的位置。如果遇見了一個和插入元素相等的，則把插入元素放在這個相等元素的後面。是以相等元素間的順序沒有改變，是穩定的。

void print(int a[], int n ,int i){
    cout<<i <<":";
    for(int j= 0; j<8; j++){
        cout<<a[j] <<" ";
    }
    cout<<endl;
}
 
 
void InsertSort(int a[], int n)
{
    for(int i= 1; i<n; i++){
        if(a[i] < a[i-1]){               //若第i個元素大于i-1元素，直接插入。小于的話，移動有序表後插入
            int j= i-1;    
            int x = a[i];         //複制為哨兵，即存儲待排序元素
            a[i] = a[i-1];           //先後移一個元素
            while(x < a[j]){     //查找在有序表的插入位置
                a[j+1] = a[j];
                j--;         //元素後移
            }
            a[j+1] = x;         //插入到正确位置
        }
        print(a,n,i);            //列印每趟排序的結果
    }
    
}
 
int main(){
    int a[8] = {3,1,5,7,2,4,9,6};
    InsertSort(a,8);
    print(a,8,8);
}

(4)快速排序

快速排序有兩個方向，左邊的i下标一直往右走，當a[i] <= a[center_index]，其中center_index是中樞元素的數組下标，一般取為數組第0個元素。而右邊的j下标一直往左走，當a[j] > a[center_index]。如果i和j都走不動了，i <= j, 交換a[i]和a[j],重複上面的過程，直到i>j。交換a[j]和a[center_index]，完成一趟快速排序。在中樞元素和a[j]交換的時候，很有可能把前面的元素的穩定性打亂，比如序列為 5 3 3 4 3 8 9 10 11，現在中樞元素5和3(第5個元素，下标從1開始計)交換就會把元素3的穩定性打亂，是以快速排序是一個不穩定的排序算法，不穩定發生在中樞元素和a[j]交換的時刻。

#include <stdio.h>
#include <stdlib.h>

int partiton(int array[], int low, int high) {
    //基準資料 
    int key = array[low];
    while (low < high) {
        //因為預設基準是從左邊開始，是以從右邊開始比較 
        //當隊尾的元素大于等于 基準資料 時,就一直向前挪動high指針 
        while (low < high && array[high] >= key) {
            high--;
        }
        //當找到比 array[low] 小的時，就把後面的值 array[high] 賦給它 
        if (low < high) {
            array[low] = array[high];
        }

        //當隊首元素小于等于 基準資料 時,就一直向後挪動low指針 
        while (low < high && array[low] <= key) {
            low++;
        }
        //當找到比 array[high] 大的時，就把前面的值 array[low] 賦給它
        if (low < high) {
            array[high] = array[low];
        }
    }
    //跳出循環時low和high相等,此時的low或high就是key的正确索引位置
    //把基準資料賦給正确位置 
    array[low] = key;

    return low;
}

void quickSort(int array[], int low, int high) {
    //開始預設基準為    low=0
    if (low < high) {
        //分段位置下标 
        int standard = partiton(array, low, high);

        //遞歸調用排序
        //左邊排序 
        quickSort(array, low, standard - 1);
        //右邊排序 
        quickSort(array, standard + 1, high);
    }
}

void display(int array[], int size) {
    for (int i = 0; i < size; i++) {
        printf("%d ", array[i]);
    }
    printf("\n");
}

bool check(int array[], int size) {
    bool res = true;
    for (int i = 0; i < size - 1; i++) {
        if (array[i] > array[i + 1]) {
            res = false;
        }
    }
    return res;
}

int main() {
//    int array[] = { 49,38,65,97,76,13,27,49,10 };
//    int size = sizeof(array) / sizeof(int);
//    printf("%d \n", size);
//    quickSort(array, 0, size - 1);

    int size = 25;                            //數組大小 
    int array[25] = { 0 };                    //數組初始化 
    for (int i = 0; i < 100; i++) {            //100個數組測試 
        for (int j = 0; j < size; j++) {
            array[j] = rand() % 1000;        //随機生成數組 0~999
        }
        printf("原來的數組：");
        display(array, size);
        
        quickSort(array, 0, size - 1);
        
        printf("排序後數組：");
        display(array, size);
        
        if (check(array, size) == true) {
            printf("排序成功\n");
        }
        printf("\n");
    }

    return 0;
}

(5)歸并排序

歸并排序是把序列遞歸地分成短序列，遞歸出口是短序列隻有1個元素(認為直接有序)或者2個序列(1次比較和交換),然後把各個有序的段序列合并成一個有序的長序列，不斷合并直到原序列全部排好序。可以發現，在1個或2個元素時，1個元素不會交換，2個元素如果大小相等也沒有人故意交換，這不會破壞穩定性。那麼，在短的有序序列合并的過程中，穩定是是否受到破壞？沒有，合并過程中我們可以保證如果兩個目前元素相等時，我們把處在前面的序列的元素儲存在結果序列的前面，這樣就保證了穩定性。是以，歸并排序也是穩定的排序算法。

java實作代碼：

public static void mergeSort(int[] arr) {
    sort(arr, 0, arr.length - 1);
}

public static void sort(int[] arr, int L, int R) {
    if(L == R) {
        return;
    }
    int mid = L + ((R - L) >> 1);
    sort(arr, L, mid);
    sort(arr, mid + 1, R);
    merge(arr, L, mid, R);
}

public static void merge(int[] arr, int L, int mid, int R) {
    int[] temp = new int[R - L + 1];
    int i = 0;
    int p1 = L;
    int p2 = mid + 1;
    // 比較左右兩部分的元素，哪個小，把那個元素填入temp中
    while(p1 <= mid && p2 <= R) {
        temp[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
    }
    // 上面的循環退出後，把剩餘的元素依次填入到temp中
    // 以下兩個while隻有一個會執行
    while(p1 <= mid) {
        temp[i++] = arr[p1++];
    }
    while(p2 <= R) {
        temp[i++] = arr[p2++];
    }
    // 把最終的排序的結果複制給原數組
    for(i = 0; i < temp.length; i++) {
        arr[L + i] = temp[i];
    }
}

https://www.jianshu.com/p/33cffa1ce613

(6)基數排序

基數排序是按照低位先排序，然後收集；再按照高位排序，然後再收集；依次類推，直到最高位。有時候有些屬性是有優先級順序的，先按低優先級排序，再按高優先級排序，最後的次序就是高優先級高的在前，高優先級相同的低優先級高的在前。基數排序基于分别排序，分别收集，是以其是穩定的排序算法。

(7)希爾排序(shell)

希爾排序是按照不同步長對元素進行插入排序，當剛開始元素很無序的時候，步長最大，是以插入排序的元素個數很少，速度很快；當元素基本有序了，步長很小，插入排序對于有序的序列效率很高。是以，希爾排序的時間複雜度會比o(n^2)好一些。由于多次插入排序，我們知道一次插入排序是穩定的，不會改變相同元素的相對順序，但在不同的插入排序過程中，相同的元素可能在各自的插入排序中移動，最後其穩定性就會被打亂，是以shell排序是不穩定的。

我們簡單處理增量序列：增量序列d = {n/2 ,n/4, n/8 .....1} n為要排序數的個數

即：先将要排序的一組記錄按某個增量d（n/2,n為要排序數的個數）分成若幹組子序列，每組中記錄的下标相差d.對每組中全部元素進行直接插入排序，然後再用一個較小的增量（d/2）對它進行分組，在每組中再進行直接插入排序。繼續不斷縮小增量直至為1，最後使用直接插入排序完成排序。

void print(int a[], int n ,int i){
    cout<<i <<":";
    for(int j= 0; j<8; j++){
        cout<<a[j] <<" ";
    }
    cout<<endl;
}
/**
 * 直接插入排序的一般形式
 *
 * @param int dk 縮小增量，如果是直接插入排序，dk=1
 *
 */
 
void ShellInsertSort(int a[], int n, int dk)
{
    for(int i= dk; i<n; ++i){
        if(a[i] < a[i-dk]){            //若第i個元素大于i-1元素，直接插入。小于的話，移動有序表後插入
            int j = i-dk;    
            int x = a[i];            //複制為哨兵，即存儲待排序元素
            a[i] = a[i-dk];            //首先後移一個元素
            while(x < a[j]){        //查找在有序表的插入位置
                a[j+dk] = a[j];
                j -= dk;             //元素後移
            }
            a[j+dk] = x;            //插入到正确位置
        }
        print(a, n,i );
    }
    
}
 
/**
 * 先按增量d（n/2,n為要排序數的個數進行希爾排序
 *
 */
void shellSort(int a[], int n){
 
    int dk = n/2;
    while( dk >= 1  ){
        ShellInsertSort(a, n, dk);
        dk = dk/2;
    }
}
int main(){
    int a[8] = {3,1,5,7,2,4,9,6};
    //ShellInsertSort(a,8,1); //直接插入排序
    shellSort(a,8);              //希爾插入排序
    print(a,8,8);
}

(8)堆排序

我們知道堆的結構是節點i的孩子為2i和2i+1節點，大頂堆要求父節點大于等于其2個子節點，小頂堆要求父節點小于等于其2個子節點。在一個長為n的序列，堆排序的過程是從第n/2開始和其子節點共3個值選擇最大(大頂堆)或者最小(小頂堆),這3個元素之間的選擇當然不會破壞穩定性。但當為n/2-1, n/2-2, ...1這些個父節點選擇元素時，就會破壞穩定性。有可能第n/2個父節點交換把後面一個元素交換過去了，而第n/2-1個父節點把後面一個相同的元素沒有交換，那麼這2個相同的元素之間的穩定性就被破壞了。是以，堆排序不是穩定的排序算法

堆排序：

https://segmentfault.com/a/1190000002466215

堆定義:

堆實際上是一棵完全二叉樹，其任何一非葉節點滿足性質：

Key[i]<=key[2i+1]&&Key[i]<=key[2i+2]（小頂堆）或者：Key[i]>=Key[2i+1]&&key>=key[2i+2]（大頂堆）

即任何一非葉節點的關鍵字不大于或者不小于其左右孩子節點的關鍵字。

堆排序的思想:

利用大頂堆(小頂堆)堆頂記錄的是最大關鍵字(最小關鍵字)這一特性，使得每次從無序中選擇最大記錄(最小記錄)變得簡單。

其基本思想為(大頂堆)：

将初始待排序關鍵字序列(R1,R2....Rn)建構成大頂堆，此堆為初始的無序區；

将堆頂元素R[1]與最後一個元素R[n]交換，此時得到新的無序區(R1,R2,......Rn-1)和新的有序區(Rn),且滿足R[1,2...n-1]<=R[n];

由于交換後新的堆頂R[1]可能違反堆的性質，是以需要對目前無序區(R1,R2,......Rn-1)調整為新堆，然後再次将R[1]與無序區最後一個元素交換，得到新的無序區(R1,R2....Rn-2)和新的有序區(Rn-1,Rn)。不斷重複此過程直到有序區的元素個數為n-1，則整個排序過程完成。

#include <iostream>

using namespace std;
int arrs[] = { 23, 65, 12, 3, 8, 76, 345, 90, 21, 75, 34, 61 };
int arrLen = sizeof(arrs) / sizeof(arrs[0]);

void adjustHeap(int * arrs, int p, int len){
    int curParent = arrs[p];
    int child = 2* p + 1;   //左孩子
    while(child < len){     //沒有孩子
        if(child+1<len&&arrs[child]<arrs[child+1]){
            child++;    //較大孩子的下标
        }
        if(curParent<arrs[child]){
            arrs[p]=arrs[child];
            //沒有将curParent指派給孩子是因為還要疊代子樹，
            //如果其孩子中有大的，會上移，curParent還要繼續下移。
            p=child;
            child=2*p+1;
        }
        else
            break;
    }
    arrs[p]=curParent;
}

void heapSort(int * arrs, int arrLen){
    //建立堆，從最底層的父節點開始
    for(int i = arrLen /2 -1; i>=0; i--)
        adjustHeap(arrs, i, arrLen);
    for(int i = arrLen -1; i>=0; i--){
        int maxEle = arrs[0];
        arrs[0] = arrs[i];
        arrs[i] = maxEle;

        adjustHeap(arrs, 0, i);
    }
}

int main()
{
    heapSort(arrs, arrLen );
    for (int i = 0; i < arrLen; i++)
        cout << arrs[i] << endl;
    return 0;
}

參考：

https://blog.csdn.net/hguisu/article/details/7776068

排序算法總結

(1)冒泡排序：

(2)選擇排序：

操作方法：

(3)插入排序：

時間複雜度：O（n^2）

(4)快速排序

(5)歸并排序

(6)基數排序

(7)希爾排序(shell)

(8)堆排序

堆排序：

堆定義:

堆排序的思想:

其基本思想為(大頂堆)：

繼續閱讀

ACS基本配置-權限等級管理

無人機--飛控科普

27 Best Free Eclipse Plug-ins for Java Developer to be ProductiveCode Quality PluginsText Editor PluginsDependency ManagementVersion Control Integration PluginsFramework Development Continuous Integration Related PluginsOther Utility Plugins

Java String.format方法的簡單使用

android 主線程的相關問題

neo4j之cypher使用文檔

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

spark/scala關于【資源檔案】加載方法概述外部檔案加載方案測試資源檔案打包入jar包中小結

mybatis_入門程式Mybatis入門

AOP程式設計_Android優雅權限架構(1)概念基礎，2021金三銀四前言正文大綱正文

Effective Java 8:通用程式設計

OOM三種類型

工廠模式-三種類型

【遞歸】高效率求2的n次幂

win10本地scala和spark安裝安裝scala安裝spark

scala (3) Function 和 Method