排序

agile Posted on Mar 19 2024

面试 leetcode 排序算法

```C++
//
// Created by agile on 2024/3/19.
//
#include "iostream"
#include "functional"

#ifndef LEETCODETEST_SORTS_H
#define LEETCODETEST_SORTS_H

class Sorts {
private:
    Sorts() = default;

public:

Sorts(const Sorts &) = delete;

Sorts &operator=(const Sorts &) = delete;

static Sorts &GetInstance() {
        static Sorts sorts;
        return sorts;
    }

public:
    template<typename T>
    void BubbleSort(T *array, size_t len, std::function<int(const T &, const T &)> compare);

template<typename T>
    void SelectionSort(T *array, size_t len, std::function<int(const T &, const T &)> compare);

template<typename T>
    void InsertionSort(T *array, size_t len, std::function<int(const T &, const T &)> compare);

template<typename T>
    void BinaryInsertSort(T *array, size_t len, std::function<int(const T &, const T &)> compare);

template<typename T>
    void ShellSort(T *array, size_t len, std::function<int(const T &, const T &)> compare);

template<typename T>
    void QuickSort(T *array, size_t len, std::function<int(const T &, const T &)> compare);

template<typename T>
    void MergeSort(T *array, size_t len, std::function<int(const T &, const T &)> compare);

template<typename T>
    void HeapSort(T *array, size_t len, std::function<int(const T &, const T &)> compare);
};

template<typename T>
void swap(T *array, int l, int r) {
    auto t = array[r];
    array[r] = array[l];
    array[l] = t;
}

//冒泡排序
template<typename T>
void Sorts::BubbleSort(T *array, size_t len, std::function<int(const T &, const T &)> compare) {
    for (int i = 0; i < len; ++i) {
        auto flag = false;
        for (int j = 1; j < len - i; ++j) {
            if (compare(array[j - 1], array[j]) > 0) {
                swap(array, j, j - 1);
                flag = true;
            }
        }
        if (!flag) {
            break;
        }
    }
}

//选择排序
template<class T>
void Sorts::SelectionSort(T *array, size_t len, std::function<int(const T &, const T &)> compare) {
    for (int i = 0; i < len; ++i) {
        for (int j = i + 1; j < len; ++j) {
            if (compare(array[i], array[j]) > 0) {
                swap(array, i, j);
            }
        }
    }
}

//插入排序
template<typename T>
void Sorts::InsertionSort(T *array, size_t len, std::function<int(const T &, const T &)> compare) {
    for (int i = 1; i < len; ++i) {
        auto t = array[i];
        auto j = i - 1;
        for (; j >= 0; --j) {
            if (compare(array[j], t) > 0) {
                array[j + 1] = array[j];
            } else {
                break;
            }
        }
        array[j + 1] = t;
    }
}

//二分插入排序
template<typename T>
void Sorts::BinaryInsertSort(T *array, size_t len, std::function<int(const T &, const T &)> compare) {
    for (int i = 1; i < len; ++i) {
        auto temp = array[i];
        auto left = 0;
        auto right = i - 1;
        //找到temp具体index
        while (left <= right) {
            int mid = (left + right) / 2;
            int flag = compare(array[mid], temp);
            if (flag == 0) {
                left = mid + 1;
                break;
            } else if (flag > 0) {
                right = mid - 1;
            } else {
                //不需要包括mid，已经判断过了
                left = mid + 1;
            }
        }
        auto j = i - 1;
        for (; j >= left; --j) {
            array[j + 1] = array[j];
        }
        array[j + 1] = temp;
    }
}

//希尔排序
template<typename T>
void Sorts::ShellSort(T *array, size_t len, std::function<int(const T &, const T &)> compare) {
    for (int gap = (int) len >> 1; gap > 0; gap = gap >> 1) {
        //每一组有多少个成员
        int item_nums = (int) len / gap;
        //遍历每一组
        for (int gap_index = 0; gap_index < gap; ++gap_index) {
            //开始排序的组员index
            int start = gap_index * item_nums + 1;
            //结束组员的index,不包括这个end
            int end = (gap_index + 1) * (item_nums) + 1;
            //上一组最后index
            int last_end = start - 1;
            end = end > len ? (int) len : end;
            for (int i = start; i < end; ++i) {
                int j = i - 1;
                auto t = array[i];
                for (; j >= last_end; j--) {
                    if (compare(array[j], t) > 0) {
                        array[j + 1] = array[j];
                    } else {
                        break;
                    }
                }
                array[j + 1] = t;
            }
        }
    }
}

template<typename T>
int quick_sort_partition(T *array, std::function<int(const T &, const T &)> compare, int left, int right) {
    int mid_index = (left + right) / 2;
    if ((compare(array[left], array[mid_index]) < 0) ^ (compare(array[left], array[right]) < 0)) {
        mid_index = left;
    } else if ((compare(array[right], array[mid_index]) < 0) ^ (compare(array[right], array[left]) < 0)) {
        mid_index = right;
    }
    swap(array, mid_index, left);
    //哨兵值
    auto data = array[left];
    //记录哨兵初始位置
    mid_index = left;
    while (left < right) {
        //找到右边数组第一个小于哨兵的index
        while (left < right && compare(array[right], data) >= 0) {
            right--;
        }
        //找到左侧数组第一个大于哨兵的index
        while (left < right && compare(array[left], data) <= 0) {
            left++;
        }
        //交换left,right顺序
        swap(array, left, right);
    }
    //将哨兵放到中心位置
    swap(array, mid_index, left);
    //left是属于中间index
    return left;
}

//哨兵分组
template<typename T>
void quick_sort_guard(T *array, std::function<int(const T &, const T &)> compare, int left, int right) {
    if (left >= right) {
        return;
    }
    auto mid = quick_sort_partition(array, compare, left, right);
    quick_sort_guard(array, compare, left, mid - 1);
    quick_sort_guard(array, compare, mid + 1, right);
}

//快速排序
template<typename T>
void Sorts::QuickSort(T *array, size_t len, std::function<int(const T &, const T &)> compare) {
    quick_sort_guard(array, compare, 0, len - 1);
}

template<typename T>
void
merge_sort_merge(T *array, std::function<int(const T &, const T &)> compare,
                 int left, int right, int mid) {
    int count = right - left + 1;
    T *tempArray = (T *) malloc(sizeof(T) * count);
    memcpy(tempArray, array + left, count * sizeof(T));

int leftStart = 0;
    int leftEnd = mid - left;
    int rightStart = leftEnd + 1;
    int rightEnd = right - left;
    int k = leftStart;
    int j = rightStart;
    for (int i = left; i <= right; ++i) {
        if (k > leftEnd) {
            array[i] = tempArray[j++];
        } else if (j > rightEnd) {
            array[i] = tempArray[k++];
        } else {
            if (compare(tempArray[k], tempArray[j]) > 0) {
                array[i] = tempArray[j++];
            } else {
                array[i] = tempArray[k++];
            }
        }
    }
    free(tempArray);
    tempArray = nullptr;
}

template<typename T>
void
merge_sort_recursive_partition(T *array, std::function<int(const T &, const T &)> compare,
                               int left, int right) {
    if (left >= right) {
        return;
    }
    int mid = (left + right) / 2;
    merge_sort_recursive_partition(array, compare, left, mid);
    merge_sort_recursive_partition(array, compare, mid + 1, right);
    merge_sort_merge(array, compare, left, right, mid);
}

//合并排序
template<typename T>
void Sorts::MergeSort(T *array, size_t len, std::function<int(const T &, const T &)> compare) {
    merge_sort_recursive_partition(array, compare, 0, len - 1);
}

int hash_sort_parent(int i) {
    return (i - 1) >> 1;
}

int hash_sort_left(int pi) {
    return (pi << 1) + 1;
}

int hash_sort_right(int pi) {
    return (pi << 1) + 2;
}

template<typename T>
void heap_sort_shift_down(T *array, size_t len, std::function<int(const T &, const T &)> compare, int parentIndex) {
    while (true) {
        auto maxIndex = parentIndex;
        auto leftIndex = hash_sort_left(parentIndex);
        auto rightIndex = hash_sort_right(parentIndex);
        if (leftIndex < len && compare(array[leftIndex], array[maxIndex]) > 0) {
            maxIndex = leftIndex;
        }
        if (rightIndex < len && compare(array[rightIndex], array[maxIndex]) > 0) {
            maxIndex = rightIndex;
        }
        if (maxIndex == parentIndex) {
            break;
        }
        swap(array, parentIndex, maxIndex);
        heap_sort_shift_down(array, len, compare, maxIndex);
    }
}

template<typename T>
void Sorts::HeapSort(T *array, size_t len, std::function<int(const T &, const T &)> compare) {
    int p = hash_sort_parent((int) len - 1); //len-1序列对应的父节点id
    //创建大顶堆
    for (int i = p; i >= 0; --i) {
        heap_sort_shift_down(array, len, compare, i);
    }
    //交换最后一个和第一个
    //再重置顺序
    for (int i = (int) len - 1; i >= 0; --i) {
        swap(array, 0, i);
        heap_sort_shift_down(array, i, compare, 0);
    }
}

#endif //LEETCODETEST_SORTS_H

```