`
caiwb1990
  • 浏览: 315349 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

Java排序汇总

    博客分类:
  • java
阅读更多
几种简单的排序的 Java 实现

代码注释非常详细~

import java.util.Random;
 
/**
 * 排序测试类
 *
 * 排序算法的分类如下:
 * 1.插入排序(直接插入排序、折半插入排序、希尔排序);
 * 2.交换排序(冒泡泡排序、快速排序);
 * 3.选择排序(直接选择排序、堆排序);
 * 4.归并排序;
 * 5.基数排序。
 *
 * 关于排序方法的选择:
 * (1)若n较小(如n≤50),可采用直接插入或直接选择排序。
 *  当记录规模较小时,直接插入排序较好;否则因为直接选择移动的记录数少于直接插人,应选直接选择排序为宜。
 * (2)若文件初始状态基本有序(指正序),则应选用直接插人、冒泡或随机的快速排序为宜;
 * (3)若n较大,则应采用时间复杂度为O(nlgn)的排序方法:快速排序、堆排序或归并排序。
 *
 */
public class SortTest {
 
       /**
        * 初始化测试数组的方法
        * @return 一个初始化好的数组
        */
       public int[] createArray() {
              Random random = new Random();
              int[] array = new int[10];
              for (int i = 0; i < 10; i++) {
                     array[i] = random.nextInt(100) - random.nextInt(100);//生成两个随机数相减,保证生成的数中有负数
              }
              System.out.println("==========原始序列==========");
              printArray(array);
              return array;
       }
 
       /**
        * 打印数组中的元素到控制台
        * @param source
        */
       public void printArray(int[] data) {
              for (int i : data) {
                     System.out.print(i + " ");
              }
              System.out.println();
       }
 
       /**
        * 交换数组中指定的两元素的位置
        * @param data
        * @param x
        * @param y
        */
       private void swap(int[] data, int x, int y) {
              int temp = data[x];
              data[x] = data[y];
              data[y] = temp;
       }
 
       /**
        * 冒泡排序----交换排序的一种
        * 方法:相邻两元素进行比较,如有需要则进行交换,每完成一次循环就将最大元素排在最后(如从小到大排序),下一次循环是将其他的数进行类似操作。
        * 性能:比较次数O(n^2),n^2/2;交换次数O(n^2),n^2/4
        *
        * @param data 要排序的数组
        * @param sortType 排序类型
        * @return
        */
       public void bubbleSort(int[] data, String sortType) {
              if (sortType.equals("asc")) { //正排序,从小排到大
                     //比较的轮数
                     for (int i = 1; i < data.length; i++) {
                            //将相邻两个数进行比较,较大的数往后冒泡
                            for (int j = 0; j < data.length - i; j++) {
                                   if (data[j] > data[j + 1]) {
                                          //交换相邻两个数
                                          swap(data, j, j + 1);
                                   }
                            }
                     }
              } else if (sortType.equals("desc")) { //倒排序,从大排到小
                     //比较的轮数
                     for (int i = 1; i < data.length; i++) {
                            //将相邻两个数进行比较,较大的数往后冒泡
                            for (int j = 0; j < data.length - i; j++) {
                                   if (data[j] < data[j + 1]) {
                                          //交换相邻两个数
                                          swap(data, j, j + 1);
                                   }
                            }
                     }
              } else {
                     System.out.println("您输入的排序类型错误!");
              }
              printArray(data);//输出冒泡排序后的数组值
       }
 
       /**
        * 直接选择排序法----选择排序的一种
        * 方法:每一趟从待排序的数据元素中选出最小(或最大)的一个元素, 顺序放在已排好序的数列的最后,直到全部待排序的数据元素排完。
        * 性能:比较次数O(n^2),n^2/2
        *       交换次数O(n),n
        *       交换次数比冒泡排序少多了,由于交换所需CPU时间比比较所需的CUP时间多,所以选择排序比冒泡排序快。
        *       但是N比较大时,比较所需的CPU时间占主要地位,所以这时的性能和冒泡排序差不太多,但毫无疑问肯定要快些。
        *
        * @param data 要排序的数组
        * @param sortType 排序类型
        * @return
        */
       public void selectSort(int[] data, String sortType) {
 
              if (sortType.equals("asc")) { //正排序,从小排到大
                     int index;
                     for (int i = 1; i < data.length; i++) {
                            index = 0;
                            for (int j = 1; j <= data.length - i; j++) {
                                   if (data[j] > data[index]) {
                                          index = j;
                                   }
                            }
                            //交换在位置data.length-i和index(最大值)两个数
                            swap(data, data.length - i, index);
                     }
              } else if (sortType.equals("desc")) { //倒排序,从大排到小
                     int index;
                     for (int i = 1; i < data.length; i++) {
                            index = 0;
                            for (int j = 1; j <= data.length - i; j++) {
                                   if (data[j] < data[index]) {
                                          index = j;
 
                                   }
                            }
                            //交换在位置data.length-i和index(最大值)两个数
                            swap(data, data.length - i, index);
                     }
              } else {
                     System.out.println("您输入的排序类型错误!");
              }
              printArray(data);//输出直接选择排序后的数组值
       }
 
       /**
        * 插入排序
        * 方法:将一个记录插入到已排好序的有序表(有可能是空表)中,从而得到一个新的记录数增1的有序表。
        * 性能:比较次数O(n^2),n^2/4
        *       复制次数O(n),n^2/4
        *       比较次数是前两者的一般,而复制所需的CPU时间较交换少,所以性能上比冒泡排序提高一倍多,而比选择排序也要快。
        *
        * @param data 要排序的数组
        * @param sortType 排序类型
        */
       public void insertSort(int[] data, String sortType) {
              if (sortType.equals("asc")) { //正排序,从小排到大
                     //比较的轮数
                     for (int i = 1; i < data.length; i++) {
                            //保证前i+1个数排好序
                            for (int j = 0; j < i; j++) {
                                   if (data[j] > data[i]) {
                                          //交换在位置j和i两个数
                                          swap(data, i, j);
                                   }
                            }
                     }
              } else if (sortType.equals("desc")) { //倒排序,从大排到小
                     //比较的轮数
                     for (int i = 1; i < data.length; i++) {
                            //保证前i+1个数排好序
                            for (int j = 0; j < i; j++) {
                                   if (data[j] < data[i]) {
                                          //交换在位置j和i两个数
                                          swap(data, i, j);
                                   }
                            }
                     }
              } else {
                     System.out.println("您输入的排序类型错误!");
              }
              printArray(data);//输出插入排序后的数组值
       }
 
       /**
        * 反转数组的方法
        * @param data 源数组
        */
       public void reverse(int[] data) {
 
              int length = data.length;
              int temp = 0;//临时变量
 
              for (int i = 0; i < length / 2; i++) {
                     temp = data[i];
                     data[i] = data[length - 1 - i];
                     data[length - 1 - i] = temp;
              }
              printArray(data);//输出到转后数组的值
       }
 
       /**
        * 快速排序
        * 快速排序使用分治法(Divide and conquer)策略来把一个序列(list)分为两个子序列(sub-lists)。
        * 步骤为:
        * 1. 从数列中挑出一个元素,称为 "基准"(pivot),
        * 2. 重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分割之后,该基准是它的最后位置。这个称为分割(partition)操作。
        * 3. 递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序。
        * 递回的最底部情形,是数列的大小是零或一,也就是永远都已经被排序好了。虽然一直递回下去,但是这个算法总会结束,因为在每次的迭代(iteration)中,它至少会把一个元素摆到它最后的位置去。
        * @param data 待排序的数组
        * @param low
        * @param high
        * @see SortTest#qsort(int[], int, int)
        * @see SortTest#qsort_desc(int[], int, int)
        */
       public void quickSort(int[] data, String sortType) {
              if (sortType.equals("asc")) { //正排序,从小排到大
                     qsort_asc(data, 0, data.length - 1);
              } else if (sortType.equals("desc")) { //倒排序,从大排到小
                     qsort_desc(data, 0, data.length - 1);
              } else {
                     System.out.println("您输入的排序类型错误!");
              }
       }
 
       /**
        * 快速排序的具体实现,排正序
        * @param data
        * @param low
        * @param high
        */
       private void qsort_asc(int data[], int low, int high) {
              int i, j, x;
              if (low < high) { //这个条件用来结束递归
                     i = low;
                     j = high;
                     x = data[i];//用x变量先保存这个值,以便比较和最后的存放
                                         //这里实际上是选择了第一个数作为基准点
                     while (i < j) {
                            while (i < j && data[j] > x) {
                                   j--; //从右向左找第一个小于x的数
                            }
                            if (i < j) {//找到了小于x的数
                                   data[i] = data[j];
                                   i++;
                            }
                            while (i < j && data[i] < x) {
                                   i++; //从左向右找第一个大于x的数
                            }
                            if (i < j) {
                                   data[j] = data[i];
                                   j--;
                            }
                     }
                     data[i] = x;//此时i和j相遇(相等)了
                     qsort_asc(data, low, i - 1);
                     qsort_asc(data, i + 1, high);
              }
       }
 
       /**
        * 快速排序的具体实现,排倒序
        * @param data
        * @param low
        * @param high
        */
       private void qsort_desc(int data[], int low, int high) {
              int i, j, x;
              if (low < high) { //这个条件用来结束递归
                     i = low;
                     j = high;
                     x = data[i];
                     while (i < j) {
                            while (i < j && data[j] < x) {
                                   j--; //从右向左找第一个小于x的数
                            }
                            if (i < j) {
                                   data[i] = data[j];
                                   i++;
                            }
                            while (i < j && data[i] > x) {
                                   i++; //从左向右找第一个大于x的数
                            }
                            if (i < j) {
                                   data[j] = data[i];
                                   j--;
                            }
                     }
                     data[i] = x;
                     qsort_desc(data, low, i - 1);
                     qsort_desc(data, i + 1, high);
              }
       }
 
       /**
        *二分查找特定整数在整型数组中的位置(递归)
        *查找线性表必须是有序列表
        *@paramdataset
        *@paramdata
        *@parambeginIndex
        *@paramendIndex
        *@returnindex
        */
       public int binarySearch(int[] dataset, int data, int beginIndex,
                     int endIndex) {
              int midIndex = (beginIndex + endIndex) >>> 1; //相当于mid = (low + high) / 2,但是效率会高些
              if (data < dataset[beginIndex] || data > dataset[endIndex]
                            || beginIndex > endIndex)
                     return -1;
              if (data < dataset[midIndex]) {
                     return binarySearch(dataset, data, beginIndex, midIndex - 1);
              } else if (data > dataset[midIndex]) {
                     return binarySearch(dataset, data, midIndex + 1, endIndex);
              } else {
                     return midIndex;
              }
       }
 
       /**
        *二分查找特定整数在整型数组中的位置(非递归)
        *查找线性表必须是有序列表
        *@paramdataset
        *@paramdata
        *@returnindex
        */
       public int binarySearch(int[] dataset, int data) {
              int beginIndex = 0;
              int endIndex = dataset.length - 1;
              int midIndex = -1;
              if (data < dataset[beginIndex] || data > dataset[endIndex]
                            || beginIndex > endIndex)
                     return -1;
              while (beginIndex <= endIndex) {
                     midIndex = (beginIndex + endIndex) >>> 1; //相当于midIndex = (beginIndex + endIndex) / 2,但是效率会高些
                     if (data < dataset[midIndex]) {
                            endIndex = midIndex - 1;
                     } else if (data > dataset[midIndex]) {
                            beginIndex = midIndex + 1;
                     } else {
                            return midIndex;
                     }
              }
              return -1;
       }
 
       public static void main(String[] args) {
              SortTest sortTest = new SortTest();
 
              int[] array = sortTest.createArray();
 
              System.out.println("==========冒泡排序后(正序)==========");
              sortTest.bubbleSort(array, "asc");
              System.out.println("==========冒泡排序后(倒序)==========");
              sortTest.bubbleSort(array, "desc");
 
              array = sortTest.createArray();
 
              System.out.println("==========倒转数组后==========");
              sortTest.reverse(array);
 
              array = sortTest.createArray();
 
              System.out.println("==========选择排序后(正序)==========");
              sortTest.selectSort(array, "asc");
              System.out.println("==========选择排序后(倒序)==========");
              sortTest.selectSort(array, "desc");
 
              array = sortTest.createArray();
 
              System.out.println("==========插入排序后(正序)==========");
              sortTest.insertSort(array, "asc");
              System.out.println("==========插入排序后(倒序)==========");
              sortTest.insertSort(array, "desc");
 
              array = sortTest.createArray();
              System.out.println("==========快速排序后(正序)==========");
              sortTest.quickSort(array, "asc");
              sortTest.printArray(array);
              System.out.println("==========快速排序后(倒序)==========");
              sortTest.quickSort(array, "desc");
              sortTest.printArray(array);
 
              System.out.println("==========数组二分查找==========");
              System.out.println("您要找的数在第" + sortTest.binarySearch(array, 74)
                            + "个位子。(下标从0计算)");
       }
}
0
2
分享到:
评论
1 楼 逼上IT 2012-02-08  
正在学习ing

相关推荐

    数学建模学习资料 神经网络算法 参考资料-Matlab 共26页.pptx

    数学建模学习资料 神经网络算法 参考资料-Matlab 共26页.pptx

    happybirthday2 升级版生日祝福密码0000(7).zip

    happybirthday2 升级版生日祝福密码0000(7).zip

    ssm框架Java项目源码-基于web技术的税务门户网站的实现+vue毕设-大作业.zip

    本项目是一个基于SSM框架的税务门户网站实现,结合了Vue技术,旨在提供一个全面的税务信息管理平台。该项目主要功能包括税务信息查询、税务申报、税务政策浏览及用户管理等多个模块。通过这些功能,用户可以方便地查询和管理税务相关的各类信息,同时也能及时了解最新的税务政策和规定。 项目采用SSM框架,即Spring、Spring MVC和MyBatis,这三者的结合为项目提供了强大的后端支持,确保了数据的安全性和系统的稳定性。前端则采用Vue.js框架,以其高效的数据绑定和组件化开发模式,提升了用户界面的响应速度和用户体验。 开发此项目的目的不仅是为了满足计算机相关专业学生在毕业设计中的实际需求,更是为了帮助Java学习者通过实战练习,深入理解并掌握SSM框架的应用,从而在实际工作中能够更好地运用这些技术。

    php7.4.33镜像7z压缩包

    php7.4.33镜像7z压缩包

    ssm框架Java项目源码-基于java的珠宝购物网站系统的建设+jsp毕设-大作业.zip

    本项目是一个基于Java的珠宝购物网站系统,采用SSM框架进行开发,旨在为计算机相关专业学生提供一个实践平台,同时也适合Java学习者进行实战练习。项目的核心功能涵盖商品展示、用户注册登录、购物车管理、订单处理和支付系统等。通过这一系统,用户可以浏览各类珠宝商品,包括详细的商品描述、高清图片和价格信息,同时能够方便地添加商品至购物车,并进行结算和支付操作。 在技术实现方面,项目运用了Spring、Spring MVC和MyBatis三大框架,确保系统的稳定性和扩展性。Spring负责业务逻辑层,提供依赖注入和面向切面编程的支持;Spring MVC则处理Web层的请求和响应,实现MVC设计模式;MyBatis作为持久层框架,简化了数据库操作。 此外,项目采用JSP技术进行前端页面展示,结合HTML、CSS和JavaScript等技术,为用户提供友好的交互界面。

    基于java的高校大学生党建系统设计与实现.docx

    基于java的高校大学生党建系统设计与实现.docx

    毕设源码-python-django疫情数据可视化分析系统(论文+PPT)-期末大作业+说明文档.rar

    本项目是一个基于Python-Django框架开发的疫情数据可视化分析系统,旨在为计算机相关专业的学生提供一个实践平台,同时也适用于需要进行项目实战练习的同学。项目集成了疫情数据的收集、处理、分析和可视化功能,为用户提供了一个直观、高效的数据分析环境。 在功能方面,系统能够自动抓取最新的疫情数据,包括确诊、疑似、治愈和死亡人数等关键指标。数据处理模块则负责清洗和整理这些数据,以确保分析的准确性。分析模块采用了多种统计方法和机器学习算法,以揭示疫情的发展趋势和潜在模式。可视化模块则通过图表和地图等形式,直观地展示了分析结果,便于用户理解和分享。 项目的开发框架选择了Django,这是一个高级Python Web框架,它鼓励快速开发和清晰、务实的设计。Django的强大功能和灵活性,使得项目能够快速响应需求变化,同时保证了系统的稳定性和安全性。

    果树领养计划.docx

    果树领养计划.docx

    java毕设项目之java基于云平台的信息安全攻防实训平台(源码+说明文档+mysql).zip

    环境说明:开发语言:Java 框架:springboot JDK版本:JDK1.8 服务器:tomcat7 数据库:mysql 5.7 数据库工具:Navicat 开发软件:eclipse/myeclipse/idea Maven包:Maven 浏览器:谷歌浏览器。 项目均可完美运行 基于Java的云平台信息安全攻防实训平台提供了以下核心功能: 1. **实训课程与项目**:平台提供了丰富多样的实训课程和项目,覆盖网络安全基础知识、漏洞挖掘与利用、渗透测试技术、安全防护策略等多个领域。 2. **在线学习模块**:学员可以通过在线学习模块观看教学视频、阅读文档资料,系统地学习信息安全知识。 3. **虚拟实验室环境**:平台提供虚拟实验室环境,学员可以在模拟的真实网络场景中进行攻防演练,包括漏洞扫描、攻击测试和防御措施的学习。 4. **教学管理功能**:教师可以创建和管理课程内容,制定教学计划,布置实训作业和考试任务。 5. **监控和统计功能**:教师可以实时了解学员的学习进度、实践操作情况和考试成绩,进行有针对性的指导和辅导。 6. **平台管理功能**:管理员负责用户管理、资源分配、系统安全维护等,确保平台稳定运行和实训环境的安全性。 7. **实时监控和评估**:系统具备实时监控和评估功能,能够及时反馈学生的操作情况和学习效果。 8. **用户认证和授权机制**:平台采用了严格的用户认证和授权机制,确保数据的安全性和保密性。 这些功能共同构建了一个功能丰富、操作便捷的实训环境,旨在提升学员的信息安全技能,为信息安全领域的发展输送专业人才。

    基于GrampusFramework的轻量级单体RBAC权限管理系统.zip

    基于GrampusFramework的轻量级单体RBAC权限管理系统

    软考(中级-软件设计师)知识点汇总与解析

    内容概要:本文档全面整理了软考(中级-软件设计师)的关键知识点,涵盖了计算复杂度、网络协议、数据结构、编程语言、数据库理论、软件测试、编译原理、设计模式、安全协议等多个方面的内容。具体涉及环路复杂度计算、SSH协议、数据字典与数据流图、对象的状态与数字签名、编程语言分类、海明码、著作权法、物理层与数据链路层设备、归纳法与演绎法、模块间耦合、能力成熟度模型集成、配置管理与风险管理、数据库关系范式、内存技术、计算机网络端口、路由协议、排序算法、中间代码、软件测试类型、编译器各阶段任务、设计模式、耦合与内聚、计算机病毒种类等。 适用人群:备考软考(中级-软件设计师)的技术人员,尤其是有一定工作经验但希望进一步提升自身技能和知识的IT从业人员。 使用场景及目标:帮助考生系统梳理考试重点,理解和掌握软件设计师应具备的专业知识和技术。适合考前复习和巩固基础知识。文档还可以作为参考资料,用于日常工作中遇到相关问题时查阅。 其他说明:本文档不仅提供了丰富的知识点,还附带了一些关键术语的定义和详细的解释,确保读者能够全面理解相关内容。建议在复习过程中结合实际案例进行练习,加深理解。

    数学建模学习资料 神经网络算法 Hopfield网络 共58页.pptx

    数学建模学习资料 神经网络算法 Hopfield网络 共58页.pptx

    工作寻(JobHunter)是一款招聘信息整合的网站,目前固定的模板有拉勾网,中华英才网,前程无忧。工作寻可以在线通过关.zip

    工作寻(JobHunter)是一款招聘信息整合的网站,目前固定的模板有拉勾网,中华英才网,前程无忧。工作寻可以在线通过关

    毕设源码-基于python协同过滤的音乐推荐系统的设计与实现_joqt--论文-期末大作业+说明文档.rar

    本项目是基于Python实现的协同过滤音乐推荐系统,旨在为计算机相关专业学生提供一个完整的毕设实战案例。项目以协同过滤算法为核心,通过分析用户历史行为数据,为用户推荐符合其兴趣偏好的音乐。 主要功能包括用户兴趣建模、音乐推荐生成以及用户反馈机制。系统能够实时捕捉用户听歌行为,动态更新用户兴趣模型,从而更精准地推送个性化音乐推荐。同时,系统设计了友好的用户界面,使用户能够方便地获取推荐音乐,并通过反馈机制不断完善推荐算法。 在技术框架方面,项目采用了Python编程语言,借助scikit-learn等机器学习库实现协同过滤算法,并结合Flask框架搭建了Web服务,确保了系统的性能和稳定性。此项目的开发,不仅能够帮助学生深入理解协同过滤算法及音乐推荐系统的工作原理,还能提升其软件开发和项目管理能力。

    微型餐饮补正备案材料通知书.docx

    微型餐饮补正备案材料通知书.docx

    食品生产许可质量跟踪监督建议书.docx

    食品生产许可质量跟踪监督建议书.docx

    基于django的音乐推荐系统.zip

    基于django的音乐推荐系统.zip

    如果让某人推荐Python技术书,请让他看这个列表.zip

    如果让某人推荐Python技术书,请让他看这个列表很棒的 Python 书籍如果让某人推荐Python技术书,请让他看这个列表前言好的技术书籍可以帮助我们快速成长,大部分人新生儿或者少部分受益于经典的技术书籍。在「Python开发者」微信公号后台,我们经常能收到帮忙推荐书籍的消息。此类问题在@Python开发者微博和伯乐在线的Python小组讨论中也绝非耳熟能详。 7月3日,伯乐在线在「Python开发者」微信公号发起了一个讨论(注PC端无法看到大家的评论,需要关注微信公号后,从微信公号才可以看到),通过这个讨论话题,在评论中分享对自己有帮助的大量Python技术书籍。 (Python开发者)入门《Head First Python》+入门级+微信49票+豆瓣评分9.5推荐语**66**浅显易懂,编排的顺序特别,有大量插图、对话,感觉枯燥古心通熟易懂,大量の图片,不会觉得枯燥,是一本不错的入门书《集体智慧编程》+入门级+微信123票+豆瓣评分 9.0推荐语**Mèrçurý**以实例具体的方式来展示Python的编程技巧,受益良多《Py

    基于java的博客系统设计与实现.docx

    基于java的博客系统设计与实现.docx

    建设工程基本建设程序检查表.docx

    建设工程基本建设程序检查表.docx

Global site tag (gtag.js) - Google Analytics