排序演算法
常用排序演算法的理解及示例代碼：冒泡排序、插入排序、選擇排序、歸并排序、快速排序、二叉樹排序
分析演算法
- 記憶體消耗：是否是原地排序演算法，指空間復雜度為 O(1) 的演算法
- 穩定性：是否是穩定的排序演算法，等值元素排序后次序不變，為穩定的排序演算法
- 執行效率：時間復雜度，最好、最壞、平均或均攤
冒泡排序
相鄰元素根據大小交換位置，每次遍歷將一個元素放到合適的位置上
- 是否原地排序：原地排序
- 是否穩定：控制相鄰元素大小相等時不做交換，則為穩定排序
- 時間復雜度：\(O(n^2)\)
- 設定標志位，優化演算法，避免已經有序后還在做無用回圈
public static void bubble(int[] a) {
for (int i = 0; i < a.length - 1; i++) {
boolean traverse = true;//是否還需要遍歷的標志
for (int j = 0; j < a.length - i - 1; j++) {
if (a[j] > a[j + 1]) {
traverse = false;
int temp = a[j];
a[j] = a[j + 1];
a[j + 1] = temp;
}
if (traverse) break;
}
}
}
插入排序
總是取無序區第一個元素，有序區由大向小與該元素比較，比該元素大則后移一位，最終讓出合適位置
- 是否原地排序：原地排序
- 是否穩定：控制后面出現的元素插入到前面相同元素的后面，則為穩定排序
- 時間復雜度：\(O(n^2)\)
public static void insert(int[] a) {
for (int i = 0; i < a.length - 1; i++) {
int x = a[i + 1];
int j = i;
for (; j >= 0; j--) {
if (a[j] > x) a[j + 1] = a[j];//比 x 大后移一位
else break;//找到合適位置
}
a[j + 1] = x;//回圈中多減了一次 1
}
}
選擇排序
依次遍歷每個位置，與后續元素比較，比該位小的換到該位
- 是否原地排序：原地排序
- 是否穩定：不是穩定排序
- 時間復雜度：\(O(n^2)\)
public static void select(int[] a) {
for (int i = 0; i < a.length - 1; i++) {
for (int j = i + 1; j < a.length; j++) {
if (a[j] < a[i]) {
int temp = a[j];
a[j] = a[i];
a[i] = temp;
}
}
}
}
歸并排序
原陣列分成兩部分，遞回得到 length 個陣列，每個陣列中一個元素
兩兩陣列合并，遞回得出排序結果
- 是否原地排序：非原地排序，空間復雜度較高，\(O(n)\)
- 是否穩定：穩定
- 時間復雜度：\(O(nlogn)\)
public static void sort(int[] a, int left, int right) {
if (left >= right) return;
int mid = left + (right - left >> 2);//取中間元素
sort(a, left, mid);
sort(a, mid + 1, right);
merge(a, left, mid, right);
}
public static void merge(int[] a, int left, int mid, int right) {
int[] temp = new int[right - left + 1];
int l = left, r = mid + 1, count = 0;
// 比較兩部分放入大小，小元素放入陣列
while (l <= mid && r < right) {
temp[count++] = a[l] < a[r] ? a[l++] : a[r++];
}
// 兩部分個數不一樣時，將長的部分剩余元素加入陣列
while (l > mid && r <= right) temp[count++] = a[r++];
while (l <= mid && r > left) temp[count++] = a[l++];
// 復制給原陣列
for (int i = 0; i < temp.length; i++) {
a[left + i] = temp[i];
}
}
快速排序
設定頭尾指標，選取一個元素作為中點
先從尾指標向前找比中點小的，移到頭指標，頭指標后移一位
再從頭指標向后找比中點大的，移到尾指標，尾指標前移一位
指標相遇時，得到中點位置，保證了該位置左邊元素小，右邊元素大
遞回執行頭結點到中點 -1、中點 +1 到尾結點兩段元素的排序
- 是否原地排序：原地排序
- 是否穩定：不穩定
- 時間復雜度：\(O(nlogn)\)
public static void quick(int[] a, int left, int right) {
if (left >= right) return;
int i = left, j = right;
int x = a[left];
while (i < j) {
while (i < j && a[j] >= x) j--;
if (i < j) a[i++] = a[j];
while (i < j && a[i] <= x) i++;
if (i < j) a[j--] = a[i];
}
a[i] = x;
quick(a, left, i - 1);
quick(a, i + 1, right);
}
二叉樹排序
左小右大生成二叉樹，中序遍歷得出的結果有序
- 是否原地排序：非原地排序
- 是否穩定：控制相等時放在右結點，則為穩定排序
- 時間復雜度：\(O(n)\)
public static void treeSort(int[] a) {
TreeNode tree = new TreeNode();
for (int i : a) {//生成樹
tree.add(i);
}
List<Integer> list = tree.inOrder();//中序遍歷
for (int i = 0; i < list.size(); i++) {
a[i] = list.get(i);//裝回陣列
}
}
static class TreeNode {//靜態內部類，可在靜態方法中實體化
TreeNode left, right;
Object value;
// 左小右大生成二叉樹樹
public void add(Object o) {
if (value =https://www.cnblogs.com/pgjett/p/= null) {
value = o;
} else {
if ((int) o < (int) value) {
left = (left == null) ? new TreeNode() : left;
left.add(o);
} else {
right = (right == null) ? new TreeNode() : right;
right.add(o);
}
}
}
// 中序遍歷得出的結果有序
public List inOrder() {
List list = new ArrayList<>();
if (left != null) list.addAll(left.inOrder());
list.add((int) value);
if (right != null) list.addAll(right.inOrder());
return list;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/73556.html
標籤：其他
上一篇：Latex學習體會