查找算法

性能优化小案例1.二分法查找

image.pngimage.png

  1. public static int find(int[] array, int aim) {
  2.     for (int i = 0; i < array.length; i++) {
  3.         if (aim == array[i]) {
  4.             return i;
  5.         }
  6.     }
  7.     return -1;
  8. }

image.png
image.png
image.png

  1. public static int find(int[] array, int aim) {
  2.     // 初始化left = 最左侧, right = 最右侧
  3.     int left = 0;
  4.     int right = array.length - 1;
  6.     // 当left > right则表示遍历完成
  7.     while (left <= right) {
  8.         // 获取中间的值
  9.         int middle = (left + right) / 2;
  10.         int middleValue = array[middle];
  11.         if (middleValue == aim) {
  12.             // 已经找到目标
  13.             return middle;
  14.         } else if (middleValue < aim) {
  15.             // 目标在middle的右侧，重置left
  16.             left = middle + 1;
  17.         } else {
  18.             // 目标在middle的左侧，重置right
  19.             right = middle - 1;
  20.         }
  21.     }
  22.     return -1;
  23. }

image.png

练习：利用二分法查找降序排列数组的某个值

  2. public class Find {
  4.   public static int find(int[] array, int aim) {
  5.     // 初始化left = 最左侧, right = 最右侧
  6.     int left = 0;
  7.     int right = array.length;
  9.     // 当left > right则表示遍历完成
  10.     while (left <= right) {
  11.       // 获取中间的值
  12.       int middle = (left + right) / 2;
  13.       int middleValue = array[middle];
  14.       if (middleValue == aim) {
  15.         // 已经找到目标
  16.         return middle;
  17.       } else if (middleValue < aim) {
  18.         // 目标在middle的左侧，重置right
  19.         right = middle - 1;
  20.       } else {
  21.         // 目标在middle的右侧，重置left
  22.         left = middle + 1;
  23.       }
  24.     }
  25.     return -1;
  26.   }
  28.   public static void main(String[] args) {
  29.     int[] array = {100, 90, 80, 75, 22, 3, 2};
  30.     int result1 = find(array, 22);
  31.     if (result1 == -1) {
  32.       System.out.println("22 不存在数组中");
  33.     } else {
  34.       System.out.println("22 存在数组中，索引值是 " + result1);
  35.     }
  37.     int result2 = find(array, 50);
  38.     if (result2 == -1) {
  39.       System.out.println("50 不存在数组中");
  40.     } else {
  41.       System.out.println("50 存在数组中，索引值是 " + result2);
  42.     }
  43.   }
  44. }

练习：根据已排好序的字母二分查找某值

image.pngimage.png

  2. import java.util.ArrayList;
  3. import java.util.Comparator;
  5. public class Address {
  7.   public static int find(ArrayList<String> array, String aim) {
  8.     // 初始化left = 最左侧, right = 最右侧
  9.     int left = 0;
  10.     int right = array.size();
  12.     // 当left > right则表示遍历完成
  13.     while (left <= right) {
  14.       // 获取中间的值
  15.       int middle = (left + right) / 2;
  16.       String middleValue = array.get(middle);
  17.       if (middleValue.equals(aim)) {
  18.         // 已经找到目标
  19.         return middle;
  20.       } else if (middleValue.compareTo(aim) > 0) {
  21.         // 目标在middle的左侧，重置right
  22.         right = middle - 1;
  23.       } else {
  24.         // 目标在middle的右侧，重置left
  25.         left = middle + 1;
  26.       }
  27.     }
  28.     return -1;
  29.   }
  31.   public static void main(String[] args) {
  32.     ArrayList<String> array = new ArrayList<>();
  33.     array.add("Allen");
  34.     array.add("Emma");
  35.     array.add("James");
  36.     array.add("Jeanne");
  37.     array.add("Kelly");
  38.     array.add("Kevin");
  39.     array.add("Mary");
  40.     array.add("Natasha");
  41.     array.add("Olivia");
  42.     array.add("Rose");
  44.     int result1 = find(array, "Kelly");
  45.     if (result1 == -1) {
  46.       System.out.println("Kelly 不存在名单中");
  47.     } else {
  48.       System.out.println("Kelly 存在名单中，位置是 " + result1);
  49.     }
  51.     int result2 = find(array, "Edith");
  52.     if (result2 == -1) {
  53.       System.out.println("Edith 不存在名单中");
  54.     } else {
  55.       System.out.println("Edith 存在名单中，位置是 " + result2);
  56.     }
  57.   }
  58. }

