排序

一、选择排序

void selection_sort(int* arr, int L, int R)
{
    for (int i = L; i < R; i++)
    {
        int ind = i;
        for (int j = i + 1; j < R; j++)
            if (arr[j] < arr[ind]) ind = j;
        swap(arr[i], arr[ind]);
    }
}

二、插入排序

//普通的插入排序
void insert_sort(int *arr, int L, int R)
{
    for (int i = L + 1; i < R; i++)
    {
        int j = i;
        while (j > L && arr[j] < arr[j - 1])
        {
            swap(arr[j], arr[j - 1]);
            j--;
        }
    }
}

//优化后的插入排序(无监督的插入排序)
void unguarded_insert_sort(int *arr, int L, int R)
{
    int idx = L;
    for (int i = L + 1; i < R; i++)
        if (arr[i] < arr[idx]) idx = i;
    while (idx > L)
    {
        swap(arr[idx], arr[idx - 1]);
        idx--;
    }
    for (int i = L + 1; i < R; i++)
    {
        int j = i;
        while (arr[j] < arr[j - 1])
        {
            swap(arr[j], arr[j - 1]);
            j--;
        }
    }
}

 三、希尔排序（分组插入排序）

步骤：

　　设计一个【步长】序列；按照步长对序列进行分组，每组采用插入排序；直到执行到步长为1为止。

　　下标间隔为步长的为一组，多组分别执行插入排序，步长不断缩小，直到1。

希尔排序的时间复杂度：

　　不是固定的，而是与步长序列有关系。

　　参考时间复杂度：O(nlogn) ~ O(n^2)

两种增量序列：

　　希尔增量序列，最坏O(n^2)：n / 2 , n / 4 , n / 8 , n / 16 ...

　　Hibbard增量序列，最坏O(n^1.5)：1 , 3 , 7 ,  ... , (2^k) - 1.其中(2^k) - 1小于当前数列中的元素数量

#include <bits/stdc++.h>
using namespace std;
void unguarded_insert_sort(int* arr, int L, int R, int step)
{
    int idx = L;
    for (int i = L + step; i < R; i += step)
        if (arr[i] < arr[idx]) idx = i;
    while (idx > L)
    {
        swap(arr[idx], arr[idx - step]);
        idx -= step;
    }
    for (int i = L + 2 * step; i < R; i += step)
    {
        int j = i;
        while (arr[j] < arr[j - step])
        {
            swap(arr[j], arr[j - step]);
            j -= step;
        }
    }
}
void shell_sort(int* arr, int L, int R)
{
    int k = 2, n = R - L, step;
    do{
        step = n / k == 0 ? 1 : n / k;
        for (int i = L; i < L + step; i++)
        {
            unguarded_insert_sort(arr, i, R, step);
        }
        k *= 2;
    } while (step != 1);
    return;
}
void shell_sort_hibbard(int* arr, int L, int R)
{
    int step = 1, n = (R - L);
    while (step <= n / 2) step = step * 2 + 1;
    do
    {
        step /= 2;
        for (int i = L; i < L + step; i++)
        {
            unguarded_insert_sort(arr, i, R, step);
        }
    } while (step != 1);
    return;
}
int main()
{
    int a[110] = {-10, 9 ,77 ,12, 24 ,-500, 12,12,344,12};
    
    // for (int i = 1; i <= 10; i++) cin >> a[i];
    shell_sort(a, 1, 11);
    for (int i = 1; i <= 10; i++) cout << a[i] << ' ';

    cout << '\n';

    int b[110] = { -10, 9 ,77 ,12, 24 ,-500, 12,12,344,12 };
    // for (int i = 1; i <= 10; i++) cin >> a[i];
    shell_sort_hibbard(b, 1, 11);
    for (int i = 1; i <= 10; i++) cout << b[i] << ' ';

    cout << '\n';

    return 0;
}

对于所有基于比较的排序，最优时间复杂度为O(nlogn).

四、冒泡排序及其优化

冒泡排序

void bubble_sort(int* arr, int L, int R)
{
    for (int i = R - 1; i >= L + 1; i--)
    {
        for (int j = L; j < i; j++)
        {
            if (arr[j] > arr[j + 1])
                swap(arr[j], arr[j + 1]);
        }
    }
    return;
}

优化的冒泡排序

void bettered_bubble_sort(int* arr, int L, int R)
{
    int cnt;
    for (int i = R - 1; i >= L + 1; i--)
    {
        cnt = 0;
        for (int j = L; j < i; j++)
        {
            if (arr[j] <= arr[j + 1]) continue;
            swap(arr[j], arr[j + 1]);
            cnt++;
        }
        if (cnt == 0) break; // 已经有序，不需要再执行冒泡排序
    }
    return;
}

五、快速排序

void quick_sort(int q[],int L,int R)
{
    if(L >= R)
    {
        return;
    }
    int i = L - 1, j = R + 1;
    int x = q[(L + R)>>1];
    while(i < j)
    {
        do
        {
            i++;
        }while(q[i] < x);
        do
        {
            j--;
        }while(q[j] > x);
        if(i < j)
        {
            swap(q[i],q[j]);
        }
    }
    quick_sort(q,L,j);
    quick_sort(q,j + 1,R);
}