排序算法总结一
本文共 7519 字，大约阅读时间需要 25 分钟。
1.冒泡排序
排序算法: 冒泡排序规律：O（n^2） 1.有n个数，就需要进行n-1趟排序 2.每一趟的排序次数在减少。 3.如果在某一趟排序的过程当中没有一次交换，那么可以直接提前结束冒泡排序。（相当于优化了代码）
private static void bubbleSort(int[] arr) { //外层循环控制趟数，趟数为数组的长度减去一。 int temp1 = 0; boolean flag = false;//起到优化代码的作用,如果在某一趟排序当中没有发生过交换，那么就一直是false，如果发生了交换那么置为true for (int i = 0; i < arr.length - 1; i++) { //控制每趟比较的次数，随着趟数的增加，那么元素的比较次数会变少。 for (int j = 0; j < arr.length - 1 - i; j++) { if (arr[j] > arr[j + 1]) { flag=true;//发生了交换 temp1 = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp1; } } /*System.out.println("第"+(i+1)+"次比较"); System.out.println(Arrays.toString(arr));*/ if(!flag){ //如果没有发生过交换，该数组已经有序了，那么直接退出循环. break; }else{ flag = false; } } } 测试冒泡排序，随机生成8万个数据，测试排序的所需要的时间。
//生成随机数，Math.random随机生成从0到1的小数 int []arr2 = new int [80000]; for(int i=0;i<80000;i++){ arr2[i]=(int)(Math.random()*800000); } Date date = new Date(); SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss"); String dateFormat = simpleDateFormat.format(date); System.out.println("排序前的时间"); System.out.println(dateFormat); bubbleSort(arr2);//调用冒泡排序 Date date2 = new Date(); SimpleDateFormat simpleDateFormat2 = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss"); String dateFormat2 = simpleDateFormat.format(date2); System.out.println("排序后的时间"); System.out.println(dateFormat2); 运行截图:
2.选择排序
选择排序:O（n^2）
1.n个元素，需要进行n-1此比较 2.每一轮都是一个循环。 2.1假定当前元素为最小的元素，然后依次和最后面的元素进行比较，如果有比当前元素更小的元素，那么就更新最小元素，并且记录下标。 2.2一轮循环结束之后，就进行交换，和未排好序的位置元素进行交换。选择排序的分析拆解过程:
//分析过程 int minIndex = 0;//设置最小元素的小标为0 for (int j = 1; j < arr.length; j++) { if (minIndex >= arr[j]) { minIndex = j; min = arr[j]; } } System.out.println(Arrays.toString(arr)); //交换 if (minIndex != 0) { int temp = arr[0]; arr[0] = arr[minIndex]; arr[minIndex] = temp; } System.out.println(Arrays.toString(arr)); ///************************ minIndex = 1;//设置最小元素的小标为1 for (int j = 2; j < arr.length; j++) { if (minIndex >= arr[j]) { minIndex = j; min = arr[j]; } } System.out.println(Arrays.toString(arr)); if (minIndex != 1) { int temp = arr[1]; arr[1] = arr[minIndex]; arr[minIndex] = temp; } System.out.println(Arrays.toString(arr)); //************************ minIndex = 2;//设置最小元素的小标为2 for (int j = 3; j < arr.length; j++) { if (minIndex >= arr[j]) { minIndex = j; min = arr[j]; } } System.out.println(Arrays.toString(arr)); if (minIndex != 2) { int temp = arr[2]; arr[2] = arr[minIndex]; arr[minIndex] = temp; } System.out.println(Arrays.toString(arr)); //......依次类推，最终可以找到规律 具体代码如下:
private static void selectSort(int[] arr) { //定义多少轮（n-1） for (int i = 0; i < arr.length - 1; i++) { int minIndex = i; for (int j = i + 1; j < arr.length; j++) { //内层循环控制找到每一轮当中的最小的元素下标和值元素 if (arr[minIndex] > arr[j]) { minIndex = j; } } //如果最小元素的小标发生了改变才需要交换，否则最初的小标对应的元素就是最小的值。 if (minIndex != i) { int temp = arr[i]; arr[i] = arr[minIndex]; arr[minIndex] = temp; } //System.out.println(Arrays.toString(arr)); } } 测试排序算法，同样也是8万个数据
//随机生成8万个数据 int []arr2 = new int [80000]; for(int i=0;i<80000;i++){ arr2[i]=(int)(Math.random()*800000); } Date date = new Date(); SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss"); String dateFormat = simpleDateFormat.format(date); System.out.println("排序前的时间"); System.out.println(dateFormat); selectSort(arr2);//调用选择排序 Date date2 = new Date(); SimpleDateFormat simpleDateFormat2 = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss"); String dateFormat2 = simpleDateFormat.format(date2); System.out.println("排序后的时间"); System.out.println(dateFormat2); 运行结果:
3.插入排序:
插入排序指的是在一个数组当中，分为有序组，和无序组，刚开始有序组只有一个元素，也就是第一个元素，然后在选定无序组当中的第一个元素插入到有序组适当的位置。再次让无序组的第一个元素插入到有序组的适当的位置，直到所有的元素已经排好了序（有序组当中）
插入排序的缺点:当需要插入的数据是较小的数时，后移的次数明显增加，影响效率。
分析步骤//定义待插入的数据 int insertVal = arr[1]; //插入的位置（总是要插入的元素的数组下标的前一个位置） int insertIndex = 1 - 1;//跟待插入的元素的下标减一有关 //用户找到待插入元素的插入位置。 while (insertIndex >= 0 && insertVal < arr[insertIndex]) { //如果进的了这个循环，说明还没有找到位置 //首先将index处的元素后移 arr[insertIndex + 1] = arr[insertIndex]; //将index前移，以便进行下一轮循环的判断 insertIndex--; } arr[insertIndex + 1] = insertVal; ///************** //定义待插入的数据 insertVal = arr[2]; //插入的位置（总是要插入的元素的数组下标的前一个位置） insertIndex = 2 - 1;//跟待插入的元素的下标减一有关 //用户找到待插入元素的插入位置。 while (insertIndex >= 0 && insertVal < arr[insertIndex]) { //如果进的了这个循环，说明还没有找到位置 //首先将index处的元素后移 arr[insertIndex + 1] = arr[insertIndex]; //将index前移，以便进行下一轮循环的判断 insertIndex--; } arr[insertIndex + 1] = insertVal; //************************ //定义待插入的数据 insertVal = arr[3]; //插入的位置（总是要插入的元素的数组下标的前一个位置） insertIndex = 3 - 1;//跟待插入的元素的下标减一有关 //用户找到待插入元素的插入位置。 while (insertIndex >= 0 && insertVal < arr[insertIndex]) { //如果进的了这个循环，说明还没有找到位置 //首先将index处的元素后移 arr[insertIndex + 1] = arr[insertIndex]; //将index前移，以便进行下一轮循环的判断 insertIndex--; } arr[insertIndex + 1] = insertVal; //依次类推下午，直到所有的元素都已经排好了序。 插入排序具体实现过程如下:
private static void insertSort(int[] arr) { for (int i = 1; i < arr.length; i++) { //定义待插入的数据 int insertVal = arr[i]; //插入的位置（总是要插入的元素的数组下标的前一个位置） int insertIndex = i - 1;//跟待插入的元素的下标减一有关 //用户找到待插入元素的插入位置。 while (insertIndex >= 0 && insertVal < arr[insertIndex]) { //如果进的了这个循环，说明还没有找到位置 //首先将index处的元素后移 arr[insertIndex + 1] = arr[insertIndex]; //将index前移，以便进行下一轮循环的判断，也是为了将index的前一个元素可以进行后移。 insertIndex--; } if (insertIndex + 1 != i) { arr[insertIndex + 1] = insertVal; } } } 对插入排序进行测试:
Date date = new Date(); SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss"); String dateFormat = simpleDateFormat.format(date); System.out.println("排序前的时间"); System.out.println(dateFormat); insertSort(arr2); Date date2 = new Date(); SimpleDateFormat simpleDateFormat2 = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss"); String dateFormat2 = simpleDateFormat.format(date2); System.out.println("排序后的时间"); System.out.println(dateFormat2); 
转载地址：http://irlen.baihongyu.com/
你可能感兴趣的文章
labview 局部变量问题
查看>>
labview 循环外部与数组相连时问题
查看>>
哈佛大学凌晨4点半的景象--哈佛图书馆的二十条训言
查看>>
Outlook2010到处通讯录
查看>>
Gmail导入通讯录
查看>>
小米笔记本安装Win 10历程
查看>>
【转】SLAM 论文阅读和分类整理
查看>>
【转】Ubuntu 16.04 重置密码（忘记密码）
查看>>
【转】信息奥赛一本通1185：单词排序（OJ题目描述有问题）
查看>>
webclient
查看>>
从百度MP3搜索结果中提取歌曲列表
查看>>
Python Set
查看>>
SWT 中实现最小化到托盘图标，并只能通过托盘的弹出菜单关闭程序
查看>>
Java Table Examples
查看>>
Java read file
查看>>
界面主线程，子线程更新主界面控件
查看>>
敲两遍引号键才出现
查看>>
欢迎使用CSDN-markdown编辑器
查看>>
剑指Offer
查看>>
五大常用算法&实例列举
查看>>