algorithm

Algorithm：【Algorithm算法进阶之路】之十大经典排序算法

 

相关文章
Algorithm：【Algorithm算法进阶之路】之数据结构二十多种算法演示
Algorithm：【Algorithm算法进阶之路】之十大经典排序算法
Algorithm：【Algorithm算法进阶之路】之数据结构基础知识
Algorithm：【Algorithm算法进阶之路】之数据结构相关习题(数组、字符串、链表、栈、队列、树、图、哈希)
Algorithm：【Algorithm算法进阶之路】之算法中的数学编程(时间速度、进制转换、排列组合、条件概率、斐波那契数列)相关习题
Algorithm：【Algorithm算法进阶之路】之算法(查找、排序、递归、复杂度、高级算法)相关习题
Algorithm：【Algorithm算法进阶之路】之机器学习相关习题
Algorithm：【Algorithm算法进阶之路】之Python语言相关习题

 

目录

如何理解P和NP问题

十大经典排序算法

一、排序算法基础知识

1、排序定义

2、排序术语

二、十大排序算法

0、十大算法复杂度、稳定性比较

1、简单插入排序（Insertion Sort）

2、希尔排序（Shell Sort）——简单插入排序的高效版——分治法

3、选择排序（Selection Sort）

4、堆排序（Heap Sort）——分治法

5、冒泡排序（Bubble Sort）

6、快速排序（Quick Sort）——分治法

7、归并排序（Merge Sort）——分治法

8、计数排序（Counting Sort）——非比较的排序算法

9、桶排序（Bucket Sort）——计数排序的升级版

10、基数排序（Radix Sort）——非比较的排序算法

API

Temp文件(Local Computer)

版权声明

 

 

 

 

相关文章
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符号表述，不包括这个函数的低阶项和首项系数。使用这种方式时，时间复杂度可被称为是渐近的，它考察当输入值大小趋近无穷时的情况。

			注：当n趋于∞时，O()看的是最大的那一级，比如O(n-1)即O(n)、
≈。

			 

			(1)、按数量级递增排列，常见的时间复杂度有：下边随着问题规模n的不断增大，上述时间复杂度不断增大，算法的执行效率越低。

			常数阶O(1)、对数阶O()、线性阶O(n)

				(1)、二分查找的时间复杂度为的原因：Algorithm：【Algorithm算法进阶之路】之数据结构(数组、字符串、链表、栈、队列、树、图、哈希、堆)相关习题
				线性对数阶O()
				平方阶O()、立方阶O()、k次方阶O()
				指数阶O()
			
2、空间复杂度

			        空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度，记做S(n)=O(f(n))。比如直接插入排序的时间复杂度是O(),空间复杂度是O(1) 。而一般的递归算法就要有O(n)的空间复杂度了，因为每次递归都要存储返回信息。
			
		
 

 

二、十大排序算法

思维导图：https://www.processon.com/mindmap/5d764121e4b04a19501b9f1d



0、十大算法复杂度、稳定性比较

冒泡排序、选择排序、插入排序等，问题规模为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、内排序，指所有排序操作都在内存中完成。外排序，排序方式需要额外内存，指由于数据太大，因此把数据放在磁盘中，而排序通过磁盘和内存的数据传输才能进行。



1、简单插入排序（Insertion Sort）

       插入排序，是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

算法描述
			
			一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：

			从第一个元素开始，该元素可以认为已经被排序；
				取出下一个元素，在已经排序的元素序列中，从后向前扫描；
				如果该元素（已排序）大于新元素，将该元素移到下一位置；
				重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
				将新元素插入到该位置后；
				重复步骤2~5。

				(1)、最坏情况：当待排序列完全逆序时，每个元素需要进行n-1次数据搬移和插入操作，因为有n个元素，即时间复杂度为；
			
		
动画演示
			
		

			算法分析
			
			最佳情况：T(n) = O(n)   最坏情况：T(n) = O()   平均情况：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)

 

 

