數(shù)據(jù)結構與算法---排序篇

前言：

2016年5月21號開始學習排序算法及其主要思想，并通過代碼實現(xiàn)

插入排序

插入排序有兩種：

  • 直接插入排序
  • 折半插入排序

直接插入排序

算法思想：

設有n + 1個記錄，存放在數(shù)組R中，重新安排記錄在數(shù)組中的存放順序，使得按關鍵字有序即R[0].key <= R2.Key <= ...<=R[n].key(有序表)

  • 假設待排序的記錄存放在數(shù)組R[1..n]中。
  • 初始時，R[1]自成1個有序區(qū)，無序區(qū)為R[2..n]。
  • 從i=2起直至i=n為止，依次將R[i]插入當前的有序區(qū)R[1..i-1]中，生成含n個記錄的有序區(qū)。

算法描述

直接插入排序演示圖
  • （1）若比較r[0] < r[i]時， j = i - 1; // 從第i個記錄向前測試插入位置，用r[0]為輔助單元
  • （2）若r[0].key >=r[j].key 轉(zhuǎn)(4)
  • （3）若r[0].key < r[j].key時，r[j + 1] = r[j]; j--；轉(zhuǎn)(2) // 調(diào)整待插入位置
  • (4) r[j + 1] = r[0];結束

算法實現(xiàn)

  #include <stdio.h>
  #define N 10

  void insertSort(int a[],int length) {
    int j;
    for (int i = 1; i <= length; i++) { 
        a[0] = a[i];   // 將第i個待排序記錄賦值給a[0],a[0]位置為哨兵
        j = i - 1;  // 此時的j為哨兵的前一個元素
        while (a[0] < a[j] && j >=0) { // 將第i個待排序記錄同前面的i - 1 個記錄比較，并為第j個記錄尋找合適的插入位置
            a[j + 1] = a[j];
            j--;
        }
        a[j + 1] = a[0]; // 此時的j為合適插入位置

    }   
  }

  void main() {
    int a[N + 1],i;
    for (i = 1;i <= N; i++) {
        scanf("%d",&a[i]);
    }
    insertSort(&a,N);
    printf("Input Sort:\n");
    for (i = 1; i < N + 1; i++)  {
        printf("%d",a[i]);
    }
}

算法分析

時間復雜度 O(n2)

  • 向有序表(R1[0].key <= R[1].key <= ... R[j - 1].key)中逐個插入記錄的操作，進行了n - 1趟，每趟操作分為比較關鍵字和移動記錄，而比較的次數(shù)和移動的次數(shù)取決于待排序列按關鍵字的初始排列。
  • 最好情況：待排序列已按關鍵字正序，比較次數(shù)Cmin = n - 1 次，移動次數(shù)Mmin = 0 次

  • 最壞情況：待排序列已按關鍵字逆序


    最壞情況比較和移動次數(shù).png

  • 平均情況：待排序可能出現(xiàn)的各種排列的概率相同


    平均情況比較和移動次數(shù).png
  • 直接插入算法的穩(wěn)定性：是穩(wěn)定的排序方法。

空間復雜度

  • 需要一個輔助控件(監(jiān)視哨)，輔助空間復雜度S(n)=O(1)，此算法是就地排序

折半插入排序

直接插入排序算法漸變，且容易實現(xiàn)。當排序的數(shù)量n很小時，這是一種很好的排序方法。但是，通常待排序序列中的記錄數(shù)量n很大，則不宜采用直接插入排序。折半插入排序（binary insertion sort）是對插入排序算法的一種改進，由于排序算法過程中，就是不斷的依次將元素插入前面已排好序的序列中。由于前半部分為已排好序的數(shù)列，這樣我們不用按順序依次尋找插入點，可以采用折半查找的方法來加快尋找插入點的速度。

算法思想：

折半插入排序

  • 向有序表中插入一個記錄，插入位置是通過對有序表中記錄按關鍵字逐個比較得到的
  • 平均情況下總比較次數(shù)n2/4
  • 通過二分有序表來確定插入位置，既一次比較，通過待插入記錄與有序表居中的記錄按關鍵字比較，將有序列一份為二，下次比較在其中一個有序子表中進行，將字表又一分為二。這樣繼續(xù)下去，直到要比較字表中只有一個記錄時，比較一次就確定了插入位置

算法流程圖

折半插入排序流程圖

算法實現(xiàn)

算法分析

時間復雜度 O(n2)

