各种排序方法(C/C++语言版本)

sort.cpp

#include <iostream>
#include <math.h>

using namespace std;
//-------------------------------------------------------------------------------------
// 直接插入排序
void insertionSort(int arr[], int n, int g)
{
    for (int i = g; i < n; i++)
    {
        int cur = arr[i], j = i - g;
        for (; j >= 0 && arr[j] > cur; j -= g)
            arr[j + g] = arr[j];
        arr[j + g] = cur;
    }
}
//-------------------------------------------------------------------------------------
// 冒泡排序
void bubbleSort(int arr[], int n)
{
    bool flag = true;
    for (int i = 0; flag; i++)
    {
        flag = false;
        for (int j = n - 1; j >= i + 1; j--)
        {
            swap(arr[j], arr[j - 1]);
            flag = true;
        }
    }
}
//-------------------------------------------------------------------------------------
// 选择排序
void selectionSort(int arr[], int n)
{
    for (int i = 0; i < n; i++)
    {
        int min_i = i;
        for (int j = i + 1; j < n; j++)
        {
            if (arr[j] < arr[min_i])
            {
                min_i = j;
            }
        }
        swap(arr[i], arr[min_i]);
    }
}
//-------------------------------------------------------------------------------------
// 希尔排序
void shellSort(int arr[], int n)
{
    int G_len = (int)ceil(log((n + 0.5) / 1.5) / log(3));
    int G[G_len];
    for (int i = 0; i < G_len; i++)
        G[i] = (int)(pow(3, i) * 1.5 - 0.5);
    for (int i = G_len - 1; i >= 0; i--)
    {
        insertionSort(arr, n, G[i]);
    }
}
//-------------------------------------------------------------------------------------
// 数组归并
void merge(int arr[], int l, int m, int r)
{
    int temp[r - l + 1], k = 0, i = l, j = m + 1;
    while (i <= m && j <= r)
    {
        if (arr[i] <= arr[j])
            temp[k++] = arr[i++];
        else
            temp[k++] = arr[j++];
    }
    while (i <= m)
        temp[k++] = arr[i++];
    while (j <= r)
        temp[k++] = arr[j++];
    for (int ii = 0; ii < k; ii++)
    {
        arr[l + ii] = temp[ii];
    }
}
// 归并排序
void mergeSort(int arr[], int l, int r)
{
    if (l < r)
    {
        int m = (l + r) / 2;
        mergeSort(arr, l, m);
        mergeSort(arr, m + 1, r);
        merge(arr, l, m, r);
    }
}
//-------------------------------------------------------------------------------------
// 寻找切割点
int partition(int arr[], int l, int r)
{
    int p = arr[r];
    int i = l - 1;
    for (int j = l; j < r; j++)
    {
        if (arr[j] <= p)
        {
            i++;
            swap(arr[i], arr[j]);
        }
    }
    swap(arr[i + 1], arr[r]);
    return i + 1;
}
// 快速排序
void quickSort(int arr[], int l, int r)
{
    if (l < r)
    {
        int v = partition(arr, l, r);
        quickSort(arr, l, v - 1);
        quickSort(arr, v + 1, r);
    }
}
//-------------------------------------------------------------------------------------
// 计数排序/桶排序
void countingSort(int arr[], int n, int k)
{
    int cnt[k + 1];
    for (int i = 0; i <= k; i++)
        cnt[i] = 0;
    for (int i = 0; i < n; i++)
        cnt[arr[i]]++;
    for (int i = 1; i <= k; i++)
        cnt[i] += cnt[i - 1];
    int temp[n];
    for (int i = 0; i < n; i++)
    {
        temp[cnt[arr[i]] - 1] = arr[i];
        cnt[arr[i]]--;
    }
    for (int i = 0; i < n; i++)
        arr[i] = temp[i];
}