2、希尔排序（Shell Sort）——简单插入排序的高效版——分治法

       希尔排序，是希尔（Donald Shell）于1959年提出的一种排序算法。希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序，同时该算法是冲破O(n2）的第一批算法之一。它与插入排序的不同之处在于，它会优先比较距离较远的元素。

      希尔排序的实质就是分组插入排序，该方法又称缩小增量排序，因DL．Shell于1959年提出而得名。希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法。

      希尔排序是基于插入排序的以下两点性质而提出改进方法的：

(1)、插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率。

(2)、但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位。

       希尔排序又叫缩小增量排序。希尔排序是把记录按下表的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。

算法特点
			希尔的不稳定：由于多次插入排序，我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以，Shell排序是不稳定的。
排序越来越快：每组含有的整数越来越多，但由于这些数也越来越有序，所以排序速度也很快。
		
算法描述
			
			      希尔排序的基本步骤，在此我们选择增量gap=length/2，缩小增量继续以gap = gap/2的方式，这种增量选择我们可以用一个序列来表示，{n/2,(n/2)/2...1}，称为增量序列。希尔排序的增量序列的选择与证明是个数学难题，我们选择的这个增量序列是比较常用的，也是希尔建议的增量，称为希尔增量，但其实这个增量序列不是最优的。此处我们做示例使用希尔增量。先将整个待排序的记录序列，分割成为若干子序列分别进行直接插入排序，具体算法描述：

			选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；
				按增量序列个数k，对序列进行k趟排序；
				每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。如果仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。
			
		
动画演示
			
			案例一理解

			     注：增量的选择 gap = 10/2 ，缩小增量继续以 gap = gap/2 的方式

			第一步：
整体分组：初始增量为 gap = 10/2 = 5，整个数组分成了 5 组。按颜色划分为【 8 , 3 】，【 9 , 5 】，【 1 , 4 】，【 7 , 6 】，【 2 , 0 】。
组内采用插入排序：对分开的这 5 组分别使用简单插入排序。结果可以发现，这五组中的相对小元素都被调到前面了

			第二步：
整体分组：缩小增量 gap = 5/2 = 2，整个数组分成了 2 组。【 3 , 1 , 0 , 9 , 7  】，【 5 , 6 , 8 , 4 , 2  】。
组内采用插入排序：对这分开的 2 组分别使用上节所讲的插入排序。此时整个数组的有序性是很明显的。

			第三步：
整体分组：再缩小增量 gap = 2/2 = 1，整个数组分成了 1 组，【 0, 2 , 1 , 4 , 3 , 5 , 7 , 6 , 9 , 0  】。
组内采用插入排序：此时，只需要对以上数列进行简单的微调(移动的步幅比较小)，不需要大量的移动操作即可完成整个数组的排序。

			

			参考文章：https://cloud.tencent.com/developer/article/1377652

			案例二理解

			
			
		

			算法分析
			
			最佳情况：T(n) = O()  最坏情况：T(n) = O()  平均情况：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))

 

 

3、选择排序（Selection Sort）

          选择排序，是一种简单直观的排序算法。它的工作原理：首先在未排序的序列中，找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中，继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。 

理解：第一次n个数全走一遍，选择最小的放到前边第一位置；第二次，在n-1个数列内再走一遍，选择次小的放到第二位置……

算法特点
			
			够稳定：表现最稳定的排序算法之一，因为无论什么数据进去都是O()的时间复杂度，所以用到它的时候，数据规模越小越好。
				不占额外内存：唯一的好处可能就是不占用额外的内存空间了吧。
				最常见：理论上讲，选择排序可能也是平时排序一般人想到的最多的排序方法了吧。
			
		
算法描述
			
			n个记录的直接选择排序，可经过n-1趟直接选择排序，得到有序结果。具体算法步骤如下：

			初始状态：无序区为R[1..n]，有序区为空；
				第i趟排序(i=1,2,3…n-1)开始时，当前有序区和无序区分别为R[1..i-1]和R(i..n）。该趟排序从当前无序区中-选出关键字最小的记录 R[k]，将它与无序区的第1个记录R交换，使R[1..i]和R[i+1..n)分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区；
				n-1趟结束，数组有序化了。
			
		
动画演示
			
		

			算法分析
			
			最佳情况：T(n) = O()  最差情况：T(n) = O()  平均情况：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))

 

 

 

