程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> C++線性時光的排序算法剖析

C++線性時光的排序算法剖析

編輯:關於C++

C++線性時光的排序算法剖析。本站提示廣大學習愛好者:(C++線性時光的排序算法剖析)文章只能為提供參考,不一定能成為您想要的結果。以下是C++線性時光的排序算法剖析正文


後面的文章曾經引見了幾種排序算法,如拔出排序(直接拔出排序,折半拔出排序,希爾排序)、交流排序(冒泡排序,疾速排序)、選擇排序(簡略選擇排序,堆排序)、2-路合並排序(可以參考前一篇文章:各類外部排序算法的完成)等,這些排序算法都有一個配合的特色,就是基於比擬。

本文將引見三種非比擬的排序算法:計數排序,基數排序,桶排序。它們將沖破比擬排序的Ω(nlgn)下界,以線性時光運轉。

1、比擬排序算法的時光下界

所謂的比擬排序是指經由過程比擬來決議元素間的絕對順序。

“定理:關於含n個元素的一個輸出序列,任何比擬排序算法在最壞情形下,都須要做Ω(nlgn)次比擬。”
也就是說,比擬排序算法的運轉速度不會快於nlgn,這就是基於比擬的排序算法的時光下界。

經由過程決議計劃樹(Decision-Tree)可以證實這個定理,關於決議計劃樹的界說和證實進程在這裡就不贅述了。讀者可以本身去查找材料,這裡推舉年夜家看一看麻省理工學院地下課:算法導論的《MIT地下課:線性時光排序》。

依據下面的定理,我們曉得任何比擬排序算法的運轉時光不會快於nlgn。那末我們能否可以沖破這個限制呢?固然可以,接上去我們將引見三種線性時光的排序算法,它們都不是經由過程比擬來排序的,是以,下界Ω(nlgn)對它們不實用。

2、計數排序(Counting Sort)

計數排序的根本思惟就是對每個輸出元素x,肯定小於x的元素的個數,如許便可以把x直接放在它在終究輸入數組的地位上,例如:

 

算法的步調年夜致以下:

①.找出待排序的數組中最年夜和最小的元素

②.統計數組中每一個值為i的元素湧現的次數,存入數組C的第i項

③.對一切的計數累加(從C中的第一個元素開端,每項和前一項相加)

④.反向填充目的數組:將每一個元素i放在新數組的第C(i)項,每放一個元素就將C(i)減去1

C++代碼以下:

/************************************************************************* 
  > File Name: CountingSort.cpp 
  > Author: SongLee 
 ************************************************************************/ 
#include<iostream> 
using namespace std; 
 
/* 
 *計數排序:A和B為待排和目的數組,k為數組中最年夜值,len為數組長度 
 */ 
void CountingSort(int A[], int B[], int k, int len) 
{ 
  int C[k+1]; 
  for(int i=0; i<k+1; ++i) 
    C[i] = 0; 
  for(int i=0; i<len; ++i) 
    C[A[i]] += 1; 
  for(int i=1; i<k+1; ++i) 
    C[i] = C[i] + C[i-1]; 
  for(int i=len-1; i>=0; --i) 
  { 
    B[C[A[i]]-1] = A[i]; 
    C[A[i]] -= 1; 
  } 
} 
 
/* 輸入數組 */ 
void print(int arr[], int len) 
{ 
  for(int i=0; i<len; ++i) 
    cout << arr[i] << " "; 
  cout << endl; 
} 
 
/* 測試 */ 
int main() 
{ 
  int origin[8] = {4,5,3,0,2,1,15,6}; 
  int result[8]; 
  print(origin, 8); 
  CountingSort(origin, result, 15, 8); 
  print(result, 8); 
  return 0; 
}

當輸出的元素是0到k之間的整數時,時光龐雜度是O(n+k),空間龐雜度也是O(n+k)。當k不是很年夜而且序列比擬集中時,計數排序是一個很有用的排序算法。計數排序是一個穩固的排序算法。

能夠你會發明,計數排序仿佛饒了點彎子,好比當我們方才統計出C,C[i]可以表現A中值為i的元素的個數,此時我們直接次序地掃描C,便可以求出排序後的成果。切實其實是如許,不外這類辦法不再是計數排序,而是桶排序,確實地說,是桶排序的一種特別情形。

3、桶排序(Bucket Sort)

桶排序(Bucket Sort)的思惟是將數組分到無限數目的桶子裡。每一個桶子再個體排序(有能夠再應用其余排序算法)。當要被排序的數組內的數值是平均分派的時刻,桶排序可以以線性時光運轉。桶排序進程動畫演示:Bucket Sort,桶排序道理圖以下:

 

C++代碼以下:

/************************************************************************* 
  > File Name: BucketSort.cpp 
  > Author: SongLee 
 ************************************************************************/ 
#include<iostream> 
using namespace std; 
 
