烟台建设集团招聘信息网站,做个中英文网站多少钱,网络商城网站怎样做关键词优化,wordpress怎么进入论坛一 选择排序 原理#xff1a;选择排序很简单#xff0c;他的步骤如下#xff1a; 从左至右遍历#xff0c;找到最小(大)的元素#xff0c;然后与第一个元素交换。从剩余未排序元素中继续寻找最小#xff08;大#xff09;元素#xff0c;然后与第二个元素进行交换。以此…一 选择排序 原理选择排序很简单他的步骤如下 从左至右遍历找到最小(大)的元素然后与第一个元素交换。从剩余未排序元素中继续寻找最小大元素然后与第二个元素进行交换。以此类推直到所有元素均排序完毕。 之所以称之为选择排序是因为每一次遍历未排序的序列我们总是从中选择出最小的元素。下面是选择排序的动画演示 public class Sort {//选择排序public static void SelectionSort(int[] array) {int n array.length;for (int i 0; i n; i) {int min i; // 从第i1个元素开始找最小值for (int j i 1; j n; j) {if (array[min] array[j])min j;}Swap(array, i, min);}}//插入排序public static void insertionSort(int[] array){int n array.length;for (int i 1; i n; i) {for (int j i; j 0; j--) {if (array[j] array[j-1])Swap(array, j, j-1);elsebreak;} }}//冒泡排序public static void bubbleSort(int[] array){int n array.length;for (int i 0; i n; i) {for (int j n-1; j i; j--) {if (array[j] array[j-1])Swap(array, j, j-1);} }}//希尔排序public static void shellSort(int[] arr){int Narr.length;int h1;while(hN/3){h3*h1;}while (h1) {for(int i h; i N; i) {for (int j i; jh(arr[j]arr[j-h]); j-h) {swap(arr, j, j-h); }}hh/3;}}private static void Swap(int[] array, int i, int min) {int temp array[i];array[i] array[min];array[min] temp;}private static void printArr(int[] array){for (int i 0; i array.length; i) {System.out.print(array[i] );}System.out.println();}public static void main(String[] args) {int[] array new int[] { 1, 3, 1, 4, 2, 4, 2, 3, 2, 4, 7, 6, 6, 7, 5,5, 7, 7 };System.out.println(Before Sort:);printArr(array);//SelectionSort(array);//insertionSort(array);bubbleSort(array);System.out.println(After Sort:);printArr(array);}
} View Code 下图分析了选择排序中每一次排序的过程您可以对照图中右边的柱状图来看。 (array); 分析 选择排序的在各种初始条件下的排序效果如下 选择排序需要花费 (N – 1) (N – 2) … 1 0 N(N- 1) / 2 ~ N2/2次比较 和 N-1次交换操作。对初始数据不敏感不管初始的数据有没有排好序都需要经历N2/2次比较这对于一些原本排好序或者近似排好序的序列来说并不具有优势。在最好的情况下即所有的排好序需要0次交换最差的情况倒序需要N-1次交换。数据交换的次数较少如果某个元素位于正确的最终位置上则它不会被移动。在最差情况下也只需要进行N-1次数据交换在所有的完全依靠交换去移动元素的排序方法中选择排序属于比较好的一种。二 插入排序 原理 插入排序也是一种比较直观的排序方式。可以以我们平常打扑克牌为例来说明假设我们那在手上的牌都是排好序的那么插入排序可以理解为我们每一次将摸到的牌和手中的牌从左到右依次进行对比如果找到合适的位置则直接插入。具体的步骤为 从第一个元素开始该元素可以认为已经被排序取出下一个元素在已经排序的元素序列中从后向前扫描如果该元素小于前面的元素则依次与前面元素进行比较如果小于则交换直到找到大于该元素的就则停止如果该元素大于前面的元素已排序则重复步骤2重复步骤2~4 直到所有元素都排好序 。 下面是插入排序的动画演示 分析 插入排序的在各种初始条件下的排序效果如下 1. 插入排序平均需要N2/4次比较和N2/4 次交换。在最坏的情况下需要N2/2 次比较和交换在最好的情况下只需要N-1次比较和0次交换。 先考虑最坏情况那就是所有的元素逆序排列那么第i个元素需要与前面的i-1个元素进行i-1次比较和交换所有的加起来大概等于N(N- 1) / 2 ~ N2 / 2在数组随机排列的情况下只需要和前面一半的元素进行比较和交换所以平均需要N2/4次比较和N2/4 次交换。 在最好的情况下所有元素都排好序只需要从第二个元素开始都和前面的元素比较一次即可不需要交换所以为N-1次比较和0次交换。 2. 插入排序中元素交换的次数等于序列中逆序元素的对数。元素比较的次数最少为元素逆序元素的对数最多为元素逆序的对数 加上数组的个数减1。 3.总体来说插入排序对于部分有序序列以及元素个数比较小的序列是一种比较有效的方式。 如上图中序列AEELMOTRXPS中逆序的对数为T-RT-PT-SR-PX-S 6对。典型的部分有序队列的特征有 数组中每个元素离最终排好序后的位置不太远小的未排序的数组添加到大的已排好序的数组后面数组中只有个别元素未排好序 对于部分有序数组插入排序是比较有效的。当数组中逆元素的对数越低插入排序要比其他排序方法要高效的多。 选择排序和插入排序的比较 上图展示了插入排序和选择排序的动画效果。图中灰色的柱子是不用动的黑色的是需要参与到比较中的红色的是参与交换的。图中可以看出插入排序不会动右边的元素选择排序不会动左边的元素由于插入排序涉及到的未触及的元素要比插入的元素要少涉及到的比较操作平均要比选择排序少一半。 3.冒泡排序 冒泡排序也被称为下沉排序是一个简单的排序算法通过多次重复比较每对相邻的元素并按规定的顺序交换他们最终把数列进行排好序。一直重复下去直到结束。该算法得名于较小元素“气泡”会“浮到”列表顶部。由于只使用了比较操作所以这是一个比较排序。冒泡排序算法的运作如下 比较相邻的元素。如果第一个比第二个大就交换他们两个。对每一对相邻元素作同样的工作从开始第一对到结尾的最后一对。这步做完后最后的元素会是最大的数。针对所有的元素重复以上的步骤除了最后一个。持续每次对越来越少的元素重复上面的步骤直到没有任何一对数字需要比较。 时间复杂度 若文件的初始状态是正序的一趟扫描即可完成排序。所需的关键字比较次数 C和记录移动次数 M均达到最小值 Cminn-1Mmin0。所以冒泡排序最好的时间复杂度为 O(n)。 若初始文件是反序的需要进行 n-1趟排序。每趟排序要进行 n-i次关键字的比较(1≤i≤n-1)且每次比较都必须移动记录三次来达到交换记录位置。在这种情况下比较和移动次数均达到最大值 冒泡排序的最坏时间复杂度为O(n*n)综上因此冒泡排序总的平均时间复杂度为O(n*n)。 算法稳定性 冒泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个元素比较交换也发生在这两个元素之间。所以如果两个元素相等我想你是不会再无聊地把他们俩交换一下的如果两个相等的元素没有相邻那么即使通过前面的两两交换把两个相邻起来这时候也不会交换所以相同元素的前后顺序并没有改变所以冒泡排序是一种稳定排序算法。 希尔排序 原理希尔排序也称之为递减增量排序它是对插入排序的改进。在插入排序中我们知道插入排序对于近似已排好序的序列来说效率很高可以达到线性排序的效率。但是插入排序效率也是比较低的他 一次只能将数据向前移一位。比如如果一个长度为N的序列最小的元素如果恰巧在末尾那么使用插入排序仍需一步一步的向前移动和比较要N-1次比较和交 换。希尔排序通过将待比较的元素划分为几个区域来提升插入排序的效率。这样可以让元素可以一次性的朝最终位置迈进一大步然后算法再取越来越小的步长进行排序最后一步就是步长为1的普通的插入排序的但是这个时候整个序列已经是近似排好序的所以效率高。 如下图我们对下面数组进行 排序的时候首先以4为步长这是元素分为了LMPTEHSSELOXAELR几个序列我们对这几个独立的序列 进行插入排序排序完成之后我们减小步长继续排序最后直到步长为1步长为1即为一般的插入排序他保证了元素一定会被排序。 希尔排序的增量递减算法可以随意指定可以以N/2递减只要保证最后的步长为1即可。 实现 public static void shellSort(int[] arr){int Narr.length;int h1;while(hN/3){h3*h1;}while (h1) {for(int i h; i N; i) {for (int j i; jh; j-h) {if(arr[j]arr[j-h]){swap(arr, j, j-h);}else{break;}}}hh/3;}
}可以看到希尔排序的实现是在插入排序的基础上改进的插入排序的步长为1每一次递减1希尔排序的步长为我们定义的h然后每一次和前面的-h位置上的元素进行比较。算法中我们首先获取小于N/3 的最大的步长然后逐步长递减至步长为1的一般的插入排序。 下面是希尔排序在各种情况下的排序动画 分析 1. 希尔排序的关键在于步长递减序列的确定任何递减至1步长的序列都可以目前已知的比较好的序列有 Shell’s 序列: N/2 , N/4 , …, 1 (重复除以2);Hibbard’s 序列: 1, 3, 7, …, 2k – 1 ;Knuth’s 序列: 1, 4, 13, …, (3k – 1) / 2 ;该序列是本文代码中使用的序列。已知最好的序列是 Sedgewick’s (Knuth的学生Algorithems的作者)的序列: 1, 5, 19, 41, 109, ….该序列由下面两个表达式交互获得: 1, 19, 109, 505, 2161,….., 9(4k – 2k) 1, k 0, 1, 2, 3,…5, 41, 209, 929, 3905,…..2k2 (2k2 – 3 ) 1, k 0, 1, 2, 3, … “比较在希尔排序中是最主要的操作而不是交换。”用这样步长的希尔排序比插入排序和堆排序都要快甚至在小数组中比快速排序还快但是在涉及大量数据时希尔排序还是比快速排序慢。 2. 希尔排序的分析比较复杂使用Hibbard’s 递减步长序列的时间复杂度为O(N3/2)平均时间复杂度大约为O(N5/4) ,具体的复杂度目前仍存在争议。 3. 实验表明对于中型的序列( 万)希尔排序的时间复杂度接近最快的排序算法的时间复杂度nlogn。 最后总结一下本文介绍的三种排序算法的最好最坏和平均时间复杂度。 名称最好平均最坏内存占用稳定排序插入排序nn2n21是选择排序n2n2n21否希尔排序nnlog2n 或 n3/2依赖于增量递减序列目前最好的是 nlog2n1否转载于:https://www.cnblogs.com/wxgblogs/p/5499569.html
