[数据结构与算法]关于排序算法

排序算法

稳定性：在原始的数据序列中，相同元素经过排序后前后顺序并没有改变就是稳定的，否则不稳定

冒泡排序

将相邻元素比较大小两两交换，将最大值的元素往下交换，每一轮遍历都能够将当前乱序的数字中的最大元素排到最后

// 冒泡排序
void BubbleSort(int arr[], int size) {
    // 趟数 O(n)
    // size - 1这里的-1是因为到了最后一趟只剩下一个元素未处理 是已经有序了的 无需处理
    for (int i = 0; i < size - 1; i++) {
        // 标识一趟里面有没有交换 如果没有交换说明元素已经有序 可以直接退出
        bool flag = false;
        // 一趟的处理 O(n)
        // 这里-1是因为是通过j和j+1所在的元素比较的 已经比较过了 防止溢出
        for (int j = 0; j < size - 1 - i; j++) {
            if (arr[j] > arr[j+1]) {
                swap(arr[j],arr[j+1]);
                flag = true;
            }
        }
        if (!flag) return;
    }
}

冒泡排序是所有排序算法里效率最低的，因为交换次数太多，每比较一次都可能需要交换

因为两两元素进行比较，如果相同不会交换位置，所以是稳定的

选择排序

每次在剩下的元素中选择最小的元素，和当前的元素进行交换

// 选择排序
void ChoiceSort(int arr[], int size) {
    // O(n)
    // -1是因为最后一个元素不需要处理
    for (int i = 0; i < size - 1; i++) {
        int minIndex = i;

        // O(n)
        for (int j = i + 1; j < size; j++) {
            if (arr[minIndex] > arr[j]) minIndex = j;
        }

        if (minIndex != i) swap(arr[minIndex],arr[i]);
    }
}

交换次数减少了，但是比较的次数依然很多

是不稳定的，比如5 5 3，在第一次遍历的时候会将第一个5和3交换，导致第一个5换到第二个5的后面

插入排序

将前面的元素看成是有序的数组，在数组中寻找一个合适的位置将当前元素插入

// 插入排序
void InsertSort(int arr[], int size) {
    for (int i = 1; i < size; i++) {
        // 需要保存这个要插入有序数组中的值 因为后面可能会被覆盖
        int val = arr[i];
        // 寻找数组要插入的元素的位置
        // 最终arr[j]就是当前数组中第一个小于要插入的元素的值
        int j = i - 1;
        for (; j >= 0; j--) {
            if (arr[j] <= val) break; // 已经是有序的了
            // 如果要插入的元素比arr[j]的小 需要将数组中的元素后移 给要插入的元素腾出位置
            arr[j+1] = arr[j];
        }
        arr[j+1] = val;
    }
}

如果数据趋于有序，那么插入排序是所有排序算法中效率最高的

因为交换和比较的次数比较少

希尔排序

对插入排序的优化

对数据进行分组插入排序，整体的数据会越来越有序，最后整体进行插入排序

// 希尔排序
void ShellSort(int arr[], int size) {
    for (int gap = size / 2; gap > 0; gap /= 2) {
        // O(n)
        for (int i = gap; i < size; i++) {
            int val = arr[i];
            int j = i - gap;
            // O(n)
            for (; j >= 0; j -= gap) {
                if (arr[j] <= val) break;
                arr[j+gap] = arr[j];
            }
            arr[j+gap] = val;
        }
    }
}

是不稳定的，相同的元素可能位于不同的组

一般中等数据量的排序选择希尔排序

数据量较大选择高级的排序算法

快速排序

选取一个基准数，将小于基准数的元素都调整到基准数的左边，将大于基准数的调准到基准数的右边，然后将基准数左边和右边的序列继续这样的操作，直到整个序列变成有序

• 循环条件L<R
  • 选取基准数val = arr[L]
  • 从R开始往前找第一个小于val的数字存放到L的地方，L++
  • 从L开始往后找第一个大于val的数字存放到R的地方，R++
  • 重复上面过程

// 快速排序
// 快排实现
// O(n)
int Partation(int arr[], int l, int r) {
    int val = arr[l];
    while (l < r) {
        // 从R开始往前找第一个<val的数字存放到L L++
        while (l < r && arr[r] > val) r--;
        if (l < r) {
            swap(arr[l],arr[r]);
            l++;
        }

        // 从L开始往后找找第一个大于val的数字存放到R R--
        while (l < r && arr[l] < val) l++;
        if (l < r) {
            swap(arr[l],arr[r]);
            r--;
        }
    }
}

// 快排的递归接口
void QuickSort(int arr[], int begin, int end) {
    // 递归结束条件
    if (begin >= end) return;

    // 在[begin,end]的元素做快排处理
    int pos = Partation(arr,begin,end);

    // 对基准数的左右边在进行快排
    // O(logn)
    QuickSort(arr,begin,pos-1);
    QuickSort(arr,pos+1,end);
}

void QuickSort(int arr[], int size) {
    QuickSort(arr,0,size-1);
}

是不稳定的，在排序过程中可能由于后面的相同数字比基准数小导致移动到相同数字的前面，也可能因为前面相同的数字比基准数大导致移动到相同数字的后面，比如5 7 7 3 2

优化

• 随着快排算法的执行，数据越来越有序，可以在一定的范围内采用插入排序代替快速排序

if (end - begin <= 50) {
        InsertSort(arr,begin,end);
        return;
}

• 选择合适的基准数，防止快排退化为冒泡排序：三数取中法

int mid = (L+R) / 2;
// arr[l] arr[mid] arr[r]取中间的数字作为基准数

归并排序

采用分治思想，先进行序列划分，再进行元素的有序合并

