理论面试C语言学习

计算机算法基础总结

2017-03-16  本文已影响2532人  Jerry4me

我的Github地址 : Jerry4me, demo : JRBaseAlgorithm

本文主要是通过通俗易懂的算法和自然语言, 向大家介绍基础的计算机排序算法和查找算法, 还有一些作为一名程序猿应该知道的名词, 数据结构, 算法等等. 但是仅仅止于介绍, 因为本人能力不足, 对一些高级的算法和数据结构理解不够通透, 所以也不作太多的深入的剖析.. demo都在我的Github中能找得到.

同样的, 通过最近面试实习生的机会, 把一些基础都捡起来, 巩固巩固, 同时如果能帮助到大家, 那也是极好的. 废话不多说, 入正题吧.

排序算法

算法 最优复杂度 最差复杂度 平均复杂度 稳定性
选择排序 O(n²) O(n²) O(n²) 不稳定
冒泡排序 O(n) O(n²) O(n²) 稳定
插入排序 O(n) O(n²) O(n²) 稳定
希尔排序 O(n) O(n²) O(n1.3) 不稳定
归并排序 O(nlog n) O(nlog n) O(nlog n) 稳定
快速排序 O(nlog n) O(n²) O(nlog n) 不稳定
堆排序 O(nlog n) O(nlog n) O(nlog n) 不稳定
基数排序 O(d(r+n)) O(d(n+rd)) O(d(r+n)) 稳定

ps : 基数排序的复杂度中, r代表关键字的基数, d代表位数, n代表关键字的个数. 也就是说, 基数排序不受待排序列规模的影响.

算法复杂度 : 这里表中指的是算法的时间复杂度, 一般由O(1), O(n), O(logn), O(nlogn), O(n²), ..., O(n!). 从左到右复杂度依次增大, 时间复杂度是指在多少时间内能够执行完这个算法, 常数时间内呢, 还是平方时间还是指数时间等等.
还有个概念叫空间复杂度, 这就指的是执行这个算法需要多少额外的空间. (源数组/链表所占的空间不算)

稳定性 : 算法的稳定性体现在执行算法之前, 若a = b, a在b的前面, 若算法执行完之后a依然在b的前面, 则这个算法是稳定的, 否则这个算法不稳定.

选择排序

原理 : 每次从无序区中找出最小的元素, 跟无序区的第一个元素交换

void selectSort(int array[], int count){

    for (int i = 0; i < count; i++) {
    
        // 最小元素的位置
        int index = i;
        // 找出最小的元素所在的位置
        for (int j = i + 1; j < count; j++) {
    
         if (array[j] < array[index]){
            index = j;
         }
    
        }
        // 交换元素
        int temp = array[index];
        array[index] = array[i];
        array[i] = temp;
    
    }
}

冒泡排序

原理 : 每次对比相邻两项的元素的大小, 不符合顺序则交换

void bubblingSort(int array[], int count){


    for (int i = 0; i < count; i++) {
    
        // 交换相邻的元素
        for (int j = 1; j < count - i; j++) {
    
            if (array[j] < array[j-1]){
                // 交换元素
                int temp = array[j-1];
                array[j-1] = array[j];
                array[j] = temp;
            }
    
        }
    }
}

插入排序

原理 : 每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子序列中的适当位置，直到全部记录插入完成为止。

void insertSort(int array[], int count){

    int i, j, k;

    for (i = 1; i < count ; i++) {

        for (j = i - 1; j >= 0; j--) { // 为a[i]在a[0, i-1]上找一个合适的位置
            if(array[j] < array[i]) break;
        }
    
        if (j != i-1) { // 找到了一个合适的位置j
        
            int temp = array[i];
            // 将比array[i]大的数据全部往后移
            for(k = i - 1; k > j; k--) {
                array[k+1] = array[k];
            }
            // 将array[i]放入合适的位置
            array[k+1] = temp;
        
        }

    }
}

希尔排序

其实就是分组插入排序, 也称为缩小增量排序. 比普通的插入排序拥有更高的性能.

