基數排序演算法python

⑴ python分類演算法有哪些

常見的分類演算法有：

• K近鄰演算法

• 決策樹

• 樸素貝葉斯

• SVM

• Logistic Regression

⑵ 關於基數(桶)排序演算法

既然每次排一個位元組, 一個位元組有256種取值可能, 就需要256個桶

⑶ 演算法設計：輸入N個只含一位數字的整數,試用基數排序的方法,對這N個數排序.

typedef struct
{
int key;
int next;
}SLRecType;
SLRecType R[N+1];
typedef struct
{
int f,e;
}SLQueue;
SLQueue B[10];
int Radixsort(SLRecType R[],int n)//設關鍵字已輸入到R數組
{
int k,t;
for(i=1;i<n;i++)R[i].next=i+1;
R[n].next=-1;p=1; //-1表示靜態鏈表的結束
for(i=0;i<=9;i++){B[i].f=-1;b[i].e=-1} //設置隊頭隊尾指針初值
while(p!=-1) //一趟分配
{
k=R[p].key; //取關鍵字
if (B[k].f==-1)B[k].f=p; //修改隊頭指針
else R[B[k].e].next=p;
B[k].e=p;
p=R[p].next; //一趟收集
}
i=0;
while(B[i].f==-1)i++;
t=B[i].e;p=B[i].f;
while(i<9)
{
i++;
if( B[i].f!=-1)
{
R[t].next=B[i].f;
t= B[i].e;
}
}
R[].next=-1;
return p; //返回第一個記錄指針
}

⑷ 數據結構裡面的「基數排序」到底是什麼

