常用的排序算法

常用的排序算法：

堆排序

定义：priority_queue<Type, Container, Functional>

1. Type 就是数据类型
2. Container 就是容器类型（Container必须是用数组实现的容器，比如vector,deque等等，但不能用 list。STL里面默认用的是vector）
3. Functional 就是比较的方式，当需要用自定义的数据类型时才需要传入这三个参数

⭐️使用基本数据类型时，只需要传入数据类型，默认是大顶堆

//小顶堆
priority_queue <int,vector<int>,greater<int> > q;

//大顶堆
priority_queue <int,vector<int>,less<int> > q;

快速排序：左闭右闭

void quick_sort(vector<int> &nums,int l,int r) {

        if (l > r) return {};

        int first = l,last = r,key = nums[first];

        while (first < last) {

            while (first < last && nums[last] >= key) {
                --last;
            }
            nums[first] = nums[last];

            while (first < last && nums[first] <= key) {
                ++first;
            }
            nums[last] = nums[first];
        } 

        nums[first] = key;
        quick_sort(nums,l,first - 1);
        quick_sort(nums,first + 1,r); 
}

快速排序：左闭右开

void quick_sort(vector<int> &nums,int l,int r) {

        if (l + 1 > r) return {};

        int first = l,last = r - 1,key = nums[first];

        while (first < last) {

            while (first < last && nums[last] >= key) {
                --last;
            }
            nums[first] = nums[last];

            while (first < last && nums[first] <= key) {
                ++first;
            }
            nums[last] = nums[first];
        } 

        nums[first] = key;
        quick_sort(nums,l,first);
        quick_sort(nums,first + 1,r);
}

归并排序

void merge_sort(vector<int> &nums,int l,int r,vector<int> &temp) {
  
  if (l + 1 >= r) return;
  
  //divide
  int m = l + (r - l) / 2;
  merge_sort(nums,l,m,temp);
  merge_sort(nums,m,r,temp);
  
  //conquer
  int p = l,q = m,i = l;
  while (p < m || q < r) {
    
    if (q >= r || (p < m && nums[p] <= nums[q])) {
      temp[i++] = nums[p++];
    } else {
      temp[i++] = nums[q++];
    }
  }
  
  for (i = l;i < r;++i) {
    nums[i] = temp[i];
  }
}

插入排序

void insertion_sort(vector<int> &nums,int n) {

    for (int i = 0;i < n;++i) {
        
        for (int j = i;j > 0 && nums[j] < nums[j - 1];--j) {
            swap(nums[j],nums[j - 1]);
        }
    }
}

冒泡排序

void bubble_sort(vector<int> &nums,int n) {
  
  bool swapped;
  
  for (int i = 1;i < n;++i) {
    
    swapped = false;
    for (int j = 1;j < n - i + 1;++j) {
      
      if (nums[j] < nums[j - 1]) {
        swap(nums[j],nums[j - 1]);
        swapped = true;
      }
    }
    
    if (swapped == false) break;
  }
}

选择排序

void selection_sort(vector<int> &nums,int n) {
  
  int mid;
  for (int i = 0;i < n - 1;++i) {
    
    mid = i;
    for (int j = i + 1;j < n;++j) {
      
      if (nums[j] < nums[mid]) mid = j;
    }
    
    swap(nums[mid],nums[i]);
  }
}