本文共 2503 字，大约阅读时间需要 8 分钟。

目录

排序算法

01 堆排序

• 大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列；
• 小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列；
  

02 快速排序

1. 选择数组左边第一个元素为枢轴pivot，把数组所有元素比pivot大的放在数组右边，比pivot小的放在左边。（复杂度为O(n)）
2. 对pivot左右两边的序列分别进行快速排序。

平均时间复杂度分析：

T(1) = 1;	T(n) = 2*T(n/2) + a*n;(a为常数，每次合并时，复杂度为O(n))	= 2*(2*T(n/4)+a*n/2) + a*n	= 4*T(n/4) + 2*a*n	= 4*(2*T(n/8)+a*n/4) + 2*a*n	= 8*T(n/8) + 3*a*n	=......	= 2^k*T(1) + k*a*n  (其中n==2^k,即k=log2(n))	= n + a*n*log2(n);

所以时间复杂度为O(nlogn)

• 注意：对左右分别快排时，可能出现一遍元素个数为0，这是最坏情况，此时时间复杂度为O(n^2)。

#include 
   
    using namespace std;#include 
    
     void quicksort(vector < int > & nums, int low, int high) {
       if (low < high) {
           int i = low;        int j = high;        int tmp = nums[low];        while (i < j) {
               while (i < j && nums[j] > tmp) {
                   j--;            }            if (i < j) {
                   nums[i] = nums[j];            }            while (i < j && nums[i] <= tmp) {
                   i++;            }            if (i < j) {
                   nums[j] = nums[i];            }        }        nums[i] = tmp;        quicksort(nums, low, i - 1);        quicksort(nums, i + 1, high);    }}int main() {
       int n;    cin >> n;    vector < int > nums(n);    for (int i = 0; i < n; i++) {
           cin >> nums[i];    }    quicksort(nums, 0, n - 1);    for (int i = 0; i < n; i++) {
           cout << nums[i] << " ";    }    return 0;}
    
   

03 归并排序

#include 
   
    using namespace std;#include 
    
     void Merge(vector
     
       &Array, int front, int mid, int end) {
       vector
      
        LeftSubArray(Array.begin() + front, Array.begin() + mid + 1);    vector
       
         RightSubArray(Array.begin() + mid + 1, Array.begin() + end + 1);        int idxLeft = 0, idxRight = 0;    LeftSubArray.insert(LeftSubArray.end(), numeric_limits
        
         ::max()); RightSubArray.insert(RightSubArray.end(), numeric_limits
         
          ::max()); for (int i = front; i <= end; i++) { if (LeftSubArray[idxLeft] < RightSubArray[idxRight]) { Array[i] = LeftSubArray[idxLeft]; idxLeft++; } else { Array[i] = RightSubArray[idxRight]; idxRight++; } }}void MergeSort(vector
          
            &Array, int front, int end) { if (front >= end) return; int mid = (front + end) / 2; MergeSort(Array, front, mid); MergeSort(Array, mid + 1, end); Merge(Array, front, mid, end);}int main(){ int n; cin >> n; vector
           
             nums(n); for(int i=0;i
            
             > nums[i]; } MergeSort(nums,0,n-1); for(int i=0;i
            
           
          
         
        
       
      
     
    
   

转载地址：http://zkztn.baihongyu.com/