日志

C语言实现九大排序算法

 来源    2021-01-14    1  
  • C语言实现九大排序算法
    • 直接插入排序
    • 折半插入排序
    • 希尔排序
    • 冒泡排序
    • 快速排序
    • 直接选择排序
    • 堆排序
    • 归并排序
    • 基数排序

C语言实现九大排序算法

直接插入排序

将数组分为两个部分,一个是有序部分,一个是无序部分。从无序部分中依次取出元素插入到有序部分中。过程就是遍历有序部分,实现起来比较简单。

#include <stdio.h>

void insertion_sort(int arr[], int array_length) {
    for (int i = 0; i < array_length; ++i) {
        int data = arr[i];
        int j = 0;
        while (arr[j] < arr[i]) {
            j++;
        }
        for (int k = i; k >= j + 1; k--) {
            arr[k] = arr[k - 1];
        }
        arr[j] = data;
    }
}

void print_array(int arr[], int array_length) {
    for (int i = 0; i < array_length; ++i) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

int main() {
    int arr[7] = {8, 2, 6, 0, 5, 7, 4};
    insertion_sort(arr, 7);
    print_array(arr, 7);
    return 0;
}

折半插入排序

折半插入再直接插入上有改进,用折半搜索替换遍历数组,在数组长度大时能够提升查找性能。其本质还是从无序部分取出元素插入到有序部分中。

#include <stdio.h>

void binary_insertion_sort(int arr[], int array_length) {
    int i, j, low = 0, high = 0, mid;
    int temp = 0;
    for (i = 1; i < array_length; i++) {
        low = 0;
        high = i - 1;
        temp = arr[i];
        while (low <= high) {
            mid = (low + high) / 2;
            if (arr[mid] > temp) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        for (j = i; j > low; j--) {
            arr[j] = arr[j - 1];
        }
        arr[low] = temp;
    }
}

void print_array(int arr[], int array_length) {
    for (int i = 0; i < array_length; ++i) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

int main() {
    int brr[5] = {2, 6, 0, 5, 7};
    binary_insertion_sort(brr, 5);
    print_array(brr, 5);
    return 0;
}

希尔排序

希尔排序的核心就是根据步长分组,组内进行插入排序。关于步长的选取,第一次步长取元素的个数,后面每次取原来步长的一半。

希尔排序属于插入排序的一种。

#include <stdio.h>

void shell_sort(int arr[], int array_length) {
    int step = array_length / 2;
    while (step >= 1) {
        for (int i = 0; i < array_length; i += step) {
            int data = arr[i];
            int j = 0;
            while (arr[j] < arr[i]) {
                j++;
            }
            for (int k = i; k >= j + 1; k--) {
                arr[k] = arr[k - 1];
            }
            arr[j] = data;
        }
        step = step / 2;
    }
}

void print_array(int arr[], int array_length) {
    for (int i = 0; i < array_length; ++i) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

int main() {
    int crr[10] = {73, 22, 93, 43, 55, 14, 28, 65, 39, 81};
    shell_sort(crr, 10);
    print_array(crr, 10);
    return 0;
}

冒泡排序

冒泡的特点是两两交换。通过交换把最大的元素交换到后面去了,每次循环遍历都把无序部分最大的“沉”到后面去。小数上“浮”和大数下“沉”其实没有差别,都能实现冒泡。

#include <stdio.h>

void bubble_sort(int arr[], int array_length) {
    for (int i = 0; i < array_length - 1; ++i) {
        for (int j = 0; j < array_length - i - 1; ++j) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

void print_array(int arr[], int array_length) {
    for (int i = 0; i < array_length; ++i) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

int main() {
    int drr[7] = {8, 2, 6, 0, 5, 7, 4};
    bubble_sort(drr, 7);
    print_array(drr, 7);
    return 0;
}

快速排序

快排的精髓在于选定一个标准(通常选数组的第一个元素),然后将所有元素根据标准分为小于和大于两个部分,然后这两个部分再选取标准,继续递归下去,不难想象最终排序结果是整体有序的。

#include <stdio.h>

int getStandard(int arr[], int low, int high) {
    int flag = arr[low];
    while (low < high) {
        while (low < high && arr[high] >= flag) {
            high--;
        }
        if (low < high) {
            arr[low] = arr[high];
        }
        while (low < high && arr[low] <= flag) {
            low++;
        }
        if (low < high) {
            arr[high] = arr[low];
        }
    }
    arr[low] = flag;
    return low;
}

void quick_sort(int arr[], int low, int high) {
    if (low < high) {
        int pos = getStandard(arr, low, high);
        quick_sort(arr, low, pos - 1);
        quick_sort(arr, pos + 1, high);
    }
}

void print_array(int arr[], int array_length) {
    for (int i = 0; i < array_length; ++i) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

int main() {
    int err[10] = {73, 22, 93, 43, 55, 14, 28, 65, 39, 81};
    quick_sort(err, 0, 9);
    print_array(err, 10);
    return 0;
}

直接选择排序

如其名,直接选择一个最小的放到最前面,但是遍历往往导致效率较低。

#include <stdio.h>

void select_sort(int arr[], int array_length) {
    for (int i = 0; i < array_length; ++i) {
        int min_pos = i;
        for (int j = i; j < array_length; ++j) {
            if (arr[min_pos] > arr[j])
                min_pos = j;
        }
        int temp = arr[min_pos];
        arr[min_pos] = arr[i];
        arr[i] = temp;
    }
}

void print_array(int arr[], int array_length) {
    for (int i = 0; i < array_length; ++i) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

int main() {
    int frr[7] = {8, 2, 6, 0, 5, 7, 4};
    select_sort(frr, 7);
    print_array(frr, 7);
    return 0;
}

堆排序

将数组转换为一颗完全二叉树。任意一个父节点大于它的子节点,这样的完全二叉树叫做大顶堆;与之相反的,任意一个父节点小于它的子节点,这样的完全二叉树叫做小顶堆。

堆排序的精华就在于把元素个数为n的完全二叉树转换为大顶堆,然后把堆顶和最后一个元素交换,此时产生了一个元素个数为n-1的完全二叉树,然后再转换为大顶堆,继续把堆顶和最后一个元素交换。循环往复就实现了排序。其实质还是选择排序,每次选出一个最大的,和最后一个交换,不过完全二叉树中选最大元素比遍历数组会快很多。

#include <stdio.h>

void heap_adjust(int arr[], int n) {
    for (int i = n / 2; i >= 1; i--) {
        if (arr[i - 1] < arr[2 * i - 1]) {
            int temp = arr[i - 1];
            arr[i - 1] = arr[2 * i - 1];
            arr[2 * i - 1] = temp;
        }
        if (arr[i - 1] < arr[2 * i] && (2 * i) < n) {
            int temp = arr[i - 1];
            arr[i - 1] = arr[2 * i];
            arr[2 * i] = temp;
        }
    }
}

void heap_sort(int arr[], int array_length) {
    int n = array_length;
    do {
        heap_adjust(arr, n);
        int temp = arr[0];
        arr[0] = arr[n - 1];
        arr[n - 1] = temp;
    } while (n--);
}

void print_array(int arr[], int array_length) {
    for (int i = 0; i < array_length; ++i) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

int main() {
    int grr[7] = {8, 2, 6, 0, 5, 7, 4};
    heap_sort(grr, 7);
    print_array(grr, 7);
    return 0;
}

归并排序

归并的思想在于对复杂问题的分治,打散到最小长度后然后再进行合并操作。假设有两个数组A、B,指针i指向A的头部,指针j指向B的头部,两边同时进行遍历,找到一个小的就放到数组里面,对应指针后移一位,这样就能够保证合并后的数组是有序的。

#include <stdio.h>
#include <malloc.h>

void merge(int arr[], int start, int mid, int end) {
    int *new_array = (int *) malloc(sizeof(int) * (end - start + 1));
    int i = start;
    int j = mid + 1;
    int k = 0;
    while (i <= mid && j <= end) {
        if (arr[i] < arr[j]) {
            new_array[k++] = arr[i++];
        } else {
            new_array[k++] = arr[j++];
        }
    }
    while (i <= mid) {
        new_array[k++] = arr[i++];
    }
    while (j <= end) {
        new_array[k++] = arr[j++];
    }
    for (int l = 0; l < k; ++l) {
        arr[start + l] = new_array[l];
    }
    free(new_array);
}

void merge_sort(int arr[], int start, int end) {
    int mid = (start + end) / 2;
    if (start >= end) {
        return;
    }
    merge_sort(arr, start, mid);
    merge_sort(arr, mid + 1, end);
    merge(arr, start, mid, end);
}

void print_array(int arr[], int array_length) {
    for (int i = 0; i < array_length; ++i) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

int main() {
    int hrr[10] = {73, 22, 93, 43, 55, 14, 28, 65, 39, 81};
    merge_sort(hrr, 0, 9);
    print_array(hrr, 10);
    return 0;
}

基数排序

先按照个位排序将所有数字分配到0-9这10个桶里面,然后再按照桶的顺序收集起来;再按照十位排序,同样的步骤……

基础排序的本质是对每一位进行排序,对每一位进行排序后就能保证这一个数整体的大小是按照顺序排列的。

#include <stdio.h>
#include <malloc.h>

int get_num(int number, int pos) {
    int num = 0;
    while (pos--) {
        num = number % 10;
        number = number / 10;
    }
    return num;
}

void radix_sort(int arr[], int array_length) {
    int *bucket[10];
    for (int i = 0; i < 10; ++i) {
        bucket[i] = (int *) malloc(sizeof(int) * array_length + 1);
        bucket[i][0] = 0;//桶的第一位保存桶中元素个数
    }
    for (int b = 1; b <= 31; ++b) {
        for (int i = 0; i < array_length; ++i) {
            int num = get_num(arr[i], b);//计算每个位上的数字(个位、十位、百位...)
            int index = ++bucket[num][0];//计算下标
            bucket[num][index] = arr[i];//保存到桶中
        }
        for (int i = 0, k = 0; i < 10; i++) {
            for (int j = 1; j <= bucket[i][0]; ++j) {
                arr[k++] = bucket[i][j];//从桶里面按顺序取出来
            }
            bucket[i][0] = 0;//下标清零
        }
    }
}

void print_array(int arr[], int array_length) {
    for (int i = 0; i < array_length; ++i) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

int main() {
    int irr[10] = {73, 22, 93, 43, 55, 14, 28, 65, 39, 81};
    radix_sort(irr, 10);
    print_array(irr, 10);
    return 0;
}
相关文章
九大排序算法汇总
日志一.算法说明 数据结构中经常需要用到各种排序算法,故参考网上代码,将九个排序算法整合在一起,以便日后使用.算法运行时,可以选择所要采用的排序算法,并会输出每一趟的排序过程,更利于对排序算法的理解. 二 ...
1
九大排序算法的Java实现
日志1.冒泡排序 package Sort; import java.util.Arrays; public class BubbleSort { public static void main(Stri ...
1
十大排序算法--多图预警
日志十大排序算法 简单的排序算法 Θ(n^2) 插入排序 动画演示 enter description here 原理 将数组看成两部分,一部分为已排序好的数组,后面的部分为未排序数组,每次从后面的数组中 ...
1
十大排序算法
日志前言 你好,我是小赵,最近在系统的整理算法方面的知识,当你度过了新手阶段,想要成为牛逼的技术达人,算法是必须要掌握的东西,而算法中的排序,是每个程序员都绕不开的基本功,重要性就没必要多说了. 在工作之 ...
1
Java学习笔记之十一 Java中常用的8大排序算法详解总结
日志分类: 1)插入排序(直接插入排序.希尔排序) 2)交换排序(冒泡排序.快速排序) 3)选择排序(直接选择排序.堆排序) 4)归并排序 5)分配排序(基数排序) 所需辅助空间最多:归并排序 所需辅助空 ...
4
Java程序员必须掌握的8大排序算法
日志8种排序之间的关系: 1, 直接插入排序 (1)基本思想:在要排序的一组数中,假设前面(n-1)[n>=2] 个数已经是排 好顺序的,现在要把第n个数插到前面的有序数中,使得这n个数 也是排好顺 ...
2
Java常用排序算法/程序员必须掌握的8大排序算法
日志转载: Java常用排序算法/程序员必须掌握的8大排序算法 分类: 1)插入排序(直接插入排序.希尔排序) 2)交换排序(冒泡排序.快速排序) 3)选择排序(直接选择排序.堆排序) 4)归并排序 5) ...
2
十大排序算法,看这篇就够了(附完整代码/动图/优质文章)
日志说明 十大排序算法可以说是每个程序员都必须得掌握的了,花了一天的时间把代码实现且整理了一下,为了方便大家学习,我把它整理成一篇文章,每种算法会有简单的算法思想描述,为了方便大家理解,我还找来了动图演示 ...
1
8大排序算法图文讲解
日志排序有内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问外存. 我们这里说说八大排序就是内部排序.          ...
2
面试——8大排序算法图文讲解
日志排序算法可以分为内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问外存. 常见的内部排序算法有:插入排序.希尔排序. ...
2
十大排序算法以及关系
日志0.算法概述 0.1 算法分类 十种常见排序算法可以分为两大类: 非线性时间比较类排序:通过比较来决定元素间的相对次序,由于其时间复杂度不能突破O(nlogn),因此称为非线性时间比较类排序. 线性时 ...
1
Algorithm --> 十大排序算法
日志十大排序算法 主要排序法有:  一.冒泡( Bubble)排序—— 相邻交换  二.选择排序 ——每次最小/ 大排在相应的位置  三.插入排序 ——将下一个插入已排好的序列中  四.壳( Shell) ...
2
JS-几大排序算法(更新中...)
日志关于排序都会讲的名词:(我自己的理解) 时间复杂度: 指排序过程中,程序消耗的时间. 空间复杂度: 指排序过程中,程序所消耗内存的大小. 稳定: 如果两个值相等,a和b,a=b且a在b位置的左边,排序 ...
1
10 大排序算法总结
日志前言 查找和排序算法是算法的入门知识,其经典思想可以用于很多算法当中.因为其实现代码较短,应用较常见.所以在面试中经常会问到排序算法及其相关的问题.但万变不离其宗,只要熟悉了思想,灵活运用也不是难事. ...
2
用 C 语言描述几种排序算法
日志排序算法是最基本且重要的一类算法,本文基于 VS2017,使用 C 语言来实现一些基本的排序算法.  一.选择排序 选择排序,先找到数组中最小的元素,然后将这个元素与数组的第一个元素位置互换(如果第一 ...
1
JS十大排序算法
日志十大经典算法排序总结对比 一张图概括: 主流排序算法概览 名词解释: n: 数据规模k:“桶”的个数In-place: 占用常数内存,不占用额外内存Out-place: 占用额外内存稳定性:排序后2个 ...
3
python 下的数据结构与算法---6:6大排序算法
日志顶先最后推荐:哈哈,意思是放到顶部强调其重要性,但是应该我总结的六种算法看完了后再看的一篇醍醐灌顶的文章 一:冒泡排序(Bubble Sort) 原理:假设有n个数,第一轮时:从第一个元素开始,与相邻 ...
1
8大排序算法的java实现--做个人收藏
日志      排序算法分为内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因为数据量太大,一次不能容纳全部的排序记录,在排序过程中需要访问外存.这里只讨论内部排序,常见的内部排序算法 ...
1
十大排序算法之(四)——插入排序
日志#1,概念 有一个已经有序的数据序列,要求在这个已经排好的数据序列中插入一个数,但要求插入后此数据序列仍然有序,这个时候就要用到一种新的排序方法——插入排序法,插入排序的基本操作就是将一个数据插入到已 ...
1
十大排序算法之(三)——选择排序
日志#1,选择排序简介 选择排序(Selection sort)是一种简单直观的排序算法.它的工作原理是每一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,直到全部待排序的数据元 ...
1