浦东新区建设机械网站,百度竞价排名机制,成品人和精品人的区别在哪约,wordpress关键词描述最详细的排序解析#xff0c;理解七大排序 mp.weixin.qq.com点击上方“方志朋”#xff0c;选择“置顶或者星标” 你的关注意义重大#xff01; 注#xff1a; lgN在这里为1og2N简写 为了方便描述,本文默认用int类型比较#xff0c;从小到大排序 本文排序算法以java语言… 最详细的排序解析理解七大排序 mp.weixin.qq.com 点击上方“方志朋”选择“置顶或者星标” 你的关注意义重大 注 lgN在这里为1og2N简写 为了方便描述,本文默认用int类型比较从小到大排序 本文排序算法以java语言实现 本文的排序都是比较排序 比较次数和赋值和交换次数有的排序不好分析可能不准确 一.插入排序 对于未排序数据在已排序序列中从后向前扫描找到相应位置并插入 从第一个元素开始该元素认为已经被排序 取出下一个元素在已排序的元素序列中从后向前扫描 如果已排序元素大于新元素新元素继续比较前一个元素直到找到已排序的元素小于或者等于新元素的位置 将新元素插入到该位置后 重复步骤2~4。 java实现 public static void insertionSort(int[] a){int insertIndex,insertElement;for(int i 1; i a.length; i){ //外层循环默认第一个元素有序从第二个元素开始时间复杂度NinsertIndex i - 1; //插入的位置默认有序数列的最后一个元素的位置insertElement a[i]; //新插入的元素默认外层循环的元素while(insertIndex 0 a[insertIndex] insertElement){ //内层循环只要新元素比待插入位置的元素小就继续时间复杂度Na[insertIndex 1] a[insertIndex]; //比待插入元素大的元素后移一位insertIndex--; //插入位置前移一位}a[insertIndex 1] insertElement; //内层循环结束把新元素放到插入位置后面}
} 插入排序为两层循环嵌套时间复杂度O(N2),插入排序的while循环是先比较移动待插入的位置循环结束才真正交换数据位置。这里需要注意常用的for循环嵌套进行插入排序会导致每次插入一直和前面元素交换直到插入到待插入位置上面的内循环用while寻找待插入位置把其他元素后移的算法更合理每次插入只一次进行一次交换。因插入排序每次只比较一位对于逆序较多的数组效率较低衍生算法希尔排序会大幅加快逆序交换后面详细介绍。 二.选择排序 在未排序序列中找到最小元素放到排序序列的起始位置然后再从剩余未排序元素中继续寻找最小元素然后放到已排序序列的末尾循环直到所有元素均排序完毕。 初始状态无序区为R[1..n]有序区为空 第i趟排序(i1,2,3…n-1)开始时当前有序区和无序区分别为R[1..i-1]和R[i..n]。该趟排序从当前无序区中选出最小的记录 R[k]将它与无序区的第1个记录R[i]交换使R[1..i]和R[i1..n]分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区 循环n-1次排序完成。 java实现 public static void selectionSort(int[] a){int minIndex,temp;for(int i 0; i a.length - 1; i){ //外层循环从无序区第一个元素开始到数组倒数第二个元素时间复杂度NminIndex i; //每次外层循环假设无序区第一个元素是最小元素for(int j i 1; j a.length; j){ //内层循环从假设的最小元素的后一个位置开始到数组最后一个元素时间复杂度Nif(a[j] minIndex){ //判断内层循环的元素是否小于假设的最小元素 minIndex j; //如果比最小元素小标记该元素的位置为新的最小元素的位置内层循环完毕会找出无序区的最小值 }} temp a[i]; a[i] a[minIndex];a[minIndex] temp; //无序区真正最小值和第一个元素交换位置下一次循环无序区从下一个值开始}
} 选择排序为两层for循环嵌套内层循环始终去找最小值放到最前面。交换次数比冒泡排序少很多所以实际执行效率比冒泡排序快。 衍生算法双向选择排序每次循环同时选出最大值放在末尾最小值放在前方可以提高选择效率。 三.冒泡排序 重复地走访过要排序的数列一次比较两个元素如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换 初始状态无序区为R[1..n]有序区为空 第i趟排序(i0,1,2…n-1)开始时当前无序区和有序区分别为R[0..n-i]和R[n-i1..n]。对每一对相邻元素进行比较从开始第一对到结尾的最后一对如果第一个比第二个大就交换它们两个这样在最后的元素应该会是最大的数使R[1..n-i-1]和R[n-i..n]分别变为记录个数减少1个的新无序区和记录个数增加1个的新有序区 循环n-1次直到排序完成。 java实现 public static void bubbleSort(int[] a){int temp;for(int i 0; i a.length - 1; i){ //外层循环从数组第一个元素到倒数第二个元素时间复杂度为Nfor(int j 0; j a.length - 1 -i; j){ //内层循环从数组第一个元素到剩余的元素减去有序区的元素if(a[j] a[j1]){ temp a[j1];a[j1] a[j];a[j] temp; //相邻元素只要前面的比后面的大就交换位置}}}
} 冒泡排序在代码实现上是最简单的不需要什么思考两层for循环嵌套比大小交换。因为冒泡通常的例子都是让大的往后移对于刚接触排序的人来说看来上面可能认为冒泡排序与选择排序是反向操作其实冒泡排序也可以把小数向前移这样能明显的看出冒泡排序和选择的排序的不同针对无序区的元素冒泡排序总是不断地交换而选择排序是先找出最小的元素再做一次交换。 衍生算法鸡尾酒排序该排序从左往右找出最大值后再从右往左找出最小值类似鸡尾酒搅拌左右循环。在某些情况下优于冒泡排序以序列(2,3,4,5,1)为例鸡尾酒排序只需要访问两次升序降序各一次 次序列就可以完成排序但如果使用冒泡排序则需要四次。 四.希尔排序 插入排序的改进版优先比较距离远的元素减少交换次数 1.选择一个增量序列t1t2…tk其中titjtk1 2.按增量序列个数k对序列进行k 趟排序 3.每趟排序根据对应的增量ti将待排序列分割成若干长度为m 的子序列分别对各子表进行直接插入排序。仅增量因子为1 时整个序列作为一个表来处理表长度即为整个序列的长度。 java实现 public static void shellSort(int[] a){int h 1 //希尔排序是使间隔为h的元素有序int temp;while(h a.length/3) { //while循环扩大hh 3*h 1; //这里用3倍作为希尔排序的间隔是常用的值加1是为了防止排序的都是3的倍数}while(h 1){ //while循环让h从大到小插入排序for(int i h; i a.length; i){ //从h位置开始对整个数组遍历i为插入元素的位置temp a[i]; 把i当前值保存到temp中for(int j i - h; j 0 a[j] temp ;j - h){ //遍历把i每隔h位进行比较确定插入的位置a[j h] a[j]; //如果前面的元素大于temp把前面元素的值放在后面}a[j h] temp; //把原来i的值赋值给前面元素此时发生了j -h实际上j h等于循环里的j}h h/3; //更大间隔的插入完成缩小插入间隔}
} 上面是常用的写法每次比较如果前面的更大都会交换可以优化一下,直接把上面插入算法嵌入内循环比较的间隔由1改为h,比较的时候只移动插入位置比较完只需交换一次 java实现 public static void shellSort(int[] a){int h 1 //希尔排序是使间隔为h的元素有序int insertIndex,insertElement;while(h a.length/3) { //while循环扩大hh 3*h 1; //这里用3倍作为希尔排序的间隔是常用的值加1是为了防止排序的都是3的倍数}while(h 1){ //while循环让h从大到小插入排序for(int i h; i a.length; i){ //从h位置开始对整个数组遍历i为插入元素的位置insertIndex i - h; //插入的位置默认前面间隔h的位置insertElement a[i]; //新插入的元素默认外层循环的最后一个元素while(insertIndex 0 a[insertIndex] insertElement){ //内层循环只要新元素比待插入位置的元素小就继续a[insertIndex h] a[insertIndex]; //比待插入元素大的元素后移h位insertIndex - h; //插入位置前移h位}a[insertIndex h] insertElement; //内层循环结束把新元素放到插入位置后面}h h/3; //更大间隔的插入完成缩小插入间隔}
} 希尔排序的时间复杂度与增量序列的选取有关例如希尔增量时间复杂度为O(N²)而Hibbard增量的希尔排序的时间复杂度为O(N1.5)希尔排序时间复杂度的下界是Nlg2N。希尔排序没有快速排序算法快 O(N(lgN))因此中等大小规模表现良好对规模非常大的数据排序不是最优选择。但是比O(N²)复杂度的算法快得多。并且希尔排序非常容易实现算法代码短而简单。 此外希尔算法在最坏的情况下和平均情况下执行效率相差不是很多与此同时快速排序在最坏的情况下执行的效率会非常差。 五.堆排序 堆就是完全二叉树分为最大堆和最小堆最大堆要求节点的元素都要不小于其孩子最小堆要求节点元素都不大于其左右孩子对左右孩子的大小关系不做要求所以处于最大堆的根节点的元素一定是这个堆中的最大值。堆排序算法就是抓住了堆的这一特点每次都取堆顶的元素将其放在序列最后面然后将剩余的元素重新调整为最大堆依次类推最终得到排序的序列。 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则整个排序过程完成。 java实现 public static void heapSort(int[] a){int N a.length;for(int k N/2; k 1; k--){ //for循环用来构造堆最终生成最大堆sink(a,k,N);}while(N 1){ //循环排序无序区exch(a,1,N--); //堆顶a[1]与堆的最后一个元素a[N]交换位置并且去掉最后一个元素到有序区减小新堆sink(a,1,N); //重新生成为最大堆}
}/*** 从上至下堆有序化*/
private static void sink(int[] a,int k,int N){ while(2*k N) {int j 2*k;if(j N a[j] a[j1]){ //jn保证j1不越界a[j]和a[j1]是a[k]的左右子节点这里是为了选取两个子节点较大的一个a[j]大取a[j],a[j]小取a[j] a[j]) { //如果父节点大于等于值大的子节点堆有序终止循环break }if(a[k] a[j]) { //如果父节点大于等于值大的子节点堆有序终止循环break }exch(a,k,j); //交换值大的子节点和父节点的值达到堆有序k j; //子节点作为下一个循环的父节点继续下沉}
}/*** 交换两个元素*/
private static void exch(int[] a,int i,int j){int temp a[i];a[i] a[j];a[j] temp;
}}/n保证j1不越界a[j]和a[j1]是a[k]的左右子节点这里是为了选取两个子节点较大的一个a[j]大取a[j],a[j]小取a[j] 因为堆的父节点k的子节点为2k和2k1下标为0会导致父节点和左子节点都是0所以上述排序的数组从下标从1开始比较方便。堆排序只需要NlgN的时间而且算法稳定只需要少量辅助空间是最优的利用时间和空间的方法但因为它的缓存命中率低应用很少用它多用于嵌入式。 六.归并排序 递归的把已有序列均分为两个子序列使子序列有序合并子序列 1.把长度为n的输入序列分成两个长度为n/2的子序列 2.对这两个子序列分别采用归并排序 3.将两个排序好的子序列合并成一个最终的排序序列。 java实现 private static int[] aux; //归并所需的辅助数组
public static void mergeSort(int[] a){aux new int[a.length];sort(a,0,a.length-1); //开始递归排序
}/*** 递归的排序归并*/
private static void sort(int[] a,int left,int right){if(right left){ //排序从左到右确保右边比左边大return;}int mid (left right)/2; //找出中间位置sort(a,left,mid); //将左半边排序sort(a,mid1,right); //将右半边排序merge(a,left,mid,right); //归并结果
}/*** 原地归并方法*/
private static void merge(int[] a,int left,int mid,int right){ //将a[left..mid]和a[mid1..right]归并int i left,j mid 1; //左右半边起始位置for(int k left; k right; k){ //将a[left..right]复制到aux[left..right]aux(k) a(k);}for(int k left; k right; k){ //归并回到a[left..right]if(i mid){ //i比mid大代表左半边用完只有右半边有元素a[k] aux[j]; //右边元素给a[k]}else if(j right){ //j比right大代表右半边用完只有左半边有元素a[k] aux[i]; //左边元素给a[k]}else if(aux[j] aux[i]){ //如果右边元素大于左边a[k] aux[j]; //右边元素给a[k] }else{ //否则左边大于等于右边a[k] aux[i]; //左边元素给a[k]}}
} 归并排序是分治法的典型应用高效稳定但是归并排序需要一个数组长度的辅助空间在空间成本高的时候不适合使用 七.快速排序 通过一趟排序将待排记录分隔成独立的两部分其中一部分记录的关键字均比另一部分的关键字小则可分别对这两部分记录继续进行排序以达到整个序列有序。 1.从数列中挑出一个元素称为 “基准”pivot 2.重新排序数列所有元素比基准值小的摆放在基准前面所有元素比基准值大的摆在基准的后面相同的数可以到任一边。在这个分区退出之后该基准就处于数列的中间位置。这个称为分区partition操作 3.递归地recursive把小于基准值元素的子数列和大于基准值元素的子数列排序。 java实现 public static void quickSort(int[] a){sort(a,0,a.length-1);
}/*** 递归进行快速排序*/
private static void sort(int[] a,int left,int right){if(right left){ //排序从左到右确保右边比左边大return;}int j partition(a,left,right); //切分sort(a,left,j-1); //将左半边排序sort(a,j1,right); //将右半边排序
}/*** 快速排序切分*/
private static int partition(int[] a,int left,int right){ int i left,j right 1; //左右扫描指针int v a[left]; //选取切分元素这里选第一个实际数据可以自行挑选while(true){while(a[i] v){ //a[i]v时增大i只要比v小继续往右扫描 i v a[--j]){ //a[j]v时减小j只要比v大继续往左扫描if(j left){ //扫描到左边则终止break;}}while(v a[--j]){ //a[j]v时减小j只要比v大继续往左扫描if(j left){ //扫描到左边则终止break;}}if(i j){ //如果左右指针交叉终止循环break; }exch(a,i,j); //不满足上述条件左边比v大右边比v小指针未交叉左右元素交换位置}exch(a,left,j); //将切分元素v放入正确的位置return j; //a[left..j-1]a[j]a[j1..right]并返回j
}/*** 交换两个元素*/
private static void exch(int[] a,int i,int j){int temp a[i];a[i] a[j];a[j] temp;
}/v时增大i只要比v小继续往右扫描 快速排序是通常情况下的最优选择高效只需要lgN级别的辅助空间但是快速排序不稳定受切分点的影响很大 七种排序总结 上面详细介绍了七种排序的实现细节和特点下面的表格总结了七种排序的各种特征。 其中插入排序选择排序冒泡排序都是简单排序时间复杂度是O(N2),其中插入排序和冒泡排序适合原始序列有序的数组选择排序的交换和赋值次数会比较少可以根据不同环境和数据的实际情况和长度选择具体的排序。整体插入排序优于选择排序优于冒泡排序。希尔排序是插入排序的优化突破了前三个排序O(N2)的时间复杂度但是本质还是插入排序突破比较相邻元素的惯性思维直接比较一定间隔的元素大幅度减少了逆序调整的比较次数和交换次数从而达到比较理想的算法复杂度适合对中等规模数组进行排序。堆排序是利用了最大堆的特点始终把堆顶元素最大元素和最后一个元素替换再重新构造最大堆重复执行达到排序的效果。堆结构的特性让算法的复杂度降低到NlgN级别但是有不方便索引元素的确定缓存命中率较低。而归并排序则是充分运用了分治原理把大问题不断的拆分成小问题进行排序再合并小数组达到整体排序的目标归并排序即高效又可靠唯一的缺点是需要数组长度的辅助空间在空间成本低的时候适合使用。快速排序则解决了归并排序占用空间的问题在数组内部用很小的辅助栈即可完成对元素的分离再去解决分离后的更小的数组正常情况下拥有和归并相同级别的时间复杂度但是得注意选取好切分元素。 实际上一个复杂的序列可能用不止一种排序例如分治和快速排序在分割到很小的序列时再进行分割反而效率不如插入排序等简单排序可以设置一定的阈值先用分治或者快速排序的方式分割数组再转换成插入等简单排序完成最终的排序。 希望本文大家加深对排序的理解有所帮助。我的微信公众号程序之路会持续发布技术成长文章欢迎长按下图关注 转载于:https://www.cnblogs.com/bigben0123/p/10414202.html
