网站开发工作容易出现的失误,西安抖音代运营公司,音乐中文网站模板下载,招远网站制作这里详细讲解了十大经典算法的分类#xff0c;例如交换排序、插入排序、选择排序等比较类排序#xff0c;以及计数排序、桶排序和基数排序的非比较类排序#xff0c;分析了各种排序算法的复杂度和稳定性#xff0c;还有JAVA代码的详细实现。对冒泡排序、插入排序、选择排序…这里详细讲解了十大经典算法的分类例如交换排序、插入排序、选择排序等比较类排序以及计数排序、桶排序和基数排序的非比较类排序分析了各种排序算法的复杂度和稳定性还有JAVA代码的详细实现。对冒泡排序、插入排序、选择排序和堆排序等十种算法进行了详细的思想总结。一、算法概述1、算法分类十种常见排序算法可以分为两大类(1)比较类排序通过比较来决定元素间的相对次序由于其时间复杂度不能突破O(nlogn)因此也称为非线性时间比较类排序。(2)非比较类排序不通过比较元素间的相对次序它可以突破基于比较排序的时间下界以线性时间运行因此也称为线性时间非比较类排序。2、算法复杂度3、相关概念(1)稳定如果a原本在b前面而ab排序之后a仍然在b的前面。(2)不稳定如果a原本在b的前面而ab排序之后 a 可能会出现在 b 的后面。(3)时间复杂度对排序数据的总的操作次数。反映当n变化时操作次数呈现什么规律。(4)空间复杂度是指算法在计算机内执行时所需存储空间的度量它也是数据规模n的函数。二、排序算法的代码实现1、冒泡排序(Bubble Sort)冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列一次比较两个元素如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。1.1、算法描述(1)比较相邻的元素。如果第一个比第二个大就交换它们两个(2)对每一对相邻元素作同样的工作从开始第一对到结尾的最后一对这样在最后的元素应该会是最大的数(3)针对所有的元素重复以上的步骤除了最后一个(4)重复步骤1~3直到排序完成。1.2、代码实现(1)java代码的一般实现// 一般的冒泡排序public static void BubbleSort(int[] arr){int temp; //临时变量for (int i arr.length-1;i 0 ; i--){ // 表示趟数一共arr.length-1次for (int j 0;j i; j){ // 表示比较次数,从后往前每趟比较把最大的冒到最后面System.out.println(第(arr.length-i)趟 第(j1)次比较Arrays.toString(arr));if(arr[j] arr[j1]){temp arr[j];arr[j] arr[j1];arr[j1] temp;}}}}(2)优化的排序算法针对问题数据的顺序排好之后冒泡算法仍然会继续进行下一轮的比较直到arr.length-1次后面的比较没有意义的。改进方案设置标志位flag如果发生了交换flag设置为true如果没有交换就设置为false。这样当一轮比较结束后如果flag仍为false即这一轮没有发生交换说明数据的顺序已经排好没有必要继续进行下去。public static void BubbleSort(int[] arr){int temp; //临时变量boolean flag; //是否交换的标记for (int i arr.length-1;i 0 ; i--){ // 表示趟数一共arr.length-1次flag false; //设置起始标志位为falsefor (int j 0;j i; j){ // 表示比较次数,从后往前每趟比较把最大的冒到最后面System.out.println(第(arr.length-i)趟 第(j1)次比较Arrays.toString(arr));if(arr[j] arr[j1]){temp arr[j];arr[j] arr[j1];arr[j1] temp;flag true;}}if (!flag) break;}}(3)改进的鸡尾酒冒泡排序改进的冒泡排序鸡尾酒冒泡排序也叫定向冒泡排序它的改进在于同时的冒泡两边从低到高然后从高到低相当于顺便把最小的数也冒泡到最前面。public static void cocktailSort(int[] arr){int left 0,right arr.length -1,temp;while (left right){for (int i left;i right;i){ //将最大值冒到数组末尾if (arr[i] arr[i1]){temp arr[i];arr[i] arr[i1];arr[i1] temp;}}right--;for (int i right;i left;i--){ //将较小值冒到数组前面if (arr[i] arr[i-1]){temp arr[i];arr[i] arr[i-1];arr[i-1] temp;}}left;}}2、选择排序(SelctionSort)选择排序(Selection-sort)是一种简单直观的排序算法。它的工作原理首先在未排序序列中找到最小(大)元素存放到排序序列的起始位置然后再从剩余未排序元素中继续寻找最小(大)元素然后放到已排序序列的末尾。以此类推直到所有元素均排序完毕。2.1、算法描述n个记录的直接选择排序可经过n-1趟直接选择排序得到有序结果。具体算法描述如下(1)初始状态无序区为R[1..n]有序区为空(2)第i趟排序(i1,2,3…n-1)开始时当前有序区和无序区分别为R[1..i-1]和R(i..n)。该趟排序从当前无序区中-选出关键字最小的记录 R[k]将它与无序区的第1个记录R交换使R[1..i]和R[i1..n)分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区(3)n-1趟结束数组有序化了。2.2、代码实现public static void selectSort(int[] arr){//从无序的数组中选出最小值替换到数组最前面for(int i 0;i arr.length - 1;i){int minIndex i;for(int j i 1;j arr.length;j){if (arr[minIndex] arr[j]){minIndex j;}}int temp arr[i];arr[i] arr[minIndex];arr[minIndex] temp;System.out.println(第(i1)次选择Arrays.toString(arr));}}2.3、算法分析表现最稳定的排序算法之一因为无论什么数据进去都是O(n2)的时间复杂度所以用到它的时候数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。理论上讲选择排序可能也是平时排序一般人想到的最多的排序方法了吧。3、插入排序(Insertion Sort)插入排序(Insertion-Sort)的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列对于未排序数据在已排序序列中从后向前扫描找到相应位置并插入。3.1算法描述一般来说插入排序都采用in-place在数组上实现。具体算法描述如下(1)从第一个元素开始该元素可以认为已经被排序(2)取出下一个元素在已经排序的元素序列中从后向前扫描(3)如果该元素(已排序)大于新元素将该元素移到下一位置(4)重复步骤3直到找到已排序的元素小于或者等于新元素的位置(5)将新元素插入到该位置后(6)重复步骤2~5。3.2、代码实现public static void insetSort(int[] arr){for (int i 0;i arr.length;i){for (int j i;j 0;j--){//配合交换的实现if (arr[j] arr[j-1]){int temp arr[j];arr[j] arr[j-1];arr[j-1] temp;}else {break;}}System.out.println(第(i1)次插入Arrays.toString(arr));}}3.3、算法分析插入排序在实现上通常采用in-place排序(即只需用到O(1)的额外空间的排序)因而在从后向前扫描过程中需要反复把已排序元素逐步向后挪位为最新元素提供插入空间。4、希尔排序(Shell Sort)第一个突破O(n2)的排序算法是简单插入排序的改进版。它与插入排序的不同之处在于它会优先比较距离较远的元素。希尔排序又叫缩小增量排序。4.1、算法描述先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序具体算法描述(1)选择一个增量序列t1t2…tk其中titjtk1(2)按增量序列个数k对序列进行k 趟排序(3)每趟排序根据对应的增量ti将待排序列分割成若干长度为m 的子序列分别对各子表进行直接插入排序。仅增量因子为1 时整个序列作为一个表来处理表长度即为整个序列的长度。4.2、代码实现public static void ShellSort(int[] arr){//定义增量序列数组长度的每次折半int incre arr.length;int n 0;while (true){n 1;incre incre / 2;System.out.println(第n遍排序增量序列为increArrays.toString(arr));// 根据增量拆分成不同的数组序列拆分为incre组for (int k 0;k incre; k){ //对拆分的序列用插入排序for (int i k;i arr.length;i incre){for (int j i;jk;j-incre){if (arr[j] arr[j-incre]){int temp arr[j];arr[j] arr[j-incre];arr[j-incre] temp;}else {break;}}}}if (incre 1){break;}}}4.3、算法分析希尔排序的核心在于间隔序列的设定。既可以提前设定好间隔序列也可以动态的定义间隔序列。动态定义间隔序列的算法是《算法(第4版)》的合著者Robert Sedgewick提出的。5、归并排序(Merge Sort)归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并得到完全有序的序列即先使每个子序列有序再使子序列段间有序。若将两个有序表合并成一个有序表称为2-路归并。5.1、算法描述(1)把长度为n的输入序列分成两个长度为n/2的子序列(2)对这两个子序列分别采用归并排序(3)将两个排序好的子序列合并成一个最终的排序序列。5.2、代码实现public static int[] MergeSort(int[] arr){if (arr.length 2) return arr;int mid arr.length / 2;int[] left Arrays.copyOfRange(arr,0,mid);int[] right Arrays.copyOfRange(arr,mid,arr.length);return merge_sort(MergeSort(left),MergeSort(right));}public static int[] merge_sort(int[] left,int[] right){int[] newarr new int[left.length right.length];for (int index 0,i 0,j 0;index newarr.length;index){if (i left.length){newarr[index] right[j];}else if (j right.length){newarr[index] left[i];}else if (left[i] right[j]){newarr[index] right[j];}else {newarr[index] left[i];}}return newarr;}5.3、算法分析归并排序是一种稳定的排序方法。和选择排序一样归并排序的性能不受输入数据的影响但表现比选择排序好的多因为始终都是O(nlogn)的时间复杂度。代价是需要额外的内存空间。6、快速排序(Quick Sort)快速排序的基本思想通过一趟排序将待排记录分隔成独立的两部分其中一部分记录的关键字均比另一部分的关键字小则可分别对这两部分记录继续进行排序以达到整个序列有序。6.1、算法描述快速排序使用分治法来把一个串(list)分为两个子串(sub-lists)。具体算法描述如下(1)从数列中挑出一个元素称为 “基准”(pivot)(2)重新排序数列所有元素比基准值小的摆放在基准前面所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分区退出之后该基准就处于数列的中间位置。这个称为分区(partition)操作(3)递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序。6.2、代码实现public static void QuickSort(int[] arr,int left,int right){if (left right){return;}//选择第一个数为keyint l left,r right;int key arr[left];while (l r){//先从右边找到第一个小于key的数while (l r key arr[r]){r--;}if (l r){arr[l] arr[r];l;}//再从左边起找到第一个大于key的值while (l r key arr[l]){l;}if (larr[r] arr[l];r--;}arr[l] key;QuickSort(arr,left,l-1);QuickSort(arr,l1,right);}}public static void QuickSortFunc(int[] arr){int left 0;int right arr.length-1;QuickSort(arr,left,right);}7、堆排序(Heap Sort)堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构并同时满足堆积的性质即子结点的键值或索引总是小于(或者大于)它的父节点。7.1、算法描述(1)将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆此堆为初始的无序区(2)将堆顶元素R[1]与最后一个元素R[n]交换此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]R[n](3)由于交换后新的堆顶R[1]可能违反堆的性质因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆然后再次将R[1]与无序区最后一个元素交换得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1则整个排序过程完成。7.2、代码实现public static void HeapSort(int[] arr){//1、构建大项堆for (int i arr.length/2 - 1;i0;i--){//从第一个非叶子节点从下至上从右至左调整结构adjustHeap(arr,i,arr.length);}//2、调整堆结构交换堆顶元素与末尾元素for(int j arr.length-1;j0;j--){int temp arr[0];arr[0] arr[j];arr[j] temp; //将堆顶元素与末尾元素进行交换adjustHeap(arr,0,j); //重新进行堆调整}}//调整堆public static void adjustHeap(int[] arr,int i,int length){//先取出当前元素iint temp arr[i];//从i结点的左子结点开始也就是2i1处开始for (int k i*2 1;k//如果左子节点小于右子节点k指向右子节点if(k1k;}if (arr[k] temp){//如果子节点大于父节点将子节点值付给父节点(不用进行交换)arr[i] arr[k];i k;}else {break;}}arr[i] temp; //将temp值放到最终的位置}8、计数排序(Counting Sort)计数排序不是基于比较的排序算法其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。 作为一种线性时间复杂度的排序计数排序要求输入的数据必须是有确定范围的整数。它的优势在于在对于较小范围内的整数排序。它的复杂度为Ο(nk)(其中k是待排序数的范围)快于任何比较排序算法缺点就是非常消耗空间。很明显如果而且当O(k)O(n*log(n))的时候其效率反而不如基于比较的排序比如堆排序和归并排序和快速排序。要求待排序数中最大数值不能太大。8.1、算法描述(1)找出待排序的数组中最大和最小的元素(2)统计数组中每个值为i的元素出现的次数存入数组C的第i项(3)对所有的计数累加(从C中的第一个元素开始每一项和前一项相加)(4)反向填充目标数组将每个元素i放在新数组的第C(i)项每放一个元素就将C(i)减去1。8.2、代码实现public static int[] CountSort(int[] arr){//1、找出数组arr中的最大值int k arr[0];for (int i 1;i arr.length;i){if (k arr[i]){k arr[i];}}//2、构造C数组将A中每个元素对应C中的元素大小1int[] C new int[k1];int sum 0;for (int i 0;i arr.length;i){C[arr[i]] 1; //统计A中各元素个数对应到C数组}//3、将C中每个i位置的元素大小改成C数组前i项和for (int i0;isum C[i];C[i] sum;}//4、构造B数组初始化一个和A同样大小的数组B用于存储排序后数组然后倒序遍历A中元素(后面会提到为何要倒序遍历)通过查找C数组将该元素放置到B中相应的位置同时将C中对应的元素大小-1(表明已经放置了一个这样大小的元素下次再放同样大小的元素就要往前挤一个位置)int[] B new int[arr.length];for (int i arr.length-1;i0;i--){ //倒序遍历A数组构造B数组B[C[arr[i]]-1] arr[i]; //将A中该元素放到排序后数组B中指定的位置C[arr[i]]--; //将C中该元素-1方便存放下一个同样大小的元素}//5、将排序好的数组B返回完成排序return B;}8.3、算法分析计数排序是一个稳定的排序算法。当输入的元素是 n 个 0到 k 之间的整数时时间复杂度是O(nk)空间复杂度也是O(nk)其排序速度快于任何比较排序算法。当k不是很大并且序列比较集中时计数排序是一个很有效的排序算法。9、桶排序桶排序是计数排序的升级版。它利用了函数的映射关系高效与否的关键就在于这个映射函数的确定。桶排序 (Bucket sort)的工作的原理假设输入数据服从均匀分布将数据分到有限数量的桶里每个桶再分别排序(有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排)。要求待排序数长度一致。9.1、算法描述(1)设置一个定量的数组当作空桶(2)遍历输入数据并且把数据一个一个放到对应的桶里去(3)对每个不是空的桶进行排序(4)从不是空的桶里把排好序的数据拼接起来。9.2、代码实现算法实现逻辑(1)找出待排序数组中的最大值max、最小值min(2)我们使用 动态数组ArrayList 作为桶桶里放的元素也用 ArrayList 存储。桶的数量为(max-min)/arr.length1(3)遍历数组 arr计算每个元素 arr[i] 放的桶(4)每个桶各自排序(5)遍历桶数组把排序好的元素放进输出数组public static void BucketSort(int[] arr){int max Integer.MIN_VALUE;int min Integer.MAX_VALUE;for (int i 0;i arr.length;i){max Math.max(max,arr[i]);min Math.min(min,arr[i]);}//计算桶数int bucketNum (max - min) / arr.length 1;ArrayList bunketArr new ArrayList(bucketNum);for (int i 0;i bucketNum;i){bunketArr.add(new ArrayList());}for (int i 0;iint num (arr[i] - min) / (arr.length);bunketArr.get(num).add(arr[i]);}//对每个桶进行排序for (int i 0;i bunketArr.size();i){Collections.sort(bunketArr.get(i));}//将桶中排好序的数据依次复制回原数组int index 0;for (int i 0;i bucketNum;i){for (int j 0;j bunketArr.get(i).size();j){arr[index] bunketArr.get(i).get(j);}}}9.3、算法分析桶排序最好情况下使用线性时间O(n)桶排序的时间复杂度取决与对各个桶之间数据进行排序的时间复杂度因为其它部分的时间复杂度都为O(n)。很显然桶划分的越小各个桶之间的数据越少排序所用的时间也会越少。但相应的空间消耗就会增大。10、基数排序(Radix Sort)基数排序是按照低位先排序然后收集再按照高位排序然后再收集依次类推直到最高位。有时候有些属性是有优先级顺序的先按低优先级排序再按高优先级排序。最后的次序就是高优先级高的在前高优先级相同的低优先级高的在前。基数排序属于“分配式排序”(distribution sort)是非比较类线性时间排序的一种又称“桶子法”(bucket sort)顾名思义它是透过键值的部分信息将要排序的元素分配至某些“桶”中藉以达到排序的作用。10.1、算法描述基数排序(以×××为例)将×××10进制按每位拆分然后从低位到高位依次比较各个位。主要分为两个过程(1)分配先从个位开始根据位值(0-9)分别放到0~9号桶中(比如4个位为则放入号桶中)(2)收集再将放置在0~9号桶中的数据按顺序放到数组中(3)重复(1)(2)过程从个位到最高位(比如32位无符号整型最大数4294967296最高位为第10位)。基数排序的方式可以采用LSD(Least Significant Digital)或MSD(Most Significant Digital)LSD的排序方式由键值的最右边开始而MSD则相反由键值的最左边开始。10.2、代码实现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 bucketList newArrayList();for (int i 0; i 10; i)bucketList.add(new ArrayList());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;}10.3、算法分析基数排序基于分别排序分别收集所以是稳定的。但基数排序的性能比桶排序要略差每一次关键字的桶分配都需要O(n)的时间复杂度而且分配之后得到新的关键字序列又需要O(n)的时间复杂度。假如待排数据可以分为d个关键字则基数排序的时间复杂度将是O(d*2n) 当然d要远远小于n因此基本上还是线性级别的。基数排序的空间复杂度为O(nk)其中k为桶的数量。一般来说nk因此额外空间需要大概n个左右。