性能优化小案例2.二次(查重)问题

image.png
image.png
image.pngimage.pngimage.pngimage.pngimage.pngimage.pngimage.pngimage.pngimage.png

  2. public static ArrayList<Integer> repeat(int[] array) {
  3.     ArrayList<Integer> result = new ArrayList<>();
  4.     int[] exists = new int[11];
  5.     for (int i = 0; i < array.length; i++) {
  6.         int value = array[i];
  7.         // 如果当前位置已经为1，则表示重复
  8.         if (exists[value] == 1) {
  9.             result.add(value);
  10.         } else {
  11.             // 否则将当前位置设置为1
  12.             exists[value] = 1;
  13.         }
  14.     }
  15.     return result;
  16. }

image.png

练习：字符串查重

image.pngimage.png

  2. import java.util.ArrayList;
  4. public class Second {
  6.   public static ArrayList<Character> repeat(String str) {
  7.     ArrayList<Character> result = new ArrayList<>();
  8.     int[] exists = new int[26];
  9.     for (int i = 0; i < str.length(); i++) {
  10.       char c = str.charAt(i);
  11.       if (exists[c - 'a'] == 1) {
  12.         result.add(c);
  13.       } else {
  14.         exists[c - 'a'] = 1;
  15.       }
  16.     }
  17.     return result;
  18.   }
  20.   public static void main(String[] args) {
  21.     String str = "abcdkioudofanzdfpqwe";
  22.     System.out.println(repeat(str));
  23.   }
  24. }

排序算法

冒泡排序

image.png
image.pngimage.png
image.png
image.pngimage.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.pngimage.pngimage.pngimage.png
image.png
image.png

练习：冒泡排序的降序排序算法

  2. package com.youkeda;
  3. import java.util.Arrays;
  5. public class Sort {
  7.   // 冒泡排序
  8.   public static void bubbleSort(int[] array) {
  9.     // 每次循环，都能冒泡出剩余元素中最大的元素，因此需要循环 array.length 次
  10.     for (int i = 0; i < array.length; i++) {
  11.       // 每次遍历，只需要遍历 0 到 array.length - i - 1中元素，因此之后的元素都已经是最大的了
  12.       for (int j = 0; j < array.length - i - 1; j++) {
  13.         // 交换元素
  14.         if (array[j] < array[j + 1]) {
  15.           int temp = array[j + 1];
  16.           array[j + 1] = array[j];
  17.           array[j] = temp;
  18.         }
  19.       }
  20.     }
  21.   }
  24.   public static void main(String[] args) {
  25.     int[] array = {9, 2, 4, 7, 5, 3};
  26.     // Arrays.toString 可以方便打印数组内容
  27.     System.out.println(Arrays.toString(array));
  28.     bubbleSort(array);
  29.     System.out.println(Arrays.toString(array));
  30.   }
  31. }

方式二：

  1. import java.util.Arrays;
  3. public class Demo {
  4.     public static void bubbleSort(int[] array) {
  5.         int maxIndex = 0;
  6.         for (int i = 0; i < array.length; i++) {
  7.             for (int j = i+1; j < array.length; j++) {
  8.                 //如果后面的数大于前面的数，排前面
  9.                 if (array[i]<array[j]) {
  10.                     //交换
  11.                     int temp = array[i];
  12.                     array[i] = array[j];
  13.                     array[j] = temp;
  14.                 }
  15.             }
  16.         }
  17.     }
  18.     public static void main(String[] args) {
  19.         int[] array = {9, 2, 4, 7, 5, 3};
  20.         // Arrays.toString 可以方便打印数组内容
  21.         System.out.println(Arrays.toString(array));
  22.         bubbleSort(array);
  23.         System.out.println(Arrays.toString(array));
  24.     }    
  25. }

选择排序

image.pngimage.png
image.png
image.png
image.pngimage.png

