数据结构和算法
数据结构是计算机存储,组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下,精心选择的数据结构可以带来更高的运行或存储效率。数据结构往往同高效的检索算法和索引技术有关;算法是指令的集合,是为解决特定问题而规定的一系列操作,可以简洁而快速的得到预期的结果集。程序=数据结构+算法
冒泡排序
冒泡大家都知道,在河水中的泡泡,水底刚冒出来的时候是比较小的,随着慢慢向水面浮起会逐渐增大。
图文描述
- 首先创建一个数组 int[] arr ={60,40,80,20,30}
-
然后进行冒泡排序如下图:
- 计算的顺序
1.第一次循环:arr[0]和arr[1],arr[1]和arr[2],arr[2]和arr[3],arr[3]和arr[4] 得到全部5位数中最大值
2.第二次循环:arr[0]和arr[1],arr[1]和arr[2],arr[2]和arr[3] 得到剩下的4位数中最大的值
3.第三次循环:arr[0]和arr[1],arr[1]和arr[2] 得到剩下的3位数中最大的值
4.第四次循环:arr[0]和arr[1] 得到剩下的2位数中最大的值
冒泡算法的运作规律如下:
- 比较相邻的元素。如果第一个比第二个大,就交换他们两个的值。
- 最外层可以用个for循环 ,循环4次 也就是(arr.lenght-1)次。
- 第1次循环i=0时判断4次,第2次循环i=1时判断3次,第3次循环i=2时判断2次,第4循环i=3时判断1次。arr.lenght-1=4,4-0=4,4-1=3,4-2=2,4-3=1,内部循环判断每次都是从下标为0开始的,得到的规律内部j初始化时为0,j<(arr.lenght-1-i)内部判断的次数。
实现代码如下
import java.util.Arrays;
import java.util.Random;
public class MrpSort{
public static void main(String[] args) {
/**
* 第一步首先创建一个数组 内容是100以内的随机数字
*/
int[] arr = new int[20];
Random random = new Random();
for (int i = 0; i < arr.length; i++) {
arr[i] = random.nextInt(100);
}
System.out.println("排序前数组="+ Arrays.toString(arr));
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]){
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
System.out.println("排序后数组="+Arrays.toString(arr));
}
}
结果
选择排序
选择排序是每一次从待排序的数据元素中选出最小的一个元素,存放在序列的起始位置,直到全部待排序的数据元素排完。
图文描述
- 首先创建一个数组 int[] arr ={60,40,80,20,30}
-
然后进行选择排序如下图:
- 计算顺序
- 第一次循环:arr[0]和arr[1],arr[0]和arr[2],arr[0]和arr[3],arr[0]和arr[4] 得到全部5位数中最小的值。
- 第二次循环:arr[1]和arr[2],arr[1]和arr[3],arr[1]和arr[4] 得到剩下四位数中最小的值。
- 第三次循环:arr[2]和arr[3],arr[2]和arr[4] 得到剩下三位数中最小的值。
- 第四次循环:arr[3]和arr[4] 得到剩下两位数中最小的值。
选择排序计算规律如下:
- 从待排序序列中,用第一个数字和以下数字比较,如果arr[i]>arr[n] 则换值。
- 最外层用个for循环,循环4次 也就是(arr.lenght-1)次。
- 第1次循环i=0时判断4次,第2次循环i=1时判断3次,第3次循环i=2时判断2次,第4循环i=3时判断1次。arr.lenght-1=4,4-0=4,4-1=3,4-2=2,4-3=1,内部循环判断每次都是从下标为i开始的,得到的规律内部j初始化时为i+1,j<arr.lenght 内部判断的次数。
实现代码如下
import java.util.Arrays;
import java.util.Random;
public class selectSort {
public static void main(String[] args){
/**
* 第一步首先创建一个数组 内容是100以内的随机数字
*/
int[] arr = new int[20];
Random random = new Random();
for (int i = 0; i < arr.length; i++) {
arr[i] = random.nextInt(100);
}
System.out.println("排序前数组="+ Arrays.toString(arr));
for (int i = 0; i < arr.length-1; i++) {
for (int j = i+1; j < arr.length; j++){
if (arr[i] > arr[j]){
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
}
System.out.println("排序后数组="+Arrays.toString(arr));
}
}
结果
插入排序
直接插入排序基本思想是每一步将一个待排序的记录,插入到前面已经排好序的有序序列中去,直到插完所有元素为止。从下标为1的元素开始选择合适的位置插入,因为下标为0的只有一个元素,默认是有序的。
图文描述
首先创建一个数组 int[] arr ={60,40,80,20,30}
-
然后进行选择排序如下图(借用大神一张图):
-
计算顺序
- 第一次循环:arr[1]和arr[0] 得到前两位最小的值。
- 第二次循环:arr[2]和arr[1],arr[2]和arr[0] 得到前三位最小的值。
- 第三次循环:arr[3]和arr[2],arr[3]和arr[1],arr[3]和arr[0] 得到前四位最小的值。
- 第四次循环: arr[4]和arr[3], arr[4]和arr[2], arr[4]和arr[1], arr[4]和arr[0] 得到五位最小的值。
选择排序计算规律如下:
- 最外层用个for循环,循环4次,因为从下标为1开始,所以i<arr.lenght。
- 拿到右边待排序的值和左边已排序最右边的值依次比较,如果待排序的值小于已排序的值继续对比。
实现代码如下
import java.util.Arrays;
import java.util.Random;
public class InsertSort {
public static void main(String[] args){
/**
* 第一步首先创建一个数组 内容是100以内的随机数字
*/
int[] arr = new int[20];
Random random = new Random();
for (int i = 0; i < arr.length; i++) {
arr[i] = random.nextInt(100);
}
System.out.println("排序前数组="+ Arrays.toString(arr));
int j;
for(int i = 1 ; i < arr.length ; i++){
int tmp = arr[i];//记录要插入的数据
j = i;
while(j > 0 && tmp < arr[j-1]){//从已经排序的序列最右边的开始比较,找到比其小的数
arr[j] = arr[j-1];//向后挪动
j--;
}
arr[j] = tmp;//存在比其小的数,插入
}
System.out.println("排序后数组="+Arrays.toString(arr));
}
}
结果
冒泡、选择、插入排序 效率对比
分别用冒泡、选择、插入排序,来实现同一个需求,分别看完成花费的时间。
实现代码
import java.util.Random;
/**
* 冒泡、选择、插入 排序对比
*/
public class CompareSort {
public static void main(String[] args){
/**
* 冒泡排序
*/
int[] arrayBub = getArray();
long startTimeBub = System.currentTimeMillis();
for (int i = 0; i < arrayBub.length-1; i++) {
for(int j = 0; j < arrayBub.length-1-i; j++){
if (arrayBub[j] > arrayBub[j+1]){
int temp = arrayBub[j];
arrayBub[j] = arrayBub[j+1];
arrayBub[j+1] = temp;
}
}
}
long endTimeBub = System.currentTimeMillis();
System.out.println("冒泡排序时间戳= "+(endTimeBub-startTimeBub));
/**
* 选择排序
*/
int[] arraySelect = getArray();
long startTimeSelet = System.currentTimeMillis();
for (int i = 0; i < arraySelect.length-1; i++) {
for (int j = i+1; j < arraySelect.length; j++){
if (arraySelect[i] > arraySelect[j]){
int temp = arraySelect[i];
arraySelect[i] = arraySelect[j];
arraySelect[j] = temp;
}
}
}
long endTimeSelet = System.currentTimeMillis();
System.out.println("选择排序时间戳= "+(endTimeSelet-startTimeSelet));
/**
* 插入排序
*/
int[] arrayInsert = getArray();
long startTimeInset = System.currentTimeMillis();
int j;
for(int i = 1 ; i < arrayInsert.length ; i++){
int tmp = arrayInsert[i];//记录要插入的数据
j = i;
while(j > 0 && tmp < arrayInsert[j-1]){//从已经排序的序列最右边的开始比较,找到比其小的数
arrayInsert[j] = arrayInsert[j-1];//向后挪动
j--;
}
arrayInsert[j] = tmp;//存在比其小的数,插入
}
long endTimeInset = System.currentTimeMillis();
System.out.println("插入排序时间戳= "+(endTimeInset-startTimeInset));
}
/**
* 创建一个数组 内容是一万个1000以内的随机数字
*/
public static int[] getArray(){
int[] arr = new int[10000];
Random random = new Random();
for (int i = 0; i < arr.length; i++) {
arr[i] = random.nextInt(1000);
}
return arr;
}
}
结果
- 最终结论显示,插入排序的效率要高于选择排序高于冒泡排序。