cpp排序算法总结

快排

注意：

- 快排是不稳定排序

思路：
选基数，双指针移动/交换，分治
示例：
> 坐在马桶上看算法：快速排序 - 51CTO.COM http://developer.51cto.com/art/201403/430986.htm
> 快速排序(三种算法实现和非递归实现) - CSDN博客 https://blog.csdn.net/qq_36528114/article/details/78667034

第一轮
        i                               j
    6   1   2   7   9   3   4   5   10  8
    基数 x=6
    先从 j 往前遍历(j--)，遇到小于 x 的数停下，再从 i 往后遍历，遇到大于 x 的数停下，交换 *j 和 *i
                i               j
    6   1   2   7   9   3   4   5   10  8
    6   1   2   5   9   3   4   7   10  8（交换后）
    重复以上步骤，继续先移动 j，再移动 i
                    i       j
    6   1   2   5   9   3   4   7   10  8
    6   1   2   5   4   3   9   7   10  8（交换后）
                       ij
    6   1   2   5   4   3   9   7   10  8
    6   1   2   5   4   3   9   7   10  8（交换后）
    此时 i 与 j 相遇，交换 *i 与 *x
                       ij
    3   1   2   5   4   6   9   7   10  8
    第一轮完成，之后递归完成子部分
基数的选择不固定，一般选择第一个或最后一个，或中位数

void quickSort(vector<int> &array, int low, int high){
    if(low >= high) return;
    
    //随机int randomPivot = low+rand()%(right-low);
    //swap(array[low],array[randomPivot];)
    
    //*****partition部分,用局部变量low,high
    //为了确保是从对立面找不能直接随机化pivot的值，否则出现同侧移动
    int i = low, j = high, pivot = i;
    while(i < j){
        //pivot的对立面找一个小于pivot
        while(i < j && array[j] >= array[pivot])
            j--;
        while(i < j && array[i] <= array[pivot])
            i++;
        //交换完不用两边++会自动满足
        swap(array[i], array[j]);
    }
    //最后一次把pivot放到合适位置现在的单个元素也要放到pivot的地方去
    swap(array[pivot], array[i]);
    int mid = i;
    
    //写在一个函数里需要新的变量来遍历不然low和high已经移动
    quickSort(array, low, mid - 1);
    quickSort(array, mid + 1, high);
    return;
}

归并排序

• 归并排序是稳定排序
  思路：
  分治
  划分子区间、子区间排序、合并子区间

void mergeSort(vector<int> &array, int low, int high){
    if(low >= high) return;
  
    //分解原问题为若干子问题
    int mid = low + (high - low)/2;
  	
  	//递归求解子问题，若足够小和直接求得
    mergeSort(array, low, mid);
    mergeSort(array, mid + 1, high);
  	
	  //合并子问题的解
    merge(array, low, mid, high);
}

void merge(vector<int> &array, int low, int mid, int high){
    vector<int> temp(array);
    //t取low按同样位置排序，t取0拷贝时从low下标开始拷贝
    int cur1 = low, cur2 = mid + 1, t = low;
    while (cur1 <= mid && cur2 <= high) {
        if (array[cur1] <= array[cur2])
            temp[t++] = array[cur1++];
        else
            temp[t++] = array[cur2++];
    }
    while(cur1 <= mid)
        temp[t++] = array[cur1++];
    while(cur2 <= high)
        temp[t++] = array[cur2++];
    for (t = low; t <= high; t++) {
        array[t] = temp[t];
    }
}

链表归并

ListNode *findhalf(ListNode *head){
    ListNode *low = head,*fast = head;
    
    //不能仅判断fast->next->next
    while(fast->next && fast->next->next){
        low=low->next;
        fast=fast->next->next;
    }
    return low;
}
ListNode *mergeSort(ListNode *head){
    //归并排序划分到空或仅有一个节点时,list中是l>=时退出
    if(head==nullptr || head->next==nullptr) return head;
    ListNode* hf = findhalf(head);
    
    ListNode* pb = mergeSort(hf->next);
    //先找右，再断链！！
    hf->next=nullptr;
    ListNode* pa = mergeSort(head);
    return merge(pa,pb);
}
ListNode* merge(ListNode *pa,ListNode *pb){
    ListNode dummy(0);
    ListNode *rear=&dummy;//上面结构体,这里取地址,不是new放在堆栈的临时变量,出括号自动消失
    
    //也不用cur1和cur2来遍历
    while(pa && pb){
        if(pa->val < pb->val) {
            rear->next = pa;
            pa = pa->next;
        }
        else{
            rear->next = pb;
            pb = pb->next;
        }
        rear = rear->next;
    }
    if(pa)
        rear->next = pa;
    if(pb)
        rear->next = pb;
    
    return dummy.next;
}

