面试常见的排序

---

一、快速排序

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

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

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

​

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

void quickSort(int start, int end, vector<int>& 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])||(nums[left]>nums[mid]&&nums[mid]>nums[right])){
        swap(nums[left],nums[mid]);
    }
    else if((nums[left]<nums[right]&&nums[right]<nums[mid])||(nums[left]>nums[right]&&nums[right]>nums[mid])){
        swap(nums[left],nums[right]);
    }
    /* 双指针 */
    while(left<right){
        while(left<right&&nums[start]<=nums[right]) right--;
        while(left<right&&nums[start]>=nums[left]) left++;
        if(left<right) swap(nums[left],nums[right]);
    }
    swap(nums[start],nums[left]);
    
    /* 递归调用 */
    quickSort(start,left-1,nums);
    quickSort(left+1,end,nums);
    return;
}

int main() {
    vector<int> nums = {2,5,1,6,8,4,2,8,1,25,8};
    quickSort(0,nums.size()-1,nums);
    for(int i=0;i<nums.size();i++){
        cout<<nums[i]<<",";
    }
    return 0;
}

二、归并排序

归并排序时间复杂度为o(nlogn)，空间复杂度为o(n)，稳定;

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

void mergeSort(int start, int end, vector<int>& nums, vector<int>& 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<int> nums = {2,5,1,6,8,4,2,8,1,25,8};
    vector<int> temp(nums.size(),0);
    mergesSort(0,nums.size()-1,nums,temp);
    for(int i=0;i<nums.size();i++){
        cout<<nums[i]<<",";
    }
    return 0;
}

三、堆排序

堆排序时间复杂度为o(nlogn)，空间时间复杂度为o(1)，不稳定;

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

/* 向下调整堆 */
void siftDown(int index, int end, vector<int>& 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<int>& 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<int> nums = {2,5,1,6,8,4,2,8,1,25,8};
    heapSort(nums);
    for(int i=0;i<nums.size();i++){
        cout<<nums[i]<<",";
    }
    return 0;
}

四、希尔排序

希尔排序时间复杂度为o(nlogn)，空间时间复杂度为o(1)，不稳定;

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

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


int main() {
    vector<int> nums = {2,5,1,6,8,4,2,8,1,25,8};
    shellSort(nums);
    for(int i=0;i<nums.size();i++){
        cout<<nums[i]<<",";
    }
    return 0;
}