折半插入排序算法是一種穩(wěn)定的排序算法，比直接插入算法明顯減少了關鍵字之間比較的次數(shù)，因此速度比直接插入排序算法快，但記錄移動的次數(shù)沒有變，所以折半插入排序算法的時間復雜度仍然為O(n^2)，與直接插入排序算法相同。附加空間O(1)。

  • 穩(wěn)定性：是穩(wěn)定排序

空間復雜度

  • 需要一個輔助控件，附加空間O(1)。，此算法是就地排序

希爾排序

希爾排序(Shell Sort)是插入排序的一種。也稱縮小增量排序，是直接插入排序算法的一種更高效的改進版本。希爾排序是非穩(wěn)定排序算法。

算法思想：

希爾排序

  • 選擇一個步長序列t(1),t(2),...,t(<sub >k),其中t(i) > t(j), t(k) = 1。
  • 按步長序列個數(shù)k，對序列進行k趟排序
  • 每趟排序根據(jù)對應的步長t(i),將待排序列分隔成若干長度為m的子序列，分別對各子表進行直接插入排序。僅步長因子為1時，整個序列作為一個表來處理，表長度即為整個序列的長度。

算法流程圖

希爾排序流程圖

p:步長因子 顏色相同：每趟排序根據(jù)對應的步長p,將待排序列分隔成若干長度為m的子序列，分別對各子表進行直接插入排序。僅步長因子為1時，整個序列作為一個表來處理，表長度即為整個序列的長度。

算法實現(xiàn)

    #include<stdio.h>
    #include<math.h>
     
    #define MAXNUM 10
     
    void main()
    {
        void shellSort(int array[],int n,int t);//t為排序趟數(shù)
        int array[MAXNUM],i;
        for(i=0;i<MAXNUM;i++)
            scanf("%d",&array[i]);
        shellSort(array,MAXNUM,int(log(MAXNUM+1)/log(2)));//排序趟數(shù)應為log2(n+1)的整數(shù)部分
        for(i=0;i<MAXNUM;i++)
            printf("%d ",array[i]);
        printf("\n");
    }
     
    //根據(jù)當前增量進行插入排序
    void shellInsert(int array[],int n,int dk)
    {
        int i,j,temp;
        for(i=dk;i<n;i++)//分別向每組的有序區(qū)域插入
        {
            temp=array[i];
            for(j=i-dk;(j>=i%dk)&&array[j]>temp;j-=dk)//比較與記錄后移同時進行
                array[j+dk]=array[j];
            if(j!=i-dk)
                array[j+dk]=temp;//插入
        }
    }
     
    //計算Hibbard增量
    int dkHibbard(int t,int k)
    {
        return int(pow(2,t-k+1)-1);
    }
     
    //希爾排序
    void shellSort(int array[],int n,int t)
    {
        void shellInsert(int array[],int n,int dk);
        int i;
        for(i=1;i<=t;i++)
            shellInsert(array,n,dkHibbard(t,i));
    }

或：
#include <stdio.h>

#define MAXNUM 10

void shellSort(int a[],int n) {

int i,j,gap,x;
gap = n / 2; // 初始步長一般為待排序文件長度的一半
while (gap > 0) {   // 當步長大于0時繼續(xù)排序

    for ( i = gap; i < n; i++) {
        // 從每個子序列的第一個位置開始比較
        j = i - gap;   // 
        while (j >= 0) 
            if (a[j] > a[j + gap]) { // (1) a[j]前面的元素，(2) a[j + gap]后面的元素，如果(1) > (2) 交換兩個元素的位置

                x = a[j];
                a[j] = a[j + gap];
                a[j + gap] = x;
                j = j - gap;  // 無符號，當前子序列的下一個結點
                printf("j--!%d",j);
            } else j = -1;  
    }
    gap =  gap / 2; // 步長減半
    
}
}

void main() {
int a[MAXNUM] = {26,76,83,56,13,29,50,78,30,11};

shellSort(a,MAXNUM);

for (int i = 0; i < MAXNUM; i++) {
    
    printf("%d ",a[i]);
}
}

算法分析

時間復雜度 O(n2)

希爾排序是按照不同步長對元素進行，當剛開始元素很無序的時候，步長最大，所以插入排序的元素個數(shù)很少，速度很快；當元素基本有序了，步長很小，插入排序?qū)τ谟行虻男蛄行屎芨?。所以，希爾排序的時間復雜度]會比o(n^2)好一些。

  • 穩(wěn)定性：是穩(wěn)定排序

空間復雜度

  • 需要一個輔助控件，附加空間O(1)。，此算法是就地排序

冒泡排序

冒泡排序：

  • 冒泡排序
  • 優(yōu)化冒泡排序

