基础算法

2022-11-20 372 words 2 minutes

Contents

1. 排序算法

1.1 冒泡排序

冒泡排序意思就是每一次遍历，将最大/的最小元素移动到末尾. 显然对于长度为len的输入而言,最多需要遍历len -1 次. 时间复杂度O(n^2) 空间复杂度O(1)

template<typename T>
void bubble_sort(T arr[], size_t len){
    bool swap = true;   // 若是当前的遍历没有发生交换说明已经是正序的,不需要继续下去
    for(size_t loop_num = 0; loop_num < len -1 && swap; ++loop_num) {
        swap = false;
        for(size_t index = 0; index < len -1 - loop_num; ++index) {
            if(arr[index] > arr[index+1]) {
                const T tmp = arr[index];
                arr[index] = arr[index+1];
                arr[index+1] = tmp;
                swap = true;
            }
        }
    }
}

1.2 选择排序

选择排序的意思是每次选择一个指定的位置,将通过一次遍历之后取得的值放入指定位置时间复杂度O(n^2) 空间复杂度O(1)

template<typename T>
void selection_sort(T arr[], size_t len){
    for(size_t location = 0; location < len -1; ++location){
        for(size_t index = location + 1; index < len; ++index){
            if(arr[index] < arr[location]){
                T tmp = arr[location];
                arr[location] = arr[index];
                arr[index] = tmp;
            }
        }
    }
}

1.3 插入排序

插入排序保证已经遍历过的串是已经排好序的,对于新出现的元素则通过比较插入到正常位置时间复杂度O(n^2) 空间复杂度O(1)

template<typename T>
void insertion_sort(T arr[], size_t len){
    // finial_location 当前遍历位置，该位置之前是有序的
    for(size_t finial_location = 1; finial_location < len; ++finial_location){
        for(int pre_index = finial_location - 1; pre_index >= 0; --pre_index){
            // 从后向前比较,将当前元素插入到正确位置
            if(arr[pre_index+1] < arr[pre_index]){
                T tmp = arr[pre_index+1];
                arr[pre_index+1] = arr[pre_index];
                arr[pre_index] = tmp;
            }
        }
    }
}

1.4 快排

快排的核心思想是分治,每次选定一个元素Key,经过一次排序后使得Key左侧元素均小于Key,而右侧元素均大于Key Key选择也很重要

template<typename T>
void quick_sort(T arr[], int start, int finished){
    if(start >= finished) return;
    size_t start_copy = start, finished_copy = finished;
    T key = arr[start];// 选定Key为最左侧元素
    while(start < finished) {
        // 从右侧开始遍历,直到碰到一个小于Key的元素
        while (start < finished && arr[finished] >= key) {
            --finished;
        }
        arr[start] = arr[finished];
        // 从左侧开始遍历,直到碰到一个大于Key的元素
        while (start < finished && arr[start] <= key) {
            ++start;
        }
        // 交换left right
        arr[finished] = arr[start];
    }
    // 将key填入正确位置
    arr[start] = key;
    // 递归 分治
    quick_sort(arr, start_copy, start-1);
    quick_sort(arr, start+1, finished_copy);
}

1.5 堆排

1.6 归并

归并分为两个过程, 首先将数组不断二分，直到每组仅含一个元素，然后开始两两有序合并

// 合并两个有序数组
template<typename T>
void merge(T arr[], int start, int middle, int finished){
    int left_start = start;
    int right_start = middle + 1;
    T arr_tmp[finished - start +1];
    int index = 0;
    while (left_start <= middle && right_start <=finished){
        arr_tmp[index++] = arr[left_start] < arr[right_start] ? arr[left_start++] : arr[right_start++];
    }
    while(left_start <= middle){
        arr_tmp[index++] = arr[left_start++];
    }
    while(right_start <= finished){
        arr_tmp[index++] = arr[right_start++];
    }
    // copy
    for(int index = start; index <= finished;++index){
        arr[index] = arr_tmp[index - start];
    }
}
template<typename T>
void merge_sort(T arr[], int start, int finished){
    if(start >= finished) return;
    int middle = start + (finished - start)/2;
    merge_sort(arr, start, middle);
    merge_sort(arr, middle+1, finished);
    merge(arr,start, middle,finished);
}