关于算法-数据结构:算法与数据结构2排序算法

抉择排序

过程：

arr[0～N-1]范畴上，找到最小值所在的地位，而后把最小值替换到 0 地位。
arr[1～N-1]范畴上，找到最小值所在的地位，而后把最小值替换到 1 地位。
arr[2～N-1]范畴上，找到最小值所在的地位，而后把最小值替换到 2 地位。
…
arr[N-1～N-1]范畴上，找到最小值地位，而后把最小值替换到 N - 1 地位。

估算：

很显著，如果 arr 长度为 N，每一步常数操作的数量，如等差数列个别
所以，总的常数操作数量 = a(N^2) + bN + c (a、b、c 都是常数)

所以抉择排序的工夫复杂度为 O(N^2)。

public static void selectionSort(int[] arr) {if (arr == null || arr.length < 2) {return;}
 // 0 ~ N-1
 // 1~n-1 // 2 for (int i = 0; i < arr.length - 1; i++) { // i ~ N-1
 // 最小值在哪个地位上 i～n-1
 int minIndex = i;
 for (int j = i + 1; j < arr.length; j++) { // i ~ N-1 上找最小值的下标 
minIndex = arr[j] < arr[minIndex] ? j : minIndex;
 }
 swap(arr, i, minIndex);
 }
}
public static void swap(int[] arr, int i, int j) {int tmp = arr[i];
 arr[i] = arr[j];
 arr[j] = tmp;
}

冒泡排序

过程：

在 arr[0～N-1]范畴上：
arr[0]和 arr[1]，谁大谁来到 1 地位；arr[1]和 arr[2]，谁大谁来到 2 地位…arr[N-2]和 arr[N-1]，谁大谁来到 N - 1 地位

在 arr[0～N-2]范畴上，反复下面的过程，但最初一步是 arr[N-3]和 arr[N-2]，谁大谁来到 N - 2 地位
在 arr[0～N-3]范畴上，反复下面的过程，但最初一步是 arr[N-4]和 arr[N-3]，谁大谁来到 N - 3 地位
…
最初在 arr[0～1]范畴上，反复下面的过程，但最初一步是 arr[0]和 arr[1]，谁大谁来到 1 地位

估算：

很显著，如果 arr 长度为 N，每一步常数操作的数量，仍然如等差数列个别
所以，总的常数操作数量 = a(N^2) + bN + c (a、b、c 都是常数)

所以冒泡排序的工夫复杂度为 O(N^2)。

public static void bubbleSort(int[] arr) {if (arr == null || arr.length < 2) {return;}
 // 0 ~ N-1
 // 0 ~ N-2 // 0 ~ N-3 for (int e = arr.length - 1; e > 0; e--) { // 0 ~ e
 for (int i = 0; i < e; i++) {if (arr[i] > arr[i + 1]) {swap(arr, i, i + 1);
 }
 } }}
// 替换 arr 的 i 和 j 地位上的值
public static void swap(int[] arr, int i, int j) {arr[i] = arr[i] ^ arr[j];
 arr[j] = arr[i] ^ arr[j];
 arr[i] = arr[i] ^ arr[j];
}

插入排序

过程

很显著，在最差状况下，如果 arr 长度为 N，插入排序的每一步常数操作的数量，还是如等差数列个别

估算

所以，总的常数操作数量 = a(N^2) + bN + c (a、b、c 都是常数)
所以插入排序排序的工夫复杂度为 O(N^2)。

public static void insertionSort(int[] arr) {if (arr == null || arr.length < 2) {return;}
 // 0~0 有序的
 // 0~i 想有序
 for (int i = 1; i < arr.length; i++) { // 0 ~ i 做到有序
 for (int j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--) {swap(arr, j, j + 1);
 }
 }}
// i 和 j 是一个地位的话，会出错
public static void swap(int[] arr, int i, int j) {arr[i] = arr[i] ^ arr[j];
 arr[j] = arr[i] ^ arr[j];
 arr[i] = arr[i] ^ arr[j];
}

二分法

1. 在一个有序数组中，找某个数是否存在
2. 在一个有序数组中，找 >= 某个数最左侧的地位
3. 在一个有序数组中，找 <= 某个数最右侧的地位
4. 部分最值问题 (不肯定有序)
5. 次要找到一个排他性的规范

public static boolean exist(int[] sortedArr, int num) {if (sortedArr == null || sortedArr.length == 0) {return false;}
 int L = 0;
 int R = sortedArr.length - 1;
 int mid = 0;
 // L..R
 while (L < R) {// mid = (L+R) / 2;
 // L 10 亿 R 18 亿
 // mid = L + (R - L) / 2
 // N / 2    N >> 1 mid = L + ((R - L) >> 1); // mid = (L + R) / 2
 if (sortedArr[mid] == num) {return true;} else if (sortedArr[mid] > num) {R = mid - 1;} else {L = mid + 1;}
 } return sortedArr[L] == num;
}