默认按 从小到大 排序, insert 到 insertPos 前

内部排序
    
    交换
        bubble
        quick
        
    insert
        直接
        折半
        希尔: 不 易 记, 不 care
        
    选择
        simple select
        heap sort

    归并

1 交换 sort: 序列长度 n

交换: 据 两 element key 的 compare result, 决定是否 交换 其 position

1.1 bubble sort

(1) 1 趟排序

从后往前 / 从前往后 两两比较 相邻元素, 若 逆序, 则 交换;

    => untill 比较完 最后 2 个 => minElem 冒到 first/last position

(2) 下一趟, 前面已冒出 elem 不参与, 待排序列 少 1 个

(3) 最多 n - 1 趟 就能 sort 好 所有 elem

void swap(int *v1, int *v2)
{
    int tmp = *v1;
    *v1 = *v2;
    *v2 = tmp;
}

void bubbleSort(int arr[], int n)
{
    //(1) n - 1 times
    for(int times = 0; times < n - 1; times++)
    {
        //(2) 从后往前 两两比较
        int walk;
        for(walk = n - 1; walk > times; walk--)
            if(arr[walk - 1] > arr[walk] )
                swap(arr + walk - 1, arr + walk);
    }
}

改进: 加 swapFlag, 若 某趟 中无交换 => sort 提前完成

void bubbleSort(int arr[], int n)
{
    for(int times = 0; times < n - 1; times++)
    {
        int swapFlag = false;
        
        int walk;
        for(walk = n - 1; walk > times; walk--)
        {
            if(arr[walk - 1] > arr[walk] )
            {
                swap(arr + walk - 1, arr + walk);
                swapFlag = true;
            }
        }
        
        if(swapFlag == false)
            return;
    }
}

2 quick sort

思想: 分治

(1) 划分

    1) 待排序列 a[1..n]  中 
    
        任取一 elem 作 pivot 中心

    2) 用 `1 趟 快排` 将 a[1..n] 划分为 two parts
    
        a[1...pivotPos - 1] 和 a[pivotPos + 1.. n],
        
            分别 < 和 >= pivot

        => 找到 pivotPos

    3) pivotPos == 当前序列 pivot 的 最终排序 pos

(2) 分别对 left / right 2 个 子序列 递归 上述过程

#include <stdio.h>

int partition(int a[], int left, int right);
    
void quickSort(int a[], int left, int right)
{
    // 递归 出口: left == right, 即 1 elem -> do nothing
    if(left < right)
    {
        int pivotPos = partition(a, left, right);
        
        quickSort(a, left, pivotPos - 1);
        quickSort(a, pivotPos + 1, right);
    }
}

int partition(int a[], int left, int right)
{   
    // (1) 记录 pivot: 任选, 如取 left 元素 => 左元素无效
    int pivot = a[left];
    
    // (2) 循环出口: left == right 
    while(left < right)
    {
        // 双指针 left / right
        // 1) 从右向左 比 pivot: 右元素 大, 则 右指针 左移; else, 右元素 移到 左指针处 => 右元素 无效 
        while(left < right && a[right] >= pivot )
            right--;
        a[left] = a[right]; // Note:    左元素无效 
        
        // 2) 从左向右 比 pivot:  
        while(left < right && a[left] < pivot )
            left++;
        a[right] = a[left]; // Note:    右元素无效 
    }   

    // (3) pivot 放 最终 sorted pos
    a[left] = pivot; // Note:   left == right 
    
    // (4) return pivotPos
    return left;
}

// 2 1 3 -> left = 0, right = 2
// pivot = 2 
// while 1 1 3 -> 1

空间效率

    `递归 => 用 递归工作栈: 栈 容量 与 递归最大深度 一致:`

    最好情况 ceil(log_2(n + 1) )
    最坏情况: n - 1 次 递归 => 栈 深度 O(n)
    平均: 栈深度 O(log_2 n)

    `最坏/平均 O(n) / O(log_2 n)`

时间效率

    与 划分 是否对称(划分算法) 有关
    最坏: two parts 分别 n - 1 / 0 个 elem
        -> 这种 最大程度的不对称 发生在 每层递归上
        -> O(n^2)

    改进: 
    (1) sub_sequence 较小时, no longer 递归调 快排, 
        而是用 direct insert sort

    (2) 尽量选 1 个 可将 sequence 中分 的 pivot

    eg: 取 head/tail/mid elem -> 再取 3 者 的 middle 

稳定性: 不稳定

    划分 中, 若 right range 有 2 key 相等, 且 < pivot
    => 交换到 left range 后, 2 key 相对位置 会变

        seq = {3, `2`, 2} -> 1趟 快排后 -> {2, `2`, 3}                      

3 insert sort

每次 将 待排 record 按其 key 大小 insert 到 preSortedSubsequence -> loop

引出 3 insert 算法

direct / half / shell insert

3.1 直接插入: 边比较 边 移动元素

(1) 某时刻, 前 i = 1,2,... 个 已 insert / sorted: sorted arr[0 .. i - 1] / arr[i] / unsorted arr[i + 1 .. ]

(2) 插 arr[i] 到 sorted arr[0 .. i - 1]

void directInsert(int arr[], int n)
{
    for(int i = 1; i < n; i++) // (1) n-1 趟
    {
        if(arr[i - 1] > arr[i]  ) // (2) 逆序才需要插入
        {
            int targetToBeInsert = arr[i];
            
            int walk;
            
            // (3) 每1趟, 从前一 pos 开始, 逐个与 targetToBeInsert 比较, 逆序则 后移1位
            for(walk = i - 1; walk >=0 && arr[walk] > targetToBeInsert; --walk )
                arr[walk + 1] = arr[walk]; 
            
            // (4) insert 到 targetPos
            arr[walk + 1] = targetToBeInsert;
        }
    }

3.2 折半插入: 分离 比较 和 移动

(1) 先 折半 find insertPos

(2) 再 统一移动 insertPos + 之后 elem

void halfSort(int arr[], int n)
{
    for(int i = 1; i < n; i++)
    {
        int targetToBeInsert = arr[i - 1];
        int left = 0;
        int right = i - 1;
        int walk = 0;

        // exit: right = left + 1
        while(left <= right)
        {
            int mid = left + (right - left) / 2;
             
            if(arr[mid] > targetToBeInsert)
                right = mid - 1;
            else // <= 
                left = mid + 1;
        }

        for(walk = i - 1; walk > right; walk--)
            arr[walk + 1] = arr[walk];

        arr[right + 1] = targetToBeInsert; 
    }
}