4、堆排序（Heap Sort）——分治法

         堆排序，是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。堆排序是利用 堆进行排序的。  

算法特点
			
			1、堆是一种完全二叉树。

			2、堆有两种类型: 大根堆、小根堆。

			每个结点的值(非叶子节点的关键字)都大于或等于其左右孩子结点的值，称为大顶堆；即大顶堆的堆顶元素是最大的。
				或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。
			
3、可用数组存储：完全二叉树可以用数组完美存储，对于长度为n的数组a[0，…，n-1]，若" 0≤i≤n-1，a[i]≤a[2i+1]且a[i]≤a[2i+2]，那么，a表示一个小顶堆。

			4、代码编程中，父子节点可相互索引：

			k的孩子结点：如果存在分别是2k+ 1，2k+2。
				k的父结点：若k为左孩子：则k的父结点为k/2；若k为右孩子：则k的父结点为k/2-1。
				发现：二者公式不一样，十分不便。 若k为左孩子，则k为奇数，则((k+1)/2)-1与k/2相等；若k为右孩子，则k为偶数，则((k+1)/2)-1与k/2-1相等。
				结论：若待考查结点为k，记k+1为K，则k的父结点为K/2-1。
			
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、堆排序的四个过程

			将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆，此堆为初始的无序区；
				将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]<=R[n]；
				由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)
				不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。
			
		
算法改进
			
			堆排序中的改进思考

			       得到一个堆后，堆排序仅输出堆顶元素，便又重新组织新堆了，没有利用完全堆的全部信息。根据堆的逻辑结构和特征，堆顶结点的左右孩子之一必有一个是数据中的第二大(小)者，通过加入比较，完全可以随着堆顶一起文换到末尾。然后，分别对次顶堆和顶堆调整即可。
			
		
动画演示
			
			两个案例理解

			

			动画演示：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))

 

 

 

5、冒泡排序（Bubble Sort）

        冒泡排序，是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复进行，直到没有再需要交换，也就是说该数列已经排序完成。冒泡名字源自，越小的元素会经由交换慢慢“浮”到数列的顶端。 

每进行一轮，会将当前轮最大值交换到最末尾。
算法描述
			
			比较相邻的元素。如果第一个比第二个大，就交换它们两个；
				对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
				针对所有的元素重复以上的步骤，除了最后一个；
				重复步骤1~3，直到排序完成。

				(1)、平均情况：第一个需要n次比较，共n个，故O()。

				(2)、最好情况：如果是排好序的数列，只需要第一个n次即可，故 O(n)。
			
		
动画演示
			
		

			算法分析
			
			
			最佳情况：T(n) = O(n)   最差情况：T(n) = O()   平均情况：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))

 

 

 

6、快速排序（Quick Sort）——分治法

        快速排序的。其基本思想是通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字，均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

算法描述
			
			   

			快速排序使用分治法来把一个串（list）分为两个子串（sub-lists）。具体算法描述如下：

			从数列中挑出一个元素，称为 “基准”（pivot）；
				重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
				递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
			
		
动画演示
			

			其他案例理解：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)    



 

