排序算法（C ） – 此乃刘同学-记录生活

描述

介绍了常用的几种排序算法：冒泡排序、选择排序、插入排序、快排、希尔排序、归并排序、堆排
为什么后面两个没有加租？因为目前的我还没发熟练使用
后期如果有时间会出分析讲解视频

加油！愿祖国强盛😊😊😊

冒泡排序

冒泡排序原理

从第一个元素开始比较相邻的元素，如果顺序错误则调换顺序，继续往下一一对比，直到序列末尾。

冒泡排序分析

冒泡排序的核心就是：多趟排序

冒泡排序模板

/* 冒泡排序 ，升序排序为例 */
void BubbleSort(int *arr, int len) {
    int temp;   // 用于缓存交换的变量 两数交换，使用第三者

    for(int i = 0; i < len; i++)             /* 两两比较把最大的放到“最后一个位置” ，所以需要遍历n边*/
        for(int x = 0; x < len - 1; x++)    /* 两两比较，不能超出数组范围，所以x+1 和 x都不能超过len */
            if(arr[x] > arr[x+1])           /* 如果前面的数比后面的数大，则将两个数进行调换 */
            {
                temp = arr[x];              /* 进行交换 */
                arr[x] = arr[x+1];
                arr[x+1] = temp;
            }
}

冒泡排序时间复杂度

时间复杂度：O(N^2)

选择排序

选择排序原理

通过遍历数组，选出该数组中较大或者较小的，放在数组的起始位置，当遍历完整个数组时排序完成

选择排序分析

选择排序的核心就是多次选择

遍历整个数组，选择最小（最大）的一个数与第一个数进行交换；
其次，在第二位开始的范围中选择次小（大）的数与第二位进行交换……
直到最后一个数，经过N-1次遍历，就可以得到一个有序的数组

选择排序模板

/* 选择排序 ,降序排序为例 */
void SelectSort(int *arr, int len) {
    int max, temp;              //max用于存储最大的下标， temp是缓存交换数据
    for(int i = 0; i < len; i++) {          /* 从第i个数开始比较，选择到结尾最大的结果 */
        max = i;                            /* 假设最小的数就是开始的值 */
        for(int x = i; x < len; x++)        /* 从下一个数到结尾一一比对，选择大的进行替换 */
            if(arr[x] > arr[max]) {              /* 当前的数，比max下标的数大，进行替换 */
                max = x; 
            }
        temp = arr[i];                      /* 进行数据交换的操作 */
        arr[i] = arr[max];
        arr[max] = temp;  
    }
}

选择排序复杂度

时间复杂度：O(N^2)
空间复杂度：O(1)

插入排序

插入排序原理

将待排序的数，按照顺序插入到一个有序的数组中，直到所有记录都插入，那么就获得一个有序的数组

插入排序分析

插入排序的核心就是多趟选择插入

当插入第i个元素的时候，那么此时0……i-1数组之间是有序的数组
在有序数组中比较，选择合适的插入位置，将i元素插入
其后的元素向后移动一格。直到所有的数据都进行进入操作

插入排序模板

/* 插入排序 */
void InsertSort(int *arr, int len) {
    for(int i = 1; i < len; i++) {          /* 从下标为1 的数开始，与此前面的有序数组进行比较并插入到合适的位置 */
        int temp = arr[i];                  /* 缓存一下要插入的数，一定要缓存，否则会被覆盖掉 */
        int a;                              /* 要插入数的位置 */
        for(a = i-1; a >= 0; a--){          /* 从有序数组的后面开始遍历 */
            if(arr[a] > temp){              /* 比较的数比要插入的数大，那么插入的位置还在前面 */
                arr[a+1] = arr[a];          /* 如果比他大，就往后移，留出空位 */
            }else{                          /* 有序数组的数小于等于插入的数字了，那么就插入它上一个位置 */
                break;
            }
        }
        arr[a+1] = temp;                    /* 将数插入到比它小的下一个位置 */
    }
}