算法思想 : 根据增量dk将整个序列分割成若干个子序列. 如dk = 3, 序列1, 7, 12, 5, 13, 22 就被分割成1, 5, 7, 13和12, 22, 在这几个子序列中分别进行直接插入排序, 然后依次缩减增量dk再进行排序, 直到序列中的元素基本有序时, 再对全体元素进行一次直接插入排序. (直接插入排序在元素基本有序的情况下效率很高)

void shellSort(int array[], int count){

    for (int dk = count / 2; dk > 0; dk = dk / 2) { // dk增量
    
        for (int i = 0; i < dk; i++) { // 直接插入排序
    
            for (int j = i + dk; j < count; j += dk) {
        
                if (array[j] < array[j - dk]) { // 如果相邻的两个元素, 后者比前者大, 则不用调整
                
                    int temp = array[j];
                    int k = j - dk;
                    while (k >= 0 && array[k] > temp) { // 每次while循环结束后, 保证把最小的插入到每组的最前面
                    
                        array[k + dk] = array[k];
                        k -= dk;
                    
                    }
                    // 每组第一个元素为最小的元素
                    array[k + dk] = temp;
                
                }
        
            }
    
        }
    
    }

}

归并排序

原理 : 归并排序是把序列递归地分成短序列，递归出口是短序列只有1个元素(认为直接有序)或者2个序列(1次比较和交换),然后把各个有序的段序列并成一个有序的长序列，不断合并直到原序列全部排好序。

void merge(int array[], int temp[], int start, int middle, int end) {
    // 将两个有序序列array[start, middle]和array[middle+1, end]进行合并

    int i = start, m = middle, j = middle + 1, n = end, k = 0;

    while(i <= m && j <= n) { // 哪个小就先插那个, 然后把temp下标和array插入位置的下标++
    
        if (array[i] <= array[j]) {
            temp[k++] = array[i++];
        } else {
            temp[k++] = array[j++];
        }
    
    }
    // 插完之后看谁没插完就继续插谁
    while(i <= m) temp[k++] = array[i++];
    while(j <= n) temp[k++] = array[j++];

    // 把temp的元素copy回array中
    for (int i = 0; i < k; i++) array[start + i] = temp[i];



}

void mSort(int array[], int temp[], int start, int end) {

    if (start < end) {
        int middle = (start + end) / 2;
        mSort(array, temp, start, middle); // 递归出来以后左边有序
        mSort(array, temp, middle + 1, end); // 右边有序
        merge(array, temp, start, middle, end); // 合并两个有序序列
    }

}

void mergeSort(int array[], int count){

    // 定义辅助数组
    int *temp = (int *)malloc(sizeof(array[0]) * count);
    // 开始进行归并排序
    mSort(array, temp, 0, count - 1);
    // 释放指针
    free(temp);

}

堆排序

大顶堆 : 父结点的键值总是大于或等于任何一个子节点的键值
小顶堆 : 父结点的键值总是小于或等于任何一个子节点的键值

算法思想 : 堆排序 = 构造堆 + 交换堆末尾元素与根结点 + 删除末尾结点 + 构造堆 + 交换....依次循环, 由于根结点必定是堆中最大(最小)的元素, 所以删除出来的元素序列也必定是升序(降序)的.

void minHeapFixdown(int array[], int i, int count) {

    int j, temp;

    temp = array[i];
    j = 2 * i + 1;
    while(j < count) {
        if (j + 1 < count && array[j+1] < array[j]) j++; // 找出较小的子节点
    
        if (array[j] >= temp) break; // 如果较小的子节点比父节点大, 直接返回
    
        array[i] = array[j]; // 设置父节点为较小节点
        i = j; // 调整的子节点作为新一轮的父节点
        j = 2 * i + 1; // 调整的子节点的子节点
    }

    array[i] = temp;
}