练习：选择排序的升序排列代码

  1. import java.util.Arrays;
  3. public class Demo {
  4.     public static void selectSort(int[] array) {
  5.         //i仅仅起到循环次数的作用
  6.         for (int i = 0; i < array.length; i++) {
  7.             //每次从数组第一个数开始比较最大数的index
  8.             int maxIndex = 0;
  9.             for (int j = 0; j < array.length-i; j++) {
  10.                 //找到比array[maxIndex]大的数了，更新maxIndex值
  11.                 if (array[j]>array[maxIndex]) {
  12.                     maxIndex = j;
  13.                 }
  14.             }
  15.             //如果找到了就是最新的maxIndex值，否则第一个数就是最大值，交换最大值和右边的数
  16.             int temp = array[maxIndex];
  17.             array[maxIndex] = array[array.length-i-1];
  18.             array[array.length-i-1] = temp;
  19.         }
  20.     }
  21.     public static void main(String[] args) {
  22.         int[] array = {9, 2, 4, 7, 5, 3};
  23.         // Arrays.toString 可以方便打印数组内容
  24.         System.out.println(Arrays.toString(array));
  25.         selectSort(array);
  26.         System.out.println(Arrays.toString(array));
  27.     }    
  28. }

插入排序

image.pngimage.png
image.png
image.png
image.pngimage.png
image.pngimage.png

练习：插入排序的升序排序

（注意边界情况）

  2. import java.util.Arrays;
  4. public class Sort {
  6.   // 插入排序
  7.   public static void insertSort(int[] array) {
  8.     // 从倒数第二位开始，遍历到底0位，遍历 N-1 次
  9.     for (int i = array.length - 2; i >= 0; i--) {
  10.       // 存储当前抽离的元素
  11.       int temp = array[i];
  12.       // 从抽离元素的右侧开始遍历
  13.       int j = i + 1;
  14.       while (j <= array.length - 1) {
  15.         // 如果某个元素，小于临时元素，则这个元素左移
  16.         if (array[j] < temp) {
  17.           array[j - 1] = array[j];
  18.         } else {
  19.           // 如果大于，则直接将临时元素插入，然后退出循环。
  20.           array[j - 1] = temp;
  21.           break;
  22.         }
  23.         j++;
  24.       }
  26.       // 处理到达尾部的情况
  27.       if (j == array.length) {
  28.         array[j - 1] = temp;
  29.       }
  30.     }
  31.   }
  34.   public static void main(String[] args) {
  35.     int[] array = {9, 2, 4, 7, 5, 3};
  36.     // Arrays.toString 可以方便打印数组内容
  37.     System.out.println(Arrays.toString(array));
  38.     insertSort(array);
  39.     System.out.println(Arrays.toString(array));
  40.   }
  41. }

插序进阶—-二分插入排序

image.png
image.pngimage.png
源码：

  2. import java.util.Arrays;
  4. public class Sort {
  6.   // 查找应该插入的索引位置
  7.   public static int searchIndex(int[] array, int left, int right, int aim) {
  8.     // 循环查找节点位置
  9.     while (left < right) {
  10.       int middle = (left + right) / 2;
  11.       int value = array[middle];
  12.       if (value < aim) {
  13.         left = middle + 1;
  14.       } else {
  15.         right = middle - 1;
  16.       }
  17.     }
  18.     // 如果最终元素仍然大于目标元素，则将索引位置往左边移动一个
  19.     if(array[left] > aim){
  20.       return left -1;
  21.     }
  22.     // 否则就是当前位置
  23.     return left;
  24.   }
  26.   // 插入排序
  27.   public static void insertSort(int[] array) {
  28.     // 从倒数第二位开始，遍历到底0位，遍历 N-1 次
  29.     for (int i = array.length - 2; i >= 0; i--) {
  30.       // 存储当前抽离的元素
  31.       int temp = array[i];
  32.       int index = searchIndex(array, i + 1, array.length - 1, temp);
  34.       // 根据插入的索引位置，进行数组的移动和插入
  35.       int j = i + 1;
  36.       while (j <= index) {
  37.         array[j - 1] = array[j];
  38.         j++;
  39.       }
  40.       array[j - 1] = temp;
  41.     }
  42.   }
  45.   public static void main(String[] args) {
  46.     int[] array = {9, 2, 4, 7, 5, 3};
  47.     // Arrays.toString 可以方便打印数组内容
  48.     System.out.println(Arrays.toString(array));
  49.     insertSort(array);
  50.     System.out.println(Arrays.toString(array));
  51.   }
  52. }

链表

链表常用方式，固定下来的解题：

  1. 方便对头节点的操作，创建哑节点dummyhead
  2. cur = dummyhed, cur指向当前节点
  3. cur = cur->next，进行链表遍历