插入排序复杂度

时间复杂度：O(N^2)
空间复杂度：O(1)

快速排序算法

快速排序算法原理

快速排序就是将数组以一个节点，分为左右两部分，左右两部分数值分别小于或大于该节点
再对左右两边进行同样处理，最后得到一个有序的数组

快速排序分析

选取一个基准点，然后分别扫描数组的两端，设有两个“指针”指向起始和结束位置
先从一段开始，如果发现有元素比基准带你的数值小（大），则交换low和high的位置，然后从另一部分开始，发现元素大于（小于）基准点，则交换low和high的位置
如此循环，直到low>=high，然后把基准点放在high上，完成第一次排序
后续使用函数递归完成剩下的部分的排序

快速排序模板

/* 快速排序 */
void Quick_Sort(int *arr, int low, int high) {
    if (low >= high)    /* 递归结束条件 */
        return;  
    int low_num = low;
    int high_num = high;
    int temp = arr[low];            /* 取出基准元素 */
    while(low != high) {                                    /* 当前后节点重合时结束循环 */
        while (low < high && arr[high] >= temp) high--;     /* 从右向左找小于基准的元素 */
        arr[low] = arr[high];                               /* 将右指针的元素移动到左指针位置 */
        while (low < high && arr[low] <= temp) low++;       /* 从左向右找大于基准的元素 */
        arr[high] = arr[low];                               /* 将左指针的元素移动到右指针位置 */
    }
    arr[low] = temp;                /* 将基准元素放到正确位置 */
    Quick_Sort(arr, low_num, high-1);        /* 在对基准元素的左部分进行遍历 */
    Quick_Sort(arr, high+1, high_num);      /* 在对基准元素的右部分进行遍历 */
}

/* 快速排序入口 */
void Quick_Sort_Entry(int *arr, int len){
    Quick_Sort(arr, 0, len-1);     /* 进入快排函数 */
}

快速排序复杂度

时间复杂度O(n log n)
空间复杂度根据堆栈深度有关，最好情况O(log n)，最坏情况下为O(n)

希尔排序

希尔排序原理

希尔排序其实就是由插入排序衍生出来的，当一个升序的有序队列，需要改为降序数组的时候，那么此时使用插入排序的时间复杂度为n^2，那么选择插入排序效率就不合适了，此时就引入了希尔排序。

希尔排序分析

希尔排序就是在插入排序之前将数组做预处理。

我们把数组分为三组，对着三组进行插入排序，这是第一次预排序。
那么上面的数组为什么是分为3组呢？这就涉及一个名词“增量”——增量就是相聚多少个数的数据为一组，对这一组进行单独插入排序。
完成增量为3的排序，再进行增量为2的排序。

然后进行增量为1的插入排序

那么如何设置开始的增量呢？
这是希尔排序的核心，就是设置不同的增量序列来优化插入排序的性能。增量排序的选择对排序速度有显著影响。比较常用效果比较好的增量设定为size/3+1，size为数组长度。

希尔排序模块

/* 希尔排序 */
void ShellSort(int *arr, int len){
    int increa = len / 3 + 1;   /* 设置增量 */
    int temp;
    int count = 0;
    while (increa > 0) {                /* 增量为n，就要进行n次插入排序 */
        for(int i = increa; i < len; i++){               /* 对每组的数进行单独排序 */
            temp = arr[i];                  /* 缓存要插入的数据 */
            int j;
            for(j = i; j >= increa && arr[j - increa] > temp; j -= increa) { /* 插入排序 */
                arr[j] = arr[j - increa];
                count++;
            }
            arr[j] = temp;
        }
        increa = increa - 1;   /* 减少增量 */
    }
}

我们可是使用count来计算循环的次数，发现直接插入和希尔之间的效率，那么为什么呢？
如果有人这么问你，你可以回答“ 因为它大大的减少了数据挪动次数，在做预排序的时候它是以增量的跨度去挪动的，这就使一个数据更快的接近它的准确位置”