void heapSort(int array[], int count) {

    for (int i = (count - 1) / 2; i >= 0; i--) {
        // 构造小顶堆
        minHeapFixdown(array, i, count);
}

    for (int i = count - 1; i >= 1; i--) {
    
        // 交换根结点与最末节点
        int temp = array[i];
        array[i] = array[0];
        array[0] = temp;
    
        // 剩余的n-1个元素再次建立小顶堆
        minHeapFixdown(array, 0, i);
    
    }

}

快速排序

算法思想 : 先从数列中取出一个数作为基准数 -> 将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边 -> 再对左右区间重复第二步，直到各区间只有一个数

int quickSortPartition(int array[], int start, int end) {

    int i = start, j = end;
    // 默认第一个元素为哨兵
    int sentry = array[i];

    while (i < j) {
    
        // 从右往左找第一个小于哨兵的元素
        while (i < j && array[j] >= sentry) j--;
        // 找到了
        if (i < j) {
            array[i] = array[j];
            i++;
        }
    
        // 从左往右找第一个大于哨兵的元素
        while(i < j && array[i] <= sentry) i++;
        // 找到了
        if (i < j) {
            array[j] = array[i];
            j--;
        }
        
    }
    // 把哨兵放到i == j的位置上
    array[i] = sentry;

    // 返回哨兵的位置
    return i;
}

void quickSort(int array[], int start, int end) {

    if (start < end) {
    
        // 找出分界点
        int index = quickSortPartition(array, start, end);
        quickSort(array, start, index - 1); // 对分界点左边进行排序
        quickSort(array, index + 1, end); // 对分界点右边进行排序
    }

}

void quickSortEntry(int array[], int count) {
    quickSort(array, 0, count - 1);
}

基数排序

基数排序的算法复杂度不会因为待排序列的规模而改变. 基数排序又称为桶排序. 基数排序有3个重要概念 :

这里给个例子, 没有代码.

例如一组序列121 83 17 9 13

1. 先根据个位数排序
    121 83 13 17 9
2. 再根据十位数排序
    9 13 17 121 83
3. 再根据百位数排序
    9 13 17 83 121
4. 由于没有千位数, 所以算法结束

ps : 需要注意的是, 基数排序每一轮排序所采用的算法必须是稳定的排序算法, 
也就是说, 例如13和17的十位数均为1, 但是由于个位数排序的时候13是在17的前面的, 
所以十位数排序过后13也必须在17的前面.

查找算法

算法 最优复杂度 最差复杂度 平均复杂度
顺序查找 O(1) O(n) O(n)
折半查找 O(1) O(log n) O(log n)
哈希查找 O(1) O(1) O(1)

顺序查找

算法思想 : 顾名思义就是从数组的0坐标开始逐个查找对比.

int orderSearch(int array[], int num, int count) {
    int index = -1;

    for (int i = 0; i < count; i++) {
        if (array[i] == num) {
            index = i;
            break;
        }
    }
    return index;
}

折半查找

算法思想 : 在一个有序数组里, 先对比数组中间的数middle与要查找的数num的大小关系
- middle == num : 直接返回
- middle < num : 递归查找数组右半部分
- middle > num : 递归查找数组左半部分

int binarySearch(int array[], int num, int start, int end) {

    int index = -1;

    if (start <= end) {

        int middle = (start + end) / 2; // 数组中点
        if (array[middle] == num) {
            index = middle; // 找到了
            return index;
        }
        else if (array[middle] > num) {
            return binarySearch(array, num, start, middle - 1); // 查找数组左边
        } else if (array[middle] < num) {
            return binarySearch(array, num, middle + 1, end); // 查找数组右边
        }
    
    }

    return index;
}

哈希查找

哈希查找需要一张哈希表, 哈希表又称为散列法, 是高效实现字典的方法. 查找速度在O(1), 这说明无论你需要查找的数据量有多大, 他都能在常数时间内找到, 快得有点违背常理吧? 嘿嘿.

哈希表几个重要的概念 :

可以这么说, 哈希函数设计得越好, 冲突越少, 哈希表的效率就越高.

需要了解的名词

几种图论的算法

上一篇下一篇

猜你喜欢

热点阅读