基數排序的方式可以採用LSD（Least significant digital）或MSD（Most significant digital），LSD的排序方式由鍵值的最右邊開始，而MSD則相反，由鍵值的最左邊開始。 以LSD為例，假設原來有一串數值如下所示： 73, 22, 93, 43, 55, 14, 28, 65, 39, 81 首先根據個位數的數值，在走訪數值時將它們分配至編號0到9的桶子中： 0 1 81 2 22 3 73 93 43 4 14 5 55 65 6 7 8 28 9 39 接下來將這些桶子中的數值重新串接起來，成為以下的數列： 81, 22, 73, 93, 43, 14, 55, 65, 28, 39 接著再進行一次分配，這次是根據十位數來分配： 0 1 14 2 22 28 3 39 4 43 5 55 6 65 7 73 8 81 9 93 接下來將這些桶子中的數值重新串接起來，成為以下的數列： 14, 22, 28, 39, 43, 55, 65, 73, 81, 93 這時候整個數列已經排序完畢；如果排序的對象有三位數以上，則持續進行以上的動作直至最高位數為止。 LSD的基數排序適用於位數小的數列，如果位數多的話，使用MSD的效率會比較好，MSD的方式恰與LSD相反，是由高位數為基底開始進行分配，其他的演算方式則都相同。
編輯本段效率分析
時間效率：設待排序列為n個記錄，d個關鍵碼，關鍵碼的取值范圍為radix，則進行鏈式基數排序的時間復雜度為O(d(n+radix))，其中，一趟分配時間復雜度為O(n)，一趟收集時間復雜度為O(n)，共進行d趟分配和收集。 空間效率：需要2*radix個指向隊列的輔助空間，以及用於靜態鏈表的n個指針。
編輯本段實現方法
最高位優先(Most Significant Digit first)法，簡稱MSD法：先按k1排序分組，同一組中記錄，關鍵碼k1相等，再對各組按k2排序分成子組，之後，對後面的關鍵碼繼續這樣的排序分組，直到按最次位關鍵碼kd對各子組排序後。再將各組連接起來，便得到一個有序序列。 最低位優先(Least Significant Digit first)法，簡稱LSD法：先從kd開始排序，再對kd-1進行排序，依次重復，直到對k1排序後便得到一個有序序列。
編輯本段實現
* C
#include <stdio.h> #include <stdlib.h> int main(){ int data[10]={73,22,93,43,55,14,28,65,39,81}; int temp[10][10]={0}; 基數排序演算法
int order[10]={0}; int i,j,k,n,lsd; k=0;n=1; printf("\n排序前: "); for (i=0;i<10;i++) printf("%d ",data[i]); putchar('\n'); while (n<=10){ for (i=0;i<10;i++){ lsd=((data[i]/n)%10); temp[lsd][order[lsd]]=data[i]; order[lsd]++; } printf("\n重新排列: "); for (i=0;i<10;i++){ if(order[i]!=0) for (j=0;j<order[i];j++){ data[k]=temp[i][j]; printf("%d ",data[k]); k++; } order[i]=0; } n*=10; k=0; } putchar('\n'); printf("\n排序後: "); for (i=0;i<10;i++) printf("%d ",data[i]); return 0; }
* Java
public class RadixSort { public static void sort(int[] number, int d) { int k=0; int n=1; int m=1; int[][] temp = new int[number.length][number.length]; int[] order = new int[number.length]; while(m <= d) { for(int i = 0; i < number.length; i++) { int lsd = ((number[i] / n) % 10); temp[lsd][order[lsd]] = number[i]; order[lsd]++; } for(int i = 0; i < d; i++) { if(order[i] != 0) for(int j = 0; j < order[i]; j++) { number[k] = temp[i][j]; k++; } order[i] = 0; } n *= 10; k = 0; m++; } } public static void main(String[] args) { int[] data = {73, 22, 93, 43, 55, 14, 28, 65, 39, 81, 33, 100}; RadixSort.sort(data, 10); for(int i = 0; i < data.length; i++) { System.out.print(data[i] + " "); } }
* pascal
program jspx; const n=8; type link=^node; node=record data:integer; next:link; end; var i,j,l,m,k:integer; a:array[1..n] of integer; s:string; q,head:array[0..9] of link; p,p1:link; begin writeln('Enter data:'); for i:=1 to n do read(a[i]); for i:=5 downto 1 do begin for j:=0 to 9 do begin new(head[j]); head[j]^.next:=nil; q[j]:=head[j] end; for j:=1 to n do begin str(a[j],s); for k:=1 to 5-length(s) do s:='0'+ s; m:=ord(s[i])-48; new(p); p^.data:=a[j]; p^.next:=nil; q[m]^.next:=p; q[m]:=p; end; l:=0; for j:=0 to 9 do begin p:=head[j]; while p^.next<>nil do begin l:=l+1;p1:=p;p:=p^.next;dispose(p1);a[l]:=p^.data; end; end; end; writeln('Sorted data:'); for i:= 1 to n do write(a[i]:6); end.
編輯本段c++實現基數排序
int maxbit(int data[],int n) //輔助函數，求數據的最大位數 { int d = 1; //保存最大的位數 int p =10; for(int i = 0;i < n; ++i) { while(data[i] >= p) { p *= 10; ++d; } } return d; } void radixsort(int data[],int n) //基數排序 { int d = maxbit(data,n); int * tmp = new int[n]; int * count = new int[10]; //計數器 int i,j,k; int radix = 1; for(i = 1; i<= d;i++) //進行d次排序 { for(j = 0;j < 10;j++) count[j] = 0; //每次分配前清空計數器 for(j = 0;j < n; j++) { k = (data[j]/radix)%10; //統計每個桶中的記錄數 count[k]++; } for(j = 1;j < 10;j++) count[j] = count[j-1] + count[j]; //將tmp中的位置依次分配給每個桶 for(j = n-1;j >= 0;j--) //將所有桶中記錄依次收集到tmp中 { k = (data[j]/radix)%10; count[k]--; tmp[count[k]] = data[j]; } for(j = 0;j < n;j++) //將臨時數組的內容復制到data中 data[j] = tmp[j]; radix = radix*10; } delete [] tmp; delete [] count; } C# 實現基數排序 using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace LearnSort { class Program { static void Main(string[] args) { int[] arr = CreateRandomArray(10);//產生隨機數組 Print(arr);//輸出數組 RadixSort(ref arr);//排序 Print(arr);//輸出排序後的結果 Console.ReadKey(); } public static void RadixSort(ref int[] arr) { int iMaxLength = GetMaxLength(arr); RadixSort(ref arr, iMaxLength); } //排序 private static void RadixSort(ref int[] arr, int iMaxLength) { List<int> list = new List<int>();//存放每次排序後的元素 List<int>[] listArr = new List<int>[10];//十個桶 char currnetChar;//存放當前的字元 比如說 某個元素123 中的2 string currentItem;//存放當前的元素 比如說 某個元素123 for (int i = 0; i < listArr.Length; i++)//給十個桶分配內存初始化。 listArr[i] = new List<int>(); for (int i = 0; i < iMaxLength; i++)//一共執行iMaxLength次，iMaxLength是元素的最大位數。 { foreach (int number in arr)//分桶 { currentItem = number.ToString();//將當前元素轉化成字元串 try { currnetChar = currentItem[currentItem.Length-i-1]; }//從個位向高位開始分桶 catch { listArr[0].Add(number); continue; }//如果發生異常，則將該數壓入listArr[0]。比如說5 是沒有十位數的，執行上面的操作肯定會發生越界異常的，這正是期望的行為，我們認為5的十位數是0，所以將它壓入listArr[0]的桶里。 switch (currnetChar)//通過currnetChar的值，確定它壓人哪個桶中。 { case '0': listArr[0].Add(number); break; case '1': listArr[1].Add(number); break; case '2': listArr[2].Add(number); break; case '3': listArr[3].Add(number); break; case '4': listArr[4].Add(number); break; case '5': listArr[5].Add(number); break; case '6': listArr[6].Add(number); break; case '7': listArr[7].Add(number); break; case '8': listArr[8].Add(number); break; case '9': listArr[9].Add(number); break; default: throw new Exception("unknow error"); } } for (int j = 0; j < listArr.Length; j++)//將十個桶里的數據重新排列，壓入list foreach (int number in listArr[j].ToArray<int>()) { list.Add(number); listArr[j].Clear();//清空每個桶 } arr = list.ToArray<int>();//arr指向重新排列的元素 //Console.Write("{0} times:",i); Print(arr);//輸出一次排列的結果 list.Clear();//清空list } } //得到最大元素的位數 private static int GetMaxLength(int[] arr) { int iMaxNumber = Int32.MinValue; foreach (int i in arr)//遍歷得到最大值 { if (i > iMaxNumber) iMaxNumber = i; } return iMaxNumber.ToString().Length;//這樣獲得最大元素的位數是不是有點投機取巧了... } //輸出數組元素 public static void Print(int[] arr) { foreach (int i in arr) System.Console.Write(i.ToString()+'\t'); System.Console.WriteLine(); } //產生隨機數組。隨機數的范圍是0到1000。 參數iLength指產生多少個隨機數 public static int[] CreateRandomArray(int iLength) { int[] arr = new int[iLength]; Random random = new Random(); for (int i = 0; i < iLength; i++) arr[i] = random.Next(0,1001); return arr; } } }

⑸ 數據結構===基數排序演算法設計/C或者C++

#include<stdio.h>
#include<malloc.h>
#define MaxQueueSize 100
typedef int KeyType;
typedef struct
{
KeyType key;
} DataType;
#include "SeqCQueue.h"
void RadixSort(DataType a[], int n,int m,int d)
{
int i, j, k, power = 1;
SeqCQueue *tub;

tub = (SeqCQueue *)malloc(sizeof(SeqCQueue )* d);
for(i = 0; i < d; i++)
QueueInitiate(&tub[i]);

//進行m次放和收
for(i = 0; i < m; i++)
{
if(i == 0) power = 1;
else power = power *d;

//將數據元素按關鍵字第k位的大小放到相應的隊列中
for(j = 0; j < n; j++)
{
k = a[j].key /power - (a[j].key /(power * d)) * d;
QueueAppend(&tub[k], a[j]);
}

//順序回收各隊列中的數據元素
for(j = 0, k = 0; j < d; j++)
while(QueueNotEmpty(tub[j]) != 0)
{
QueueDelete(&tub[j], &a[k]);
k++;
}
}
}
void main(void)
{
DataType test[]={710, 342, 45, 686, 6, 841, 429, 134, 68, 246};
int i, n = 10, m = 3, d = 10;

RadixSort(test, n, m, d);
for(i = 0; i < n; i++)
printf("%d ", test[i].key);
}

⑹ 幾種排序演算法分析及python實現

排序演算法針對不同情況有所不同，不能一概而論。
計算機課程的數據結構有幾個章節在討論排序，這里不能盡述，大致來說快速排序、希爾排序、堆排序、直接選擇排序不是穩定的排序演算法，而基數排序、冒泡排序、直接插入排序、折半插入排序、歸並排序是穩定的排序演算法。
直接網路「排序」，查看網路里的解釋，裡面有常用演算法和例子代碼，可以研究一下。

⑺ 跪求 基數排序演算法設計。要求：（1）設計基於順序隊列的基數排序函數。（2）設計一個測試主函數，測試所設

C語言源代碼：

#include<stdio.h>

#include<stdlib.h>

#defineN1024

intRadixCountSort(int*npIndex,intnMax,int*npData,intnLen)

{

int*pnCount=(int*)malloc(sizeof(int)*nMax);//保存計數的個數

inti=0;

for(i=0;i<nMax;++i)

{

pnCount[i]=0;

}

for(i=0;i<nLen;++i)//初始化計數個數

{

++pnCount[npIndex[i]];

}

for(i=1;i<10;++i)//確定不大於該位置的個數。

{

pnCount[i]+=pnCount[i-1];

}

int*pnSort=(int*)malloc(sizeof(int)*nLen);//存放零時的排序結果。

//注意：這里i是從nLen-1到0的順序排序的，是為了使排序穩定。

for(i=nLen-1;i>=0;--i)

{

--pnCount[npIndex[i]];

pnSort[pnCount[npIndex[i]]]=npData[i];

}

for(i=0;i<nLen;++i)//把排序結構輸入到返回的數據中。

{

npData[i]=pnSort[i];

}

free(pnSort);//記得釋放資源。

free(pnCount);

return1;

}

//基數排序

intRadixSort(int*nPData,intnLen)

{

//申請存放基數的空間

int*nDataRadix=(int*)malloc(sizeof(int)*nLen);

intnRadixBase=1;//初始化倍數基數為1

intnIsOk=0;//設置完成排序為false

inti;

//循環，知道排序完成

while(nIsOk==0)

{

nIsOk=1;

nRadixBase*=10;

for(i=0;i<nLen;++i)

{

nDataRadix[i]=nPData[i]%nRadixBase;

nDataRadix[i]/=nRadixBase/10;

if(nDataRadix[i]>0)

{

nIsOk=0;

}

}

if(nIsOk==1)//如果所有的基數都為0，認為排序完成，就是已經判斷到最高位了。

{

break;

}

RadixCountSort(nDataRadix,10,nPData,nLen);

}

free(nDataRadix);

return1;

}

intmain(intargc,char*argv[])

{

inti=0;

intj;

intnData[N];

printf("請輸入你要排序的個數：");

scanf("%d",&j);

if(j==0)return0;

printf("請輸入的%d個整數：",j);

for(i=0;i<j;i++)

{

scanf("%d",&nData[i]);

}

RadixSort(nData,j);

printf("基數排序法排序後： ");

for(i=0;i<j;++i)

{

printf("%d",nData[i]);

}

printf(" ");

return0;

}

運行效果如圖

⑻ 大佬們，可以詳細講解一下python這三句代碼的意思嗎

我用的python 3.7，al.clear那一句需要修正為al.clear()，不然無法清空列表。
第一、二句打勾的是創建列表。第一句找出基數中最長的位數，第二句是創建10個列表，演算法中稱之為「桶」。第三句根據基數某一位的值而把該基數放入相應的桶中，[-1*i]是逆著取值，如[-2]是逆著取倒數第二位的值：
'123'[-2]
結果是'2'
'183'[-2]
結果是'8'
整個演算法，外循環從基數位數1一直循環到最大位數。第一輪循環比較最低位，第2輪循環比較次低位，如此比較到最高位。內循環是把參與本輪循環的基數放入相應的桶里。那些位數少於本輪位數要求的基數，將放入0桶。所以0桶存的是已經排好序的基數，越先入桶的說明最小。如：
al = [1, 5, 4, 3, 100, 898, 67, 45, 65]
第一輪比較個位，1、3、4、5分別位於1、3、4、5桶。其餘的依次類推入桶。本輪結束後，又把所有基數依桶的順序收回原列表，以下相同。但很明顯，僅看個位數的話，顯然已經排好了序。
第二輪比較十位，1、3、4、5小於位數2的要求，直接依次進入0桶，它們已經在上輪排好了序。100入0桶，898入9桶、67入6桶、45入4桶、65入6桶（注意，雖然65和67同處於6桶，但由於65在第一輪處5桶、67處7桶，所以65先被循環到，也因而先於67在第二輪入6桶。顯然45、65、67在第二輪排好了序）。
第三輪比較千位，45、65、67入0桶，排在1、3、4、5之後。100入1桶、898入8桶（100、898也排好了序）。至此排序結束。

自己去看下網路，那裡的實例講得更清楚

⑼ python簡單實現基數排序演算法

python簡單實現基數排序演算法
這篇文章主要介紹了python簡單實現基數排序演算法,僅用4行代碼即可實現基數排序演算法,非常簡單實用,分享給大家供大家參考。
具體實現方法如下：
from random import randint
def main():
A = [randint(1, 99999999) for _ in xrange(9999)]
for k in xrange(8):
S = [ [] for _ in xrange(10)]
for j in A:
S[j / (10 ** k) % 10].append(j)
A = [a for b in S for a in b]
for i in A:
print i
main()

希望本文所述對大家的Python程序設計有所幫助。

⑽ python幾種經典排序方法的實現

class SortMethod:
'''
插入排序的基本操作就是將一個數據插入到已經排好序的有序數據中，從而得到一個新的、個數加一的有序數據，演算法適用於少量數據的排序，時間復雜度為O(n^2)。是穩定的排序方法。
插入演算法把要排序的數組分成兩部分：
第一部分包含了這個數組的所有元素，但將最後一個元素除外（讓數組多一個空間才有插入的位置）
第二部分就只包含這一個元素（即待插入元素）。
在第一部分排序完成後，再將這個最後元素插入到已排好序的第一部分中。
'''
def insert_sort(lists):
# 插入排序
count = len(lists)
for i in range(1, count):
key = lists[i]
j = i - 1
while j >= 0:
if lists[j] > key:
lists[j + 1] = lists[j]
lists[j] = key
j -= 1
return lists
'''
希爾排序 (Shell Sort) 是插入排序的一種。也稱縮小增量排序，是直接插入排序演算法的一種更高效的改進版本。希爾排序是非穩定排序演算法。該方法因 DL．Shell 於 1959 年提出而得名。
希爾排序是把記錄按下標的一定增量分組，對每組使用直接插入排序演算法排序；隨著增量逐漸減少，每組包含的關鍵詞越來越多，當增量減至 1 時，整個文件恰被分成一組，演算法便終止。
'''
def shell_sort(lists):
# 希爾排序
count = len(lists)
step = 2
group = count / step
while group > 0:
for i in range(0, group):
j = i + group
while j < count:
k = j - group
key = lists[j]
while k >= 0:
if lists[k] > key:
lists[k + group] = lists[k]
lists[k] = key
k -= group
j += group
group /= step
return lists
'''
冒泡排序重復地走訪過要排序的數列，一次比較兩個元素，如果他們的順序錯誤就把他們交換過來。走訪數列的工作是重復地進行直到沒有再需要交換，也就是說該數列已經排序完成。
'''
def bubble_sort(lists):
# 冒泡排序
count = len(lists)
for i in range(0, count):
for j in range(i + 1, count):
if lists[i] > lists[j]:
temp = lists[j]
lists[j] = lists[i]
lists[i] = temp
return lists
'''
快速排序
通過一趟排序將要排序的數據分割成獨立的兩部分，其中一部分的所有數據都比另外一部分的所有數據都要小，然後再按此方法對這兩部分數據分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數據變成有序序列
'''
def quick_sort(lists, left, right):
# 快速排序
if left >= right:
return lists
key = lists[left]
low = left
high = right
while left < right:
while left < right and lists[right] >= key:
right -= 1
lists[left] = lists[right]
while left < right and lists[left] <= key:
left += 1
lists[right] = lists[left]
lists[right] = key
quick_sort(lists, low, left - 1)
quick_sort(lists, left + 1, high)
return lists
'''
直接選擇排序
第 1 趟，在待排序記錄 r[1] ~ r[n] 中選出最小的記錄，將它與 r[1] 交換；
第 2 趟，在待排序記錄 r[2] ~ r[n] 中選出最小的記錄，將它與 r[2] 交換；
以此類推，第 i 趟在待排序記錄 r[i] ~ r[n] 中選出最小的記錄，將它與 r[i] 交換，使有序序列不斷增長直到全部排序完畢。
'''
def select_sort(lists):
# 選擇排序
count = len(lists)
for i in range(0, count):
min = i
for j in range(i + 1, count):
if lists[min] > lists[j]:
min = j
temp = lists[min]
lists[min] = lists[i]
lists[i] = temp
return lists
'''
堆排序 (Heapsort) 是指利用堆積樹（堆）這種數據結構所設計的一種排序演算法，它是選擇排序的一種。
可以利用數組的特點快速定位指定索引的元素。堆分為大根堆和小根堆，是完全二叉樹。大根堆的要求是每個節點的值都不大於其父節點的值，即 A[PARENT[i]] >= A[i]。
在數組的非降序排序中，需要使用的就是大根堆，因為根據大根堆的要求可知，最大的值一定在堆頂。
'''
# 調整堆
def adjust_heap(lists, i, size):
lchild = 2 * i + 1
rchild = 2 * i + 2
max = i
if i < size / 2:
if lchild < size and lists[lchild] > lists[max]:
max = lchild
if rchild < size and lists[rchild] > lists[max]:
max = rchild
if max != i:
lists[max], lists[i] = lists[i], lists[max]
adjust_heap(lists, max, size)
# 創建堆
def build_heap(lists, size):
for i in range(0, (size/2))[::-1]:
adjust_heap(lists, i, size)
# 堆排序
def heap_sort(lists):
size = len(lists)
build_heap(lists, size)
for i in range(0, size)[::-1]:
lists[0], lists[i] = lists[i], lists[0]
adjust_heap(lists, 0, i)
'''
歸並排序是建立在歸並操作上的一種有效的排序演算法,該演算法是採用分治法 （Divide and Conquer） 的一個非常典型的應用。將已有序的子序列合並，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。若將兩個有序表合並成一個有序表，稱為二路歸並。
歸並過程為：
比較 a[i] 和 a[j] 的大小，若 a[i]≤a[j]，則將第一個有序表中的元素 a[i] 復制到 r[k] 中，並令 i 和 k 分別加上 1；
否則將第二個有序表中的元素 a[j] 復制到 r[k] 中，並令 j 和 k 分別加上 1，如此循環下去，直到其中一個有序表取完，然後再將另一個有序表中剩餘的元素復制到 r 中從下標 k 到下標 t 的單元。歸並排序的演算法我們通常用遞歸實現，先把待排序區間 [s,t] 以中點二分，接著把左邊子區間排序，再把右邊子區間排序，最後把左區間和右區間用一次歸並操作合並成有序的區間 [s,t]。
'''
def merge(left, right):
i, j = 0, 0
result = []
while i < len(left) and j < len(right):
if left[i] <= right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
result += left[i:]
result += right[j:]
return result
def merge_sort(lists):
# 歸並排序
if len(lists) <= 1:
return lists
num = len(lists) / 2
left = merge_sort(lists[:num])
right = merge_sort(lists[num:])
return merge(left, right)
'''
基數排序 （radix sort） 屬於「分配式排序」 （distribution sort），又稱「桶子法」 （bucket sort） 或 bin sort，顧名思義，它是透過鍵值的部份資訊，將要排序的元素分配至某些「桶」中，藉以達到排序的作用，基數排序法是屬於穩定性的排序。
其時間復雜度為 O (nlog(r)m)，其中 r 為所採取的基數，而 m 為堆數，在某些時候，基數排序法的效率高於其它的穩定性排序法。
'''
import math
def radix_sort(lists, radix=10):
k = int(math.ceil(math.log(max(lists), radix)))
bucket = [[] for i in range(radix)]
for i in range(1, k+1):
for j in lists:
bucket[j/(radix**(i-1)) % (radix**i)].append(j)
del lists[:]
for z in bucket:
lists += z
del z[:]
return lists
---------------------
作者：CRazyDOgen
來源：CSDN
原文：https://blog.csdn.net/jipang6225/article/details/79975312
版權聲明：本文為博主原創文章，轉載請附上博文鏈接！