genetic algorithm遗传算法
encryption algorithm加密算法
pseudo ['psju:dəu]
- n. 伪君子;假冒的人
- adj. 冒充的,假的
algorithm ['ælɡəriðəm]算法
genetic algorithm遗传算法
encryption algorithm加密算法
pseudo ['psju:dəu]
pseudo-terminal 伪终端
- n. 伪君子;假冒的人
- adj. 冒充的,假的
转载于:https://www.cnblogs.com/-song/archive/2011/12/01/3331914.html
选择排序
def findSmallest(arr):smallest = arr[0]smallest_index = 0for i in range(1,len(arr)):if arr[i] < smallest:smallest = arr[i]smallest_index = ireturn smallest_indexdef selectionSort(arr):newArr = []for i in range(len(arr)):smallest = findSmallest(arr)newArr.append(arr.pop(smallest))return newArrprint(selectionSort([5,3,6,2,10]))
Algorithm:【Algorithm算法进阶之路】之十大经典排序算法
相关文章
Algorithm:【Algorithm算法进阶之路】之数据结构二十多种算法演示
Algorithm:【Algorithm算法进阶之路】之十大经典排序算法
Algorithm:【Algorithm算法进阶之路】之数据结构基础知识
Algorithm:【Algorithm算法进阶之路】之数据结构相关习题(数组、字符串、链表、栈、队列、树、图、哈希)
Algorithm:【Algorithm算法进阶之路】之算法中的数学编程(时间速度、进制转换、排列组合、条件概率、斐波那契数列)相关习题
Algorithm:【Algorithm算法进阶之路】之算法(查找、排序、递归、复杂度、高级算法)相关习题
Algorithm:【Algorithm算法进阶之路】之机器学习相关习题
Algorithm:【Algorithm算法进阶之路】之Python语言相关习题
目录
2、希尔排序(Shell Sort)——简单插入排序的高效版——分治法
8、计数排序(Counting Sort)——非比较的排序算法
相关文章
Algorithm:Algorithm算法进阶之路之数据结构二十多种算法演示
Algorithm:Algorithm算法进阶之路之十大经典排序算法
如何理解P和NP问题
T1、最简单的解释(来自知乎怎么理解 P 问题和 NP 问题?)
P:算起来很快的问题
NP:算起来不一定快,但对于任何答案我们都可以快速的验证这个答案对不对
NP-hard:比所有的NP问题都难的问题
NP-complete:满足两点,首先属于是NP hard的问题,也属于NP问题
T2、P就是能在多项式时间内解决的问题,NP就是能在多项式时间验证答案正确与否的问题。
用大白话讲大概就是这样。所以P是否等于NP实质上就是在问,如果对于一个问题我能在多项式时间内验证其答案的正确性,那么我是否能在多项式时间内解决它?这个表述不太严谨,但通俗来讲就是如此。
十大经典排序算法
一、排序算法基础知识
1、排序定义
对一序列对象根据某个关键字进行排序。
2、排序术语
时间复杂度: 一个算法执行所耗费的时间。
空间复杂度:运行完一个程序所需内存的大小。
算法复杂度分为时间复杂度和空间复杂度。其作用: 时间复杂度是指执行算法所需要的计算工作量;而空间复杂度是指执行这个算法所需要的内存空间。 1、意义: |
1、时间复杂度 时间复杂度是同一问题可用不同算法解决,而一个算法的质量优劣将影响到算法乃至程序的效率。算法分析的目的在于选择合适算法和改进算法。计算机科学中,算法的时间复杂度是一个函数,它定性描述了该算法的运行时间。这是一个关于代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述,不包括这个函数的低阶项和首项系数。使用这种方式时,时间复杂度可被称为是渐近的,它考察当输入值大小趋近无穷时的情况。
(1)、按数量级递增排列,常见的时间复杂度有:下边随着问题规模n的不断增大,上述时间复杂度不断增大,算法的执行效率越低。
2、空间复杂度 空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度,记做S(n)=O(f(n))。比如直接插入排序的时间复杂度是O( |
思维导图:https://www.processon.com/mindmap/5d764121e4b04a19501b9f1d
冒泡排序、选择排序、插入排序等,问题规模为n,又因为需要比较n次,所以平均时间复杂度为O(n²)。
非比较排序(计数、桶、基数),只要确定每个元素之前的已有的元素个数即可,所有一次遍历即可解决,算法时间复杂度O(n)。
经验总结
(1)、对任意数列进行排序时,平均排序时间最短的排序算法为:快速排序。
排序方法 | 时间复杂度(平均) | 时间复杂度(最坏) | 时间复杂度(最好) | 辅助空间复杂度 | 稳定性 | 复杂性 |
---|---|---|---|---|---|---|
直接 插入排序 |
O( |
O( |
O(n) | O(1) | 稳定 | 简单 |
希尔插入排序 | O( |
O( |
O( |
O(1) | 不稳定 | 较复杂 |
直接 选择排序 |
O( |
O( |
O( |
O(1) | 不稳定 | 简单 |
堆排序 | O( |
O( |
O( |
O(1) | 不稳定 | 较复杂 |
冒泡排序 | O( |
O( |
O(n) | O(1) | 稳定 | 简单 |
快速排序 | O( |
O(n2) | O( |
O( |
不稳定 | 较复杂 |
归并排序 | O( |
O( |
O( |
O(n) | 稳定 | 较复杂 |
计数排序 | 稳定 | |||||
桶排序 | 稳定 | |||||
基数排序 | O(d(n+r)) | O(d(n+r)) | O(d(n+r)) | O(n+r) | 稳定 | 较复杂 |
注:
1、稳定排序:指排序前后两个相等的数,相对位置不变,则算法稳定。
理解:如果a=b,且a原本在b前面,排序之后a仍然在b的前面,则是稳定算法。,但是排序之后,a可能会出现在b的后面,则为不稳定算法。前六大排序算法中,只有直接插入排序、冒泡排序稳定!
(1)、事实上,任何一个非稳定的排序,如果能够将元素值value与元素所在位置index共同排序,即可得到稳定的排序。
2、内排序,指所有排序操作都在内存中完成。外排序,排序方式需要额外内存,指由于数据太大,因此把数据放在磁盘中,而排序通过磁盘和内存的数据传输才能进行。
插入排序,是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。插入排序在实现上,通常采用in-place排序(即只需用到O(1)的额外空间的排序),因而在从后向前扫描过程中,需要反复把已排序元素逐步向后挪位,为最新元素提供插入空间。
算法描述 |
一般来说,插入排序都采用in-place在数组上实现。具体算法描述如下:
|
动画演示 | ![]() ![]() |
算法分析 |
最佳情况:T(n) = O(n) 最坏情况:T(n) = O( |
/**
* 插入排序
* @param array
* @return
*/
public static int[] insertionSort(int[] array) {
if (array.length == 0)
return array;
int current;
for (int i = 0; i < array.length - 1; i++) {
current = array[i + 1];
int preIndex = i;
while (preIndex >= 0 && current < array[preIndex]) {
array[preIndex + 1] = array[preIndex];
preIndex--;
}
array[preIndex + 1] = current;
}
return array;
}
def Insertion_Sort(lists):
#外for循环是依次取出第i个元素,插入到内嵌for循环中(插入到当前合适的位置)
for i in range(1,len(lists)): #默认第一个元素(索引0)已经在有序序列中,从后面元素开始插入
#内嵌for循环,把第i内所有元素升序排好
for j in range(i,0,-1): #逆向遍历比较,交换位置实现插入
if lists[j-1] > lists[j]: #当前边的数>后边的数时,才交换位置,即小的靠前插入
lists[j],lists[j-1]=lists[j-1],lists[j]
return lists
list01=[5, 2, 4, 3, 1]
print('Insertion_Sort:',Insertion_Sort(list01))
import random
max_num = 100
length = 5
list = random.sample(range(max_num),length) #在指定序列中随机获取指定长度片段
list01=[5, 2, 4, 3, 1]
print('自定义:',list01)
Insertion_Sort(list01)
希尔排序,是希尔(Donald Shell)于1959年提出的一种排序算法。希尔排序也是一种插入排序,它是简单插入排序经过改进之后的一个更高效的版本,也称为缩小增量排序,同时该算法是冲破O(n2)的第一批算法之一。它与插入排序的不同之处在于,它会优先比较距离较远的元素。
希尔排序的实质就是分组插入排序,该方法又称缩小增量排序,因DL.Shell于1959年提出而得名。希尔排序,也称递减增量排序算法,是插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法。
希尔排序是基于插入排序的以下两点性质而提出改进方法的:
(1)、插入排序在对几乎已经排好序的数据操作时,效率高,即可以达到线性排序的效率。
(2)、但插入排序一般来说是低效的,因为插入排序每次只能将数据移动一位。
希尔排序又叫缩小增量排序。希尔排序是把记录按下表的一定增量分组,对每组使用直接插入排序算法排序;随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1时,整个文件恰被分成一组,算法便终止。
算法特点 | 希尔的不稳定:由于多次插入排序,我们知道一次插入排序是稳定的,不会改变相同元素的相对顺序,但在不同的插入排序过程中,相同的元素可能在各自的插入排序中移动,最后其稳定性就会被打乱,所以,Shell排序是不稳定的。 排序越来越快:每组含有的整数越来越多,但由于这些数也越来越有序,所以排序速度也很快。 |
算法描述 |
希尔排序的基本步骤,在此我们选择增量gap=length/2,缩小增量继续以gap = gap/2的方式,这种增量选择我们可以用一个序列来表示,{n/2,(n/2)/2...1},称为增量序列。希尔排序的增量序列的选择与证明是个数学难题,我们选择的这个增量序列是比较常用的,也是希尔建议的增量,称为希尔增量,但其实这个增量序列不是最优的。此处我们做示例使用希尔增量。先将整个待排序的记录序列,分割成为若干子序列分别进行直接插入排序,具体算法描述:
|
动画演示 |
案例一理解 第一步: 参考文章:https://cloud.tencent.com/developer/article/1377652 案例二理解 |
算法分析 |
最佳情况:T(n) = O( |
/**
* 希尔排序
*
* @param array
* @return
*/
public static int[] ShellSort(int[] array) {
int len = array.length;
int temp, gap = len / 2;
while (gap > 0) {
for (int i = gap; i < len; i++) {
temp = array[i];
int preIndex = i - gap;
while (preIndex >= 0 && array[preIndex] > temp) {
array[preIndex + gap] = array[preIndex];
preIndex -= gap;
}
array[preIndex + gap] = temp;
}
gap /= 2;
}
return array;
}
def Shell_Sort(lists):
step = len(lists)//2 #定义增量的选择gap
while step > 0:
for i in range(step,len(lists)): #在[step,len(lists)],比较lists[i]和lists[i-step]的大小
while(i >= step and lists[i-step] > lists[i]): #前半>后半,即后边的小→要向前移,实现降序
lists[i],lists[i-step] = lists[i-step],lists[i] #位置变化
i -= step #对应的索引位置也要变化
step //= 2 #外while内,分一半继续循环
return lists
list01=[5, 2, 4, 3, 1]
print('Shell_Sort:',Shell_Sort(list01))
选择排序,是一种简单直观的排序算法。它的工作原理:首先在未排序的序列中,找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中,继续寻找最小(大)元素,然后放到已排序序列的末尾。以此类推,直到所有元素均排序完毕。
理解:第一次n个数全走一遍,选择最小的放到前边第一位置;第二次,在n-1个数列内再走一遍,选择次小的放到第二位置……
算法特点 |
|
算法描述 |
n个记录的直接选择排序,可经过n-1趟直接选择排序,得到有序结果。具体算法步骤如下:
|
动画演示 | ![]() |
算法分析 |
最佳情况:T(n) = O( |
/**
* 选择排序
* @param array
* @return
*/
public static int[] selectionSort(int[] array) {
if (array.length == 0)
return array;
for (int i = 0; i < array.length; i++) {
int minIndex = i;
for (int j = i; j < array.length; j++) {
if (array[j] < array[minIndex]) //找到最小的数
minIndex = j; //将最小数的索引保存
}
int temp = array[minIndex];
array[minIndex] = array[i];
array[i] = temp;
}
return array;
}
def Selection_Sort(lists):
for i in range(0, len(lists)-1): #循环到最后,前边已是递增排列,故最后一个元素一定最大,不会被比较
min_ = i
for j in range(i+1, len(lists)): #for一次循环,找到后边中的最小索引:因为第i个基标准,所以比较从第i+1个开始
if lists[min_] > lists[j]: #与后边的元素挨个比较,找到最小元素的索引,去更新索引min_
min_ = j
#再利用最小元素作为标准即赋值给lists[i],进入下一个循环
lists[i], lists[min_] = lists[min_], lists[i] #理解:因为min_、i要进行交换,所以双向交换
return lists
list01=[5, 2, 4, 3, 1]
print('Selection_Sort:',Selection_Sort(list01))
堆排序,是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点。堆排序是利用 堆进行排序的。
算法特点 |
1、堆是一种完全二叉树。
3、可用数组存储:完全二叉树可以用数组完美存储,对于长度为n的数组a[0,…,n-1],若" 0≤i≤n-1,a[i]≤a[2i+1]且a[i]≤a[2i+2],那么,a表示一个小顶堆。 4、代码编程中,父子节点可相互索引:
5、堆排序的时间复杂度O(N*log2N):初始化堆的过程O(N)、调整堆的过程O(log2N)。 |
算法描述 |
1、堆排序的三步思路: ①初始化操作:将a[0…n-1]构造为堆(如大顶堆);左至右,从下至上进行调整。 ②第i(n > i ≥ 1)趟排序:将堆顶记录a[0]和a[n-i]交换,即将堆顶元素与末尾元素交换,将最大元素"沉"到数组末端;。然后将a[0…n-i-1]调整为堆(即:重建大顶堆); ③进行n-1趟,完成排序。 2、堆排序的四个过程
|
算法改进 |
堆排序中的改进思考 得到一个堆后,堆排序仅输出堆顶元素,便又重新组织新堆了,没有利用完全堆的全部信息。根据堆的逻辑结构和特征,堆顶结点的左右孩子之一必有一个是数据中的第二大(小)者,通过加入比较,完全可以随着堆顶一起文换到末尾。然后,分别对次顶堆和顶堆调整即可。 |
动画演示 |
两个案例理解 动画演示:https://bajdcc.github.io/html/heap.html |
算法分析 |
最佳情况:T(n) = O(nlogn) 最差情况:T(n) = O(nlogn) 平均情况:T(n) = O(nlogn) |
//声明全局变量,用于记录数组array的长度;
static int len;
/**
* 堆排序算法
*
* @param array
* @return
*/
public static int[] HeapSort(int[] array) {
len = array.length;
if (len < 1) return array;
//1.构建一个最大堆
buildMaxHeap(array);
//2.循环将堆首位(最大值)与末位交换,然后在重新调整最大堆
while (len > 0) {
swap(array, 0, len - 1);
len--;
adjustHeap(array, 0);
}
return array;
}
/**
* 建立最大堆
*
* @param array
*/
public static void buildMaxHeap(int[] array) {
//从最后一个非叶子节点开始向上构造最大堆
for (int i = (len/2 - 1); i >= 0; i--) { //感谢 @让我发会呆 网友的提醒,此处应该为 i = (len/2 - 1)
adjustHeap(array, i);
}
}
/**
* 调整使之成为最大堆
*
* @param array
* @param i
*/
public static void adjustHeap(int[] array, int i) {
int maxIndex = i;
//如果有左子树,且左子树大于父节点,则将最大指针指向左子树
if (i * 2 < len && array[i * 2] > array[maxIndex])
maxIndex = i * 2;
//如果有右子树,且右子树大于父节点,则将最大指针指向右子树
if (i * 2 + 1 < len && array[i * 2 + 1] > array[maxIndex])
maxIndex = i * 2 + 1;
//如果父节点不是最大值,则将父节点与最大值交换,并且递归调整与父节点交换的位置。
if (maxIndex != i) {
swap(array, maxIndex, i);
adjustHeap(array, maxIndex);
}
}
python代码实现及理解
def big_endian(lists,start,end): #该函数实现,每调用一次函数都是调整小三角(使顶角值最大)
root=start #定义小三角的根节点
child=root*2+1 #定义左孩子
while child<=end: #理解记忆:end理解为小三角中的左索引,孩子的索引必须在小三角形内
#依次兄弟对比、父哥对比,若都不满足则要break
if child+1<=end and lists[child]<lists[child+1]: #兄弟对比,找出哥哥,目的保证child为哥哥的索引
child=child+1 #child+=1
if lists[root]<lists[child]: #父哥对比,大的作父 #父节点小于子节点直接交换位置,同时交换索引并更新child
lists[root],lists[child]=lists[child],lists[root]
root=child
child=root*2+1
else:
break
print('big_endian函数:',lists)
def Heap_Sort(lists): #无序区大根堆排序
first=len(lists)//2 - 1 #当前堆的最后一个父结点
#第一个for循环,实现对初始数列构建大顶堆
for start in range(first,-1,-1): #每一个start都是父节点,比如start∈索引[3,2,1,0]
big_endian(lists,start,len(lists)-1) #每调用一次函数都是调整小三角(使顶角值最大),从下向顶调整
print('第一个for循环,构建大顶堆结束!')
#第二个for循环,堆尾换到堆顶,但交换后新堆可能违反大顶堆的性质,每交换一次,均需新一轮的调整新堆
for end in range(len(lists)-1,0,-1):
lists[0],lists[end]=lists[end],lists[0] #顶部尾部互换位置
big_endian(lists,0,end-1) #重新调整子节点的顺序,从顶向下调整
return lists
list01=[3,1,4,6,7,5,8,2] #实现小顶堆
print(Heap_Sort(list01))
冒泡排序,是一种简单的排序算法。它重复地走访过要排序的数列,一次比较两个元素,如果它们的顺序错误就把它们交换过来。走访数列的工作是重复进行,直到没有再需要交换,也就是说该数列已经排序完成。冒泡名字源自,越小的元素会经由交换慢慢“浮”到数列的顶端。
算法描述 |
|
动画演示 | ![]() |
算法分析 |
最佳情况:T(n) = O(n) 最差情况:T(n) = O( |
/**
* 冒泡排序
*
* @param array
* @return
*/
public static int[] bubbleSort(int[] array) {
if (array.length == 0)
return array;
for (int i = 0; i < array.length; i++)
for (int j = 0; j < array.length - 1 - i; j++)
if (array[j + 1] < array[j]) {
int temp = array[j + 1];
array[j + 1] = array[j];
array[j] = temp;
}
return array;
}
def Bubble_Sort(lists):
for i in range(len(lists)-1): #外for循环,向右全比较的次数,需循环比较共计i次,-1是因为最后一个元素不必再比较,可通过前边的第i-1个元素,得出最大
for j in range(len(lists)-i-1): #内for循环取出第j个元素,-i因后边i个元素已经排好序,排好序的元素不必再去比较
if lists[j] > lists[j+1]: #如果左边的大则交换位置→保证右边大,以极大值为基准一直向右比较,直至找到该次循环的最大值放到最后边
lists[j], lists[j+1] = lists[j+1], lists[j]
return lists
list01=[3,1,4,6,7,5,8,2]
print(Bubble_Sort(list01))
快速排序的。其基本思想是通过一趟排序将待排记录分隔成独立的两部分,其中一部分记录的关键字,均比另一部分的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序。
算法描述 |
快速排序使用分治法来把一个串(list)分为两个子串(sub-lists)。具体算法描述如下:
|
动画演示 | ![]() 其他案例理解:http://www.webhek.com/post/comparison-sort.html |
算法分析 |
最佳情况:T(n) = O(nlogn) 最差情况:T(n) = O(n2) 平均情况:T(n) = O(nlogn) |
/**
* 快速排序方法
* @param array
* @param start
* @param end
* @return
*/
public static int[] QuickSort(int[] array, int start, int end) {
if (array.length < 1 || start < 0 || end >= array.length || start > end) return null;
int smallIndex = partition(array, start, end);
if (smallIndex > start)
QuickSort(array, start, smallIndex - 1);
if (smallIndex < end)
QuickSort(array, smallIndex + 1, end);
return array;
}
/**
* 快速排序算法——partition
* @param array
* @param start
* @param end
* @return
*/
public static int partition(int[] array, int start, int end) {
int pivot = (int) (start + Math.random() * (end - start + 1));
int smallIndex = start - 1;
swap(array, pivot, end);
for (int i = start; i <= end; i++)
if (array[i] <= array[end]) {
smallIndex++;
if (i > smallIndex)
swap(array, i, smallIndex);
}
return smallIndex;
}
/**
* 交换数组内两个元素
* @param array
* @param i
* @param j
*/
public static void swap(int[] array, int i, int j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
def Quick_Sort(lists):
if len(lists) <= 1:
return lists
mid = lists[len(lists)//2] # 选取基准值,也可以选取第一个或最后一个元素
left, right = [], [] # 定义基准值左右两侧的列表
lists.remove(mid) # 从原始数组中移除基准值
for num in lists:
if num >= mid: # if判断,大的放右边
right.append(num)
else:
left.append(num)
return Quick_Sort(left) + [mid] + Quick_Sort(right)
归并排序,和选择排序一样,它的性能不受输入数据的影响,但表现比选择排序好的多,因为始终都是O(n log n)的时间复杂度,代价是需要额外的内存空间。
1、归并排序的两点改进
(1)、在数组长度比较短的情况下,不进行递归,而是选择其他排序方案:如插入排序;
(2)、归并过程中,可以用记录数组下标的方式,代替申请新内存空间 间的频繁数据移动 ,从而避免A和辅助数组间的频繁数据移动。
注:基于关键字比较的排序算法的平均时间复杂度的下界为O(nlogn)。
算法特点 |
|
算法描述 |
基本设计思想:将原始数组A(1:n)中的元素,分成两个子集合A1(1 :n/2)和A2(n/2+1:n)。 分别对这两个子集合单独排序, 然后将已排序的两个子序列归并成一个含有n个元素的序列。
|
动画演示 | ![]() |
算法分析 |
最佳情况:T(n) = O(n) 最差情况:T(n) = O(nlogn) 平均情况:T(n) = O(nlogn) |
/**
* 归并排序
*
* @param array
* @return
*/
public static int[] MergeSort(int[] array) {
if (array.length < 2) return array;
int mid = array.length / 2;
int[] left = Arrays.copyOfRange(array, 0, mid);
int[] right = Arrays.copyOfRange(array, mid, array.length);
return merge(MergeSort(left), MergeSort(right));
}
/**
* 归并排序——将两段排序好的数组结合成一个排序数组
*
* @param left
* @param right
* @return
*/
public static int[] merge(int[] left, int[] right) {
int[] result = new int[left.length + right.length];
for (int index = 0, i = 0, j = 0; index < result.length; index++) {
if (i >= left.length)
result[index] = right[j++];
else if (j >= right.length)
result[index] = left[i++];
else if (left[i] > right[j])
result[index] = right[j++];
else
result[index] = left[i++];
}
return result;
}
def Merge(left,right):
R, L=0, 0
result=[]
while L<len(left) and R<len(right):
if left[L] <= right[R]: #if判断,小的左边L+1
result.append(left[L]) #归并左列表
L += 1
else:
result.append(right[R]) #归并右列表
R += 1
result += list(left[L:]) #归并剩余左列表
result += list(right[R:]) #归并剩余右列表
return result
def MergeSort(lists):
if len(lists) <= 1:
return lists
mid = len(lists)//2
left = MergeSort(lists[:mid]) #将中间以左的元素递归
right = MergeSort(lists[mid:]) #将中间以右的元素递归
return Merge(left, right)
list01=[3,1,4,6,7,5,8,2]
print('MergeSort:',MergeSort(list01))
计数排序,是一种稳定的排序算法。其核心在于将输入的数据值,转化为键存储在额外开辟的数组空间中。 作为一种线性时间复杂度的排序,计数排序要求输入的数据必须是有确定范围的整数。
计数排序使用一个额外的数组C,其中第i个元素是待排序数组A中值等于i的元素的个数。然后根据数组C来将A中的元素排到正确的位置,它只能对整数进行排序。
算法描述 |
|
动画演示 | ![]() |
算法分析 |
当输入的元素是n 个0到k之间的整数时,它的运行时间是 O(n + k)。计数排序属于非比较排序,其排序的速度快于任何比较排序算法。由于用来计数的数组C的长度取决于待排序数组中数据的范围(等于待排序数组的最大值与最小值的差加上1),这使得计数排序对于数据范围很大的数组,需要大量时间和内存。 最佳情况:T(n) = O(n+k) 最差情况:T(n) = O(n+k) 平均情况:T(n) = O(n+k) |
/**
* 计数排序
*
* @param array
* @return
*/
public static int[] CountingSort(int[] array) {
if (array.length == 0) return array;
int bias, min = array[0], max = array[0];
for (int i = 1; i < array.length; i++) {
if (array[i] > max)
max = array[i];
if (array[i] < min)
min = array[i];
}
bias = 0 - min;
int[] bucket = new int[max - min + 1];
Arrays.fill(bucket, 0);
for (int i = 0; i < array.length; i++) {
bucket[array[i] + bias]++;
}
int index = 0, i = 0;
while (index < array.length) {
if (bucket[i] != 0) {
array[index] = i - bias;
bucket[i]--;
index++;
} else
i++;
}
return array;
}
桶排序,是计数排序的升级版。它利用了函数的映射关系,高效与否的关键就在于这个映射函数的确定。
桶排序的工作的原理:假设输入数据服从均匀分布,将数据分到有限数量的桶里,每个桶再分别排序(有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排。
算法描述 |
|
动画演示 | ![]() |
算法分析 |
桶排序最好情况下使用线性时间O(n),桶排序的时间复杂度,取决与对各个桶之间数据进行排序的时间复杂度,因为其它部分的时间复杂度都为O(n)。很显然,桶划分的越小,各个桶之间的数据越少,排序所用的时间也会越少。但相应的空间消耗就会增大。 最佳情况:T(n) = O(n+k) 最差情况:T(n) = O(n+k) 平均情况:T(n) = O(n2) |
/**
* 桶排序
*
* @param array
* @param bucketSize
* @return
*/
public static ArrayList<Integer> BucketSort(ArrayList<Integer> array, int bucketSize) {
if (array == null || array.size() < 2)
return array;
int max = array.get(0), min = array.get(0);
// 找到最大值最小值
for (int i = 0; i < array.size(); i++) {
if (array.get(i) > max)
max = array.get(i);
if (array.get(i) < min)
min = array.get(i);
}
int bucketCount = (max - min) / bucketSize + 1;
ArrayList<ArrayList<Integer>> bucketArr = new ArrayList<>(bucketCount);
ArrayList<Integer> resultArr = new ArrayList<>();
for (int i = 0; i < bucketCount; i++) {
bucketArr.add(new ArrayList<Integer>());
}
for (int i = 0; i < array.size(); i++) {
bucketArr.get((array.get(i) - min) / bucketSize).add(array.get(i));
}
for (int i = 0; i < bucketCount; i++) {
if (bucketSize == 1) { // 如果带排序数组中有重复数字时 感谢 @见风任然是风 朋友指出错误
for (int j = 0; j < bucketArr.get(i).size(); j++)
resultArr.add(bucketArr.get(i).get(j));
} else {
if (bucketCount == 1)
bucketSize--;
ArrayList<Integer> temp = BucketSort(bucketArr.get(i), bucketSize);
for (int j = 0; j < temp.size(); j++)
resultArr.add(temp.get(j));
}
}
return resultArr;
}
基数排序,也是非比较的排序算法,对每一位进行排序,从最低位开始排序,复杂度为O(kn),为数组长度,k为数组中的数的最大的位数。
基数排序是按照低位先排序,然后收集;再按照高位排序,然后再收集;依次类推,直到最高位。有时候有些属性是有优先级顺序的,先按低优先级排序,再按高优先级排序。最后的次序就是高优先级高的在前,高优先级相同的低优先级高的在前。基数排序基于分别排序,分别收集,所以是稳定的。
算法描述 |
|
动画演示 | ![]() |
算法分析 |
最佳情况:T(n) = O(n * k) 最差情况:T(n) = O(n * k) 平均情况:T(n) = O(n * k)。 |
基数排序 vs 计数排序 vs 桶排序 |
基数排序 vs 计数排序 vs 桶排序。这三种排序算法都利用了桶的概念,但对桶的使用方法上有明显差异: 基数排序:根据键值的每位数字来分配桶 |
/**
* 基数排序
* @param array
* @return
*/
public static int[] RadixSort(int[] array) {
if (array == null || array.length < 2)
return array;
// 1.先算出最大数的位数;
int max = array[0];
for (int i = 1; i < array.length; i++) {
max = Math.max(max, array[i]);
}
int maxDigit = 0;
while (max != 0) {
max /= 10;
maxDigit++;
}
int mod = 10, div = 1;
ArrayList<ArrayList<Integer>> bucketList = new ArrayList<ArrayList<Integer>>();
for (int i = 0; i < 10; i++)
bucketList.add(new ArrayList<Integer>());
for (int i = 0; i < maxDigit; i++, mod *= 10, div *= 10) {
for (int j = 0; j < array.length; j++) {
int num = (array[j] % mod) / div;
bucketList.get(num).add(array[j]);
}
int index = 0;
for (int j = 0; j < bucketList.size(); j++) {
for (int k = 0; k < bucketList.get(j).size(); k++)
array[index++] = bucketList.get(j).get(k);
bucketList.get(j).clear();
}
}
return array;
}
参考文章:
算法学习总结(2)——温故十大经典排序算法
在线动画演示插入/选择/冒泡/归并/希尔/快速排序算法过程工具
用HTML5实现的各种排序算法的动画比较
(Application Programming Interface,应用程序编程接口)是一些预先定义的函数,目的是提供应用程序与开发人员基于某软件或硬件得以访问一组例程的能力,而又无需访问源码,或理解内部工作机制的细节。
如何设计出一些优雅的API接口呢?—转自知乎
1. 拼写要准确接口函数一旦发布就不能改了,要保持兼容性,拼写错误也不能改了,所以要仔细检查拼写,否则会被同行嘲笑很多年。著名悲剧:unix 的 creat
2. 不仅是英文单词不要拼错,时态也不要错。比如:返回bool的判断函数,单数要用 is 复数要用are,这样你的命名就和文档中的描述保持了一致性。表示状态的变量或者函数要注意时态,比如 onXxxxChanged 表示xxx已经变化了,isConnecting表示正在连接。 正确的时态可以给使用者传递更丰富的信息。
3. 函数最好是动宾结构动宾结构就是 doSomething,这样的函数命名含义明确比如: openFile, allocBuffer, setName如果这个函数的动词宾语就是这个对象本身,那么可以省略掉宾语
4. 属性命名最好是定语+名词比如 fileName, maxSize, textColor
5. 不要用生僻单词,这不是秀英语的地方,也不要用汉语拼音比如:rendezvous,估计大多数人要去查词典才知道什么意思,这个词源自法语,是约会的意思。Symbian OS里有个用它命名的函数,开发Symbian的是英国人,也许人家觉得很平常吧,反正我是查了词典才知道的。
6. 不要自己发明缩写除非是约定俗成已经被广泛使用的缩写,否则老老实实用完整拼写。坏例子: count->cnt, manager->mngr password->pw button->btn现代的IDE都有很好的自动完成功能,名字长一点没关系的,可读性更重要。
7. 保持方法的对称性,有些方法一旦出现就应该是成对的,比如 有open就要有close,有alloc就要有free,有add就要有remove,这些单词基本是固定搭配的,使用者就很容易理解。如果 open对应clear就有点让人困惑了。
8. 站在使用者的角度去思考,API设计也要讲究用户体验。好的API设计应该是符合直觉,能望文生义的,让使用者能用尽量简洁的代码完成调用。我最欣赏的API设计是 Qt 和 .Net Framework。
Eric之Py:Eric20180524py_gui.py记录文件
1、20180717文件查找:
因为昨天晚上安装Js框架,需要python2依赖,查找C盘仲Python2软件路径,避免与Python3冲突。
2、20180928,将该环境变量删除:G:\Program Files (x86)\Python27
原因:怕影响TFOD API安装不成功!
# -*- coding: utf-8 -*-
"""
Copyright © 2018, Jason Niu.
All Rights Reserved.
Author: Jason Niu
Date:2018.06.26
Natural Language: English
Copyright Notice
System copyrights this specification.
No part of this specification may be reproduced in any form or means, without the prior written consent of Jason Niu.
Disclaimer
This specification is preliminary and is subject to change at any time without notice.
Jason Niu assumes no responsibility for any errors contained herein.
Release history
Version 1.0
"""
相关文章
Python自带:python常用方法(自带的)、常见概念详细攻略
Python实现读入、写出各自类型如txt、csv等文件之详细攻略
Python:将常用的函数进行封装
Python自带:python自带的以字母开头的函数或方法集合
BlockChain:BTC、ETH钱包地址集合
CUMCM:全国大学生数模竞赛历年考察知识点总结
Personal preference