7、归并排序（Merge Sort）——分治法

        归并排序，和选择排序一样，它的性能不受输入数据的影响，但表现比选择排序好的多，因为始终都是O(n log n）的时间复杂度，代价是需要额外的内存空间。

1、归并排序的两点改进 

(1)、在数组长度比较短的情况下，不进行递归，而是选择其他排序方案：如插入排序； 

(2)、归并过程中，可以用记录数组下标的方式，代替申请新内存空间 间的频繁数据移动 ，从而避免A和辅助数组间的频繁数据移动。

注：基于关键字比较的排序算法的平均时间复杂度的下界为O(nlogn)。

算法特点
			
			分治：归并排序，是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。
				稳定：归并排序是一种稳定的排序方法。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。 
			
		
算法描述
			
			        基本设计思想：将原始数组A(1:n)中的元素，分成两个子集合A1(1 :n/2）和A2(n/2+1:n)。 分别对这两个子集合单独排序， 然后将已排序的两个子序列归并成一个含有n个元素的序列。 

			把长度为n的输入序列，分成两个长度为n/2的子序列；
				对这两个子序列，分别采用归并排序；
				将两个排序好的子序列，合并成一个最终的排序序列。
			
		
动画演示
			
		

			算法分析
			
			最佳情况：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))

 

 

8、计数排序（Counting Sort）——非比较的排序算法

        计数排序，是一种稳定的排序算法。其核心在于将输入的数据值，转化为键存储在额外开辟的数组空间中。 作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。

        计数排序使用一个额外的数组C，其中第i个元素是待排序数组A中值等于i的元素的个数。然后根据数组C来将A中的元素排到正确的位置，它只能对整数进行排序。

算法描述
			
			找出待排序的数组中最大和最小的元素；
				统计数组中每个值为i的元素出现的次数，存入数组C的第i项；
				对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）；
				反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1。
			
		
动画演示
			
		

			算法分析
			
			      当输入的元素是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;
}


 

9、桶排序（Bucket Sort）——计数排序的升级版

        桶排序，是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。

       桶排序的工作的原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排。

算法描述
			
			人为设置一个BucketSize，作为每个桶所能放置多少个不同数值（例如当BucketSize==5时，该桶可以存放｛1,2,3,4,5｝这几种数字，但是容量不限，即可以存放100个3）；
				遍历输入数据，并且把数据一个一个放到对应的桶里去；
				对每个不是空的桶进行排序，可以使用其它排序方法，也可以递归使用桶排序；
				从不是空的桶里把排好序的数据拼接起来。 
			
			  注意，如果递归使用桶排序为各个桶排序，则当桶数量为1时要手动减小BucketSize增加下一循环桶的数量，否则会陷入死循环，导致内存溢出。
		
动画演示
			
		

			算法分析
			
			       桶排序最好情况下使用线性时间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;
}


 

10、基数排序（Radix Sort）——非比较的排序算法

          基数排序，也是非比较的排序算法，对每一位进行排序，从最低位开始排序，复杂度为O(kn),为数组长度，k为数组中的数的最大的位数。

          基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。基数排序基于分别排序，分别收集，所以是稳定的。

算法描述
			
			取得数组中的最大数，并取得位数；
				arr为原始数组，从最低位开始取每个位组成radix数组；
				对radix进行计数排序（利用计数排序适用于小范围数的特点）
			
		
动画演示
			
		

			算法分析
			
			
			最佳情况：T(n) = O(n * k)   最差情况：T(n) = O(n * k)   平均情况：T(n) = O(n * k)。

			基数排序有两种方法：MSD 从高位开始进行排序 LSD 从低位开始进行排序 。
			
		
基数排序 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实现的各种排序算法的动画比较

 

 

 

API

         （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。

Qt之API Design Principles

 

 

Temp文件(Local Computer)

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

排序方法	时间复杂度(平均)	时间复杂度(最坏)	时间复杂度(最好)	辅助空间复杂度	稳定性	复杂性
直接插入排序	O( $n^{2}$ )	O( $n^{2}$ )	O(n)	O(1)	稳定	简单
希尔插入排序	O( $n log_{_{2}}n$ )	O( $n log_{_{2}}n$ )	O( $n log_{_{2}}n$ )	O(1)	不稳定	较复杂
直接选择排序	O( $n^{2}$ )	O( $n^{2}$ )	O( $n^{2}$ )	O(1)	不稳定	简单
堆排序	O( $n log_{_{2}}n$ )	O( $n log_{_{2}}n$ )	O( $n log_{_{2}}n$ )	O(1)	不稳定	较复杂
冒泡排序	O( $n^{2}$ )	O( $n^{2}$ )	O(n)	O(1)	稳定	简单
快速排序	O( $n log_{_{2}}n$ )	O(n2)	O( $n log_{_{2}}n$ )	O( $n log_{_{2}}n$ )	不稳定	较复杂
归并排序	O( $n log_{_{2}}n$ )	O( $n log_{_{2}}n$ )	O( $n log_{_{2}}n$ )	O(n)	稳定	较复杂
计数排序					稳定
桶排序					稳定
基数排序	O(d(n+r))	O(d(n+r))	O(d(n+r))	O(n+r)	稳定	较复杂