// 归并排序
// 合并过程 O(n)
void Merge(int arr[], int l, int m, int r) {
    int *p = new int[r-l+1];
    int idx = 0;
    int i = l;
    int j = m + 1;
    while (i <= m && j <= r) {
        if (arr[i] <= arr[j]) p[idx++] = arr[i++];
        else p[idx++] = arr[j++];
    }

    while (i <= m) {
        p[idx++] = arr[i++];
    }
    while (j <= r) {
        p[idx++] = arr[j++];
    }

    // 将合并好的有序结果拷贝到原始数组
    for (i = l, j = 0; i <= r; i++, j++) {
        arr[i] = p[j];
    }
}

// 归并排序接口 O(logn)
void MergeSort(int arr[], int begin, int end) {
    // 递归结束条件
    if (begin >= end) return;

    // 寻找中间位置进行划分
    int mid = (begin + end) / 2;

    // 递归
    MergeSort(arr,begin,mid);
    MergeSort(arr,mid+1,end);

    // 合并 [begin,mid] [mid+1,end]
    Merge(arr,begin,mid,end);

}

void MergeSort(int arr[], int size) {
    MergeSort(arr,0,size-1);
}

堆排序

二叉堆

是一颗完全二叉树，分为大根堆和小根堆

arr[i] <= arr[2 * i+1] && arr[i] <= arr[2 * i+2]，就是小根堆

arr[i] >= arr[2 * i+1] && arr[i] >= arr[2 * i+2]，就是大根堆

大根堆入堆

大根堆出堆

将末尾元素覆盖堆顶元素，然后与最大的孩子比较进行下沉操作

// 基于堆的优先级队列实现
class PriorityQueue {
public:
    using Comp = std::function<bool(int,int)>;
    PriorityQueue(int cap = 20, Comp comp = std::greater<int>())
        : size_(0)
        , cap_(cap)
        , comp_(comp)
    {
        que_ = new int[cap_];
    }

    PriorityQueue(Comp comp = std::greater<int>())
            : size_(0)
            , cap_(20)
            , comp_(comp)
    {
        que_ = new int[cap_];
    }

    ~PriorityQueue() {
        delete[] que_;
        que_ = nullptr;
    }

public:
    // 入堆
    void push(int val) {
        // 判断扩容
        if (size_ == cap_) {
            int* p = new int[2 * cap_];
            memcpy(p,que_,cap_ * sizeof(int));
            delete[] que_;
            que_ = p;
            cap_ *= 2;
        }

        if (size_ == 0) {
            que_[size_] = val;
        } else {
            // 添加到数组末尾后进行上浮调整
            siftUp(size_,val);
        }
        size_++;
    }

    // 出堆
    void pop() {
        if (size_ == 0) throw "container is empty!";

        size_--;
        if (size_ > 0) siftDown(0,que_[size_]);
    }

    bool empty() const {return size_ == 0;}

    int top() const {
        if (size_ == 0)
            throw "container is empty!";
        return que_[0];
    }

    int size() const {return size_;}
private:
    // 入堆上浮调整 O(logn) O(1)
    void siftUp(int i, int val) {
        while (i > 0) {
            int father = (i - 1) / 2;
            if (comp_(val,que_[father])) {
                que_[i] = que_[father];
                i = father;
            } else break;
        }
        que_[i] = val;
    }

    // 出堆下沉操作
    void siftDown(int i, int val) {
        // i下沉不能超过最后一个有孩子的节点
        while (i < size_ / 2) {
            int child = 2 * i + 1; // 第i个节点的左孩子
            if (child + 1 < size_ && comp_(que_[child+1],que_[child])) {
                child = child + 1;
            }

            if (comp_(que_[child],val)) {
                que_[i] = que_[child];
                i = child;
            } else {
                break;
            }
        }
        que_[i] = val;
    }

private:
    int* que_; // 指向动态扩容的数组
    int size_; // 数组元素个数
    int cap_; // 数组容量
    Comp comp_; // 比较器对象
};

堆排序

// 堆排序
// 下沉操作
void siftDown(int arr[], int i, int size) {
    int val = arr[i];
    while (i < size / 2) {
        int child = 2 * i + 1;
        if (child + 1 < size && arr[child+1] > arr[child]) child = child + 1;

        if (arr[child] > val) {
            arr[i] = arr[child];
            i = child;
        } else break;
    }
    arr[i] = val;
}

void HeapSort(int arr[], int size) {
    int n = size - 1;
    // 从第一个非叶子节点
    for (int i = (n - 1) / 2; i >= 0; i--) {
        siftDown(arr,i,size);
    }

    // 将堆顶元素与末尾元素交换 从堆顶开始下沉操作
    for (int i = n; i > 0; i--) {
        swap(arr[i], arr[0]);
        siftDown(arr,0,i);
    }
}

基数排序（桶排序）

先对个位进行排序，再对十位进行排序，依次类推

// 堆排序
void RadixSort(int arr[], int size) {
    int maxData = arr[0];
    for (int i = 1; i < size; i++) {
        if (maxData < abs(arr[i])) maxData = abs(arr[i]);
    }

    int len = to_string(maxData).size();

    vector<vector<int>> vecs;
    int mod = 10;
    int dev = 1;

    for (int i = 0; i < len; mod *= 10, dev *= 10, i++) {
        vecs.resize(20);
        for (int j = 0; j < size; j++) { //O(n)
            int index = arr[j] % mod / dev + 10;
            vecs[index].push_back(arr[j]);
        }
        int idx = 0;
        for (auto vec : vecs) { // O(20)
            for (int v : vec) { // O(n)
                arr[idx++] = v;
            }
        }

        vecs.clear();
    }
}