/* 節點 */ 
struct node 
{ 
  int value; 
  node* next; 
}; 
 
/* 桶排序 */ 
void BucketSort(int A[], int max, int len) 
{ 
  node bucket[len]; 
  int count=0; 
  for(int i=0; i<len; ++i) 
  { 
    bucket[i].value = 0; 
    bucket[i].next = NULL; 
  } 
   
  for(int i=0; i<len; ++i) 
  { 
    node *ist = new node(); 
    ist->value = A[i]; 
    ist->next = NULL; 
    int idx = A[i]*len/(max+1); // 盤算索引 
    if(bucket[idx].next == NULL) 
    { 
      bucket[idx].next = ist; 
    } 
    else /* 按年夜小次序拔出鏈表響應地位 */ 
    { 
      node *p = &bucket[idx]; 
      node *q = p->next; 
      while(q!=NULL && q->value <= A[i]) 
      { 
        p = q; 
        q = p->next; 
      } 
      ist->next = q; 
      p->next = ist; 
    } 
  } 
 
  for(int i=0; i<len; ++i) 
  { 
    node *p = bucket[i].next; 
    if(p == NULL) 
      continue; 
    while(p!= NULL) 
    { 
      A[count++] = p->value; 
      p = p->next; 
    } 
  } 
} 
 
/* 輸入數組 */ 
void print(int A[], int len) 
{ 
  for(int i=0; i<len; ++i) 
    cout << A[i] << " "; 
  cout << endl; 
} 
 
/* 測試 */ 
int main() 
{ 
  int row[11] = {24,37,44,12,89,93,77,61,58,3,100}; 
  print(row, 11); 
  BucketSort(row, 235, 11); 
  print(row, 11); 
  return 0; 
} 

4、基數排序(Radix Sort)

基數排序(Radix Sort)是一種非比擬型排序算法,它將整數按位數切割成分歧的數字,然後按每一個位分離停止排序。基數排序的方法可以采取MSD(Most significant digital)或LSD(Least significant digital),MSD是從最高有用位開端排序,而LSD是從最低有用位開端排序。

固然我們可以采取MSD方法排序,按最高有用位停止排序,將最高有用位雷同的放到一堆,然後再按下一個有用位對每一個堆中的數遞歸地排序,最初再將成果歸並起來。然則,如許會發生許多中央堆。所以,平日基數排序采取的是LSD方法。

LSD基數排序完成的根本思緒是將一切待比擬數值(正整數)同一為異樣的數位長度,數位較短的數後面補零。然後,從最低位開端,順次停止一次排序。如許從最低位排序一向到最高位排序完成今後, 數列就釀成一個有序序列。須要留意的是,對每個數位停止排序的算法必需是穩固的,不然就會撤消前一次排序的成果。平日我們應用計數排序或許桶排序作為基數排序的幫助算法。基數排序進程動畫演示:Radix Sort

C++完成(應用計數排序)以下:

/************************************************************************* 
  > File Name: RadixSort.cpp 
  > Author: SongLee 
 ************************************************************************/ 
#include<iostream> 
using namespace std; 
 
// 找出整數num第n位的數字 
int findIt(int num, int n) 
{ 
  int power = 1; 
  for (int i = 0; i < n; i++) 
  { 
    power *= 10; 
  } 
  return (num % power) * 10 / power; 
} 
 
// 基數排序(應用計數排序作為幫助) 
void RadixSort(int A[], int len, int k) 
{ 
  for(int i=1; i<=k; ++i) 
  { 
    int C[10] = {0};  // 計數數組 
    int B[len];    // 成果數組 
 
    for(int j=0; j<len; ++j) 
    { 
      int d = findIt(A[j], i); 
      C[d] += 1; 
    } 
 
    for(int j=1; j<10; ++j) 
      C[j] = C[j] + C[j-1]; 
 
    for(int j=len-1; j>=0; --j) 
    { 
      int d = findIt(A[j], i); 
      C[d] -= 1; 
      B[C[d]] = A[j]; 
    } 
     
    // 將B中排好序的拷貝到A中 
    for(int j=0; j<len; ++j) 
      A[j] = B[j]; 
  } 
} 
 
// 輸入數組 
void print(int A[], int len) 
{ 
  for(int i=0; i<len; ++i) 
    cout << A[i] << " "; 
  cout << endl; 
} 
 
// 測試 
int main() 
{ 
  int A[8] = {332, 653, 632, 5, 755, 433, 722, 48}; 
  print(A, 8); 
  RadixSort(A, 8, 3); 
  print(A, 8); 
  return 0; 
}

基數排序的時光龐雜度是 O(k·n),個中n是排序元素個數,k是數字位數。留意這不是說這個時光龐雜度必定優於O(nlgn),由於n能夠具有比擬年夜的系數k。

別的,基數排序不只可以對整數排序,也能夠對有多個症結字域的記載停止排序。例如,依據三個症結字年、月、日來對日期停止排序。

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved