c++ 面试常见的排序_C

date: 2022-05-05 12:39:54
tags: [排序]
categories: [算法,面试]

我的博客

一、快速排序

快速排序平均时间复杂度为o(nlogn)，最坏时间复杂度为o(n^2)，不稳定;

主要可以通过以下几种方式来优化：

三数取中，使选择的“标杆”能够尽量的将数组平均划分成两半，避免选择到边界值使时间复杂度退化到o(n^2)；
双指针 *** 作，减少在对比时的交换次数；
每次遍历集中放置与“标杆”相同的值，减少递归深度；

#include 
#include 
#include 
using namespace std;

void quickSort(int start, int end, vector& nums){
    if(start>=end) return;
    int left = start;
    int right = end;
    int mid = (left + right) / 2;
    /* 三数取中 */
    if((nums[left]nums[mid]&&nums[mid]>nums[right])){
        swap(nums[left],nums[mid]);
    }
    else if((nums[left]nums[right]&&nums[right]>nums[mid])){
        swap(nums[left],nums[right]);
    }
    /* 双指针 */
    while(left=nums[left]) left++;
        if(left nums = {2,5,1,6,8,4,2,8,1,25,8};;
    quickSort(0,nums.size()-1,nums);
    for(int i=0;i

 
二、归并排序 
归并排序时间复杂度为o(nlogn)，空间复杂度为o(n)，稳定; 
#include 
#include 
#include 
using namespace std;

void mergeSort(int start, int end, vector& nums, vector& temp){
    if(start>=end) return;
    /* 递归分割 */
    int mid = (start + end) / 2;
    mergeSort(start,mid,nums,temp);
    mergeSort(mid+1,end,nums,temp);
    /* 合并 */
    int index = start;
    int left = start;
    int right = mid + 1;
    while(left<=mid||right<=end){
        int x = left<=mid?nums[left]:INT_MAX;
        int y = right<=end?nums[right]:INT_MAX;
        temp[index] = min(x,y);
        if(temp[index]==x) left++;
        else right++;
        index++;
    }
  	// 复制结果
    for(int i=start;i<=end;i++) nums[i] = temp[i];
}

int main() {
    vector nums = {2,5,1,6,8,4,2,8,1,25,8};;
    vector temp(nums.size(),0);
    mergesSort(0,nums.size()-1,nums,temp);
    for(int i=0;i
 
三、堆排序 
堆排序时间复杂度为o(nlogn)，空间时间复杂度为o(1)，不稳定; 
#include 
#include 
#include 
using namespace std;

/* 向下调整堆 */
void siftDown(int index, int end, vector& nums){
    if(index>=end) return;
    int left = index*2 + 1;
    int right = left + 1;
    int max_index = index;
    if(left<=end&&nums[left]>nums[max_index]) max_index = left;
    if(right<=end&&nums[right]>nums[max_index]) max_index = right;
    if(max_index!=index){
        swap(nums[index],nums[max_index]);
        siftDown(max_index,end,nums);
    }
    return;
}

void heapSort(vector& nums){
    int len = nums.size();
    /* 建堆 */
    for(int i=len/2-1;i>=0;i--){
        siftDown(i,len-1,nums);
    }
 	
    /* 堆排序 */
    for(int i=len-1;i>0;i--){
    	siftDown(0,i,nums);
        swap(nums[0],nums[i]);
    }
    return;
}

int main() {
    vector nums = {2,5,1,6,8,4,2,8,1,25,8};;
    heapSort(nums);
    for(int i=0;i
 
四、希尔排序 
希尔排序时间复杂度为o(nlogn)，空间时间复杂度为o(1)，不稳定; 
#include 
#include 
#include 
using namespace std;

void shellSort(vector& nums){
    int len = nums.size();
    for(int k=2;k>0;k/=2){
        for(int i=k;i=0;j-=k){
                if(nums[j]>nums[j+k]) swap(nums[j],nums[j+k]);
                else break;
            }
        }
    }
}


int main() {
    vector nums = {2,5,1,6,8,4,2,8,1,25,8};;
    shellSort(nums);
    for(int i=0;i
					
										


					
						欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/langs/798465.html

c++ 面试常见的排序

发表评论

评论列表（0条）