etc

小小的注意點們

• 交換兩個變量的值時, 如果使用異或運算符, 需要先判斷兩個數是否相等

if (a == b) return;
a ^= b;
b = a ^ b;
a ^= b;
           

• 取一個數組的中間位置, 應該使用(low + high) / 2, 不适用length / 2, 目的是友善之後可能出現的函數的遞歸等操作
• 堆排序
  • 對一個整數類型的數組進行升序排序
    1. 原始數組即為一個二叉堆(左孩子的下标=父親的下标 * 2 + 1, 右孩子的下标=父親的下标 * 2 + 2, 孩子父親的下标=(孩子的下标 - 1) / 2)
    2. 調整堆, 将堆轉換為最大堆(判斷if parent < two_children: swap(parent, larger_child))
    3. 删除原始堆中最後的一個元素(并不是真的删除, 而是該堆的length - 1), 對仍然保留在堆中的元素進行$2的操作
• 快速排序
  • 遞歸成立的條件式low < high

Code here

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define ARRAY_PRINT(arr, length) do {                \
for (int i = 0; i < length; i++) {                    \
printf("%d\t", arr[i]);                             \
}                                                     \
} while (0)

#define SWAP(a, b)    do {            \
if (a == b) break;            \
(a) ^= (b);                \
(b) = (a) ^ (b);            \
(a) ^= (b);                \
} while (0)

#define MID(low, high) ((low + high) / 2)

static void quick_sort_recurision(int *a, int low, int high) {
    int pivot, i, j;
    pivot = low; // select a pivot element
    i = low;
    j = high;
    if (high - low) return;
    while (i <= j) {
        if (a[i] <= a[pivot] && i <= high) {
            i++;
        }
        else if (a[j] > a[pivot] && j >= low) {
            j--;
        }
        else {
            SWAP(a[i], a[j]);
        }
    }
    SWAP(a[j], a[pivot]);
    quick_sort_recurision(a, low, j - 1);
    quick_sort_recurision(a, j + 1, high);
}

void quick_sort(int *arr, int len) {
    if (!arr || len < 0) return;
    int low = 0, high = len - 1;
    quick_sort_recurision(arr, low, high);
}

#define LENGTH 10

int main() {
    srand((int) time(0));
    int arr[LENGTH];
    for (int i = 0; i < LENGTH; i++) {
        arr[i] = rand() % 60;
    }
    ARRAY_PRINT(arr, LENGTH);
    quick_sort(arr, LENGTH);
    putchar(10);
    ARRAY_PRINT(arr, LENGTH);
    return 0;
}