排序算法

#include<iostream>
#include<vector>
#include<stack>
using namespace std;
ostream &operator<<(ostream &out , const vector<int> &a){
    for(int i=0;i<a.size();i++){
        cout<<a[i]<<" ";
    }
    return out;
}
void swap(int& a,int& b){
    a^=b;
    b^=a;
    a^=b;
}
//冒泡排序
//1 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
//2 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
//3 针对所有的元素重复以上的步骤，除了最后一个。
//4 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比 
void bubbleSort(vector<int>arr){
    int len = arr.size();
    for(int i=0;i<len-1;i++){
        for(int j=0;j<len - i -1;j++){
            if(arr[j]>arr[j+1]){
                swap(arr[j],arr[j+1]); 
            }
        }
    }
    cout<<"冒泡排序"<<arr<<endl;
} 
//选择排序
//1 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置
//2 再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
//3 重复第二步，直到所有元素均排序完毕
void selectionSort(vector<int>arr){
    int len = arr.size();
        int maxValueId;
    for(int i=0;i<len-1;i++){
        maxValueId = i;
        for(int j=i+1;j<len;j++){
            if(arr[j]<arr[maxValueId]){
                maxValueId = j;
            }
        }
        if(i!=maxValueId)
        swap(arr[i],arr[maxValueId]);
    }
    cout<<"选择排序"<<arr<<endl; 
}

//插入排序
//1 将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。
//2 从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。） 
void insertionSort(vector<int>arr){
    int len = arr.size();
    for(int i=1;i<len;i++){
        int valueId = i;
        for(int j=i-1;j>=0;j--){
            if(arr[valueId]<arr[j]){
                swap(arr[valueId],arr[j]);
                valueId = j;
            }else{
                break;
            }
        }
    }
    cout<<"插入排序"<<arr<<endl;
}
//希尔排序 
//1 选择一个增量序列 t1，t2，……，tk，其中 ti > tj, tk = 1；
//2 按增量序列个数 k，对序列进行 k 趟排序；
//3 每趟排序，根据对应的增量 ti，将待排序列分割成若干长度为 m 的子序列，分别对各子表进行直接插入排序。仅增量因子为 1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。
void shellSort(vector<int>arr){
    int len = arr.size();
    int gap =1;
    while(gap<len/3){
        gap = gap*3+1;
    }
    while(gap>0){
        for(int i=gap;i<len;i++){
            int j = i - gap;
            int tmp = arr[i];
            while(j>=0&&arr[j]>tmp){
                swap(arr[j+gap],arr[j]);
                j-=gap;
            } 
        }
        gap = gap/3;
    }
    cout<<"希尔排序"<<arr<<endl;
}
//归并排序
//1 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；
//2 设定两个指针，最初位置分别为两个已经排序序列的起始位置；
//3 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；
//4 重复步骤 3 直到某一指针达到序列尾；
//5 将另一序列剩下的所有元素直接复制到合并序列尾。 
void merge(vector<int>&arr,int L,int mid,int R){
    vector<int>tmp;
    int l1 = L,l2 = mid+1;
    while(l1<=mid&&l2<=R){
        if(arr[l1]<arr[l2]){
            tmp.push_back(arr[l1]);
            l1++;
        }else{
            tmp.push_back(arr[l2]);
            l2++;
        }
    }
        while(l1<=mid){
            tmp.push_back(arr[l1]);
            l1++;    
        }
        while(l2<=R){
            tmp.push_back(arr[l2]);
            l2++;
        }
        for(int i=0;i<tmp.size();i++){
            arr[L+i] = tmp[i];
        }
}
void mergeSort(vector<int>arr){
    int len = arr.size();
    if(len>=2){
        int num=2;
        while(num<len*2){
            for(int i=0;i<len;i+=num){
                int L = i;
                int mid = i+num/2-1;
                int R = i+num-1;
                if(R>=len)R = len-1;
                merge(arr,L,mid,R);
            }
            
            num = num*2;
        }
    } 
    cout<<"归并排序"<<arr<<endl; 
}
//快速排序
//1 从数列中挑出一个元素，称为 “基准”（pivot）;
//2 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
//3 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序；
int  Paritition(vector<int>&arr, int low, int high) {
   int pivot = arr[low];
   while (low < high) {
     while (low < high && arr[high] >= pivot) {
       --high;
     }
     arr[low] = arr[high];
     while (low < high && arr[low] <= pivot) {
       ++low;
     }
     arr[high] = arr[low];
   }
   arr[low] = pivot;
   return low;
 }
void Quick(vector<int>&arr, int low, int high) {
   if (low < high) {
            cout<<"快速排序"<<arr<<endl;
     int pivot = Paritition(arr, low, high); 
     Quick(arr, low, pivot - 1);
     Quick(arr, pivot + 1, high);
   }
 }
void QuickSort(vector<int>arr){
    int len = arr.size();
    //Quick(arr,0,len-1)//递归
    stack<int>s;
    s.push(0);
    s.push(len-1);
    while(!s.empty()){
        int r = s.top();
        s.pop();
        int l = s.top();
        s.pop();
        if(l<r){
            int pivot = Paritition(arr, l, r);
            s.push(l);
            s.push(pivot-1);
            s.push(pivot+1); 
            s.push(r); 
        }
    } 
    cout<<"快速排序"<<arr<<endl; 
}
void QuickSortTmp(vector<int>&arr){
    int len = arr.size();
    //Quick(arr,0,len-1)//递归
    stack<int>s;
    s.push(0);
    s.push(len-1);
    while(!s.empty()){
        int r = s.top();
        s.pop();
        int l = s.top();
        s.pop();
        if(l<r){
            int pivot = Paritition(arr, l, r);
            s.push(l);
            s.push(pivot-1);
            s.push(pivot+1); 
            s.push(r); 
        }
    }  
}


