花式排序

#include<iostream>
#include<vector>
#include<algorithm>
#include<random>
#include<ctime>
using namespace std;

void bubbleSort(vector<int> &nums){
    // 冒泡排序
    for(int i=0; i<nums.size()-1; ++i)
        for(int j=nums.size()-1; j>i; j--)
            if(nums[j-1] > nums[j])swap(nums[j],nums[j-1]);
}

void bubbleSort1(vector<int> &nums) {
    for(int i=0; i<nums.size()-1; ++i) {
        bool flag = true;
        for(int j=nums.size()-1; j>i; --j)
            if(nums[j-1] > nums[j]) swap(nums[j], nums[j-1]), flag = false;
        if(flag) break;
    }
}

void bubbleSort2(vector<int> &nums) {
    int right = nums.size() - 1;
    for(int i=0; i<nums.size()-1; i++) {
        bool flag = true;
        int tem = right;
        for(int j=0; j<tem; j++)
            if(nums[j] > nums[j+1]) 
                swap(nums[j], nums[j+1]), flag = false, right = j;
        if(flag) break;
    }
}

void bubbleSort3(vector<int> &nums) {
    // 鸡尾酒排序
    for(int i=0; i<nums.size()/2; i++) {
        bool flag = true;
        for(int j=i; j<nums.size()-i-1; j++)
            if(nums[j] > nums[j+1]) 
                swap(nums[j], nums[j+1]), flag = false;
        if(flag) break;
        flag = true;
        for(int j=nums.size()-1; j>i; j--)
            if(nums[j-1] > nums[j])
                swap(nums[j],nums[j-1]), flag = false;
        if(flag) break;
    }
}

void bubbleSort4(vector<int> &nums) {
    int left = 0, right = nums.size()-1;
    // 鸡尾酒排序
    for(int i=0; i<nums.size()/2; i++) {
        bool flag = true;
        int l = left, r = right;
        for(int j=l; j<r; j++)
            if(nums[j] > nums[j+1]) 
                swap(nums[j], nums[j+1]), flag = false, right = j;
        if(flag) break;
        flag = true;
        for(int j=right; j>l; j--)
            if(nums[j-1] > nums[j])
                swap(nums[j],nums[j-1]), flag = false, left = j;
        if(flag) break;
    }
}

void selectSort(vector<int> &nums){
    // 选择排序
    for(int i=0; i<nums.size()-1; ++i){
        int minIndex = i;
        for(int j=i+1; j<nums.size(); ++j)
            if(nums[j] < nums[minIndex])minIndex = j;
        swap(nums[i],nums[minIndex]);
    }
}

void insertSort(vector<int> &nums){
    // 插入排序
    for(int i=1;i<nums.size(); ++i)
        for(int j=i-1; j >=0 && nums[j]>nums[j+1]; --j)
            swap(nums[j], nums[j+1]);
}

void merge(vector<int> &nums, int l, int m, int r){
    vector<int> tem(r-l+1);
    int i = 0, p1 = l, p2 = m+1;

    while(p1 <= m && p2 <= r)
        tem[i++] = nums[p1] >= nums[p2] ? nums[p2++] : nums[p1++];
    while(p1 <= m)
        tem[i++] = nums[p1++];
    while(p2 <= r)
        tem[i++] = nums[p2++];

    while(--i >= 0)
        nums[r--] = tem[i];
}

void mergeSort(vector<int> &nums, int left, int right){
    if(left==right)return ;
    int mid = ((right-left) >> 1) + left;
    mergeSort(nums, left, mid);
    mergeSort(nums, mid+1, right);
    merge(nums, left, mid, right);
}

void mergeSort(vector<int> &nums){
    // 归并排序
    if(nums.size() < 2)return ;
    mergeSort(nums, 0, nums.size()-1);
}