收起

算法特点	希尔的不稳定：由于多次插入排序，我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以，Shell排序是不稳定的。排序越来越快：每组含有的整数越来越多，但由于这些数也越来越有序，所以排序速度也很快。
算法描述	希尔排序的基本步骤，在此我们选择增量gap=length/2，缩小增量继续以gap = gap/2的方式，这种增量选择我们可以用一个序列来表示，{n/2,(n/2)/2...1}，称为增量序列。希尔排序的增量序列的选择与证明是个数学难题，我们选择的这个增量序列是比较常用的，也是希尔建议的增量，称为希尔增量，但其实这个增量序列不是最优的。此处我们做示例使用希尔增量。先将整个待排序的记录序列，分割成为若干子序列分别进行直接插入排序，具体算法描述：选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；按增量序列个数k，对序列进行k趟排序；每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。如果仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。
动画演示	案例一理解注：增量的选择 gap = 10/2 ，缩小增量继续以 gap = gap/2 的方式第一步：整体分组：初始增量为 gap = 10/2 = 5，整个数组分成了 5 组。按颜色划分为【 8 , 3 】，【 9 , 5 】，【 1 , 4 】，【 7 , 6 】，【 2 , 0 】。组内采用插入排序：对分开的这 5 组分别使用简单插入排序。结果可以发现，这五组中的相对小元素都被调到前面了第二步：整体分组：缩小增量 gap = 5/2 = 2，整个数组分成了 2 组。【 3 , 1 , 0 , 9 , 7 】，【 5 , 6 , 8 , 4 , 2 】。组内采用插入排序：对这分开的 2 组分别使用上节所讲的插入排序。此时整个数组的有序性是很明显的。第三步：整体分组：再缩小增量 gap = 2/2 = 1，整个数组分成了 1 组，【 0, 2 , 1 , 4 , 3 , 5 , 7 , 6 , 9 , 0 】。组内采用插入排序：此时，只需要对以上数列进行简单的微调(移动的步幅比较小)，不需要大量的移动操作即可完成整个数组的排序。参考文章：https://cloud.tencent.com/developer/article/1377652 案例二理解
算法分析	最佳情况：T(n) = O( $n log_{_{2}}n$ ) 最坏情况：T(n) = O( $n log_{_{2}}n$ ) 平均情况：T(n) =O( $n log_{_{2}}n$ )

