java常见数据结构
常见数据结构1.查找、排序
稳定的排序：归并、冒泡、插入、基数
1.1二分查找
前提:数据是有序排列的
1. 定义左边界l、右边界r，循环while(l<=r)
2. 获取中间索引m=(l+r)>>1
3. 中间索引m的值与待查找的值t比较
- arr==t,表示已经找到，则返回中间索引
- arr>t,当前中间索引值右侧的其他数大于待查找的值，则r=m-1
- arr<t,当前中间索引值左侧的其他数小于待查找的值，则l=m+1
4.当l>r时，表示没有找到，结束循环
public static int binarySearchDemo(int[] arr, int t) {
int l = 0;
int r = arr.length - 1;
int m;
while (l <= r) {
m = (l + r) >> 1;
if (arr == t) {
//已找到，返回当前索引
return m;
} else if (arr > t) {
//中间值右侧大于t
r = m - 1;
} else {
//中间值左侧小于t
l = m + 1;
}
}
return -1;
}
选择题中考察 查找次数：
- 奇数看中间偏左（向下取整）
- 偶数看中间
1.2冒泡排序(稳定)
- 依次比较数组中相邻两个元素大小，如a>a，则交换这两个元素。两两比较一遍称为一轮冒泡。(类似水底冒泡,气泡在上升至水面途中变的越来越大)
- 设置一个标志符，如果标识符未改变状态(未发生元素交换)则表示排序已经完成，跳出循环。
public static void bubbleSort(int[] arr) {
for (int i = 0; i < arr.length-1; i++) {
boolean flag=false;
for (int j = 0; j < arr.length-1-i; j++) {
if(arr>arr[j+1
swap(arr,j,j+1);
flag=true;
}
}
//如果没有发生交换，代表已经排序完成
if(!flag){
break;
}
}
System.out.println(Arrays.toString(arr));
}
public static void swap(int[] arr, int i, int j) {
int t = arr;
arr=arr;
arr=t;
}
1.3选择排序
1. 将数组分为两个子集 ，已排序的和未排序的，每一轮从未排序的子集中选出最小元素，放入已排序的子集中。循环多次，直至整个数据有序。
2. 为了减少交换次数，每一轮先找出最小值的索引。在每轮最后在交换元素。
public static void selectionSort(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
//记录最小值的索引值
int s =i;
//内层循环 初始值 从最小索引s+1处开始
for (int j = s + 1; j < arr.length; j++) {
if (arr > arr) {
s = j;
}
}
//如果最小值索引发生了改变则要交换位置
if (s != i) {
int temp = arr;
temp = arr;
arr = arr;
arr = temp;
}
}
System.out.println(Arrays.toString(arr));
}
1.3选择排序
-
public static void selectionSort(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
//记录最小值的索引值
int s = i;
//内层循环 初始值 从最小循环+1索引处开始
for (int j = s + 1; j < arr.length; j++) {
if (arr > arr) {
s = j;
}
}
//如果最小值索引发生了改变则要交换位置
if (s != i) {
int temp = arr;
temp = arr;
arr = arr;
arr = temp;
}
}
System.out.println(Arrays.toString(arr));
}
1.4插入排序(稳定)
插入排序与选择排序的比较
-
1. 将数据分为排序区域、未排序区域。每一轮从未排序区域中取出第一个元素，插入到排序区域(需按顺序)，循环多次直至整个数组有序。
2. 待插入元素进行比较时，遇到比子集小的元素，代表找到了插入位置，无需进行后续比较。
3. 插入时直接移动元素，而非交换
public static void insertSort(int[] arr) {
for (int i = 1; i < arr.length ; i++) {
//代表待插入的元素
int t = arr;
//代表已排序区域的元素索引
int j = i - 1;
while (j >= 0) {
if (t < arr) {
arr = arr;
} else {
//退出循环，减少比较次数
break;
}
j--;
}
//因为j--了
arr = t;
}
System.out.println(Arrays.toString(arr));
}
1.5希尔排序的概念(无需掌握代码)
选择增量gap=length/2，缩小增量继续以gap = gap/2的方式，这种增量选择我们可以用一个序列来表示，{n/2,(n/2)/2...1}，称为增量序列。希尔排序的增量序列的选择与证明是个数学难题，我们选择的这个增量序列是比较常用的，也是希尔建议的增量，称为希尔增量，但其实这个增量序列不是最优的。
1.6快速排序
分而治之的思想(divide-and-conquer)
1.每一轮排序选择一个基准点(pivot)进行分区
1. 让小于基准点的元素进入一个分区，大于的进入另一个分区
2. 当分区完成时，基准点元素的位置和就是其最终位置
2.在子分区内重复多次上述过程，直到子分区元素个数为1.
单边快排(洛穆托分区方案)
1. 选择最有元素作为基准点元素
2. j指针负责找到比基准点小的元素，一旦找到则与i进行交换
3. i指针维护小于基准点元素边界，也是每次交换的目标索引
4. 最后基准点与i交换，i为分区位置
public static void quick(int[] a, int l, int h) {
//如果左边界大于等于右边界，结束递归
if (l >= h) {
return;
}
//p 索引值
int p = partition(a, l, h);
//左边分区的范围确定
quick(a, l, p - 1);
//右边分区的范围确定
quick(a, p + 1, h);
}
/**
* @Param arr 待排序的数组
* @param l 左边界
* @param h 右边界
* @Return 本次基准点元素最终位置
*/
private static int partition(int[] arr, int l, int h) {
//1.基准元素
int pv = arr;
//2.左边界
int i = l;
for (int j = l; j < h; j++) {
if (arr < pv) {
//3.arr小于基准点则交换,放在基准点的左边
swap(arr, i, j);
//4，左边界+1
i++;
}
}
//5.基准点与i交换
swap(arr, h, i);
System.out.println(Arrays.toString(arr) + "i=" + i);
//本次基准点元素最终位置
return i;
}
public static void swap(int[] arr, int i, int j) {
int temp = arr;
arr = arr;
arr = temp;
}
1.7面试中出现的题目
1. 使用直接插入排序算法对序列18,23,19,9,23,15进行排序，第三趟排序后的结果为
2. 使用选择排序算法对序列18,23,19,9,23,15进行排序，第三趟排序后的结果为
中间夹杂了php的代码实现...... reder 发表于 2022-4-1 16:40
中间夹杂了php的代码实现......
都是java哇
页:
[1]