void quickSort(vector<int> &nums, int left, int right){
    if(left >= right)return ;
    // 随机选择基准点， 时间复杂度期望为 N*logN
    int tem = left + rand()%(right-left+1);
    swap(nums[left], nums[tem]);
    int val = nums[left];

    int l = left-1, r = right+1, cur = left+1;
    while(cur < r){
        if(nums[cur] < val)
            swap(nums[++l], nums[cur++]);
        else {
            if(nums[cur] > val)
                swap(nums[--r], nums[cur]);
            else cur++;
        }
    }
    quickSort(nums,left,l);
    quickSort(nums,r,right);
}

void quickSort(vector<int> &nums){
    // 快速排序
    if(nums.size() < 2) return ;
    quickSort(nums, 0, nums.size()-1);
}

void heapInsert(vector<int> &nums, int index){
    while(nums[index] > nums[(index-1)/2]){
        swap(nums[index], nums[(index-1)/2]);
        index = (index-1)/2;
    }
}

void makeHeap(vector<int> &nums){
    // 建立大根堆
    for(int i=0; i < nums.size(); ++i)
        heapInsert(nums,i);
}

void heapChange(vector<int> &nums, int index, int heapSize){
    // 小根堆中，某一个值变大 或者 大根堆中，某一个值变小
    // 目前是大根堆中的调整
    int left = index*2+1;
    while(left < heapSize){
        int largest = (left+1 < heapSize && nums[left+1] > nums[left]) ? left+1 : left;
        largest = nums[index] > nums[largest] ? index : largest;
        if(largest==index) break;
        swap(nums[index], nums[largest]);
        index = largest;
        left = index*2+1;
    }
}

void heapSort(vector<int> &nums){
    // 堆排序
    makeHeap(nums);
    int heapSize = nums.size();
    while(heapSize > 0){
        swap(nums[0], nums[--heapSize]);
        heapChange(nums, 0, heapSize);
    }
}

void bucketSort(vector<int> &nums){
    // 桶排序， 通过计数排序实现
    if(nums.size() < 2)return ;
    // 先寻找最大值和最小值，确定桶的范围，并建立桶
    int minNum = 1e9+1, maxNum = 0, i = 0;
    for(auto it:nums)minNum = min(minNum, it), maxNum = max(maxNum, it);
    vector<int> bucket(maxNum-minNum+1, 0);
    // 把数据放入桶中, 然后再拿出来
    for(auto it:nums)bucket[it-minNum]++;
    for(int j = 0; j<bucket.size(); ++j)
        while(bucket[j]--)nums[i++] = j+minNum;
}

vector<int> generateVector(int range, int length, bool repeat){
    vector<int> arr;
    if(repeat){
        // 随机生成 length 个在 0~range-1 的数，允许重复
        for(int i=0;i<length;++i)
            arr.push_back(rand()%range);
    }else {
        // 随机生成 length 个在 0~length-1 的数，不允许重复
        for(int i=0;i<length;++i)
            arr.push_back(i);
        for(int i=length-1 ;i >= 0;i--){
            int tem = rand()%(i+1);
            swap(arr[i],arr[tem]);
        }
    }

    return arr;
}

int main(){
    srand(int(time(0)));
    // 设置随机生成函数调用的次数  范围  长度
    int times = 50000, range = 50, length = 50;

    for(int i=0; i<times; ++i){
        // 再次随机生成范围和长度
        int ra = rand()%range+5, le = rand()%length+3;
        bool bl = rand()%2 == 1;

        vector<int> nums = generateVector(ra,le,bl);
        vector<int> tem = nums;
        vector<int> right = nums;
        sort(right.begin(), right.end());

        bubbleSort(tem);

        for(int i=0;i<nums.size();++i)
            if(right[i] != tem[i]){
                cout<<"***"<<endl;
                for(auto it:nums)
                    cout<<it<<' ';
                cout<<endl;
                for(auto it:right)
                    cout<<it<<' ';
                cout<<endl;
                for(auto it:tem)
                    cout<<it<<' ';
                cout<<endl;
                break;
            }

        cout<<"Nice!"<<endl;
    }

    return 0;
}