各种排序算法的分析及Java实现(5)

  直接选择排序中,为了从R[1..n]中选出关键字最小的记录,必须进行n-1次比较,然后在R[2..n]中选出关键字最小的记录,又需要做n-2次比较。事实上,后面的n-2次比较中,有许多比较可能在前面的n-1次比较中已经做过,但由于前一趟排序时未保留这些比较结果,所以后一趟排序时又重复执行了这些比较操作。

  堆排序可通过树形结构保存部分比较结果,可减少比较次数。

  堆排序的最坏时间复杂度为O(nlogn)。堆序的平均性能较接近于最坏性能。由于建初始堆所需的比较次数较多,所以堆排序不适宜于记录数较少的文件。

三、交换排序

①冒泡排序

  1、基本思想:在要排序的一组数中,对当前还未排好序的范围内的全部数,自上而下对相邻的两个数依次进行比较和调整,让较大的数往下沉,较小的往上冒。即:每当两相邻的数比较后发现它们的排序与排序要求相反时,就将它们互换。

  2、实例

各种排序算法的分析及Java实现

  3、java实现

1 package com.sort; 2 3 //稳定 4 public class 冒泡排序 { 5 public static void main(String[] args) { 6 int[] a={49,38,65,97,76,13,27,49,78,34,12,64,1,8}; 7 System.out.println("排序之前:"); 8 for (int i = 0; i < a.length; i++) { 9 System.out.print(a[i]+" "); 10 } 11 //冒泡排序 12 for (int i = 0; i < a.length; i++) { 13 for(int j = 0; j<a.length-i-1; j++){ 14 //这里-i主要是每遍历一次都把最大的i个数沉到最底下去了,没有必要再替换了 15 if(a[j]>a[j+1]){ 16 int temp = a[j]; 17 a[j] = a[j+1]; 18 a[j+1] = temp; 19 } 20 } 21 } 22 System.out.println(); 23 System.out.println("排序之后:"); 24 for (int i = 0; i < a.length; i++) { 25 System.out.print(a[i]+" "); 26 } 27 } 28 }

  4、分析

  冒泡排序是一种稳定的排序方法。 

•若文件初状为正序,则一趟起泡就可完成排序,排序码的比较次数为n-1,且没有记录移动,时间复杂度是O(n)

•若文件初态为逆序,则需要n-1趟起泡,每趟进行n-i次排序码的比较,且每次比较都移动三次,比较和移动次数均达到最大值∶O(n2)

•起泡排序平均时间复杂度为O(n2)

 

 

②快速排序

  1、基本思想:选择一个基准元素,通常选择第一个元素或者最后一个元素,通过一趟扫描,将待排序列分成两部分,一部分比基准元素小,一部分大于等于基准元素,此时基准元素在其排好序后的正确位置,然后再用同样的方法递归地排序划分的两部分。

  

  2、实例

各种排序算法的分析及Java实现

 

  3、java实现

package com.sort; //不稳定 public class 快速排序 { public static void main(String[] args) { int[] a={49,38,65,97,76,13,27,49,78,34,12,64,1,8}; System.out.println("排序之前:"); for (int i = 0; i < a.length; i++) { System.out.print(a[i]+" "); } //快速排序 quick(a); System.out.println(); System.out.println("排序之后:"); for (int i = 0; i < a.length; i++) { System.out.print(a[i]+" "); } } private static void quick(int[] a) { if(a.length>0){ quickSort(a,0,a.length-1); } } private static void quickSort(int[] a, int low, int high) { if(low<high){ //如果不加这个判断递归会无法退出导致堆栈溢出异常 int middle = getMiddle(a,low,high); quickSort(a, 0, middle-1); quickSort(a, middle+1, high); } } private static int getMiddle(int[] a, int low, int high) { int temp = a[low];//基准元素 while(low<high){ //找到比基准元素小的元素位置 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; return low; } }

  4、分析

  快速排序是不稳定的排序。

  快速排序的时间复杂度为O(nlogn)。

  当n较大时使用快排比较好,当序列基本有序时用快排反而不好。

四、归并排序

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/23bcdfca628d5dbcb49b422b1528cbe7.html