數(shù)據(jù)結(jié)構(gòu)05-排序和查找

1：排序算法分為如下5類：

  1. 插入排序：普通插入排序，shell排序等；
  2. 選擇排序：普通選擇排序，堆排序；
  3. 交換排序：冒泡法，快速排序；
  4. 歸并排序：
  5. 基數(shù)排序。

待排數(shù)據(jù)為：9,6,2,3,10，有小到大排列；下面來(lái)實(shí)現(xiàn)上面的各種排序算法

2：插入排序(希爾排序)

基本插入排序：每次將一個(gè)待排序的數(shù)據(jù)元素，插入到前面已經(jīng)排好序的數(shù)列中的適當(dāng)位置，使數(shù)列依然有序；直到待排序數(shù)據(jù)元素全部插入完為止。

穩(wěn)定排序：指待排序序列中可能存在兩個(gè)或兩個(gè)以上關(guān)鍵字相等的記錄。排序前的序列中Ri領(lǐng)先于Rj（即i<j）。若在排序后的序列中Ri仍然領(lǐng)先于Rj，則稱所用的方法是穩(wěn)定的。比如序列：3,6,1a,2,1b,8,4,7，其中1a和1b的值都是1，為了區(qū)別，1a在1b的前面。如果排序之后，1a依然在1b的前面，那么就是穩(wěn)定排序，否則就是非穩(wěn)定排序。

//基本插入排序
//基本插入排序的時(shí)間復(fù)雜度為O(n^2)，是一種穩(wěn)定排序算法
void insert_sort(int a[], int n) {
    int i, j, tmp;
    
    for(int i=1; i<n; i++) {
        tmp = a[i];
        j = i - 1;
        
        while(tmp < a[j]) {//當(dāng)tmp大于等于a[j]時(shí)不用交換
            a[j+1] = a[j];
            j--;
        }
        
        a[j+1] = tmp;
    }
}

希爾排序：是一種經(jīng)過(guò)改進(jìn)的插入排序算法。

希爾排序基本思想：先將整個(gè)待排元素序列分割成若干個(gè)子序列（由相隔某個(gè)“增量”的元素組成的）分別進(jìn)行直接插入排序，然后依次縮減增量再進(jìn)行排序，待整個(gè)序列中的元素基本有序（增量足夠?。r(shí)，再對(duì)全體元素進(jìn)行一次直接插入排序。因?yàn)橹苯硬迦肱判蛟谠鼗居行虻那闆r下（接近最好情況），效率是很高的，因此希爾排序在時(shí)間效率上比前兩種方法有較大提高。具體做法：首先確定一組增量d0，d1，d2，d3，...,dt-1()其中n>d0>d1>...>dt-1=1)，對(duì)于i =0,1,2,...,t-1,依次進(jìn)行下面的各趟處理：根據(jù)當(dāng)前增量di將n個(gè)元素分成di個(gè)組，每組中元素的下標(biāo)相隔為di;再對(duì)各組中元素進(jìn)行直接插入排序。

//希爾排序的實(shí)現(xiàn)算法：
//希爾排序的復(fù)雜度為：O(n^1.25)，它不是穩(wěn)定排序。
void shellsort(int a[], int n) {
     int i, j, gap, tmp;
     gap = n/2;

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

              while (j > 0) {
                   if (a[j] > a[j+gap]) {
                       tmp = a[j];
                       a[j] = a[j+gap];
                       a[j+gap] = a[j];
                   } else {
                       j = 0;
                   }
              }
         }

         gap /= 2;
     }
}

3：選擇排序(堆排序)

選擇排序：每一次都是從待排序的數(shù)據(jù)元素中選出最小（或最大）的一個(gè)元素，順序放在已排好序的數(shù)列的最后，直到全部待排序的數(shù)據(jù)元素排完。

//簡(jiǎn)單選擇排序
//時(shí)間復(fù)雜度為O(n^2)，它是不穩(wěn)定排序。
void selectsort(int a[], int n) {
       int i, j, k, tmp;

       for (i = 0; i < n-1; i++) {
              k = i;

              for (j = i + 1; j < n; j++) {
                     if (a[j] < a[k])
                            k = j;
              }

              if (k != i) {
                     tmp = a[i];
                     a[i] = a[k];
                     a[k] = tmp;
              }
       }
}

堆排序：是一樹(shù)形選擇排序，在排序過(guò)程中，將R[1..N]看成是一顆完全二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)，利用完全二叉樹(shù)中雙親結(jié)點(diǎn)和孩子結(jié)點(diǎn)之間的內(nèi)在關(guān)系來(lái)選擇最小的元素。