算法思想：

  • j = length - 1(j為數(shù)組最后一個元素)
  • 若i >= j ，一趟冒泡結束
  • 若a[j] < a[j - 1] 交換
  • i＋＋下一趟

算法流程圖

冒泡排序流程圖

算法實現(xiàn)

#include <stdio.h>

#define MAXNUM 10

void bubbleSort(int a[],int length) {

    for (int i = 0; i < length - 1; ++i)  
        // 趟數(shù)，最后一趟已排序
        for (int j = length - 1;j > i;--j) {
            // 如果前一個元素大于后一個元素則交換
            if (a[j] < a[j - 1]) {
                a[j] = a[j] ^ a[j - 1];
                a[j - 1] = a[j] ^ a[j - 1];
                a[j] = a[j] ^ a[j - 1];
            }

        }
    
}

void main() {
    
    int a[MAXNUM] = {26,76,83,56,13,29,50,78,30,11};

    bubbleSort(a,sizeof(a) / sizeof(int));

    for (int i = 0; i < MAXNUM ; i++) {
        printf("%d ",a[i]);
    }
}

優(yōu)化冒泡排序代碼：

    #include <stdio.h>

    #define MAXNUM 10

    void bubbleSort(int a[],int length) {
        int recordSwapValue;
        int swapValue = 0;
        for (int i = 0; i < length - 1;i++) {
            recordSwapValue = swapValue;  //i... recordSwapValue的索引為有序
            for (int j = length - 1; j > recordSwapValue; j--) { //　R[i...recordSwapValue]或R[0...recordSwapValue]區(qū)間有序的,遍歷區(qū)間由R[i...length] 縮減到[recordSwapValue..length]。
                if (a[i] > a[i - 1]) {
                    a[j] = a[j] ^ a[j - 1];
                    a[j - 1] = a[j] ^ a[j - 1];
                    a[j] = a[j] ^ a[j - 1];
                    swapValue = j; // 記錄交換位置的索引值
                }
            }
            // 如果值相當，整個過程
            if (recordSwapValue == swapValue) {
                break;
            }

        }
    }

    void main() {
        
        int a[MAXNUM] = {26,76,83,56,13,29,50,78,30,11};

        bubbleSort(a,sizeof(a) / sizeof(int));

        for (int i = 0; i < MAXNUM ; i++) {
            printf("%d ",a[i]);
        }
    }

算法分析

時間復雜度 O(n2)

  • 向有序表(R1[0].key <= R[1].key <= ... R[j - 1].key)中逐個插入記錄的操作，進行了n - 1趟，每趟操作分為比較關鍵字和移動記錄，而比較的次數(shù)和移動的次數(shù)取決于待排序列按關鍵字的初始排列。
  • 最好情況：待排序列已按關鍵字正序，比較次數(shù)Cmin = n - 1 次，移動次數(shù)Mmin = 0 次

  • 最壞情況：待排序列已按關鍵字逆序


    最壞情況比較和移動次數(shù).png

  • 平均情況：待排序可能出現(xiàn)的各種排列的概率相同


    平均情況比較和移動次數(shù)

*　冒泡排序的穩(wěn)定性：是穩(wěn)定的排序方法。

空間復雜度 Ｏ（１）

  • 需要一個輔助控件(監(jiān)視哨)，輔助空間復雜度S(n)=O(1)，此算法是就地排序

快速排序

算法思想：

快速排序
*　快速排序是通過關鍵字、交換記錄，以某個記錄為界（該記錄稱謂支點），將待排序列分成兩部分。其中一部分所有記錄的關鍵字大于支點記錄的關鍵字，另一部分所有記錄的關鍵字小于支點記錄的關鍵字。將待排序列按關鍵字以支點記錄分成兩部分的過程，稱為一次劃分。對各部分不斷劃分，直到整個序列按關鍵字有序，整個排序過程可以遞歸。

算法描述

設 1 <= p < q <= n　，r[p], r[p + 1]，...，r[q]為待排序列

  • (1) low = p;high = q;
    r[0] = r[low]; // 取第一個記錄為支點記錄，low位置暫設為支點空位
  • (2) 若low = high, 支點空位確定，即為low
    r[low] = r[0];
    否則, low < high搜索需要交換的記錄，并交換之。
  • (３)若low < high 且r[high].key >= r[0].key // 從high所指向位置向前搜索，至多到low + 1 位置
    high = high - 1；　轉(zhuǎn)3 // 尋找r[high].key < r[0].key
    r[low] = r[high]; // 找到r[high].key

未完待續(xù)

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

相關閱讀更多精彩內(nèi)容

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