基数排序算法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
版权声明：本文为博主原创文章，转载请附上博文链接！