希尔排序复杂度

时间复杂度O(n^(1.3-2))
空间复杂度O(1)

归并排序算法（递归方式）

归并排序算法原理

归并排序是建立在归并操作上的一种稳定的排序算法，认识之前首先了解什么归并？
归并操作，即为将两个有序的数组合并为一个新的有序数组。即将已有序的子序列合并，得到完全有序的序列；若将两个有序表合并为一个有序表，称为二路合并

归并排序算法分析

首先将数组递归分治，将区间进行分解；将数据分割成两个数组，再分别将两个数组细分为两个数组，直到每个数组都是一个元素，这时候每个组都是有序数组了（只有一个数）
再将分割时候的“有序数组”进行排序，排成有序数组之后继续为上一个分割的数组合并，直到数组合并为原来的数组

我们在对分割的每组数组进行排序时，需要开辟一个临时数组空间，因为原地排序非常困难，很容易混乱，将排序的结果存放在临时数组，之后再拷贝回原数组

归并排序算法模板

/* 归并函数 */
void merge(int *arr, int l, int mid, int r) {
    int n1 = mid - l + 1;  // 左子数组的长度
    int n2 = r - mid;      // 右子数组的长度
    // 创建临时数组
    int *left = (int *)malloc(n1 * sizeof(int));
    int *right = (int *)malloc(n2 * sizeof(int));
    // 将数据拷贝到临时数组
    for (int i = 0; i < n1; i++)
        left[i] = arr[l + i];
    for (int j = 0; j < n2; j++)
        right[j] = arr[mid + 1 + j];
    // 归并临时数组到原数组
    int i = 0, j = 0, k = l;
    while (i < n1 && j < n2) {
        if (left[i] <= right[j]) {
            arr[k] = left[i];
            i++;
        } else {
            arr[k] = right[j];
            j++;
        }
        k++;
    }
    // 拷贝左子数组的剩余元素
    while (i < n1) {
        arr[k] = left[i];
        i++;
        k++;
    }
    // 拷贝右子数组的剩余元素
    while (j < n2) {
        arr[k] = right[j];
        j++;
        k++;
    }
    // 释放临时数组
    free(left);
    free(right);
}

/* 递归归并排序 */
void merge_sort_recursive(int *arr, int l, int r) {
    if (l < r) {
        int mid = l + (r - l) / 2
        // 递归排序左半部分
        merge_sort_recursive(arr, l, mid);
        // 递归排序右半部分
        merge_sort_recursive(arr, mid + 1, r);
        // 合并两部分
        merge(arr, l, mid, r);
    }
}

/* 归并排序入口 */
void merge_sort(int *arr, int n) {
    merge_sort_recursive(arr, 0, n - 1);
}

归并排序算法复杂度

时间复杂度
最坏情况O(NlogN)
最好情况O(NlogN)
平均情况O(NlogN)
空间复杂度
0(n)

堆排序算法

堆排序原理

堆是一种数据结构：
堆是一颗完全二叉树
堆中每个节点的值必须大于等于（小于等于）其子节点的值

堆排序是一种基于二叉堆数据结构的排序算法，堆排序一般用于数组排序

堆排序分析

堆排序的核心就是利用堆的性质来排序。太复杂了，我能力不足以我灵活使用这样的排序算法😊，真感兴趣的话可以去查一下，等我有机会好好整理一下

堆排序模板

/* Function: 交换交换根节点和数组末尾元素的值*/
void Swap(int *heap, int len) {
    int temp;
  
    temp = heap[0];
    heap[0] = heap[len-1];
    heap[len-1] = temp;
}
  
