查找-排序算法

DS中的查找与排序算法

查找

二分查找

int binarySearch(int l[], int n, int key)
{
    int low = 0, high = n - 1, mid;
    while (low <= high)
    {
        mid = (low + high) / 2;
        if (l[mid] == key)
            return mid;
        else if (l[mid] > key)
            high = mid - 1;
        else
            low = mid + 1;
    }
    return -1;
}

排序

插入排序

1. 时间复杂度
   1. 最好: $O(n)$
   2. 平均: $O(n^2)$
   3. 最差: $O(n^2)$
2. 空间复杂度: $O(1)$
3. 稳定性: 是

void insertSort(int A[], int n)
{
    for (int i = 2; i < n; i++)
    {
        if (A[i] < A[i - 1])
        {
            A[0] = A[i];
            int j;
            for (j = i - 1; A[0] < A[j]; j++)
                A[j + 1] = A[j];
            A[j + 1] = A[0];
        }
    }
}

冒泡排序

1. 时间复杂度
   1. 最好: $O(n)$
   2. 平均: $O(n^2)$
   3. 最差: $O(n^2)$
2. 空间复杂度: $O(1)$
3. 稳定性: 是

void bubbleSort(int A[], int n)
{
    for (int i = 0; i < n - 1; i++)
    {
        bool flag = false;
        for (int j = n - 1; j > i; j--)
            if (A[j - 1] > A[j])
            {
                int t = A[j - 1];
                A[j - 1] = A[j];
                A[j] = t;
                flag = true;
            }
        if (flag == false)
            return;
    }
}

选择排序

1. 时间复杂度
   1. 最好: $O(n^2)$
   2. 平均: $O(n^2)$
   3. 最差: $O(n^2)$
2. 空间复杂度: $O(1)$
3. 稳定性: 否

void selectSort(int A[], int n)
{
    for (int i = 0; i < n - 1; i++)
    {
        int min = i;
        for (int j = i + 1; j < n; j++)
            if (A[j] < A[min])
                min = j;
        if (min != i)
        {
            int t = A[i];
            A[i] = A[min];
            A[min] = t;
        }
    }
}

快速排序

1. 时间复杂度
   1. 最好: $O(n\log_2n)$
   2. 平均: $O(n\log_2n)$
   3. 最差: $O(n^2)$
2. 空间复杂度: $O(\log_2n)$
3. 稳定性: 否

int partition(int A[], int low, int high)
{
    int pivot = A[low];
    while (low < high)
    {
        while (low < high && A[high] >= pivot)
            high--;
        A[low] = A[high];
        while (low < high && A[low <= pivot])
            low++;
        A[high] = A[low];
    }
    A[low] = pivot;
    return low;
}

void quickSort(int A[], int low, int high)
{
    if (low < high)
    {
        int pivotpos = partition(A, low, high);
        quickSort(A, low, pivotpos - 1);
        quickSort(A, pivotpos + 1, high);
    }
}

堆排序

1. 时间复杂度
   1. 最好: $O(n\log_2n)$
   2. 平均: $O(n\log_2n)$
   3. 最差: $O(n\log_2n)$
2. 空间复杂度: $O(1)$
3. 稳定性: 否

void adjustDown(int A[], int k, int n)
{
    A[0] = A[k];
    for (int i = 2 * k; i <= n; i *= 2)
    {
        if (i < n && A[i] < A[i + 1])
            i++;
        if (A[0] >= A[i])
            break;
        else
        {
            A[k] = A[i];
            k = i;
        }
    }
    A[k] = A[0];
}

void adjustUp(int A[], int k)
{
    A[0] = A[k];
    int i = k / 2;
    while (i > 0 && A[i] > A[0])
    {
        A[k] = A[i];
        k = i;
        i = k / 2;
    }
    A[k] = A[0];
}

void buildMaxHeap(int A[], int n)
{
    for (int i = n / 2; i > 0; i--)
    {
        adjustDown(A, i, n);
    }
}

void heapSort(int A[], int n)
{
    buildMaxHeap(A, n);
    for (int i = n; i > 1; i--)
    {
        int t = A[i];
        A[i] = A[1];
        A[1] = t;
        adjustDown(A, 1, i - 1);
    }
}

归并排序

1. 时间复杂度
   1. 最好: $O(n\log_2n)$
   2. 平均: $O(n\log_2n)$
   3. 最差: $O(n\log_2n)$
2. 空间复杂度: $O(n)$
3. 稳定性: 是

void merge(int A[], int low, int mid, int high)
{
    int B[high + 1];
    for (int k = low; k <= high; k++)
        B[k] = A[k];
    int i, j, k;
    for (i = low, j = mid + 1, k = i; i <= mid && j <= high; k++)
    {
        if (B[i] <= B[j])
            A[k] = B[i++];
        else
            A[k] = B[j++];
    }
    while (i <= mid)
        A[k++] = B[i++];
    while (j <= high)
        A[k++] = B[j++];
}

void mergeSort(int A[], int low, int high)
{
    if (low < high)
    {
        int mid = (low + high) / 2;
        mergeSort(A, low, mid);
        mergeSort(A, mid + 1, high);
        merge(A, low, mid, high);
    }
}