目录
选择排序算法思路图解
选择排序
基本介绍
思想
思路图解
应用实例
代码实现
运行结果
算法速度测试
代码实现
运行结果
插入排序
介绍
思想
代码实现
运行效果
算法速度测试
代码实现
运行结果
选择排序算法思路图解
选择排序
基本介绍
选择式排序也属于内部排序法，是从欲排序的数据中，按指定的规则选出某一元素，再依规定交换位置后达到排序的目的。
思想
选择排序也是一种简单的排序方法，它的基本思想是：第一次从arr[0]~arr[n-1]中选取最小值，与arr[0]交换，第二次从arr[1] arr[n-1]中选取最小值，与arr[1]交换，第三次从arr[2]~arr[n-1]中选取最小值，与arr[2]交换，......,第一次从arr[i-1]~arr[n-1]中选取最小值，与arr[i-1]交换，......,第n-1次从arr[n-2]~arr[n-1]中选取最小值，与arr[n-2]交换，总共通过n-1次，得到一个按排序码从小到大排列的有序序列。
思路图解
原始的数组：101，34，119，1
第一轮排序：1，34，119，101
第二轮排序：1，34，119，101
第三轮排序：1，34，101，119
说明：
1.选择排序一共有数组大小-1轮排序
2.每一轮排序，又是一个循环，循环的规则（代码）
2.1先假定这个数是最小的
2.2然后和后面的每个数进行比较，如果发现有比当前数更小的数，
就重新确定最小数，并得到下标
2.3当遍历到数组的最后时，就得到本轮最小数和下标
2.4交换[代码]
应用实例
代码实现
package sort;
import java.util.Arrays;
public class SelectSort {
public static void main(String[] args) {
int [] arr= {101,34,119,1};
System.out.println("排序前:");
System.out.println(Arrays.toString(arr));
selectSort(arr);
System.out.println("排序后");
System.out.println(Arrays.toString(arr));
}
//选择排序
public static void selectSort(int[] arr) {
//在推导的过程，我们发现了规律。因此，可以使用for来解决
for (int i = 0; i < arr.length-1; i++) {
int minIndex=i;
int min=arr[i];
for (int j = i+1; j < arr.length; j++) {
if (min>arr[j]) {//说明假定的最小值，并不是最小
min=arr[j];//重置min
minIndex=j;//重置minIndex
}
}
//将最小值，放在arr[0],即交换
if (minIndex!=i) {
arr[minIndex]=arr[0];
arr[i]=min;
}
// System.out.println("第"+(i+1)+"轮后~~~");
// System.out.println(Arrays.toString(arr));//1,34,119,101
}
}
}
运行结果
算法速度测试
代码实现
public static void main(String[] args) {
//int [] arr= {101,34,119,1};
//创建要给80000个的随机的数组
int[] arr=new int[80000];
for (int i = 0; i <80000; i++) {
arr[i]=(int)(Math.random()*8000000);//生成一个[0,8000000)数
}
System.out.println("排序前:");
//System.out.println(Arrays.toString(arr));
Date data1=new Date();
SimpleDateFormat simpleDateFormat=new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
String date1Str=simpleDateFormat.format(data1);
System.out.println("排序前的时间是:"+date1Str);
selectSort(arr);
Date data2=new Date();
String date2Str=simpleDateFormat.format(data2);
System.out.println("排序后的时间是:"+date2Str);
//System.out.println("排序后");
//System.out.println(Arrays.toString(arr));
}
运行结果
插入排序
介绍
插入式排序属于内部排序法，是对于欲排序的元素以插入的方式找寻该元素的适当位置，以达到排序的目的。
思想插入排序的基本思想是：把n个待排序的元素看成为一个有序表和一个无序表，开始时有序表只包含一个元素，无序表中包含有n-1个元素，排序过程中每次从无序表中取出第一个元素，把它的排序码依次与有序表元素的排序码进行比较，将它插入到有序表中的适当位置，使之成为新的有序表。
代码实现package sort;
import java.util.Arrays;
public class InsertSort {
public static void main(String[] args) {
int [] arr= {101,34,119,1,-1,89};
insertSort(arr);
}
//插入排序
public static void insertSort(int[] arr) {
//使用for循环来把代码简化
for (int i = 1; i < arr.length; i++) {
//定义待插入的数
int insertVal=arr[i];
int insertIndex=i-1;//即arr[1]的前面这个数的下标
//给insertVal找到插入的位置
//说明
//1.insertIndex>=0保证在给insertVal找插入位置，不越界
//2.insertVal=0&&insertVal{34,101,119,1}
//定义待插入的数
int insertVal=arr[1];
int insertIndex=1-1;//即arr[1]的前面这个数的下标
//给insertVal找到插入的位置
//说明
//1.insertIndex>=0保证在给insertVal找插入位置，不越界
//2.insertVal=0&&insertVal=0&&insertVal=0&&insertVal
运行效果
算法速度测试
代码实现
package sort;
import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;
public class InsertSort {
public static void main(String[] args) {
// int [] arr= {101,34,119,1,-1,89};
//创建要给80000个的随机的数组
int[] arr=new int[80000];
for (int i = 0; i <80000; i++) {
arr[i]=(int)(Math.random()*8000000);//生成一个[0,8000000)数
}
System.out.println("排序前:");
Date data1=new Date();
SimpleDateFormat simpleDateFormat=new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
String date1Str=simpleDateFormat.format(data1);
System.out.println("排序前的时间是:"+date1Str);
insertSort(arr);//调用插入排序算法
Date data2=new Date();
String date2Str=simpleDateFormat.format(data2);
System.out.println("排序后的时间是:"+date2Str);
//System.out.println(Arrays.toString(arr));
}
//插入排序
public static void insertSort(int[] arr) {
//使用for循环来把代码简化
for (int i = 1; i < arr.length; i++) {
//定义待插入的数
int insertVal=arr[i];
int insertIndex=i-1;//即arr[1]的前面这个数的下标
//给insertVal找到插入的位置
//说明
//1.insertIndex>=0保证在给insertVal找插入位置，不越界
//2.insertVal=0&&insertVal{34,101,119,1}
//定义待插入的数
int insertVal=arr[1];
int insertIndex=1-1;//即arr[1]的前面这个数的下标
//给insertVal找到插入的位置
//说明
//1.insertIndex>=0保证在给insertVal找插入位置，不越界
//2.insertVal=0&&insertVal=0&&insertVal=0&&insertVal
运行结果
package sort;
import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;
public class InsertSort {
public static void main(String[] args) {
// int [] arr= {101,34,119,1,-1,89};
//创建要给80000个的随机的数组
int[] arr=new int[80000];
for (int i = 0; i <80000; i++) {
arr[i]=(int)(Math.random()*8000000);//生成一个[0,8000000)数
}
System.out.println("排序前:");
Date data1=new Date();
SimpleDateFormat simpleDateFormat=new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
String date1Str=simpleDateFormat.format(data1);
System.out.println("排序前的时间是:"+date1Str);
insertSort(arr);//调用插入排序算法
Date data2=new Date();
String date2Str=simpleDateFormat.format(data2);
System.out.println("排序后的时间是:"+date2Str);
//System.out.println(Arrays.toString(arr));
}
//插入排序
public static void insertSort(int[] arr) {
//使用for循环来把代码简化
for (int i = 1; i < arr.length; i++) {
//定义待插入的数
int insertVal=arr[i];
int insertIndex=i-1;//即arr[1]的前面这个数的下标
//给insertVal找到插入的位置
//说明
//1.insertIndex>=0保证在给insertVal找插入位置，不越界
//2.insertVal=0&&insertVal{34,101,119,1}
//定义待插入的数
int insertVal=arr[1];
int insertIndex=1-1;//即arr[1]的前面这个数的下标
//给insertVal找到插入的位置
//说明
//1.insertIndex>=0保证在给insertVal找插入位置，不越界
//2.insertVal=0&&insertVal=0&&insertVal=0&&insertVal
运行结果