/* Function: 构建大顶堆 */
void BuildMaxHeap(int *heap, int len) {
    int i,temp;
    for (i = len/2-1; i >= 0; i--) {
        if ((2*i+1) < len && heap[i] < heap[2*i+1]) {  /* 根节点大于左子树 */
            temp = heap[i];
            heap[i] = heap[2*i+1];
            heap[2*i+1] = temp;
            /* 检查交换后的左子树是否满足大顶堆性质 如果不满足 则重新调整子树结构 */
            if ((2*(2*i+1)+1 < len && heap[2*i+1] < heap[2*(2*i+1)+1]) || (2*(2*i+1)+2 < len && heap[2*i+1] < heap[2*(2*i+1)+2])) {
                BuildMaxHeap(heap, len);
            }
        }
        if ((2*i+2) < len && heap[i] < heap[2*i+2]) {  /* 根节点大于右子树 */
            temp = heap[i];
            heap[i] = heap[2*i+2];
            heap[2*i+2] = temp;
            /* 检查交换后的右子树是否满足大顶堆性质 如果不满足 则重新调整子树结构 */
            if ((2*(2*i+2)+1 < len && heap[2*i+2] < heap[2*(2*i+2)+1]) || (2*(2*i+2)+2 < len && heap[2*i+2] < heap[2*(2*i+2)+2])) {
                BuildMaxHeap(heap, len);
            }
        }
    }
}

堆排序复杂度

时间复杂度O(n log n)
空间复杂度O(1)

验证代码

/* 
 * 排序常用算法
 */
#include "stdio.h"
#include "stdlib.h"

/* 冒泡排序 ，升序排序为例 */
void BubbleSort(int *arr, int len) {
    int temp;   // 用于缓存交换的变量 两数交换，使用第三者

    for(int i = 0; i < len; i++)             /* 两两比较把最大的放到“最后一个位置” ，所以需要遍历n边*/
        for(int x = 0; x < len - 1; x++)    /* 两两比较，不能超出数组范围，所以x+1 和 x都不能超过len */
            if(arr[x] > arr[x+1])           /* 如果前面的数比后面的数大，则将两个数进行调换 */
            {
                temp = arr[x];              /* 进行交换 */
                arr[x] = arr[x+1];
                arr[x+1] = temp;
            }
}

/* 选择排序 ,降序排序为例 */
void SelectSort(int *arr, int len) {
    int max, temp;              //max用于存储最大的下标， temp是缓存交换数据
    for(int i = 0; i < len; i++) {          /* 从第i个数开始比较，选择到结尾最大的结果 */
        max = i;                            /* 假设最小的数就是开始的值 */
        for(int x = i; x < len; x++)        /* 从下一个数到结尾一一比对，选择大的进行替换 */
            if(arr[x] > arr[max]) {              /* 当前的数，比max下标的数大，进行替换 */
                max = x; 
            }
        temp = arr[i];                      /* 进行数据交换的操作 */
        arr[i] = arr[max];
        arr[max] = temp;  
    }
}

/* 插入排序 */
void InsertSort(int *arr, int len) {
    int count;
    for(int i = 1; i < len; i++) {          /* 从下标为1 的数开始，与此前面的有序数组进行比较并插入到合适的位置 */
        int temp = arr[i];                  /* 缓存一下要插入的数，一定要缓存，否则会被覆盖掉 */
        int a;                              /* 要插入数的位置 */
        for(a = i-1; a >= 0; a--){          /* 从有序数组的后面开始遍历 */
            if(arr[a] > temp){              /* 比较的数比要插入的数大，那么插入的位置还在前面 */
                arr[a+1] = arr[a];          /* 如果比他大，就往后移，留出空位 */
            }else{                          /* 有序数组的数小于等于插入的数字了，那么就插入它上一个位置 */
                break;
            }
            count ++;
        }
        arr[a+1] = temp;                    /* 将数插入到比它小的下一个位置 */
    }
}

