这篇文章给大家介绍深入浅析java中的排序方法,内容非常详细,感兴趣的小伙伴们可以参考借鉴,希望对大家能有所帮助。
排序
1、概念:
有n个记录的序列{R1,R2,.......,Rn}(此处注意:1,2,n 是下表序列,以下是相同的作用),其相应关键字的序列是{K1,K2,.........,Kn}。通过排序,要求找出当前下标序列1,2,......,n的一种排列p1,p2,........pn,使得相应关键字满足如下的非递减(非递增)关系,即:Kp1<=Kp2<=Kpn,这样就得到一个按关键字有序的记录序列:{Rp1,Rp2,.......,Rpn}。
2、分类
根据排序时数据所占用存储器的不同,可将排序分为两类。
内部排序:整个排序过程完全在内存中进行,如下:
插入类排序(直接插入排序、折半插入排序、希尔排序);
交换类排序(冒泡排序、快速排序);
选择类排序(简单选择排序、树型选择排序、堆排序);
归并排序;
分配类排序(多关键字排序、链式基数排序、基数排序的顺序表实现));
外部排序:由于待排序记录数据量太大,内存无法容纳全部数据,排序需要借助外部存储设备才能完成(磁盘排序,磁带排序)。
3、稳定性
假设在待排序的序列中存在多个具有相同关键字的记录。设Ki=Kj(1<=i<=n,1<=j<=n,i != j),若在排序前的序列中Ri领先与Rj(即i<=j),经过排序后得到的序列中Ri仍然领先与Rj,则称所用的排序方法是稳定的;反之,当相同关键字的领先关系在排序过程中发生变化,则所用的排序方法是不稳定的。
插入排序:
思想:每次将一个待排序的记录,按其关键字大小插入到前面已经排好序的子文件中的适当位置,直到全部记录插入完成为止。
直接插入排序:
算法思想:假设待排序的记录存放在数组R[1..n]中。初始时,R[1]自成1个有序区,无序区为R[2..n]。从i=2起直至i=n为止,依次将R[i]插入当前的有序区R[1..i-1]中,生成含n个记录的有序区。
用java实现的代码如下:
package exp_sort; public class DirectInsertSort { public static void DircstSort(int array[]) { int j; // 循环从第二个数开始,第一个数用做存放待插入的记录 for (int i = 1; i < array.length; i++) { int temp = array[i]; // 寻找插入位置 for (j = i; j > 0 && temp < array[j - 1]; j--) { array[j] = array[j - 1]; } // 将待插入记录插入到已经排序的序列中 array[j] = temp; } for (int i = 0; i < array.length; i++) { System.out.print(array[i] + " "); } System.out.println("\n"); } public static void main(String[] args) { // TODO Auto-generated method stub int array[] = { 38, 62, 35, 77, 55, 14, 35, 98 }; DircstSort(array); } }
算法分析:最好的情况是待排序记录本身已经按照关键字有序排列,最坏的情况是待排序记录是按照关键字逆序排列的;时间复杂度是O(N^2),空间复杂度是O(1);该算法是稳定的排序算法:比较适用于待排序记录数目较少且基本有序的情况。
折半插入排序:
算法思想:对于有序表进行折半查找,其性能优于顺序查找。
算法实现代码如下:
package exp_sort; public class BinaryInsertSort { public static void sort(int array[]) { int temp, low, mid, high; for (int i = 1; i < array.length; i++) { temp = array[i]; low = 0; high = i -1; //确定插入位置 while (low <= high) { mid = (low + high) / 2; if (temp < array[mid]) { high = mid - 1; } else { low = mid + 1; } } //记录依次向后移动 for (int j = i; j >= low + 1; j--) { array[j] = array[j-1]; } //插入记录 array[low] = temp; } for (int i = 0; i < array.length; i++) { System.out.print(array[i] + " "); } System.out.println("\n"); } public static void main(String[] args) { // TODO Auto-generated method stub int array[] = {38, 62, 35, 77, 55, 14, 35, 98}; sort(array); } }
算法分析:是一种稳定的排序算法,比直接插入算法明显减少了关键字之间比较的次数,因此速度比直接插入排序算法快,但记录移动的次数没有变,所以折半插入排序算法的时间复杂度仍然为O(n^2),与直接插入排序算法相同。
关于深入浅析java中的排序方法就分享到这里了,希望以上内容可以对大家有一定的帮助,可以学到更多知识。如果觉得文章不错,可以把它分享出去让更多的人看到。
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。