二分查找、二路归并、快速排序、堆排序

本文最后更新于:25 天前

二分查找

最简单的算法,直接无脑默写就完事了

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0, right = nums.size() - 1;
        while ( left <= right ) {
            int mid = (left + right) / 2;
          	// if 判断的顺序,应该先判断是否相等
            if ( nums[mid] == target ) return mid;
            else if ( nums[mid] > target ) right = mid - 1;
            else left = mid + 1;
        }
        return -1;
    }
};

二路归并

在之前的博文中有写过归并排序,点击跳转

快速排序

这里的代码来源于LeetCode,多了更多细节上的处理,否则无法通过 LeetCode 的测试

class Solution {
public:
    // quickSort
    vector<int> sortArray(vector<int>& nums) {
        quickSort(nums, 0, nums.size()-1);
        return nums;
    }
    int partation(vector<int>& arr, int left, int right) {
        int random = left + rand() % (right - left + 1);
        swap(arr[random], arr[left]);
        int pivot = arr[left];
        while ( left < right ) {
            while ( left < right && arr[right] >= pivot ) {
                right--;
            }
            arr[left] = arr[right];
            while ( left < right && arr[left] <= pivot ) {
                left++;
            }
            arr[right] = arr[left];
        }
        arr[left] = pivot;
        return left;
    }
    void quickSort(vector<int>& arr, int left, int right) {
        if ( arr.size() < 2 || left >= right ) return;
      	// 主要增加的细节处理在下面这部分的函数中
        int p = partation(arr, left, right);
        quickSort(arr, left, p-1);
        quickSort(arr, p+1, right);
    }
};

堆排序

应用场景

当有大量的元素需要排序(比如有十万个元素),取出 topX 的元素时,如果使用其他排序,将整个无序序列排序成为有序序列,会消耗大量的计算资源,但实际上我们需要的只是 X 个元素。堆排序使用的是堆这种数据结构设计的选择排序算法,是一种不稳定的排序方法,时间复杂度为 O(nlogn)。

基本思路

1. build an unorder array into a head
2. swap(top element in heap, end element in heap)
3. readjust the heap structure, repeat step1 and step2 util the array is ordered

pseudocode

// build big top heap
loop i = arr.length/2-1; i >= 0; i--
  adjustHead()
end loop
  
 // adjust the heap structure
 loop i = arr.length-1; i >= 0; i--
   swap(arr[0], arr[i])
   adjustHeap()
 end loop

代码

来源见注释

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

// 代码作者:机智翔学长(B站,CSDN同名)
// 赠送内容,堆排序,从小到大排序,故大顶堆获取数据后放在末尾

// 从下标l往下调整到r
void adjustHeap(int a[], int l, int r){
    if(l>=r){
        return ;
    }
    int i = l;
    int j = 2*i+1;
    while(j<=r){
        if(j+1<=r && a[j+1]>a[j]){
            // i节点下的两个子节点j和j+1(如果存在),选择大的那个和i节点比较
            j = j+1;
        }
        if(a[j]>a[i]){
            // 如果子节点j大于父节点i,则交换
            swap(a[i], a[j]);
        }else{
            break;
        }
        i = j;
        j = 2*i+1;
    }
}

// debug
void debugOut(int a[], int l, int r){
    cout << "\ndebug out:" << endl;
    for(int i=l;i<=r;i++){
        cout << a[i] << " ";
    }
    cout << endl;
}

// 堆排序,数组a[],下标为l~r (实际上l为0)
void heapSort(int a[], int l, int r){

    // 先构建一个大顶堆
    for(int i=(r-1)/2;i>=l;i--){
        // i从最后一个父节点开始,往上
        adjustHeap(a, i, r); // 将数组a[]从i到r进行调整
    }

    // 再取出堆顶元素放在数组后边,重新调整堆
    for(int j=r;j>=l;j--){
        swap(a[l], a[j]);
        debugOut(a, l, r); // debug 可删
        adjustHeap(a, l, j-1);
    }
}

int main(){
    int a[] = {4, 6, 8, 5, 9};
    int len = sizeof(a)/sizeof(int);
    heapSort(a, 0, len-1);
    cout << "\n\nafter sort:" << endl;
    for(int i=0;i<len;i++){
        cout << a[i] << " ";
    }
}

本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!