堆排序

• 堆排序是不稳定排序

• 堆的性质：
  每个节点的值小于等于其父节点 或 大于等于父节点；前者称为“最大堆”，用于升序，后者为“最小堆”，用于降序

• 堆是一棵完全二叉树，因此常用数组进行模拟
  思路：
  建堆：

  建堆的过程实际上就是从最后一个 非叶子节点 开始不断向前做自顶向下的调整
  

  堆排序：

  建完堆后，每次交换堆顶和堆尾，
  然后对 a[0..n-1] 重新调整
  

  每次调整的操作时间复杂度为 O(logn)
  建堆的时间复杂度为 O(N)

  int heapsize = 0;
  void maxHeapify(vector<int> &array, int k){
  
      //将元素k向下进行调整,即i是k的左孩子（i在k下）
      // 注意：自顶向下的操作只完成了一个节点的调整
      
      for(int i = 2*k+1; i < heapsize; i=i*2+1){
          //当前调整节点为k,和其子节点的最大值比较若小于则违背最大堆性质
          int largest = array[k];
          
          //largest=max(a[left],a[right])并且在不越界的情况下，right<heapsize
          // 实际上，以下操作就是为了找出 a[i] 和 a[i*2+1]、a[i*2+2] 之中的最大值
          if(i+1 < heapsize && array[i] < array[i+1])
              i++;
          
          //当前节点已满足大于其子节点，调整完毕
          if(largest >= array[i]) break;
          //否则a[i] 不是最大的，说明还需继续调整
          else{
              swap(array[k], array[i]);
              k = i;
          }
      }
  }
  
  void buildMaxHeap(vector<int> &array){
      //全局变量来控制堆的调整
      heapsize = int(array.size());
      // 建堆的过程实际上就是从最后一个 **非叶子节点** 开始不断往前调整
      for (int i = int(array.size()>>1); i >= 0; --i){
          maxHeapify(array, i);
      }
  }
  
  void heapSort(vector<int> &array){
      buildMaxHeap(array);
      for(int i = int(array.size() - 1); i >= 1; --i){
          //堆顶元素array[0]即最大值换到堆尾,再重新调整堆
          swap(array[i], array[0]);
          //从堆中删除该元素
          heapsize--;
          maxHeapify(array, 0);
      }
  }
  
  int main(){
      vector<int> vec = {45, 68, 20, 39, 88, 97, 46, 59};
      heapSort(vec);
      for(int i = 0; i < vec.size(); ++i)
          cout << vec[i] << " ";
      cout << endl;
  }

直接插入排序和希尔排序

void insertSort(vector<int> &array){
    //往前方已经有序的数组内插
    //初始时第一个为已排序
    for (int i = 1, j, temp; i < array.size(); i++) {
        if (array[i] < array[i-1]) {
            temp = array[i];//或array[0]=array[i]当哨兵
            for (j = i - 1; array[j] > temp && j >= 0; j--) {
                array[j+1] = array[j];
            }
            array[j+1] = temp;
        }
    }
}

void shellSort(vector<int> &array){
    for(int k = int(array.size()/2); k > 0; k/=2){
        for (int i = 1+k,j,temp; i < array.size(); i+=k) {
            if(array[i] < array[i-k]){
                temp = array[i];
                for(j = i-k; array[j] > temp && j>=0; j-=k)
                    array[j+k] = array[j];
                array[j+k] = temp;
            }
        }
    }
}

冒泡排序

void bubbleSort(vector<int> &array){
    //n-1次找最轻
    for (int i = 0, j; i < array.size() - 1; i++) {
        bool flag = false;
        //for里一趟冒泡,最轻的气泡漂浮到顶部
        for(j = int(array.size() - 1); j > i; j--)
            if(array[j-1] > array[j]){
                swap(array[j-1], array[j]);//逆序则交换
                flag = true;
            }
        if(flag == false)
            return;
    }
}

简单选择排序

void selectSort(vector<int> &array){
    //和冒泡的FOR类似
    for (int i = 0, min = 0; i < array.size() - 1; i++) {
        //记录最小值的下标即可
        min = i;
        for (int j = int(array.size() - 1); j > i; j--)
            if (array[j] < array[min])
                min = j;
        swap(array[min], array[i]);
    }
}