精华内容
下载资源
问答
  • 【经典算法大全】收集51种经典算法 初学者必备

    万次阅读 多人点赞 2018-05-03 12:35:02
    经典算法大全》是一款IOS平台的应用。里面收录了51常用算法,都是一些基础问题。博主觊觎了好久,可悲哀的是博主没有苹果,所以从网上下了老奔的整理版并且每个都手敲了一遍。 虽然网上也有博客贴了出来,但是...

    《经典算法大全》是一款IOS平台的应用。里面收录了51种常用算法,都是一些基础问题。博主觊觎了好久,可悲哀的是博主没有苹果,所以从网上下了老奔的整理版并且每个都手敲了一遍。

    虽然网上也有博客贴了出来,但是自己写写感觉总是好的。现在分享个大家。

    代码和运行结果难免有出错的地方,请大家多多包涵。

     

    1.河内之塔(汉诺塔

    2.费式数列

    3.巴斯卡三角形

    4.三色棋

    5.老鼠走迷宫(1)

    6.老鼠走迷宫(2)

    7.骑士走棋盘

    8.八皇后

    9.八枚银币

    10.生命游戏

    11.字串核对

    12.双色河内塔三色河内塔

    13.背包问题 

    14.蒙地卡罗法求PI

    15.Eratosthenes筛选求质数

    16.超长整数运算(大数运算)  同时建议参考这篇文章:大数的四则运算-海子的博客园

    17.长PI

    18.最大公因数,最小公倍数,因式分解

    19.完美数

    20.阿姆斯壮数

    21.最大访客数

    22.中序转后序式(前序式  相关文章:中缀表达式值问题

    23.后序式运算 

    24.洗扑克牌(乱数排列)

    25.Craps赌博游戏

    26.约瑟夫问题

    27.排列组合   相关文章:母函数与排列组合

    28.格雷码(Gray Code)

    29.产生可能的集合  相关文章:集合划分问题

    30.m元素集合的n个元素子集

    31.数字拆解

    32.得分排行

    33.选择,插入,冒泡排序

    34.shell 排序法-改良的插入排序

    35.shaker排序法-改良的冒泡排序

    36.改良的选择排序

    37.快速排序法一

    38.快速排序法二

    39.快速排序法三

    40.合并排序法

    41.基数排序法

    42.循环搜寻法(使用卫兵)

    43.二分搜寻法(二分查找法,折半查找法)  相关文章:二分查找

    44.插补搜寻法

    45.费式搜寻法

    46.稀疏矩阵

    47.多维矩阵转一维矩阵

    48.上三角,下三角,对称矩阵

    49.奇数魔方阵

    50.4N魔方阵

    51.2(2N+1)魔方阵

     

    展开全文
  • 算法学习总结(2)——温故十大经典排序算法

    万次阅读 多人点赞 2019-08-29 14:57:51
    一、什么是排序算法 1.1、排序定义 对一序列对象根据某个关键字进行排序。 1.2、排序术语 稳定:如果a原本在b前面,而a=b,排序之后a仍然在b的前面;不稳定:如果a原本在b的前面,而a=b,排序之后a可能会出现在b...

    一、什么是排序算法

    1.1、排序定义

    对一序列对象根据某个关键字进行排序。

    1.2、排序术语

    稳定:如果a原本在b前面,而a=b,排序之后a仍然在b的前面;
    不稳定:如果a原本在b的前面,而a=b,排序之后a可能会出现在b的后面;
    内排序:所有排序操作都在内存中完成;
    外排序:由于数据太大,因此把数据放在磁盘中,而排序通过磁盘和内存的数据传输才能进行;
    时间复杂度: 一个算法执行所耗费的时间。
    空间复杂度运行完一个程序所需内存的大小。

    1.3、算法总结

    (注意:n指数据规模;k指“桶”的个数;In-place指占用常数内存,不占用额外内存;Out-place指占用额外内存

    1.4、算法分类

    1.5、比较和非比较的区别

    常见的快速排序、归并排序、堆排序、冒泡排序等属于比较排序在排序的最终结果里,元素之间的次序依赖于它们之间的比较。每个数都必须和其他数进行比较,才能确定自己的位置。冒泡排序之类的排序中,问题规模为n,又因为需要比较n次,所以平均时间复杂度为O(n²)。在归并排序、快速排序之类的排序中,问题规模通过分治法消减为logN次,所以时间复杂度平均O(nlogn)。比较排序的优势是,适用于各种规模的数据,也不在乎数据的分布,都能进行排序。可以说,比较排序适用于一切需要排序的情况。计数排序、基数排序、桶排序则属于非比较排序。非比较排序是通过确定每个元素之前,应该有多少个元素来排序。针对数组arr,计算arr[i]之前有多少个元素,则唯一确定了arr[i]在排序后数组中的位置。非比较排序只要确定每个元素之前的已有的元素个数即可,所有一次遍历即可解决。算法时间复杂度O(n)非比较排序时间复杂度底,但由于非比较排序需要占用空间来确定唯一位置。所以对数据规模和数据分布有一定的要求。

    二、冒泡排序(Bubble Sort)

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

    2.1、算法描述

    • 比较相邻的元素。如果第一个比第二个大,就交换它们两个;
    • 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对,这样在最后的元素应该会是最大的数;
    • 针对所有的元素重复以上的步骤,除了最后一个;
    • 重复步骤1~3,直到排序完成。

    2.2、动图演示

    2.3、代码实现

    /**
     * 冒泡排序
     *
     * @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;
    }

    2.4、算法分析

    最佳情况:T(n) = O(n)   最差情况:T(n) = O(n2)   平均情况:T(n) = O(n2)

    三、选择排序(Selection Sort)

    表现最稳定的排序算法之一,因为无论什么数据进去都是O(n2)的时间复杂度,所以用到它的时候,数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。理论上讲,选择排序可能也是平时排序一般人想到的最多的排序方法了吧。选择排序(Selection-sort)是一种简单直观的排序算法。它的工作原理:首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。以此类推,直到所有元素均排序完毕。 

    3.1、算法描述

    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趟结束,数组有序化了。

    3.2、动图演示

    3.3、代码实现

    /**
     * 选择排序
     * @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;
    }

    3.4、算法分析

    最佳情况:T(n) = O(n2)  最差情况:T(n) = O(n2)  平均情况:T(n) = O(n2)

    四、插入排序(Insertion Sort)

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

    4.1、算法描述

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

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

    4.2、动图演示

    4.3、代码实现

    /**
     * 插入排序
     * @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;
    }

    4.4、算法分析

    最佳情况:T(n) = O(n)   最坏情况:T(n) = O(n2)   平均情况:T(n) = O(n2)

    五、希尔排序(Shell Sort)

    希尔排序是希尔(Donald Shell)于1959年提出的一种排序算法。希尔排序也是一种插入排序,它是简单插入排序经过改进之后的一个更高效的版本,也称为缩小增量排序,同时该算法是冲破O(n2)的第一批算法之一。它与插入排序的不同之处在于,它会优先比较距离较远的元素。希尔排序又叫缩小增量排序希尔排序是把记录按下表的一定增量分组,对每组使用直接插入排序算法排序;随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1时,整个文件恰被分成一组,算法便终止。

    5.1、算法描述

    我们来看下希尔排序的基本步骤,在此我们选择增量gap=length/2,缩小增量继续以gap = gap/2的方式,这种增量选择我们可以用一个序列来表示,{n/2,(n/2)/2...1},称为增量序列。希尔排序的增量序列的选择与证明是个数学难题,我们选择的这个增量序列是比较常用的,也是希尔建议的增量,称为希尔增量,但其实这个增量序列不是最优的。此处我们做示例使用希尔增量。先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序,具体算法描述:

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

    5.2、过程演示

    5.3、代码实现

    /**
     * 希尔排序
     *
     * @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;
    }

    5.4、算法分析

    最佳情况:T(n) = O(nlog2 n)  最坏情况:T(n) = O(nlog2 n)  平均情况:T(n) =O(nlog2n) 

    六、归并排序(Merge Sort)

    和选择排序一样,归并排序的性能不受输入数据的影响,但表现比选择排序好的多,因为始终都是O(n log n)的时间复杂度。代价是需要额外的内存空间。归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。归并排序是一种稳定的排序方法。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为2-路归并。 

    6.1、算法描述

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

    6.2、动图演示

    6.3、代码实现

    /**
     * 归并排序
     *
     * @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;
    }

    6.4、算法分析

    最佳情况:T(n) = O(n)  最差情况:T(n) = O(nlogn)  平均情况:T(n) = O(nlogn)

    七、快速排序(Quick Sort)

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

    7.1、算法描述

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

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

    7.2、动图演示

    7.3、代码实现

    /**
     * 快速排序方法
     * @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;
    }

     


    wAAACH5BAEKAAAALAAAAAABAAEAAAICRAEAOw==7.4、算法分析

    最佳情况:T(n) = O(nlogn)   最差情况:T(n) = O(n2)   平均情况:T(n) = O(nlogn) 

    八、堆排序(Heap Sort)

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

    8.1、算法描述

    • 将初始待排序关键字序列(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,则整个排序过程完成。

    8.2、动图演示

     

    8.3、代码实现

    //声明全局变量,用于记录数组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);
    	}
    }

    8.4、算法分析

    最佳情况:T(n) = O(nlogn) 最差情况:T(n) = O(nlogn) 平均情况:T(n) = O(nlogn)

    九、计数排序(Counting Sort)

    计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中作为一种线性时间复杂度的排序,计数排序要求输入的数据必须是有确定范围的整数。计数排序(Counting sort)是一种稳定的排序算法。计数排序使用一个额外的数组C,其中第i个元素是待排序数组A中值等于i的元素的个数。然后根据数组C来将A中的元素排到正确的位置。它只能对整数进行排序。

    9.1、算法描述

    • 找出待排序的数组中最大和最小的元素;
    • 统计数组中每个值为i的元素出现的次数,存入数组C的第i项;
    • 对所有的计数累加(从C中的第一个元素开始,每一项和前一项相加);
    • 反向填充目标数组:将每个元素i放在新数组的第C(i)项,每放一个元素就将C(i)减去1。

    9.2、动图演示

    9.3、代码实现

    /**
     * 计数排序
     *
     * @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.4、算法分析

    当输入的元素是n 个0到k之间的整数时,它的运行时间是 O(n + k)。计数排序不是比较排序,排序的速度快于任何比较排序算法。由于用来计数的数组C的长度取决于待排序数组中数据的范围(等于待排序数组的最大值与最小值的差加上1),这使得计数排序对于数据范围很大的数组,需要大量时间和内存。最佳情况:T(n) = O(n+k)  最差情况:T(n) = O(n+k)  平均情况:T(n) = O(n+k)

    十、桶排序(Bucket Sort)

    桶排序是计数排序的升级版。它利用了函数的映射关系,高效与否的关键就在于这个映射函数的确定。桶排序 (Bucket sort)的工作的原理:假设输入数据服从均匀分布,将数据分到有限数量的桶里,每个桶再分别排序(有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排。

    10.1、算法描述

    • 人为设置一个BucketSize,作为每个桶所能放置多少个不同数值(例如当BucketSize==5时,该桶可以存放{1,2,3,4,5}这几种数字,但是容量不限,即可以存放100个3);
    • 遍历输入数据,并且把数据一个一个放到对应的桶里去;
    • 对每个不是空的桶进行排序,可以使用其它排序方法,也可以递归使用桶排序;
    • 从不是空的桶里把排好序的数据拼接起来。 

    注意,如果递归使用桶排序为各个桶排序,则当桶数量为1时要手动减小BucketSize增加下一循环桶的数量,否则会陷入死循环,导致内存溢出。

    10.2、图片演示

    10.3、代码实现

    /**
     * 桶排序
     * 
     * @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.4、算法分析

    桶排序最好情况下使用线性时间O(n),桶排序的时间复杂度,取决与对各个桶之间数据进行排序的时间复杂度,因为其它部分的时间复杂度都为O(n)。很显然,桶划分的越小,各个桶之间的数据越少,排序所用的时间也会越少。但相应的空间消耗就会增大。 最佳情况:T(n) = O(n+k)   最差情况:T(n) = O(n+k)   平均情况:T(n) = O(n2)  

    十一、基数排序(Radix Sort)

    基数排序也是非比较的排序算法,对每一位进行排序,从最低位开始排序,复杂度为O(kn),为数组长度,k为数组中的数的最大的位数;基数排序是按照低位先排序,然后收集;再按照高位排序,然后再收集;依次类推,直到最高位有时候有些属性是有优先级顺序的,先按低优先级排序,再按高优先级排序。最后的次序就是高优先级高的在前,高优先级相同的低优先级高的在前。基数排序基于分别排序,分别收集,所以是稳定的。

    11.1、算法描述

    • 取得数组中的最大数,并取得位数;
    • arr为原始数组,从最低位开始取每个位组成radix数组;
    • 对radix进行计数排序(利用计数排序适用于小范围数的特点);

    11.2、动图演示

    11.3、代码实现

    /**
     * 基数排序
     * @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;
    }

    11.4、算法分析

    最佳情况:T(n) = O(n * k)   最差情况:T(n) = O(n * k)   平均情况:T(n) = O(n * k)。基数排序有两种方法:MSD 从高位开始进行排序 LSD 从低位开始进行排序 。基数排序 vs 计数排序 vs 桶排序。这三种排序算法都利用了桶的概念,但对桶的使用方法上有明显差异:

    • 基数排序:根据键值的每位数字来分配桶
    • 计数排序:每个桶只存储单一键值
    • 桶排序:每个桶存储一定范围的数值
    展开全文
  • 四种加密算法

    千次阅读 2021-05-27 17:35:16
    RSA 加密算法是一典型的非对称加密算法,它基于大数的因式分解数学难题,它也是应用最广 泛的非对称加密算法。 非对称加密是通过两个密钥(公钥-私钥)来实现对数据的加密和解密的。公钥用于加密,私钥用于解密。 ...

    加密算法

    AES

    高级加密标准(AES,Advanced Encryption Standard)为最常见的对称加密算法(微信小程序加密传 输就是用这个加密算法的)。对称加密算法也就是加密和解密用相同的密钥,具体的加密流程如下图:
    在这里插入图片描述
    RSA

    RSA 加密算法是一种典型的非对称加密算法,它基于大数的因式分解数学难题,它也是应用最广 泛的非对称加密算法。
    非对称加密是通过两个密钥(公钥-私钥)来实现对数据的加密和解密的。公钥用于加密,私钥用于解密。
    在这里插入图片描述
    在这里插入图片描述
    CRC

    循环冗余校验(Cyclic Redundancy Check, CRC)是一种根据网络数据包或电脑文件等数据产生简 短固定位数校验码的一种散列函数,主要用来检测或校验数据传输或者保存后可能出现的错误。 它是利用除法及余数的原理来作错误侦测的。

    MD5

    MD5 常常作为文件的签名出现,我们在下载文件的时候,常常会看到文件页面上附带一个扩展 名为.MD5 的文本或者一行字符,这行字符就是就是把整个文件当作原数据通过 MD5 计算后的值, 我们下载文件后,可以用检查文件 MD5 信息的软件对下载到的文件在进行一次计算。两次结果对 比就可以确保下载到文件的准确性。 另一种常见用途就是网站敏感信息加密,比如用户名密码, 支付签名等等。随着 https 技术的普及,现在的网站广泛采用前台明文传输到后台,MD5 加密 (使用偏移量)的方式保护敏感数据保护站点和数据安全。

    展开全文
  • 四种聚类算法

    万次阅读 多人点赞 2016-05-22 16:08:58
    聚类分析是一重要的人类行为,早在孩提时代,一个人就通过不断改进下意识中的聚类模式来学会如何区分猫狗、动物植物。目前在许多领域都得到了广泛的研究和成功的应用,如用于模式识别、数据分析、图像处理、市场...

    聚类分析是一种重要的人类行为,早在孩提时代,一个人就通过不断改进下意识中的聚类模式来学会如何区分猫狗、动物植物。目前在许多领域都得到了广泛的研究和成功的应用,如用于模式识别、数据分析、图像处理、市场研究、客户分割、Web文档分类等[1]。
     聚类就是按照某个特定标准(如距离准则)把一个数据集分割成不同的类或簇,使得同一个簇内的数据对象的相似性尽可能大,同时不在同一个簇中的数据对象的差异性也尽可能地大。即聚类后同一类的数据尽可能聚集到一起,不同数据尽量分离。
     聚类技术[2]正在蓬勃发展,对此有贡献的研究领域包括数据挖掘、统计学、机器学习、空间数据库技术、生物学以及市场营销等。各种聚类方法也被不断提出和改进,而不同的方法适合于不同类型的数据,因此对各种聚类方法、聚类效果的比较成为值得研究的课题。
    1 聚类算法的分类
     目前,有大量的聚类算法[3]。而对于具体应用,聚类算法的选择取决于数据的类型、聚类的目的。如果聚类分析被用作描述或探查的工具,可以对同样的数据尝试多种算法,以发现数据可能揭示的结果。
     主要的聚类算法可以划分为如下几类:划分方法、层次方法、基于密度的方法、基于网格的方法以及基于模型的方法[4-6]。
     每一类中都存在着得到广泛应用的算法,例如:划分方法中的k-means[7]聚类算法、层次方法中的凝聚型层次聚类算法[8]、基于模型方法中的神经网络[9]聚类算法等。
     目前,聚类问题的研究不仅仅局限于上述的硬聚类,即每一个数据只能被归为一类,模糊聚类[10]也是聚类分析中研究较为广泛的一个分支。模糊聚类通过隶 属函数来确定每个数据隶属于各个簇的程度,而不是将一个数据对象硬性地归类到某一簇中。目前已有很多关于模糊聚类的算法被提出,如著名的FCM算法等。
     本文主要对k-means聚类算法、凝聚型层次聚类算法、神经网络聚类算法之SOM,以及模糊聚类的FCM算法通过通用测试数据集进行聚类效果的比较和分析。
    2 四种常用聚类算法研究
    2.1 k-means聚类算法

     k-means是划分方法中较经典的聚类算法之一。由于该算法的效率高,所以在对大规模数据进行聚类时被广泛应用。目前,许多算法均围绕着该算法进行扩展和改进。
     k-means算法以k为参数,把n个对象分成k个簇,使簇内具有较高的相似度,而簇间的相似度较低。k-means算法的处理过程如下:首先,随机地 选择k个对象,每个对象初始地代表了一个簇的平均值或中心;对剩余的每个对象,根据其与各簇中心的距离,将它赋给最近的簇;然后重新计算每个簇的平均值。 这个过程不断重复,直到准则函数收敛。通常,采用平方误差准则,其定义如下:
     
     这里E是数据库中所有对象的平方误差的总和,p是空间中的点,mi是簇Ci的平均值[9]。该目标函数使生成的簇尽可能紧凑独立,使用的距离度量是欧几里得距离,当然也可以用其他距离度量。k-means聚类算法的算法流程如下:
        输入:包含n个对象的数据库和簇的数目k;
        输出:k个簇,使平方误差准则最小。
        步骤:
      (1) 任意选择k个对象作为初始的簇中心;
      (2) repeat;
      (3) 根据簇中对象的平均值,将每个对象(重新)赋予最类似的簇;
      (4) 更新簇的平均值,即计算每个簇中对象的平均值;
      (5) until不再发生变化。
    2.2  层次聚类算法
        根据层次分解的顺序是自底向上的还是自上向下的,层次聚类算法分为凝聚的层次聚类算法和分裂的层次聚类算法。
     凝聚型层次聚类的策略是先将每个对象作为一个簇,然后合并这些原子簇为越来越大的簇,直到所有对象都在一个簇中,或者某个终结条件被满足。绝大多数层次聚类属于凝聚型层次聚类,它们只是在簇间相似度的定义上有所不同。四种广泛采用的簇间距离度量方法如下:

       这里给出采用最小距离的凝聚层次聚类算法流程:
     (1) 将每个对象看作一类,计算两两之间的最小距离;
     (2) 将距离最小的两个类合并成一个新类;
     (3) 重新计算新类与所有类之间的距离;
     (4) 重复(2)、(3),直到所有类最后合并成一类。
    2.3 SOM聚类算法
     SOM神经网络[11]是由芬兰神经网络专家Kohonen教授提出的,该算法假设在输入对象中存在一些拓扑结构或顺序,可以实现从输入空间(n维)到输出平面(2维)的降维映射,其映射具有拓扑特征保持性质,与实际的大脑处理有很强的理论联系。
     SOM网络包含输入层和输出层。输入层对应一个高维的输入向量,输出层由一系列组织在2维网格上的有序节点构成,输入节点与输出节点通过权重向量连接。 学习过程中,找到与之距离最短的输出层单元,即获胜单元,对其更新。同时,将邻近区域的权值更新,使输出节点保持输入向量的拓扑特征。
     算法流程:
     (1) 网络初始化,对输出层每个节点权重赋初值;
     (2) 将输入样本中随机选取输入向量,找到与输入向量距离最小的权重向量;
     (3) 定义获胜单元,在获胜单元的邻近区域调整权重使其向输入向量靠拢;
     (4) 提供新样本、进行训练;
     (5) 收缩邻域半径、减小学习率、重复,直到小于允许值,输出聚类结果。
    2.4 FCM聚类算法
     1965年美国加州大学柏克莱分校的扎德教授第一次提出了‘集合’的概念。经过十多年的发展,模糊集合理论渐渐被应用到各个实际应用方面。为克服非此即彼的分类缺点,出现了以模糊集合论为数学基础的聚类分析。用模糊数学的方法进行聚类分析,就是模糊聚类分析[12]。
      FCM算法是一种以隶属度来确定每个数据点属于某个聚类程度的算法。该聚类算法是传统硬聚类算法的一种改进。

        算法流程:
     (1) 标准化数据矩阵;
     (2) 建立模糊相似矩阵,初始化隶属矩阵;
     (3) 算法开始迭代,直到目标函数收敛到极小值;
     (4) 根据迭代结果,由最后的隶属矩阵确定数据所属的类,显示最后的聚类结果。
    3 四种聚类算法试验
    3.1 试验数据

     实验中,选取专门用于测试分类、聚类算法的国际通用的UCI数据库中的IRIS[13]数据集,IRIS数据集包含150个样本数据,分别取自三种不同 的莺尾属植物setosa、versicolor和virginica的花朵样本,每个数据含有4个属性,即萼片长度、萼片宽度、花瓣长度,单位为cm。 在数据集上执行不同的聚类算法,可以得到不同精度的聚类结果。
    3.2 试验结果说明
     文中基于前面所述各算法原理及算法流程,用matlab进行编程运算,得到表1所示聚类结果。

     如表1所示,对于四种聚类算法,按三方面进行比较:(1)聚错样本数:总的聚错的样本数,即各类中聚错的样本数的和;(2)运行时间:即聚类整个 过程所耗费的时间,单位为s;(3)平均准确度:设原数据集有k个类,用ci表示第i类,ni为ci中样本的个数,mi为聚类正确的个数,则mi/ni为 第i类中的精度,则平均精度为:

    3.3 试验结果分析
        四种聚类算法中,在运行时间及准确度方面综合考虑,k-means和FCM相对优于其他。但是,各个算法还是存在固定缺点:k-means聚类算法的初 始点选择不稳定,是随机选取的,这就引起聚类结果的不稳定,本实验中虽是经过多次实验取的平均值,但是具体初始点的选择方法还需进一步研究;层次聚类虽然 不需要确定分类数,但是一旦一个分裂或者合并被执行,就不能修正,聚类质量受限制;FCM对初始聚类中心敏感,需要人为确定聚类数,容易陷入局部最优 解;SOM与实际大脑处理有很强的理论联系。但是处理时间较长,需要进一步研究使其适应大型数据库。
        聚类分析因其在许多领域的成功应用而展现出诱人的应用前景,除经典聚类算法外,各种新的聚类方法正被不断被提出。
    参考文献
    [1]   HAN Jia Wei, KAMBER M.数据挖掘概念与技术[M].范明,孟晓峰,译.北京:机械工业出版社,2001.
    [2]   杨小兵.聚类分析中若干关键技术的研究[D]. 杭州:浙江大学,2005.
    [3]   XU Rui, Donald Wunsch 1 1. survey of clustering algorithm[J].IEEE.Transactions on Neural Networks, 2005,16(3):645-67 8.
    [4]   YI Hong, SAM K. Learning assignment order of instances for the constrained k-means clustering algorithm[J].IEEE Transactions on Systems, Man, and Cybernetics, Part B:Cybernetics,2009,39 (2):568-574.
    [5]   贺玲,吴玲达,蔡益朝.数据挖掘中的聚类算法综述[J].计算机应用研究,2007,24(1):10-13.
    [6]   孙吉贵,刘杰,赵连宇.聚类算法研究[J].软件学报,2008,19(1):48-61.
    [7]   孔英会,苑津莎,张铁峰,等.基于数据流管理技术的配变负荷分类方法研究.中国国际供电会议,CICED2006.
    [8]   马晓艳,唐雁.层次聚类算法研究[J].计算机科学,2008,34(7):34-36.
    [9]   汪海波,张海臣,段雪丽.基于MATLAB的自组织竞争神经网络聚类研究[J].邢台职业技术学院学报,2005,22(1):45-47.
    [10]  吕晓燕,罗立民,李祥生.FCM算法的改进及仿真实验研究[J].计算机工程与应用,2009,45(20):144-147.
    [11]  李戈,邵峰晶,朱本浩.基于神经网络聚类的研究[J].青岛大学学报,2001,16(4):21-24.
    [12]  戈国华,肖海波,张敏.基于FCM的数据聚类分析及matlab实现[J].福建电脑,2007,4:89-90.
    [13]  FISHER R A. Iris Plants Database//http://www.ics.uci.edu/~mlearn /MLRepository.Html.Authorized license.


    http://www.chinaaet.com/article/index.aspx?id=79936

    展开全文
  • JVM的四种GC算法

    万次阅读 多人点赞 2018-06-23 03:12:00
    介绍 程序在运行过程中,会产生大量的内存垃圾(一些没有引用指向的内存对象都属于内存...关于 JVM 的 GC 算法主要有下面四种: 引用计数算法(Reference counting) 算法思想: 每个对象在创建的时候,就给...
  • 四种经典限流算法,确保不溢出!

    千次阅读 2020-07-12 21:49:41
    本文将介绍几种经典的限流算法,相信大家耐心看了之后肯定有收获,码字不易,别忘了「在看」,「转发」哦。 计数器算法 滑动时间窗口算法 漏桶算法 令牌桶算法 正文 01 计数器算法 计数器算法的实现,比较简单粗暴。...
  • 五大经典算法贪心算法

    万次阅读 多人点赞 2017-04-13 23:24:38
    贪心算法没有固定的算法框架,算法设计的关键是贪心策略的选择,贪心策略使用的前提是局部最优能导致全局最优。必须注意的是,贪心算法不是对所有问题都能得到整体最优解,选择的贪心策略必须具备无后效性,即某个...
  • java实现四种常用排序算法

    万次阅读 多人点赞 2019-03-29 11:20:28
    四种常用排序算法 冒泡排序 特点:效率低,实现简单 思想(从小到大排):每一趟将待排序序列中最大元素移到最后,剩下的为新的待排序序列,重复上述步骤直到排完所有元素。这只是冒泡排序的一,当然...
  • C语言四种排序算法完整程序

    万次阅读 多人点赞 2016-09-22 09:36:51
    C语言四种排序算法完整程序 包含冒泡排序、插入排序、选择排序 主程序设计了菜单可以反复无限次调用查看运行结果 由于使用了随机数列,每次的待排序数列都不一样#include #include #include <time.h>//产生随机...
  • nginx四种调度算法、进阶

    千次阅读 2017-11-06 13:08:44
    upstream 支持4负载均衡调度算法:A)轮询(默认):每个请求按时间顺序逐一分配到不同的后端服务器;B)ip_hash:每个请求按访问IP的hash结果分配,同一个IP客户端固定访问一个后端服务器;C)url_hash:按访问url的hash结果...
  • 经典算法--约瑟夫环问题的三解法

    万次阅读 多人点赞 2018-05-17 17:03:07
    约瑟夫环问题,这是一个很经典算法,处理的关键是:伪链表 问题描述:N个人围成一圈,从第一个人开始报数,报到m的人出圈,剩下的人继续从1开始报数,报到m的人出圈;如此往复,直到所有人出圈。(模拟此过程,输出...
  • 聚类的四种算法

    万次阅读 2018-06-11 17:12:46
    最近看了一篇论文,涉及到数据挖掘的聚类算法,这里总结一下一、聚类算法的简介 聚类算法是一典型的无监督学习算法,主要用于将相似的样本自动归到一个类别中。聚类算法与分类算法最大的区别是:聚类算法是无监督...
  • 算法设计经典算法

    千次阅读 2018-12-04 10:35:37
    一、贪婪算法 1、概述 贪婪法又称贪心算法,是当追求的目标是一个问题的最优解时,设法把对整个问题的求解工作分成若干步骤来完成,是寻找最优解问题的常用方法。 贪婪法的特点是一般可以快速得到满意的解,因为...
  • 今后继续整理算法并写出自己的理解和备注。 C++实现的:最大公约数。C语言或其他语言同理。 多回头看看 很有帮助。1、 最大公约数 <1> 题目描述:求解两个整数(不能是负数)的最大公约数(要求两数不能同时为0) <2>...
  • 四种算法归纳比较 0.思维导图 本篇文章是对上一篇文章内存的分配与回收提到的动态分区分配算法的补充 1.首次适应算法 2.最佳适应算法 3.最坏(大)适应算法 4.临近适应算法 5.四种算法归纳比较 ...
  • preOrderParse(int n) { if(tree[n] == NULL) return ; // 如果这个节点不存在,那么结束 cout << tree[n].w ; // 输出当前节点内容 preOrderParse(tree[n].leftChild); // 递归输出左子树 ...
  • java算法大全_java经典算法_算法面试题大全含答案

    万次阅读 多人点赞 2019-05-16 09:44:18
    1、Java中用到的线程调度算法是什么? 2、java二叉树算法面试题大全含答案 3、java笔试手写算法面试题大全含答案 4、java递归算法练习:使用递归算法写个程序计算n! ...11、《java经典算法》之...
  • 知识体系树状图:四种算法思想 四种算法关系 如果我们将这四种算法思想分一下类,那贪心、回溯、动态规划可以归为一类,而分治单独可以作为一类,因为它跟其他三个都不大一样。为什么这么说呢?前三个算法解决...
  • 强化学习经典算法笔记——时间差分算法 强化学习经典算法笔记(零):贝尔曼方程的推导 强化学习经典算法笔记(一):价值迭代算法Value Iteration 强化学习经典算法笔记(二):策略迭代算法Policy Iteration 强化...
  • 今后继续整理算法并写出自己的理解和备注。 C++实现的:高效进制转换1、 高效进制转换 <1> 题目描述:对一个 unsigned long 的整数,将其转换为对应的16进制数 <2> 方法一:使用数组存储数据 <3> 方法二:使用栈存储...
  • 四种聚类算法的比较

    万次阅读 2016-04-15 21:41:54
    聚类分析是一重要的人类行为,早在孩提时代,一个人就通过不断改进下意识中的聚类模式来学会如何区分猫狗、动物植物。目前在许多领域都得到了广泛的研究和成功的应用,如用于模式识别、数据分析、图像处理、市场...
  • 大数据算法 十大经典算法

    万次阅读 2017-12-27 14:39:08
    C4.5,是机器学习算法中的一个分类决策树算法, 它是决策树(决策树也就是做决策的节点间的组织方式像一棵树,其实是一个倒树)核心算法 ID3的改进算法,所以基本上了解了一半决策树构造方法就能构造它。 ...
  • 数据挖掘领域十大经典算法之—EM算法

    万次阅读 多人点赞 2018-03-08 14:53:25
    数据挖掘领域十大经典算法之—C4.5算法(超详细附代码) 数据挖掘领域十大经典算法之—K-Means算法(超详细附代码) 数据挖掘领域十大经典算法之—Apriori算法 数据挖掘领域十大经典算法之—EM算法 数据挖掘...
  • 十大经典算法

    千次阅读 2018-03-01 15:35:13
    第十名:Huffman coding(霍夫曼编码) 霍夫曼编码(Huffman Coding)是一编码方式,是一用于无损数据压缩的熵编码(权编码)算法。1952年,David A. Huffman在麻省理工攻读博士时所发明的,并发表于《一构建极...
  • 权威分析各种实现网络流算法的时间复杂度 简单总结 FF算法: 利用dfs实现,时间复杂度O(V*E^2) EK算法:利用bfs实现,时间复杂度O(V*E^2) Dinic算法:递归实现,时间复杂度O(V^2*E) SAP算法:时间复杂度O...
  • 四种求最大公约数算法

    千次阅读 2019-03-09 21:32:33
    四种求最大公约数算法 1. 题目 运行最大公约数的常用算法,并进行程序的调式与测试,要求程序设计风格良好,并添加异常处理模块(如输入非法等)。 分析最大公约数的4种算法,补充完整算法, 进行程序的调式与测试...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,072,164
精华内容 428,865
关键字:

四种经典算法