算法特点	够稳定：表现最稳定的排序算法之一，因为无论什么数据进去都是O( $n^{2}$ )的时间复杂度，所以用到它的时候，数据规模越小越好。不占额外内存：唯一的好处可能就是不占用额外的内存空间了吧。最常见：理论上讲，选择排序可能也是平时排序一般人想到的最多的排序方法了吧。
算法描述	n个记录的直接选择排序，可经过n-1趟直接选择排序，得到有序结果。具体算法步骤如下：初始状态：无序区为R[1..n]，有序区为空；第i趟排序(i=1,2,3…n-1)开始时，当前有序区和无序区分别为R[1..i-1]和R(i..n）。该趟排序从当前无序区中-选出关键字最小的记录 R[k]，将它与无序区的第1个记录R交换，使R[1..i]和R[i+1..n)分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区； n-1趟结束，数组有序化了。
动画演示
算法分析	最佳情况：T(n) = O( $n^{2}$ ) 最差情况：T(n) = O( $n^{2}$ ) 平均情况：T(n) = O( $n^{2}$ )

算法特点	1、堆是一种完全二叉树。 2、堆有两种类型: 大根堆、小根堆。每个结点的值(非叶子节点的关键字)都大于或等于其左右孩子结点的值，称为大顶堆；即大顶堆的堆顶元素是最大的。或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。 3、可用数组存储：完全二叉树可以用数组完美存储，对于长度为n的数组a[0，…，n-1]，若" 0≤i≤n-1，a[i]≤a[2i+1]且a[i]≤a[2i+2]，那么，a表示一个小顶堆。 4、代码编程中，父子节点可相互索引： k的孩子结点：如果存在分别是2k+ 1，2k+2。 k的父结点：若k为左孩子：则k的父结点为k/2；若k为右孩子：则k的父结点为k/2-1。发现：二者公式不一样，十分不便。若k为左孩子，则k为奇数，则((k+1)/2)-1与k/2相等；若k为右孩子，则k为偶数，则((k+1)/2)-1与k/2-1相等。结论：若待考查结点为k，记k+1为K，则k的父结点为K/2-1。 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、堆排序的四个过程将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆，此堆为初始的无序区；将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]<=R[n]；由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn) 不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。
算法改进	堆排序中的改进思考得到一个堆后，堆排序仅输出堆顶元素，便又重新组织新堆了，没有利用完全堆的全部信息。根据堆的逻辑结构和特征，堆顶结点的左右孩子之一必有一个是数据中的第二大(小)者，通过加入比较，完全可以随着堆顶一起文换到末尾。然后，分别对次顶堆和顶堆调整即可。
动画演示	两个案例理解动画演示：https://bajdcc.github.io/html/heap.html
算法分析	最佳情况：T(n) = O(nlogn) 最差情况：T(n) = O(nlogn) 平均情况：T(n) = O(nlogn)

算法描述	比较相邻的元素。如果第一个比第二个大，就交换它们两个；对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；针对所有的元素重复以上的步骤，除了最后一个；重复步骤1~3，直到排序完成。 (1)、平均情况：第一个需要n次比较，共n个，故O( $n^{2}$ )。 (2)、最好情况：如果是排好序的数列，只需要第一个n次即可，故 O(n)。
动画演示
算法分析	最佳情况：T(n) = O(n) 最差情况：T(n) = O( $n^{2}$ ) 平均情况：T(n) = O( $n^{2}$ )

算法特点	分治：归并排序，是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。稳定：归并排序是一种稳定的排序方法。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。
算法描述	基本设计思想：将原始数组A(1:n)中的元素，分成两个子集合A1(1 :n/2）和A2(n/2+1:n)。分别对这两个子集合单独排序，然后将已排序的两个子序列归并成一个含有n个元素的序列。把长度为n的输入序列，分成两个长度为n/2的子序列；对这两个子序列，分别采用归并排序；将两个排序好的子序列，合并成一个最终的排序序列。
动画演示
算法分析	最佳情况：T(n) = O(n) 最差情况：T(n) = O(nlogn) 平均情况：T(n) = O(nlogn)

算法描述	找出待排序的数组中最大和最小的元素；统计数组中每个值为i的元素出现的次数，存入数组C的第i项；对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）；反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1。
动画演示
算法分析	当输入的元素是n 个0到k之间的整数时，它的运行时间是 O(n + k)。计数排序属于非比较排序，其排序的速度快于任何比较排序算法。由于用来计数的数组C的长度取决于待排序数组中数据的范围（等于待排序数组的最大值与最小值的差加上1），这使得计数排序对于数据范围很大的数组，需要大量时间和内存。最佳情况：T(n) = O(n+k) 最差情况：T(n) = O(n+k) 平均情况：T(n) = O(n+k)

算法描述	人为设置一个BucketSize，作为每个桶所能放置多少个不同数值（例如当BucketSize==5时，该桶可以存放｛1,2,3,4,5｝这几种数字，但是容量不限，即可以存放100个3）；遍历输入数据，并且把数据一个一个放到对应的桶里去；对每个不是空的桶进行排序，可以使用其它排序方法，也可以递归使用桶排序；从不是空的桶里把排好序的数据拼接起来。注意，如果递归使用桶排序为各个桶排序，则当桶数量为1时要手动减小BucketSize增加下一循环桶的数量，否则会陷入死循环，导致内存溢出。
动画演示
算法分析	桶排序最好情况下使用线性时间O(n)，桶排序的时间复杂度，取决与对各个桶之间数据进行排序的时间复杂度，因为其它部分的时间复杂度都为O(n)。很显然，桶划分的越小，各个桶之间的数据越少，排序所用的时间也会越少。但相应的空间消耗就会增大。最佳情况：T(n) = O(n+k) 最差情况：T(n) = O(n+k) 平均情况：T(n) = O(n2)

算法描述	取得数组中的最大数，并取得位数； arr为原始数组，从最低位开始取每个位组成radix数组；对radix进行计数排序（利用计数排序适用于小范围数的特点）
动画演示
算法分析	最佳情况：T(n) = O(n * k) 最差情况：T(n) = O(n * k) 平均情况：T(n) = O(n * k)。基数排序有两种方法：MSD 从高位开始进行排序 LSD 从低位开始进行排序。
基数排序 vs 计数排序 vs 桶排序	基数排序 vs 计数排序 vs 桶排序。这三种排序算法都利用了桶的概念，但对桶的使用方法上有明显差异：基数排序：根据键值的每位数字来分配桶计数排序：每个桶只存储单一键值桶排序：每个桶存储一定范围的数值

Algorithm

Algorithm-algorithm.zip

Algorithm-Algorithm.zip

Algorithm：【Algorithm算法进阶之路】之十大经典排序算法

如何理解P和NP问题

十大经典排序算法

一、排序算法基础知识

1、排序定义

2、排序术语

二、十大排序算法

0、十大算法复杂度、稳定性比较

1、简单插入排序（Insertion Sort）

2、希尔排序（Shell Sort）——简单插入排序的高效版——分治法

3、选择排序（Selection Sort）

4、堆排序（Heap Sort）——分治法

5、冒泡排序（Bubble Sort）

6、快速排序（Quick Sort）——分治法

7、归并排序（Merge Sort）——分治法

8、计数排序（Counting Sort）——非比较的排序算法

9、桶排序（Bucket Sort）——计数排序的升级版

10、基数排序（Radix Sort）——非比较的排序算法

API

Temp文件(Local Computer)

版权声明

Algorithm-AlgorithmMap.zip

Create 4 packages: algorithm, algorithm_msgs, algorithm_ros and rqt_algorithm

Algorithm-iOS-Algorithm.zip

Algorithm-Python-algorithm.zip

Algorithm-algorithm_note.zip

Algorithm-PHP-algorithm.zip

Algorithm-algorithm-learning.zip

Algorithm-algorithm-archive.zip

Algorithm-algorithm-princeton.zip

Algorithm-algorithm-implementations.zip

Algorithm-awesome-algorithm.zip

algorithm

我对 SQL 优化的一点经验

hadoop自动化运维工具Ambari应用实践

Redis数据库入门与使用

BigDataBench_开源的大数据系统评测基准_詹剑锋.pdf

React(三)

java static 静态类、方法的用处

（新）备战2021软考信息安全工程师通关套餐

2020最新小迪安全渗透视频资料

软件工程项目

java复习

21年新接口自动化测试视频postman教程 零基础接口测试

微众五年，寻找最后一块“拼图”｜分布式商业

软件测试--selenium脚本编写注意点(一)

【回顾】对话巨杉数据库核心研发团队：分布式数据库自研之路

彻底学会正则表达式

初来乍到

SpringSecurity 整合 JWT

备战2021软考网络规划设计师历年真题套餐

MockProject.rar

Hadoop平台基准性能测试研究_张新玲.pdf

21年新接口自动化测试视频postman教程零基础接口测试