//堆排序
//時(shí)間復(fù)雜度為O(nlogn)，是不穩(wěn)定排序
void sfilter(int a[], int l, int m) {
     int i, j x;
     i = l;
     j = 2 * i;
     x = a[i];

     while ( j <= m) {
         if (j < m && a[j] < a[j+1])
              j++;

         if (x < a[j]) {
              a[i] = a[j];
              i = j;
              j = 2 * i;
         } else {
              j = m + 1;
         }
     }

     a[i] = x;
}

void heapsort(int a[], int n) {
     int i, w;

     for (i = n/2; i >= 1; i--)
         sfilter(a, i, n);

     for (i = n; i >= 2; i--) {
         w = a[i];
         a[i] = a[1];
         a[1] = w;
         sfilter(a, 1, i - 1);
     }
}

4：交換排序(冒泡排序/快排)

交換排序：兩兩比較待排序記錄的關(guān)鍵字，發(fā)現(xiàn)兩個(gè)記錄的次序相反時(shí)即進(jìn)行交換，直到?jīng)]有反序的記錄為止。

首先來(lái)看著名的交換排序算法：冒泡法。冒泡法的排序思想是：從第n個(gè)元素(a[n-1])開(kāi)始，掃描數(shù)組，比較相鄰兩個(gè)元素，如果次序相反則交換。如此反復(fù)，直到?jīng)]有任何兩個(gè)違反相反原則的元素

//冒泡排序：
//時(shí)間復(fù)雜度為O(n^2)，它是穩(wěn)定排序
void bubble_sort(int a[], int n) {
       int i, j, tmp;

       for (i = 0; i < n-1; i++) {
              for (j = n-1; j >= i+1; j--) {
                     if (a[j] < a[j-1]) {
                            tmp = a[j];
                            a[j] = a[j-1];
                            a[j-1] = tmp;
                     }
              }
       }
}

快速排序：在當(dāng)前無(wú)序區(qū)R[1..H]中任取一個(gè)數(shù)據(jù)元素作為比較的“基準(zhǔn)”(不妨記為X，R[1])，用此基準(zhǔn)將當(dāng)前無(wú)序區(qū)劃分為左右兩個(gè)較小的無(wú)序區(qū)：R[1..I-1]和R[I+1..H]，且左邊的無(wú)序子區(qū)中數(shù)據(jù)元素均小于等于基準(zhǔn)元素，右邊的無(wú)序子區(qū)中數(shù)據(jù)元素均大于等于基準(zhǔn)元素，而基準(zhǔn)X則位于最終排序的位置上，即R[1..I-1]≤X≤RI+ 1..H，當(dāng)R[1..I-1]和R[I+1..H]均非空時(shí)，分別對(duì)它們進(jìn)行上述的劃分過(guò)程，直至所有無(wú)序子區(qū)中的數(shù)據(jù)元素均已排序?yàn)橹埂?/p>

找一個(gè)數(shù)X（比如頭一個(gè)元素）做基準(zhǔn)，右邊比X小的移動(dòng)到左邊，左邊比X大的移動(dòng)到右邊，最后空出的位置就是X自己的位置

快速排序的時(shí)間復(fù)雜度為O(nlogn)，最壞情況為O(n^2)。對(duì)于大的、亂數(shù)序列一般相信是最快的已知排序。待排記錄序列按關(guān)鍵字順序有序時(shí)，直接插入排序和起泡排序能達(dá)到O(n)的時(shí)間復(fù)雜度，而對(duì)于快速排序而言，這是最不好的情況。對(duì)于很小的數(shù)組（如N<=20），快速排序不如插入排序好。

void quickSort(int a[],int left,int right) {
   int i,j,temp;
   i=left;
   j=right;
   temp=a[left];

   if(left>right)
      return;

   while(i<j) {/*找到最終位置*/ 
      while(a[j]>=temp && j>i)
         j--;

      if(j>i)
         a[i++]=a[j];

      while(a[i]<=temp && j>i)
          i++;

      if(j>i)
          a[j--]=a[i];
   }

   a[i]=temp;
   quickSort(a,left,i-1);/*遞歸左邊*/
   quickSort(a,i+1,right);/*遞歸右邊*/
}

void qsort(int a[], int n) {
       quickSort(a, 0, n-1);

}

5：排序時(shí)間復(fù)雜度空間復(fù)雜度比較

