冒泡排序

較大數(shù)字往后浮動(dòng)
循環(huán) N-1 次完成排序
時(shí)間復(fù)雜度 O(n^2)

void bubble_sort(int a[], int n) {
    for (int i = 0; i < n - 1; ++i) {
        for (int j = 0; j < n - i - 1; ++j) {
            if (a[j] > a[j + 1])
                swap(a[j], a[j + 1]);
        }
    }
}

快速排序

隨機(jī)選出一個(gè)中心數(shù)
比這個(gè)數(shù)小的放到左邊颓鲜，大的放右邊
然后對(duì)左邊疾渴、右邊繼續(xù)使用相同操作
時(shí)間復(fù)雜度 O(nlogn)

void qsort(int nums[], int l, int r) {
    if (l < r) {
        int m = l;
        for (int i = l + 1; i <= r; i++) {
            int num = nums[i];
            if (num < nums[l]) {
                swap(nums[++m], nums[i]);
            }
        }
        swap(nums[m], nums[l]);
        
        qsort(nums, l, m - 1);
        qsort(nums, m + 1, r);
    }
}

插入排序

從后往前找一個(gè)合適的位置插入當(dāng)代的數(shù)字
時(shí)間復(fù)雜度O(n^2)

void insert_sort(int a[], int n) {
    // i 控制要插入的元素
    for (int i = 1; i < n; ++i) {
        int current = a[i];
        int j = i;
        while (j - 1 >= 0 && a[j - 1] > current) {
            a[j] = a[j - 1];
            j--;
        }
        a[j] = current;
    }
}

希爾排序

插入排序增強(qiáng)版
先以一定的 gap 進(jìn)行排序魄梯，降低插入排序的復(fù)雜度
時(shí)間復(fù)雜度 O（nlogn）～O（n2）

void shell_sort(int arr[], int len) {
    int gap, i, j;
    int temp;
    for (gap = len >> 1; gap > 0; gap = gap >>= 1)
        for (i = gap; i < len; i++) {
            temp = arr[i];
            for (j = i - gap; j >= 0 && arr[j] > temp; j -= gap)
                arr[j + gap] = arr[j];
            arr[j + gap] = temp;
        }
}

選擇排序

每次都選取最小值放到前面
時(shí)間復(fù)雜度O(n^2)

void select_sort(int a[], int n) {
    for (int i = 0; i < n; ++i) {
        // 找出最小值
        int pos = i;
        for (int j = i + 1; j < n; ++j) {
            if (a[j] < a[pos]) {
                pos = j;
            }
        }
        swap(a[i], a[pos]);
    }
}

歸并排序

對(duì)已經(jīng)排好序的兩個(gè)部分進(jìn)行歸并操作
排序數(shù)組時(shí)采用遞歸的方法
時(shí)間復(fù)雜度O(nlogn)

void merge(int a[], int l, int mid, int r) {
    int *temp = new int[r - l + 1];
    int p = 0;
    int i = l;
    int j = mid + 1;

    while (i <= mid && j <= r) {
        if (a[i] < a[j])
            temp[p++] = a[i++];
        else 
            temp[p++] = a[j++];
    }

    while (i <= mid)
        temp[p++] = a[i++];

    while (j <= r)
        temp[p++] = a[j++];

    for (int i = 0; i < r - l + 1; ++i)
        a[l + i] = temp[i];

    delete[] temp;
}

void merge_sort(int a[], int l, int r) {
    if (l < r) {
        int mid = l  + (r - l) / 2;
        merge_sort(a, l, mid);
        merge_sort(a, mid + 1, r);
        merge(a, l, mid, r);
    }    
}

堆排序

最大堆實(shí)現(xiàn)從小到大排序
每次從堆頂選出最大元素放到后面
時(shí)間復(fù)雜度 O(nlogn)

void down_heap(int a[], int i, int n) {
    int l = 2 * i + 1;
    int r = 2 * i + 2;

    // 找出最大元素奶浦，和最大的交換
    int largest = i;
    if (l <= n - 1 && a[l] > a[i]) 
        largest = l;
    if (r <= n - 1 && a[r] > a[largest])
        largest = r;

    if (largest != i) {
        swap(a[i], a[largest]);
        // 繼續(xù)下沉
        down_heap(a, largest, n);
    }
}

void build_heap(int a[], int n) {
    // 從最后一個(gè)父節(jié)點(diǎn)開始下沉
    for (int i = (n - 1) / 2; i >= 0; i--) {
        down_heap(a, i, n);
    }
}

void heap_sort(int a[], int n) {
    build_heap(a, n);
    for (int i = n - 1; i > 0; i--) {
        // 取出堆頂放在數(shù)組后
        swap(a[0], a[i]);
        // 新元素下沉
        down_heap(a, 0, --n);
    }
}

計(jì)數(shù)排序

不支持負(fù)數(shù)
時(shí)間復(fù)雜度O(n)
但是非常浪費(fèi)空間

void count_sort(int a[], int n, int MAX) {
    // 計(jì)數(shù)
    int *count = new int[MAX + 1];
    for (int i = 0; i <= MAX; ++i)
        count[i] = 0;
    for (int i = 0; i < n; ++i)
        ++count[a[i]];
    
    // 累計(jì)小于等于i的數(shù)量 
    for (int i = 1; i <= MAX; ++i)
        count[i] += count[i - 1];
    
    int *sort = new int[n];
    for (int i = 0; i < n; ++i) {
        // 可能有重復(fù)的數(shù)字，所以要——
        --count[a[i]];
        sort[count[a[i]]] = a[i];
    }

    for (int i = 0; i < n; ++i)
        a[i] = sort[i];
    
    delete[] count;
    delete[] sort;
}