//堆排序 
void Down(vector<int>&arr, int i, int n) { // 最后结果就是大顶堆
    int parent = i;                    // 父节点下标
    int child  = 2 * i + 1;            // 子节点下标
    while (child < n) {
        if (child + 1 < n && arr[child] < arr[child + 1]) { // 判断子节点那个大，大的与父节点比较
            child++;
        }
        if (arr[parent] < arr[child]) { // 判断父节点是否小于子节点
            swap(arr[parent], arr[child]);     // 交换父节点和子节点
            parent = child;                 // 子节点下标 赋给 父节点下标
        }
        child = child * 2 + 1; // 换行，比较下面的父节点和子节点
    }
}
void BuildHeap(vector<int>&arr){
    int len = arr.size();
    for (int i = len / 2 - 1; i >= 0; i--) { // 倒数第二排开始, 创建大顶堆，必须从下往上比较
        Down(arr, i, len);                 // 否则有的不符合大顶堆定义
    }
}
void heapSort(vector<int>arr){
    BuildHeap(arr);
    int len = arr.size();
    for (int i = len - 1; i > 0; i--) {
        swap(arr[0],arr[i]); // 交换顶点和第 i 个数据
        Down(arr, 0, i); // 重新建立大顶堆
    }
    cout<<"堆排序"<<arr<<endl; 
} 
//计数排序
void countingSort(vector<int>arr) {
    int len = arr.size();
    int maxValue = 0;
    for(int i=0;i<len;i++){
        maxValue = maxValue>arr[i] ? maxValue : arr[i];
    }
    vector<int>tmp(maxValue+1);
    for(int i=0;i<len;i++){
        tmp[arr[i]]++;
    }
    int n=0;
    for(int i=0;i < maxValue+1;i++){
        while(tmp[i]!=0){
            arr[n++] = i;
            tmp[i]--;
            
        }
    }
    cout<<"计数排序"<<arr<<endl; 
}
//桶排序
void bucketSort(vector<int>arr){
    int len = arr.size();
    // 计算最大值与最小值
    int max = 0;
    int min = 1000000;
    for(int i = 0; i < len; i++){
        max = max > arr[i] ? max : arr[i];
        min = min < arr[i] ? min : arr[i];
    }
        // 计算桶的数量
    int bucketNum = (max - min) / len + 1;
    vector<int>tmp[bucketNum];

    
    // 将每个元素放入桶
    for(int i = 0; i < len; i++){
        int num = (arr[i] - min) / len;
        tmp[num].push_back(arr[i]);
    }
    
    // 对每个桶进行排序
    for(int i = 0; i < bucketNum; i++){
       QuickSortTmp(tmp[i]);
    }
    
    // 将桶中的元素赋值到原序列
    int index = 0;
    for(int i = 0; i < bucketNum; i++){
        for(int j = 0; j < tmp[i].size(); j++){
            arr[index++] = tmp[i][j];
        }
    } 
    cout<<"桶排序"<<arr<<endl; 
} 
//基数排序
//求数据的最大位数,决定排序次数
int maxbit(vector<int>arr) 
{
    int len = arr.size();
    int d = 1; //保存最大的位数
    int p = 10;
    for(int i = 0; i < len; ++i)
    {
        while(arr[i] >= p)
        {
            p *= 10;
            ++d;
        }
    }
    return d;
}
void radixSort(vector<int>arr){
    int len = arr.size();
     int d = maxbit(arr);
     int count[10];
     int tmp[len];
     int i, j, k;
    int radix = 1;
    for(i = 1; i <= d; i++) //进行d次排序
    {
        for(j = 0; j < 10; j++)
            count[j] = 0; //每次分配前清空计数器
        for(j = 0; j < len; j++)
        {
            k = (arr[j] / radix) % 10; //统计每个桶中的记录数
            count[k]++;
        }
        for(j = 1; j < 10; j++)
            count[j] = count[j - 1] + count[j]; //将tmp中的位置依次分配给每个桶
        for(j = len- 1; j >= 0; j--) //将所有桶中记录依次收集到tmp中
        {
            k = (arr[j] / radix) % 10;
            tmp[count[k] - 1] = arr[j];
            count[k]--;
        }
        for(j = 0; j < len; j++) 
            arr[j] = tmp[j];
        radix = radix * 10;
    }
    cout<<"基数排序"<<arr<<endl;
} 
int main(){
    vector<int>arr{3,5,6,2,1,7,8,4,3,100,45,32,54,23,21,54,23,56,77,32,56};
    
    bubbleSort(arr); 
    selectionSort(arr);
    insertionSort(arr);
    shellSort(arr);
    mergeSort(arr);    
    QuickSort(arr);
    countingSort(arr);
    bucketSort(arr);
    radixSort(arr);
    heapSort(arr);
    cout<<arr<<endl;
}