门户网站建设定做,淮南公司网站建设,网站设计制作音乐排行榜,自助建站的一般流程排序一直以来都是让我很头疼的事#xff0c;以前上《数据结构》打酱油去了#xff0c;整个学期下来才勉强能写出个冒泡排序。由于要找工作了#xff0c;也知道排序算法的重要性(据说是面试必问的知识点)#xff0c;所以又花了点时间重新研究了一下。排序大的分类可以分为两…排序一直以来都是让我很头疼的事以前上《数据结构》打酱油去了整个学期下来才勉强能写出个冒泡排序。由于要找工作了也知道排序算法的重要性(据说是面试必问的知识点)所以又花了点时间重新研究了一下。排序大的分类可以分为两种内排序和外排序。在排序过程中全部记录存放在内存则称为内排序如果排序过程中需要使用外存则称为外排序。下面讲的排序都是属于内排序。内排序可以分为以下几类(1)、插入排序直接插入排序、二分法插入排序、希尔排序。(2)、选择排序简单选择排序、堆排序。(3)、交换排序冒泡排序、快速排序。外排序可以分为一下几类(既使用内部存储也使用外部存储内存不够时建议使用)(4)、归并排序(5)、基数排序稳定性就是能保证排序前两个相等的数据其在序列中的先后位置顺序与排序后它们两个先后位置顺序相同。再简单具体一点如果A i A jAi 原来在 Aj 位置前排序后 Ai 仍然是在 Aj 位置前。不稳定简单选择排序、快速排序、希尔排序、堆排序不是稳定的排序算法稳定冒泡排序、直接插入排序、二分法插入排序归并排序和基数排序都是稳定的排序算法。平均时间复杂度O(n^2):直接插入排序简单选择排序冒泡排序。在数据规模较小时(9W内)直接插入排序简单选择排序差不多。当数据较大时冒泡排序算法的时间代价最高。性能为O(n^2)的算法基本上是相邻元素进行比较基本上都是稳定的。O(nlogn):快速排序归并排序希尔排序堆排序。其中快排是最好的 其次是归并和希尔堆排序在数据量很大时效果明显。排序算法的选择1.数据规模较小(1)待排序列基本序的情况下可以选择直接插入排序(2)对稳定性不作要求宜用简单选择排序对稳定性有要求宜用插入或冒泡2.数据规模不是很大(1)完全可以用内存空间序列杂乱无序对稳定性没有要求快速排序此时要付出log(N)的额外空间。(2)序列本身可能有序对稳定性有要求空间允许下宜用归并排序3.数据规模很大(1)对稳定性有求则可考虑归并排序。(2)对稳定性没要求宜用堆排序4.序列初始基本有序(正序)宜用直接插入冒泡一、插入排序•思想每步将一个待排序的记录按其顺序码大小插入到前面已经排序的字序列的合适位置直到全部插入排序完为止。•关键问题在前面已经排好序的序列中找到合适的插入位置。•方法–直接插入排序–二分插入排序–希尔排序①直接插入排序(从后向前找到合适位置后插入)1、基本思想每步将一个待排序的记录按其顺序码大小插入到前面已经排序的字序列的合适位置(从后向前找到合适位置后)直到全部插入排序完为止。2、实例3、java实现importjava.util.Scanner;public classMain {public static voidmain(String[] args) {//输入参数Scanner in newScanner(System.in);while(in.hasNext()) {String inStrin.nextLine();String[] str inStr.split( );int a[] new int[str.length];for (int i 0; i a.length; i) {a[i]Integer.parseInt(str[i]);}//输出结果int[] results zhiJieChaRu(a);StringBuffer result newStringBuffer();for (int i 0; i results.length; i) {result.append(results[i]).append(,);}//删除最后一个逗号if (result.length() 0) {result.deleteCharAt(result.length()-1);}System.out.println(result);}}/*** 直接插入排序。*parama*return*/public static int[] zhiJieChaRu(int[] a) {//直接插入排序for (int i 1; i a.length; i) {//待插入元素int temp a[i];intj;for (j i - 1; j 0; j--) {//将大于temp的往后移动一位if (a[j] temp) {a[j 1] a[j];}else{break;}}a[j 1] temp;}returna;}}4、分析直接插入排序是稳定的排序。文件初态不同时直接插入排序所耗费的时间有很大差异。若文件初态为正序则每个待插入的记录只需要比较一次就能够找到合适的位置插入故算法的时间复杂度为O(n)这时最好的情况。若初态为反序则第i个待插入记录需要比较i1次才能找到合适位置插入故时间复杂度为O(n2)这时最坏的情况。直接插入排序的平均时间复杂度为O(n2)。②二分法插入排序(按二分法找到合适位置插入)1、基本思想二分法插入排序的思想和直接插入一样只是找合适的插入位置的方式不同这里是按二分法找到合适的位置可以减少比较的次数。2、实例3、java实现importjava.util.Scanner;public classMain {public static voidmain(String[] args) {//输入参数Scanner in newScanner(System.in);while(in.hasNext()) {String inStrin.nextLine();String[] str inStr.split( );int a[] new int[str.length];for (int i 0; i a.length; i) {a[i]Integer.parseInt(str[i]);}//调用方法得到数组int[] results erFenChaRu(a);//将数组转换成字符串输出StringBuffer result newStringBuffer();for (int i 0; i results.length; i) {result.append(results[i]).append(,);}//删除最后一个逗号if (result.length() 0) {result.deleteCharAt(result.length()- 1);}System.out.println(result);}}/*** 二分插入排序*parama*return*/public static int[] erFenChaRu(int[] a) {for (int i 0; i a.length; i) {int temp a[i];int left 0;int right i - 1;int mid 0;while (left right) {mid (left right) / 2;if (temp right mid - 1;}else{left mid 1;}}for (int j i - 1; j left; j--) {a[j 1] a[j];}if (left !i) {a[left]temp;}}returna;}}4、分析当然二分法插入排序也是稳定的。二分插入排序的比较次数与待排序记录的初始状态无关仅依赖于记录的个数。当n较大时比直接插入排序的最大比较次数少得多。但大于直接插入排序的最小比较次数。算法的移动次数与直接插入排序算法的相同最坏的情况为n2/2最好的情况为n平均移动次数为O(n2)。③希尔排序1、基本思想先取一个小于n的整数d1作为第一个增量把文件的全部记录分成d1个组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序然后取第二个增量d22、实例3、java实现/*** 希尔排序。*parama*return*/public static int[] xiErSort(int[] a) {int d a.length;while (true) {d d / 2;for (int x 0; x d; x) {for (int i x d; i a.length; i i d) {int temp a[i];intj;for (j i - d; j 0 a[j] temp; j j -d) {a[j d] a[j];}a[j d] temp;}}if (d 1) {break;}}returna;}4、分析我们知道一次插入排序是稳定的但在不同的插入排序过程中相同的元素可能在各自的插入排序中移动最后其稳定性就会被打乱所以希尔排序是不稳定的。希尔排序的时间性能优于直接插入排序原因如下(1)当文件初态基本有序时直接插入排序所需的比较和移动次数均较少。(2)当n值较小时n和n2的差别也较小即直接插入排序的最好时间复杂度O(n)和最坏时间复杂度0(n2)差别不大。(3)在希尔排序开始时增量较大分组较多每组的记录数目少故各组内直接插入较快后来增量di逐渐缩小分组数逐渐减少而各组的记录数目逐渐增多但由于已经按di-1作为距离排过序使文件较接近于有序状态所以新的一趟排序过程也较快。因此希尔排序在效率上较直接插人排序有较大的改进。希尔排序的平均时间复杂度为O(nlogn)。二、选择排序•思想每趟从待排序的记录序列中选择关键字最小的记录放置到已排序表的最前位置直到全部排完。•关键问题在剩余的待排序记录序列中找到最小关键码记录。•方法–直接选择排序–堆排序①简单的选择排序1、基本思想在要排序的一组数中选出最小的一个数与第一个位置的数交换然后在剩下的数当中再找最小的与第二个位置的数交换如此循环到倒数第二个数和最后一个数比较为止。2、实例3、java实现/*** 直接选择排序。*parama*return*/public static int[] zhiJieXuanZe(int[] a) {for (int i 0; i a.length; i) {int min a[i];int n i; //最小数的索引for (int j i 1; j a.length; j) {if (a[j] min) { //找出最小的数min a[j];nj;}}a[n]a[i];a[i]min;}returna;}4、分析简单选择排序是不稳定的排序。时间复杂度T(n)O(n2)。②堆排序1、基本思想堆排序是一种树形选择排序是对直接选择排序的有效改进。堆的定义下具有n个元素的序列 (h1,h2,...,hn),当且仅当满足(hih2i,hi2i1)或(hih2i,hi2i1) (i1,2,...,n/2)时称之为堆。在这里只讨论满足前者条件的堆。由堆的定义可以看出堆顶元素(即第一个元素)必为最大项(大顶堆)。完全二 叉树可以很直观地表示堆的结构。堆顶为根其它为左子树、右子树。思想:初始时把要排序的数的序列看作是一棵顺序存储的二叉树调整它们的存储序使之成为一个 堆这时堆的根节点的数最大。然后将根节点与堆的最后一个节点交换。然后对前面(n-1)个数重新调整使之成为堆。依此类推直到只有两个节点的堆并对 它们作交换最后得到有n个节点的有序序列。从算法描述来看堆排序需要两个过程一是建立堆二是堆顶与堆的最后一个元素交换位置。所以堆排序有两个函数组成。一是建堆的渗透函数二是反复调用渗透函数实现排序的函数。2、实例初始序列46,79,56,38,40,84建堆交换从堆中踢出最大数依次类推最后堆中剩余的最后两个结点交换踢出一个排序完成。3、java实现/*** 堆排序*parama*return*/public static int[] heapSort(inta[]) {int arrayLength a.length;//循环建堆for (int i 0; i arrayLength - 1; i) {//建堆buildMaxHeap(a, arrayLength - 1 -i);//交换堆顶和最后一个元素swap(a, 0, arrayLength - 1 -i);}returna;}//对data数组从0到lastIndex建大顶堆public static void buildMaxHeap(int[] data, intlastIndex) {//从lastIndex处节点(最后一个节点)的父节点开始for (int i (lastIndex - 1) / 2; i 0; i--) {//k保存正在判断的节点int k i;//如果当前k节点的子节点存在while (k * 2 1 lastIndex) {//k节点的左子节点的索引int biggerIndex 2 * k 1;//如果biggerIndex小于lastIndex即biggerIndex1代表的k节点的右子节点存在if (biggerIndex if (data[biggerIndex] data[biggerIndex 1]) {//biggerIndex总是记录较大子节点的索引biggerIndex;}}//如果k节点的值小于其较大的子节点的值if (data[k] swap(data, k, biggerIndex);//将biggerIndex赋予k开始while循环的下一次循环重新保证k节点的值大于其左右子节点的值k biggerIndex;}else{break;}}}}//交换private static void swap(int[] data, int i, intj) {int tmp data[i];data[i]data[j];data[j]tmp;}4、分析堆排序也是一种不稳定的排序算法。堆排序优于简单选择排序的原因直接选择排序中为了从R[1..n]中选出关键字最小的记录必须进行n-1次比较然后在R[2..n]中选出关键字最小的记录又需要做n-2次比较。事实上后面的n-2次比较中有许多比较可能在前面的n-1次比较中已经做过但由于前一趟排序时未保留这些比较结果所以后一趟排序时又重复执行了这些比较操作。堆排序可通过树形结构保存部分比较结果可减少比较次数。堆排序的最坏时间复杂度为O(nlogn)。堆序的平均性能较接近于最坏性能。由于建初始堆所需的比较次数较多所以堆排序不适宜于记录数较少的文件。三、交换排序①冒泡排序1、基本思想在要排序的一组数中对当前还未排好序的范围内的全部数自上而下对相邻的两个数依次进行比较和调整让较大的数往下沉较小的往上冒。即每当两相邻的数比较后发现它们的排序与排序要求相反时就将它们互换。2、实例3、java实现/*** 冒泡排序。*parama*return*/public static int[] maoPaoSort(inta[]) {//冒泡排序for (int i 0; i a.length; i) {for(int j 0; jif(a[j]a[j1]){int temp a[j];a[j] a[j1];a[j1] temp;}}}returna;}4、分析冒泡排序是一种稳定的排序方法。•若文件初状为正序则一趟起泡就可完成排序排序码的比较次数为n-1且没有记录移动时间复杂度是O(n)•若文件初态为逆序则需要n-1趟起泡每趟进行n-i次排序码的比较且每次比较都移动三次比较和移动次数均达到最大值∶O(n2)•起泡排序平均时间复杂度为O(n2)②快速排序1、基本思想选择一个基准元素,通常选择第一个元素或者最后一个元素,通过一趟扫描将待排序列分成两部分,一部分比基准元素小,一部分大于等于基准元素,此时基准元素在其排好序后的正确位置,然后再用同样的方法递归地排序划分的两部分。2、实例3、java实现/*** 快速排序。*parama*return*/public static int[] quick(int[] a) {quickSort(a,0, a.length - 1);returna;}public static void quickSort(int[] a, int low, inthigh) {if (low high) { //如果不加这个判断递归会无法退出导致堆栈溢出异常int middle getMiddle(a, low, high);quickSort(a,0, middle - 1);quickSort(a, middle 1, high);}}public static int getMiddle(int[] a, int low, inthigh) {int temp a[low];//基准元素while (low while (low high a[high] temp) {high--;}a[low]a[high];while (low high a[low] temp) {low;}a[high]a[low];}a[low]temp;returnlow;}4、分析快速排序是不稳定的排序。快速排序的时间复杂度为O(nlogn)。当n较大时使用快排比较好当序列基本有序时用快排反而不好。四、归并排序1、基本思想:归并(Merge)排序法是将两个(或两个以上)有序表合并成一个新的有序表即把待排序序列分为若干个子序列每个子序列是有序的。然后再把有序子序列合并为整体有序序列。2、实例3、java实现/*** 归并排序。**parama*return*/public static int[] guiBingSort(int[] a) {mergeSort(a,0, a.length-1);returna;}public static void mergeSort(int[] a, int left, intright) {if (left mergeSort(a, left, middle);//对右边进行递归mergeSort(a, middle 1, right);//合并merge(a, left, middle, right);}}public static void merge(int[] a, int left, int middle, intright) {int[] tmpArr new int[a.length];int mid middle 1; //右边的起始位置int tmp left;int third left;while (left middle mid right) {//从两个数组中选取较小的数放入中间数组if (a[left] a[mid]) {tmpArr[third] a[left];}else{tmpArr[third] a[mid];}}//将剩余的部分放入中间数组while (left middle) {tmpArr[third] a[left];}while (mid right) {tmpArr[third] a[mid];}//将中间数组复制回原数组while (tmp right) {a[tmp] tmpArr[tmp];}}4、分析归并排序是稳定的排序方法。归并排序的时间复杂度为O(nlogn)。速度仅次于快速排序为稳定排序算法一般用于对总体无序但是各子项相对有序的数列。五、基数排序1、基本思想将所有待比较数值(正整数)统一为同样的数位长度数位较短的数前面补零。然后从最低位开始依次进行一次排序。这样从最低位排序一直到最高位排序完成以后,数列就变成一个有序序列。2、实例3、java实现public static int[] jiShuSort(int[] array) {//找到最大数确定要排序几趟int max 0;for (int i 0; i array.length; i) {if(maxmaxarray[i];}}//判断位数int times 0;while(max0){max max/10;times;}//建立十个队列List queue new ArrayList();for (int i 0; i 10; i) {ArrayList queue1 newArrayList();queue.add(queue1);}//进行times次分配和收集for (int i 0; i times; i) {//分配for (int j 0; j array.length; j) {int x array[j]%(int)Math.pow(10, i1)/(int)Math.pow(10, i);ArrayList queue2queue.get(x);queue2.add(array[j]);queue.set(x,queue2);}//收集int count 0;for (int j 0; j 10; j) {while(queue.get(j).size()0){ArrayList queue3 queue.get(j);array[count] queue3.get(0);queue3.remove(0);count;}}}returnarray;}4、分析基数排序是稳定的排序算法。基数排序的时间复杂度为O(d(nr)),d为位数r为基数。