/* 希尔排序 */
void ShellSort(int *arr, int len){
    int increa = len / 3 + 1;   /* 设置增量 */
    int temp;
    int count = 0;
    while (increa > 0) {                /* 增量为n，就要进行n次插入排序 */
        for(int i = increa; i < len; i++){               /* 对每组的数进行单独排序 */
            temp = arr[i];                  /* 缓存要插入的数据 */
            int j;
            for(j = i; j >= increa && arr[j - increa] > temp; j -= increa) { /* 插入排序 */
                arr[j] = arr[j - increa];
                count++;
            }
            arr[j] = temp;
        }
        increa = increa - 1;   /* 减少增量 */
    }
}

/* 快速排序 */
void Quick_Sort(int *arr, int low, int high) {
    if (low >= high)    /* 递归结束条件 */
        return;  
    int low_num = low;
    int high_num = high;
    int temp = arr[low];            /* 取出基准元素 */
    while(low != high) {                                    /* 当前后节点重合时结束循环 */
        while (low < high && arr[high] >= temp) high--;     /* 从右向左找小于基准的元素 */
        arr[low] = arr[high];                               /* 将右指针的元素移动到左指针位置 */
        while (low < high && arr[low] <= temp) low++;       /* 从左向右找大于基准的元素 */
        arr[high] = arr[low];                               /* 将左指针的元素移动到右指针位置 */
    }
    arr[low] = temp;                /* 将基准元素放到正确位置 */
    Quick_Sort(arr, low_num, high-1);        /* 在对基准元素的左部分进行遍历 */
    Quick_Sort(arr, high+1, high_num);      /* 在对基准元素的右部分进行遍历 */
}

/* 快速排序入口 */
void Quick_Sort_Entry(int *arr, int len){
    Quick_Sort(arr, 0, len-1);     /* 进入快排函数 */
}

/* 归并函数 */
void merge(int *arr, int l, int mid, int r) {
    int n1 = mid - l + 1;  // 左子数组的长度
    int n2 = r - mid;      // 右子数组的长度
    // 创建临时数组
    int *left = (int *)malloc(n1 * sizeof(int));
    int *right = (int *)malloc(n2 * sizeof(int));
    // 将数据拷贝到临时数组
    for (int i = 0; i < n1; i++)
        left[i] = arr[l + i];
    for (int j = 0; j < n2; j++)
        right[j] = arr[mid + 1 + j];
    // 归并临时数组到原数组
    int i = 0, j = 0, k = l;
    while (i < n1 && j < n2) {
        if (left[i] <= right[j]) {
            arr[k] = left[i];
            i++;
        } else {
            arr[k] = right[j];
            j++;
        }
        k++;
    }
    // 拷贝左子数组的剩余元素
    while (i < n1) {
        arr[k] = left[i];
        i++;
        k++;
    }
    // 拷贝右子数组的剩余元素
    while (j < n2) {
        arr[k] = right[j];
        j++;
        k++;
    }
    // 释放临时数组
    free(left);
    free(right);
}

/* 递归归并排序 */
void merge_sort_recursive(int *arr, int l, int r) {
    if (l < r) {
        int mid = l + (r - l) / 2
        // 递归排序左半部分
        merge_sort_recursive(arr, l, mid);
        // 递归排序右半部分
        merge_sort_recursive(arr, mid + 1, r);
        // 合并两部分
        merge(arr, l, mid, r);
    }
}

/* 归并排序入口 */
void merge_sort(int *arr, int n) {
    merge_sort_recursive(arr, 0, n - 1);
}

int main() {
    int a[] = { 29,10,14,37,12,6,32 };
	int sz = sizeof(a) / sizeof(a[0]);   // 获取数组的大小

    // BubbleSort(a, sz);           // 冒泡排序
    // SelectSort(a, sz);           // 选择排序
    // InsertSort(a, sz);           // 插入排序
    // ShellSort(a, sz);            // 希尔排序
    // Quick_Sort_Entry(a, sz);     // 快速排序
    // merge_sort(a, sz);           // 归并排序
    
    for(int i = 0; i < sz; i++) {
        printf("%d ",a[i]);
    }
    printf("\n");

    return 0;
}

描述