发表于： 2018-10-19 20:04:57
1 329
今天完成的事情：
--今天打了一波野，看了一下排序算法；
--冒泡排序，比较直观，但是效率低
package com.lihoo.sort.util;
import java.util.Arrays;
/**
* #Title: bubble
* #ProjectName sort_demo
* #Description: TODO
* #author lihoo
* #date 2018/10/19-15:20
*/
public class bubble {
public static void main(String[] args) {
//
int[] arrays = {2, 5, 1, 3, 4};
// //使用临时变量，让两个数互换
// int temp;
// //第一位和第二位比
// if (arrays[0] > arrays[1]) {
//// 交换
// temp = arrays[0];
// arrays[0] = arrays[1];
// arrays[1] = temp;
// }
// //第二位和第三位比
// if (arrays[1] > arrays[2]) {
// temp = arrays[1];
// arrays[1] = arrays[2];
// arrays[2] = temp;
// }
// //第三位和第四位比
// if (arrays[2] > arrays[3]) {
// temp = arrays[2];
// arrays[2] = arrays[3];
// arrays[3] = temp;
// }
// //第四位和第五位比
// if (arrays[3] > arrays[4]) {
// temp = arrays[3];
// arrays[3] = arrays[4];
// arrays[4] = temp;
// }
//
// System.out.println(Arrays.toString(arrays));
//
// //第一位和第二位比
//
// //第一位和第二位比
// if (arrays[0] > arrays[1]) {
//// 交换
// temp = arrays[0];
// arrays[0] = arrays[1];
// arrays[1] = temp;
// }
// //第二位和第三位比
// if (arrays[1] > arrays[2]) {
// temp = arrays[1];
// arrays[1] = arrays[2];
// arrays[2] = temp;
// }
// //第三位和第四位比
// if (arrays[2] > arrays[3]) {
// temp = arrays[2];
// arrays[2] = arrays[3];
// arrays[3] = temp;
// }
//
// System.out.println(Arrays.toString(arrays));
// int temp;
// //外层循环是排序的趟数
// for (int i = 0; i < arrays.length - 1; i++) {
//// 内层循环是当前趟数需要比较的次数
// for (int j = 0; j < arrays.length - i-1; j++) {
//// 前一位与后一位与前一位比较，如果前一位比后一位较大，那么交换
// if (arrays[j] > arrays[j+1]) {
// temp = arrays[j];
// arrays[j] = arrays[j+1];
// arrays[j+1] = temp;
// }
// }
// }
//
// System.out.println(Arrays.toString(arrays));
// 装载临时变量
int temp;
// 记录是否发生了置换，0表示没有置换，1表示发生了置换
int isChange;
Long time1 = System.currentTimeMillis();
// 外层循环是排序的趟数
for (int i=0; i<arrays.length-1; i++) {
// 每比较一趟就重新初始化为0
isChange = 0;
// 内层循环是当前趟数需要比较的次数
for (int j=0; j<arrays.length-i-1; j++) {
if (arrays[j] > arrays[j+1]) {
temp = arrays[j];
arrays[j] = arrays[j+1];
arrays[j+1] = temp;
// 如果进到了这里面，就说明发生了置换
isChange = 1;
}
}
// 如果比较完了一趟没有发生置换，那么说明已经排好序了，不需要再执行了
if (isChange == 0) {
break;
}
}
Long time2 = System.currentTimeMillis();
System.out.println(time1);
System.out.println(time2);
Long shicha = time2 - time1;
System.out.println(shicha);
System.out.println(Arrays.toString(arrays));
}
}
--选择排序
package com.lihoo.sort.util;
import java.util.Arrays;
/**
* #Title: Selection
* #ProjectName sort_demo
* #Description: TODO
* #author lihoo
* #date 2018/10/19-18:58
* @author lihoo
*/
public class Selection {
public static void main(String[] args) {
int[] arrays = {2, 3, 1, 4, 3, 5, 1, 6, 1, 2, 3, 7, 2, 3};
// //假定max是最大的
// int max = 0;
//
// for (int i=0; i<arrays.length; i++) {
// if (arrays[i] > max) {
// max = arrays[i];
// }
// }
// System.out.println(max);
//
//
// int temp;
// temp = arrays[11];
// arrays[11] = arrays[13];
// arrays[13] = temp;
//
// System.out.println(Arrays.toString(arrays));
//
//
// /*---------------------------------------*/
// int max2 = 0;
// for (int i=0; i<(arrays.length-1); i++) {
// if (arrays[i] > max2) {
// max2 = arrays[i];
// }
// }
// System.out.println(max2);
//
// temp = arrays[7];
// arrays[7] = arrays[12];
// arrays[12] = temp;
//
// System.out.println(Arrays.toString(arrays));
System.out.println("-------");
// 记录当前趟数的最大值的角标
int pos;
// 交换的变量
int temp;
// 外层循环控制需要排序的趟数
for (int i=0; i<arrays.length-1;i++) {
// 新的趟数，将角标重新赋值为0
pos=0;
// 内层循环控制遍历数组的个数，并得到最大数的角标
for (int j=0; j<arrays.length-i; j++) {
if (arrays[j]>arrays[pos]) {
pos = j;
}
}
// 交换
temp=arrays[pos];
arrays[pos]=arrays[arrays.length-1-i];
arrays[arrays.length-1-i]=temp;
}
System.out.println(Arrays.toString(arrays));
}
}
--快速排序，
package com.lihoo.sort.util;
import java.util.Arrays;
/**
* #Title: Quick
* #ProjectName sort_demo
* #Description: TODO
* #author lihoo
* #date 2018/10/19-18:53
* @author lihoo
*/
public class Quick {
public static void main(String[] args) {
// int[] aaa = new int[];
// aaa
RandomArray s = new RandomArray();
int[] arr = s.din();
// System.out.println(Arrays.toString(arr));
// int[] arr = {1, 4, 5, 67, 2, 7, 8, 6, 9, 44};
quickSort(arr, 0, 9);
System.out.println("数组：" + Arrays.toString(arr));
}
public static void quickSort(int[] arr, int L, int R) {
int i =L;
int j =R;
// 支点
int pivot = arr[(L + R) / 2];
// 左右两端进行扫描，只要两端还没有交替，就一直扫描
while (i <= j) {
// 寻找直到比支点大的数
while (pivot > arr[i]) {
i++;
}
// 寻找直到比支点小的数
while (pivot < arr[j]) {
j--;
}
// 此时已经分别找到了比支点小的数(右边)、比支点大的数(左边)，它们进行交换
if (i <= j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
i++;
j--;
}
}
// 上面一个while保证了第一趟排序支点的左边比支点小，支点的右边比支点大了
// “左边”再做排序，直到左边剩下一个数(递归出口)
if (L < j) {
quickSort(arr, L, j);
}
// “右边”再做排序，直到右边剩下一个数(递归出口)
if (i < R) {
quickSort(arr, i, R);
}
}
}
--算法的时间复杂度；
--如图可以看出冒泡排序和选择排序的时间复杂度为：n的平方；
--快速排序比较复杂，有点没理解，看网上说复杂度是：n·log2(n)，唉，吃了数学不好的亏；
明天计划的事情：
--
明天继续准备复盘所需；
--
遇到的问题：
--
暂时没遇到问题；
--
收获：
--
返回列表
评论