排序算法 平均時(shí)間 最壞情況 輔助存儲(chǔ) 是否是穩(wěn)定算法
簡(jiǎn)單排序 O(n^2) O(n^2) O(1)
快速排序 O(nlogn) O(n^2) O(logn)
堆排序 O(nlogn) O(nlogn) 0(1)
歸并排序 O(nlogn) O(nlogn) O(n)
基數(shù)排序 O(d(n+rd)) O(d(n+rd)) O(rd)

6：查找(折半查找/HASH查找)

查找：將表中記錄的關(guān)鍵字與查找關(guān)鍵字比較，如果兩者相等，則查找成功，返回查找位置。

包含：鏈表查找，數(shù)組查找，二叉樹(shù)查找，hash

6.1: 折半查找

折半查找：又叫二分查找，首先，假設(shè)表中元素是按升序排列，將表中間位置記錄的關(guān)鍵字與查找關(guān)鍵字比較，如果兩者相等，則查找成功；否則利用中間位置記錄將表分成前、后兩個(gè)子表，如果中間位置記錄的關(guān)鍵字大于查找關(guān)鍵字，則進(jìn)一步查找前一子表，否則進(jìn)一步查找后一子表。重復(fù)以上過(guò)程，直到找到滿足條件的記錄，使查找成功，或直到子表不存在為止，此時(shí)查找不成功。

image.png

注意：折半查找必須滿足兩個(gè)條件：一，元素必須是連續(xù)存儲(chǔ)；二，元素必須有序。時(shí)間復(fù)雜度：O(logn)

//折半查找算法：
//a為存放數(shù)據(jù)的有序表，n為數(shù)據(jù)元素個(gè)數(shù)，k為要查找的元素
int bin_search(int a[], int n, int k) {
     int low, high, mid, i;

     low = 0;
     high = n-1;

     while (low <= high) {
         mid = (low + high)/2;

         if (a[mid] < k)
              low = mid + 1;
         else if (a[mid] > k)
              high = mid - 1;
         else {
              return mid;
         }
     }

     return -1;
}

//遞歸版本：

 

int iter_biSearch(int data[], const int x, int beg, int last) {  
    int mid = -1;  
    mid = (beg + last) / 2;  

    if (x == data[mid]) {  
        return mid;  
    } else if (x < data[mid]) {  
        return iter_biSearch(data, x, beg, mid - 1);  
    } else if (x > data[mid]) {  
        return iter_biSearch(data, x, mid + 1, last);  
    }  

    return -1;  
} 

int bin_search2(int a[], int n, int k) {
    return  iter_biSearch(a,k,0,n-1);
}

6.2：Hash表

Hash表用于存放key-value數(shù)據(jù)。比如一個(gè)學(xué)生的成績(jī)，那么學(xué)生的學(xué)號(hào)可以當(dāng)做key，成績(jī)當(dāng)做value，存放與hash表中。

image.png

Hash查找必須提供一個(gè)Hash函數(shù)，用于通過(guò)Key來(lái)計(jì)算數(shù)據(jù)存放在hash表中的位置。一般hash函數(shù)可以設(shè)計(jì)為key%N，其中N為hash表中元素的個(gè)數(shù)（一般為質(zhì)數(shù)）。

假如HASH表的大小為N，那么Hash函數(shù)為：Hash(key)=key%N

當(dāng)對(duì)于不同的兩個(gè)key，計(jì)算出來(lái)的hash值可能相同，在相同的時(shí)候，就叫做hash沖突。解決hash沖突的方法不止一種，比如通過(guò)鏈?zhǔn)椒ń鉀Q，即將所有含有相同hash值的數(shù)據(jù)存放在同一個(gè)鏈表中，而將鏈表的頭結(jié)點(diǎn)存放在HASH表中。

所謂hash查找，就是通過(guò)對(duì)應(yīng)的key，按照hash函數(shù)，計(jì)算出數(shù)據(jù)在hash表中的位置。Hash查找的復(fù)雜度為O(1)，所以具有較高的查找效率。

6.3：二叉搜索樹(shù)查找

typedef struct _node {
     int data;
     struct _node *left;
     struct _node *right;
} node, btree;

btree *search(btree *b, int x) {
     if (b == NULL) {
         return NULL;
     } else {
         if (b->data == x) {
              return b;
         } else if (x < b->data) {
              return (search(b->left));
         } else {
              return (search(b->right));
         }
     }
}
?著作權(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)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書(shū)系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

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

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