目錄
- 冒泡排序、選擇排序、直接插入排序
- 冒泡排序
- 選擇排序
- 選擇排序與冒泡排序的注意事項
- 小案例，使用選擇排序完成對物件的排序
- 直接插入排序(插入排序)
- 快速排序（比較排序中效率最高的一種排序）
- 折半查找(使用時有限制，只能是排序好了的陣列)
- 補充一下遞回的優點與缺點
冒泡排序、選擇排序、直接插入排序
冒泡排序
import java.util.Arrays;
/**
* @author dengqixing
* @date 2021/4/17
*/
public class BubbleSort {
public static void main(String[] args) {
// 1、定義無序陣列
int[] arr = {89, 59, 44, 12, 58, 26, 94, 98, 21, 23};
// int[] arr = {12, 21, 23, 26, 44, 58, 59, 89, 94, 98};
// 2、輸出無序陣列
System.out.println(Arrays.toString(arr));
// 3、排序
// 外回圈，至少比較陣列長度減一，因為最后一個元素無需再進行比較
for (int i = 0; i < arr.length - 1; i++) {
// 默認序列是有序的
boolean flag = true;
// 內回圈，由于每次比較都會有一個最大或最小的數被放在最邊緣的位置，所以每次回圈時都需要對應的減少比較的次數
for (int j = 0; j < arr.length - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
arr[j] = arr[j] ^ arr[j + 1];
arr[j + 1] = arr[j] ^ arr[j + 1];
arr[j] = arr[j] ^ arr[j + 1];
// 如果第一次小回圈進行過交換，說明序列不是有序的,否則說明是有序的
flag = false;
}
}
// 這么做如果陣列已經是有序了，則無需繼續進行比較，減少回圈次數，增加效率
if (flag) {
break;
}
}
// 4、輸出排序后的陣列
System.out.println(Arrays.toString(arr));
}
}
選擇排序
class SelectSort {
public static void main(String[] args) {
// 1、定義無序陣列
int[] arr = {89, 59, 44, 12, 58, 26, 94, 98, 21, 23};
// 2、輸出無序陣列
System.out.println(Arrays.toString(arr));
// 3、排序
// 外回圈，需要 n - 1的回圈次數
for (int i = 0; i < arr.length - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < arr.length; j++) {
if (arr[minIndex] > arr[j]) {
minIndex = j;
}
}
// 進行交換
if (minIndex != i) {
int temp = arr[minIndex];
arr[minIndex] = arr[i];
arr[i] = temp;
}
}
// 4、輸出排序后的陣列
System.out.println(Arrays.toString(arr));
}
}
選擇排序與冒泡排序的注意事項
- 冒泡排序至多需要n-1趟回圈，最少一趟回圈；其中n為長度
- 選擇排序一定需要n-1躺回圈，一趟也不能少
- 冒泡排序中最多的操作就是比較和交換，一趟回圈中可能發生多次交換；
- 選擇排序中最多的操作就是比較，一趟比較結束后發現更小(或更大)的值才進行交換
- 所以更推薦使用冒泡，
小案例，使用選擇排序完成對物件的排序
class SelectSort2 {
public static void main(String[] args) {
// 1、定義無序陣列
Comparable[] arr = {new Person(14,"李四"),new Person(18,"李四"),new Person(16,"李四")};
// 2、輸出無序陣列
System.out.println(Arrays.toString(arr));
// 3、排序
selectSort(arr);
// 4、輸出排序后的陣列
System.out.println(Arrays.toString(arr));
}
private static void selectSort(Comparable[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < arr.length; j++) {
if (arr[minIndex].compareTo(arr[j]) > 0) {
minIndex = j;
}
}
// 進行交換
if (minIndex != i) {
Comparable temp = arr[minIndex];
arr[minIndex] = arr[i];
arr[i] = temp;
}
}
}
}
class Person implements Comparable<Person> {
int age;
String name;
public Person(int age, String name) {
this.age = age;
this.name = name;
}
public int getAge() {
return age;
}
public void setAge(int age) {
this.age = age;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
@Override
public int compareTo(Person p) {
return Integer.compare(this.getAge(), p.getAge());
}
@Override
public String toString() {
return "Person{" +
"age=" + age +
", name='" + name + '\'' +
'}';
}
}
直接插入排序(插入排序)
public static void insertSort(int[] arr) {
// 默認第一個元素是有序序列，所以從1開始
for (int i = 1; i < arr.length; i++) {
// 臨時變數存盤當前需要插入的資料
int temp = arr[i];
// 存盤有序序列的元素下標位置
int j = i - 1;
// 如果當前的元素小于需要比較的元素
while (j >= 0 && temp < arr[j]) {
// 將當前正在比較的元素放入其后面的位置
arr[j + 1] = arr[j];
// 繼續往左進行資料比較
j--;
}
// 回圈結束后，將其比較的元素放在最后比較的一個元素的后面
arr[j + 1] = temp;
}
}
快速排序（比較排序中效率最高的一種排序）
原理：
- 首先得到一個無序序列
- 隨機選取其中一個數為基準數(一般默認為最左側的第一個元素)
- 然后會有兩個指標分別在當前需要比較的序列的最左側和最右側
- 先從最右側開始往左移動比較，一旦碰到了大于或者相等于基準數的元素，則繼續向左移動，直到指標所指向的元素小于基準數，就停下(還有一個條件，左邊的索引必須小于右邊的索引)
- 然后從最左側開始向右移動比較，一旦碰到了小于或者相等于基準數的元素，則繼續向右移動，直到指標所指向的元素大于基準數，就停下（左邊的索引必須小于右邊的索引）
- 如果左指標與右指標相等（也就是相遇了），則將其相遇位置的元素與基準數進行交換
- 最后再將基準數左邊的序列再次進行快速排序
- 將基準數右邊的序列再次進行快速排序
public static void main(String[] args) {
int[] arr = new int[100000000];
for (int i = 0; i < arr.length; i++) {
// 隨機存入1到10萬之間的數字
arr[i] = (int)(Math.random() * 100000)+1;
}
// 排序
long start = System.currentTimeMillis();
quickSort(arr, 0 , arr.length -1);
long end = System.currentTimeMillis();
//19357毫秒，排序1億個數字的序列竟只用了19秒，
冒泡排序在10萬資料時就已耗時15秒左右，快速排序在10萬資料時耗時只有20-30毫秒
System.out.println("運行時間為 :" + (end - start));
}
public static void quickSort(int[] arr, int left, int right) {
// 如果左邊索引比右邊索引還要大，是不合法的，直接return結束方法
if (left > right) {
return;
}
// 獲得基準數(默認選擇最左邊的數)與左右2個下標索引數
int base = arr[left];
int i = left;
int j = right;
// 當i和j不相遇的時候，才進行回圈檢索
while (i != j) {
// 從右邊開始檢索，如果找到了小于基準數的數，就停下
// 如果檢索到比基準數大的或者相等的，就繼續檢索
while (arr[j] >= base && i < j) {
j--;
}
// 從左開始檢索，如果找到了大于基準數的數，就停下
// 如果檢索到比基準數小的或者相等的，就繼續檢索
while (arr[i] <= base && i < j) {
i++;
}
// 到這說明i和j都停下了，交換它們兩的元素
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
// 到這說明 i 和 j相遇了，就將相遇位置的值與基準數交換
arr[left] = arr[i];
arr[i] = base;
// 然后將排序后左邊的序列再次進行排序
quickSort(arr, left , i -1);
// 將右邊的序列再次進行排序
quickSort(arr, i + 1, right);
}
}
折半查找(使用時有限制，只能是排序好了的陣列)
// 非遞回二分查找
public static int binarySearch(int[] arr, int key) {
int low = 0;
int high = arr.length - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (arr[mid] == key) {
return mid;
} else if (key < arr[mid]) {
high = mid - 1;
} else if (key > arr[mid]) {
low = mid + 1;
}
}
return -1;
}
// 遞回二分查找
public static int binarySearch2(int[] arr, int key) {
int low = 0;
int high = arr.length - 1;
int index = binarySearch(arr, key, low, high);
return index;
}
private static int binarySearch(int[] arr, int key, int low, int high) {
if (low > high) {
return -1;
}
// 計算中間索引
int mid = (low + high) / 2;
if (arr[mid] == key) {
return mid;
} else if (key < arr[mid]) {
return binarySearch(arr, key, low, mid - 1);
} else {
return binarySearch(arr, key, mid + 1, high);
}
}
補充一下遞回的優點與缺點
- 優點：編碼簡單，適合處理相同業務邏輯的問題
- 缺點：占用記憶體空間多，每遞回一次都會在堆疊空間中開辟新空間執行方法
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/277292.html
標籤：其他
上一篇：2、尋找重復數字
下一篇：Pyinstaller原理詳解