排序

参考：视频

交换排序：冒泡排序和快速排序

冒泡：比较两个元素，比较大就往后放，那么每一次都会将一个最大的元素放在末尾，所以下一次就不需要遍历最后哪些排完序的元素。
时间复杂度：O(n^2)
稳定

#include<vector>
#include<iostream>
using namespace std;

void blue_blue(vector<int>& nums){
    
    for(int i=0;i<nums.size()-1;i++){ // 每一轮将完成一个元素的排序，最多只需要执行nums.size()-1轮。
        bool sign= false;
        for(int j=0;j<=nums.size()-2-i;j++){// 完成排序的元素不会再进行比较，所以“-i”
            if(nums[j]> nums[j+1]) {
                sign =true;
                swap(nums[j],nums[j+1]);
            }   
        }
        if(!sign) return; // 本轮没有发生交换，则代表已经排序完成了
    }
    return ;
}

int main(){
    int number;
    vector<int> nums;
    cin>> number;

    for(int i=0;i<number;i++){
        int tmp;
        cin>> tmp;
        nums.push_back(tmp);
    }
    blue_blue(nums);
    for(auto num:nums){
        cout<< num << endl;;
    }

    return 0;
}

快速排序：选择第一个元素作为轴，如果将右边比轴小的元素放入轴所在的位置，然后将左边比轴大的元素放入右边上次空出来的位置，如此往复，直到左右指针相遇，此时将轴放入相遇的位置。
在最糟情况下，其运行时间为O(n^2)。在平均情况下，快速排序的运行时间为O(nlogn)。
【注】如果元素和轴相等的话，交不交换都一样。
不稳定

void fast_sort(vector<int>& nums,int start, int end){
    if(end<=start) return ;
    int tmp =nums[start];
    int left =start,right = end;

    while(left!=right){
        while(left!=right && nums[right]>= tmp) right--;
        if(left!=right) swap(nums[right],nums[left++]);
        else break;

        
        while(left!=right && nums[left]<= tmp) left++;
        if(left!=right) swap(nums[left],nums[right--]);
        else break;
    }
    nums[left] =tmp;
    fast_sort(nums,start,left-1);
    fast_sort(nums,left+1,end);
    return ;    
}

插入排序：直接插入、折半插入和希尔排序

直接插入：在排好序的数组中，从右往左查找第一个小于等于当前元素的元素。没找到时，每次查找都向后移动一个位置；找到时将元素放在空位中。
稳定。

void insert_direct(vector<int>& nums){
    if(nums.size()<2) return;
    for(int i=1;i<nums.size();i++){
        for(int j=i;j>=1;j--){
            if(nums[j] >= nums[j-1]) 
                break;
            else 
                swap(nums[j],nums[j-1]);
        }
    }

    return ;    
}

折半插入：查找时使用折半查找。折半查找见数组章节.
折半插入并没有比直接插入快。

int search(const vector<int> nums,int target,int start, int end){
    int left = start; // target不存在时，left要么指向第一个大于target的元素，要么指向小于target的元素。
    int right=end;    // target不存在时，right要么指向最后一个小于target的元素，要么指向大于target的元素。
                      // nums[mid]==target时，移动left且target存在，则最终left-1指向最后一个target。
                      // nums[mid]==target时，移动right且target存在，则最终right+1指向第一个target

    while(right>=left){
        int mid = (right+left)/2; 
        if(nums[mid]<=target){
            left = mid+1;
        }
        else right = mid-1;
    }

    return left;
}

void half_direct(vector<int>& nums){
    if(nums.size()<2) return;
    int j=0;
    for(int i=1;i<nums.size();++i){
        int index = search(nums,nums[i],0,i-1);
        int tmp = nums[i];
        for(j=i;j>index;--j)  swap(nums[j-1],nums[j]);
    }

    return ;    
}

希尔排序：最坏的时间复杂度为O(n^2)
不稳定

void shell_sort(vector<int>& arr)
{
    int i, j, inc, key;
    // 初始增量：len/2，每一趟之后除以二
    for (inc = arr.size() / 2; inc > 0; inc /= 2) // inc代表跨度
    {
        // 每一趟采用插入排序
        for (i = inc; i < arr.size(); i++) // 
        {
            key = arr[i];
            for (j = i; j >= inc && key < arr[j - inc]; j -= inc)
                arr[j] = arr[j - inc];
            arr[j] = key;
        }
    }
}

上面代码中：i代表跨度为inc的第二个点，而i加一以后跨度还是inc，即所有距离为五的元素都进行了希尔排序，而普通的希尔排序中只对其中的几个元素进行排序

选择：

• 简单选择排序：每次扫描整个数组找出最小的元素，然后将最小的元素和最前面元素进行交换。和冒泡排序一样，每一轮都完成一个元素的排序。
  时间复杂度：
• 堆排序：

简单选择排序

void simple_selection_sort(vector<int>& nums){
    for(int i=0;i <nums.size();i++){
        int minE = i;
        for(int j=i+1; j<nums.size();j++){
            if(nums[j]< nums[minE]) minE=j;
        }
        swap(nums[minE],nums[i]);
    }

    return ;    
}

堆排序（大顶堆和小顶堆）

整数除法代表结果向下取整。

大顶堆实现升序排列：

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

// 将节点i向下调整
void heapify(vector<int>& nums,int n, int i){ // 从节点i开始向下调整堆，堆的是从nums[0]到nums[n-1]
    int largest =i;
    int lson = 2*i + 1;
    int rson = 2*i + 2;
    if(lson<n && nums[largest]< nums[lson]) largest = lson; // 如果构建小顶堆，只需要将这里小于号变为大于号。
    if(rson<n && nums[largest]< nums[rson]) largest = rson; // 如果构建小顶堆，只需要将这里小于号变为大于号。
    

    if(largest!=i) {
        swap(nums[largest],nums[i]);
        heapify(nums,n,largest); // 孩子节点可能也许要向下调整
    }
}

void heap_sort(vector<int> &nums){
    // 将乱序的堆变成大顶堆
    for(int i=(nums.size()-2)/2;i>=0;i--)
        heapify(nums,nums.size(),i);

    // 排序
    for(int i = nums.size()-1;i>0;i--){
        swap(nums[i],nums[0]); // 将堆顶元素（最大值）放在数组末尾i，从而实现排序
        heapify(nums,i,0); // 调整元素nums[0]~nums[i-1]
    }
    
}


int main(){
    int number;
    vector<int> nums;
    cin>> number;

    for(int i=0;i<number;i++){
        int tmp;
        cin>> tmp;
        nums.push_back(tmp);
    }
    heap_sort(nums);
    for(auto num:nums){
        cout<< num << endl;;
    }

    return 0;
}

大顶堆用于升序排序，大顶堆用于降序排序。