首页 算法

# 算法分类

img

  • 比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破 O (nlogn)，因此也称为非线性时间比较类排序。
  • 非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此也称为线性时间非比较类排序。

# 算法比较

img

稳定排序算法：会让原本有相等键值的纪录维持相对次序。也就是如果一个排序算法是稳定的，当有两个相等键值的纪录 R 和 S，且在原本的列表中 R 出现在 S 之前，在排序过的列表中 R 也将会是在 S 之前。

# 算法实现分析

# 1、冒泡排序（Bubble Sort）

冒泡排序（英语：Bubble Sort）又称为泡式排序，是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢 “浮” 到数列的顶端。

# 1.1 执行流程：

  • 比较相邻的元素。如果第一个比第二个大，就交换他们两个；
  • 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数；
  • 针对所有的元素重复以上的步骤，除了最后一个；
  • 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

# 1.2 动图演示：

img

# 1.3 代码实现：

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

# 2、直接选择排序（Straight Selection sort）

下称选择排序

选择排序（Selection Sort）是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

# 2.1 执行流程：

  • 初始状态：无序区为 R [1..n]，有序区为空；
  • 第一趟：在无序区 R [1..n] 中选出最小元素，将他 R [1] 交换，R [1] 为有效区；
  • 第二趟：在无序区 R [2..n] 中选出最小元素，将他 R [1] 交换，R [1..2] 为有效区；
  • 第 n-1 趟：在无序区 R [n-1..n] 中选出最小元素，将他 R [n-1] 交换，R [1..n-1] 为有效区；
  • n-1 趟结束，区间 R [1..n] 中记录按递增有序排列。

# 2.2 动图演示：

img

# 2.3 代码实现：

void Selection_Sort(int *arr, int len)
{
    int i, j, k, temp;
    for (i = 0; i < len - 1; i++) {
        k = i;
        for (j = i + 1; j < len; j++)
            if (arr[j] < arr[k])
                k = j;
        if(k != i){
            temp = arr[k];
            arr[k] = arr[i];
            arr[i] = temp;	
        }
    }
}

# 3、直接插入排序（Straight Insertion Sort）

下称插入排序

插入排序（英语：Insertion Sort）是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用 in-place 排序（即只需用到 {O (1)} 的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

# 3.1 执行流程：

  • 从第一个元素开始，该元素可以认为已经被排序
  • 取出下一个元素，在已经排序的元素序列中从后向前扫描
  • 如果该元素（已排序）大于新元素，将该元素移到下一位置
  • 重复步骤 3，直到找到已排序的元素小于或者等于新元素的位置
  • 将新元素插入到该位置后
  • 重复步骤 2~5

# 3.2 动图演示：

img

# 3.3 代码实现：

void Insertion_Sort(int *arr, int len)    
{    
    int i, j, temp;    
    for (i = 1; i < len; i++)
        if (arr[i] < arr[i-1]) {    
            temp = arr[i];    
            for (j = i - 1; j >= 0 && arr[j] > temp; j--)
                arr[j+1] = arr[j];
            arr[j+1] = temp;    
        }
}

# 4、希尔排序（Shell Sort）

希尔排序（Shell Sort），也称递减增量排序算法，是直接插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法。

希尔排序是基于直接插入排序的以下两点性质而提出改进方法的：

  • 插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率
  • 但直接插入排序一般来说是低效的，因为直接插入排序每次只能将数据移动一位

# 4.1 执行流程：

  • 取增量，一般取数组长度 / 2；
  • 按增量取得子序列，对子序列进行插入排序；
  • 将增量递减，重复 1、2 步骤；
  • 直至增量均为 0，数列已经排好序。

img

# 4.2 动图演示：

img

# 4.3 代码实现：

void Shell_Sort(int *arr, int len) {
    int gap, i, j;
    int temp;
    for (gap = len >> 1; gap > 0; gap >>= 1)
        for (i = gap; i < len; i++) {
            temp = arr[i];
            for (j = i - gap; j >= 0 && arr[j] > temp; j -= gap)
                arr[j + gap] = arr[j];
            arr[j + gap] = temp;
        }
}

# 5、二路归并排序（Two-way Merge Sort）

下称归并排序

归并排序（Merge sort）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。

作为一种典型的分而治之思想的算法应用，归并排序的实现由两种方法：

  • 自上而下的递归（所有递归的方法都可以用迭代重写，所以就有了第 2 种方法）；
  • 自下而上的迭代。

# 5.1 执行流程（以递归过程为例）：

  • 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；
  • 设定两个指针，最初位置分别为两个已经排序序列的起始位置；
  • 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；
  • 重复步骤 3 直到某一指针达到序列尾；
  • 将另一序列剩下的所有元素直接复制到合并序列尾。

总执行分解图：

img

合并过程如下（以第 2 趟归并为例）：

img

# 5.2 动图演示：

img

# 5.3 代码实现：

#define MIN(x,y)     ((x) < (y) ? (x) : (y))
void Merge_Sort(int *arr, int len) {
    int *a = arr;
    int *b = (int *) malloc(len * sizeof(int));
    int seg, start;
    
    for (seg = 1; seg < len; seg += seg) {
        for (start = 0; start < len; start += seg * 2) {
            int low = start, mid = MIN(start + seg, len), high = MIN(start + seg * 2, len);
            int k = low;
            int start1 = low, end1 = mid;
            int start2 = mid, end2 = high;
            while (start1 < end1 && start2 < end2)
                b[k++] = a[start1] < a[start2] ? a[start1++] : a[start2++];
            while (start1 < end1)
                b[k++] = a[start1++];
            while (start2 < end2)
                b[k++] = a[start2++];
        }
        int *temp = a;
        a = b;
        b = temp;
    }
    if (a != arr) {
        int i;
        for (i = 0; i < len; i++)
            b[i] = a[i];
        b = a;
    }
    free(b);
}
# 6、快速排序（Quick Sort）
快速排序（英语：Quick Sort），又称分区交换排序（partition-exchange sort），简称快排，是对冒泡排序的一种改进，亦是分而治之思想在排序算法上的典型应用。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列的目的。
# 6.1 执行流程：
快速排序使用分治法（Divide and conquer）策略来把一个序列（list）分为较小和较大的 2 个子序列，然后递归地排序两个子序列。
  • 从数列中挑出一个元素，称为 “基准”（pivot）;
  • 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
  • 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序；
img
递归的最底部情形，是数列的大小是零或一，也就是永远都已经被排序好了。虽然一直递归下去，但是这个算法总会退出，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。
# 6.2 动图演示：
img
# 6.3 代码实现：
void Quick_Sort(int *arr, int low, int high)
{
    int i = low;
    int j = high;
    int pivot = arr[i];
    if(low > high) {
        return ;
    }
    while(i < j) {
        while((arr[j] >= pivot) && (i < j)) {
            j--;
        }
        arr[i] = arr[j];
        while((arr[i] <= pivot) && (i < j)) {
            i++;
        }
        arr[j]= arr[i];
    }
    arr[i] = pivot;
    Quick_Sort(arr, low, i-1);
    Quick_Sort(arr, j+1, high);
}
# 7、堆排序（Heap Sort）
堆排序（英语：Heap Sort）是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆的性质：即子节点的键值或索引总是小于（或者大于）它的父节点。
img
# 7.1 执行流程：
  • 将无序序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆；
  • 将堆顶元素与末尾元素交换，将最大元素 "沉" 到数组末端；
  • 重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整 + 交换步骤，直到整个序列有序。
假设给定无序序列结构如下（以大顶堆为例）：
img
1) 构造大顶堆
a. 从最后一个非叶子结点开始，从左至右，从下至上进行调整。叶结点自然不用调整，第一个非叶子结点 arr.length/2-1=5/2-1=1，也就是下面的 6 结点；在 [6, 5, 9] 这个小堆里边，父节点 97 最大，所以 6 和 9 交换。
img
b. 找到第二个非叶节点 4，由于 [4, 9, 8] 中 9 元素最大，4 和 9 交换。
img
c. 这时，交换导致了子根 [4, 5, 6] 结构混乱，继续调整，在 [4, 5, 6] 这个小堆里边，父节点 6 最大，所以 4 和 6 交换。
img
至此，一个无序序列已经构造成一个大顶堆。
2) 堆排序
a. 将堆顶元素 9 和末尾元素 4 进行交换
img
b. 重新调整结构，使其继续满足堆定义
img
c. 再将堆顶元素 8 与末尾元素 5 进行交换，得到第二大元素 8
img
d. 后续过程，继续进行调整，交换，如此反复进行，最终使得整个序列有序
img
# 7.2 动图演示：
img
# 7.3 代码实现：
void swap(int *a, int *b)
{
    int temp = *b;
    *b = *a;
    *a = temp;
}
void Heapify(int *arr, int start, int end)
{
#if 1
    int i, temp;
    temp = arr[start];
    for (i = 2*start + 1; i < end; i = 2*i + 1) {// 左孩子 2*i + 1，右孩子 2*i + 2
        if (i + 1 < end && arr[i] < arr[i+1]) {// 如果左子结点小于右子结点，i 指向右子结点
            i++;
        }
        if (temp < arr[i]) {
            arr[start] = arr[i];// 将根节点设置为子节点的较大值
            start = i;// 继续往下
        } else
            break;// 已经满足大根堆
    }
    arr[start] = temp;// 将 temp 值放到最终的位置
#else
    // 建立父節點指標和子節點指標
    int dad = start;
    int son = dad * 2 + 1;
    while (son < end) { // 若子節點指標在範圍內才做比較
        if (son + 1 < end && arr[son] < arr[son + 1]) // 先比較兩個子節點大小，選擇最大的
            son++;
        if (arr[dad] >= arr[son]) // 如果父節點大於子節點代表調整完畢，直接跳出函數
            return;
        else { // 否則交換父子內容再繼續子節點和孫節點比較
            swap(&arr[dad], &arr[son]);
            dad = son;
            son = dad * 2 + 1;
        }
    }
#endif
}
void Heap_Sort(int *arr, int len)
{
    int i;
	// 先将数组构造成大顶堆
    for (i = len / 2 - 1; i >= 0; i--)
        Heapify(arr, i, len);// 从第一个非叶子结点从下至上，从右至左调整结构
    // 调整堆结构 + 交换堆顶元素与末尾元素
    for (i = len - 1; i > 0; i--) {
        swap(&arr[0], &arr[i]);// 将堆顶元素与末尾元素进行交换
        Heapify(arr, 0, i);// 重新对堆进行调整
	}
}
# 8、计数排序（Counting Sort）
计数排序（Counting Sort）是一种稳定的线性时间排序算法。该算法于 1954 年由 Harold H. Seward 提出。比较适合数值跨度比较小的， 也就是数组中最大值减去最小值得到的值尽量小， 同时数组元素又比较多的情况下用计数排序效率比较高。计数排序使用一个额外的数组 C，其中第 i 个元素是待排序数组 A 中值等于 i 的元素的个数。然后根据数组 C 来将 A 中的元素排到正确的位置。
# 8.1 执行流程：
  • 找出待排序的数组中最大的元素；
  • 设置一个定量的数组 counts，最大范围为 max（max 为步骤 1 求得的最大值）；
  • 统计数组中每个值为 i 的元素出现的次数，存入数组 counts 的第 i 项；
  • 对所有的计数累加（从 counts 中的第一个元素开始，每一项和前一项相加）；
  • 反向填充目标数组：将每个元素 i 放在新数组的第 counts [i] 项，每放一个元素就将 counts [i] 减去 1。
# 8.2 动图演示：
img
# 8.3 代码实现：
int Counting_Sort(DataType *arr, int len)
{
    DataType *counts,
             *temp;
    int i;
    int max_val = arr[0];
    for(i = 1; i < len; i++)
        if(arr[i] > max_val)
            max_val = arr[i];
    /* 为计数器数组分配空间 */
    counts = (DataType *)malloc((max_val+1) * sizeof(DataType));
    /* 为已排序元素临时存放数组分配空间 */
    temp = (DataType *)malloc(len * sizeof(DataType));
    if(counts == NULL)
        return -1;
    if(temp == NULL)
        return -1;
    /* 初始化计数数组 */
    for(i = 0; i < max_val+1; i++)
        counts[i] = 0;
    /* 统计每个元素出现的次数（counts 的下标索引即是要统计的元素本身）*/
    for(i = 0; i < len; i++)
        counts[arr[i]]++;
    /* 将元素本身的次数加上它前一个元素的次数 (得到元素偏移量) */
    for(i = 1; i < max_val+1; i++)
        counts[i] += counts[i - 1];
    /* 关键代码：使用上面得到的计数数组去放置每个元素要排序的位置 */
    for(i = len - 1; i >= 0; i--) {
        temp[counts[arr[i]] -1] = arr[i];      /* counts 的值是元素要放置到 temp 中的偏移量 */
        counts[arr[i]]--;  /* counts 的计数减 1 */
//        temp[--counts[arr[i]]] = arr[i];
    }
	
    /* 将 Counting_Sort 已排序的元素从 temp 拷贝回 data */
    memcpy(arr, temp, len * sizeof(DataType));
    /* 释放前面分配的空间 */
    free(counts);
    free(temp);
    return 0;
}
# 9、桶排序（Bucket Sort）
桶排序（Bucket Sort）或所谓的箱排序，是一个排序算法，工作的原理是将数组分到有限数量的桶里。每个桶再个别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序）。
为了使桶排序更加高效，我们需要做到这两点：
  • 在额外空间充足的情况下，尽量增大桶的数量
  • 使用的映射函数能够将输入的 N 个数据均匀的分配到 K 个桶中
# 9.1 执行流程：
  • 找出待排序数组 arr 中的最大值 max、最小值 min；
  • 设置一个定量的数组当作空桶，范围为 min~max（min、max 为步骤 1 求得的最小值、最大值）；
  • 遍历待排序数组 arr，计算每个元素 arr [i] 放的桶，把数据放到对应的桶里；
  • 如果桶不为空，对桶中的数据进行排序；
  • 遍历桶数组，把所有桶中排序好的元素放到一个新的数组里。
# 9.2 动图演示：
img
# 9.3 代码实现：
int Bucket_Sort(DataType *arr, int len)
{
    int i, j, n;
    DataType *buckets;
    int max_val = arr[0];
	int min_val = arr[0];
    for(i = 1; i < len; i++) {
        if(arr[i] > max_val)
            max_val = arr[i];
        else if(arr[i] < min_val)
            min_val = arr[i];
    }
	
    n = max_val - min_val + 1;
    buckets = (DataType *)malloc((n) * sizeof(DataType));
    if(buckets == NULL)
        return -1;
    memset(buckets, 0, (n) * sizeof(DataType));
    for (i = 0; i < len; i++)
        buckets[arr[i] - min_val]++;
    for (i = 0, j = 0; i < n; i++)
        while((buckets[i]--) > 0)
            arr[j++] = i + min_val;
	
    return 0;
}
点击并拖拽以移动
# 10、基数排序（Radix Sort）
基数排序（英语：Radix Sort）是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。
它是这样实现的：将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后，数列就变成一个有序序列。
基数排序的方式可以采用 LSD（Least significant digital）或 MSD（Most significant digital），LSD 的排序方式由键值的最右边开始，而 MSD 则相反，由键值的最左边开始。
# 10.1 执行流程：
  • 取得数组中的最大数，并取得位数；
  • arr 为原始数组，从最低位开始取每个位组成 radix 数组；
  • 对 radix 进行计数排序（利用计数排序适用于小范围数的特点）。
# 10.2 动图演示：
img
# 10.3 代码实现：
#define BASE            10
int Radix_Sort(DataType *arr, int len)
{
    DataType *temp,
	         *counts; // 计数器
    int i, j, k;
    int radix = 1;
    int max_val = arr[0];
    for(i = 1; i < len; i++)
        if(arr[i] > max_val)
            max_val = arr[i];
	/* 为计数器数组分配空间 */
    counts = (DataType *)malloc((BASE+1) * sizeof(DataType));
    /* 为已排序元素临时存放数组分配空间 */
    temp = (DataType *)malloc(len * sizeof(DataType));
    if(counts == NULL)
        return -1;
    if(temp == NULL)
        return -1;
    while (max_val / radix > 0) {
        for(j = 0; j < BASE+1; j++)
            counts[j] = 0; // 每次分配前清空计数器
        for(j = 0; j < len; j++) {
            k = (arr[j] / radix) % BASE; // 统计每个桶中的记录数
            counts[k]++;
        }
        for(j = 1; j < BASE+1; j++)
            counts[j] += counts[j - 1]; // 将 temp 中的位置依次分配给每个桶
        for(j = len - 1; j >= 0; j--) { // 将所有桶中记录依次收集到 temp 中
            k = (arr[j] / radix) % BASE;
            temp[counts[k] - 1] = arr[j];
            counts[k]--;
        }
        for(j = 0; j < len; j++) // 将临时数组的内容复制到 data 中
            arr[j] = temp[j];
        radix *= 10;
    }
    /* 释放前面分配的空间 */
    free(counts);
    free(temp);
    return 0;
}
# 十大经典排序算法 C 语言总代码实现
/* 排序算法 */
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef int DataType;
#define SIZEOF(x,y)		(sizeof(x)/sizeof(y))
#define LEN				SIZEOF(buffer,DataType)
int buffer[10] = {3,6,13,1,78,35,22,11,32,60};
void Bubble_Sort(DataType *arr, int len)
{
	int i, j, temp;
	for (i = 0; i < len - 1; i++)
		for (j = 0; j < len - 1 - i; j++)
			if (arr[j] > arr[j + 1]) {
				temp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = temp;
			}
}
void Selection_Sort(DataType *arr, int len)
{
	int i, j, k, temp;
	for (i = 0; i < len - 1; i++) {
		k = i;
		for (j = i + 1; j < len; j++)
			if (arr[j] < arr[k])
				k = j;
		if(k != i) {
			temp = arr[k];
			arr[k] = arr[i];
			arr[i] = temp;
		}
	}
}
void Insertion_Sort(DataType *arr, int len)
{
	int i, j, temp;
	for (i = 1; i < len; i++)
		if (arr[i] < arr[i-1]) {
			temp = arr[i];
			for (j = i - 1; j >= 0 && arr[j] > temp; j--)
				arr[j+1] = arr[j];
			arr[j+1] = temp;
		}
}
void Shell_Sort(DataType *arr, int len)
{
	int gap, i, j;
	int temp;
	for (gap = len >> 1; gap > 0; gap >>= 1)
		for (i = gap; i < len; i++) {
			temp = arr[i];
			for (j = i - gap; j >= 0 && arr[j] > temp; j -= gap)
				arr[j + gap] = arr[j];
			arr[j + gap] = temp;
		}
}
#define MIN(x,y)     ((x) < (y) ? (x) : (y))
int Merge_Sort(DataType *arr, int len)
{
	DataType *a = arr;
	DataType *b = (DataType *) malloc(len * sizeof(DataType));
	int seg, start;
	if(b == NULL)
		return -1;
	for (seg = 1; seg < len; seg += seg) {
		for (start = 0; start < len; start += seg * 2) {
			int low = start, mid = MIN(start + seg, len), high = MIN(start + seg * 2, len);
			int k = low;
			int start1 = low, end1 = mid;
			int start2 = mid, end2 = high;
			while (start1 < end1 && start2 < end2)
				b[k++] = a[start1] < a[start2] ? a[start1++] : a[start2++];
			while (start1 < end1)
				b[k++] = a[start1++];
			while (start2 < end2)
				b[k++] = a[start2++];
		}
		DataType *temp = a;
		a = b;
		b = temp;
	}
	if (a != arr) {
		int i;
		for (i = 0; i < len; i++)
			b[i] = a[i];
		b = a;
	}
	free(b);
	return 0;
}
void Quick_Sort(DataType *arr, int low, int high)
{
	int i = low;
	int j = high;
	int pivot = arr[i];
	if(low > high) {
		return ;
	}
	while(i < j) {
		while((arr[j] >= pivot) && (i < j)) {
			j--;
		}
		arr[i] = arr[j];
		while((arr[i] <= pivot) && (i < j)) {
			i++;
		}
		arr[j]= arr[i];
	}
	arr[i] = pivot;
	Quick_Sort(arr, low, i-1);
	Quick_Sort(arr, j+1, high);
}
void swap(DataType *a, DataType *b)
{
	DataType temp = *b;
	*b = *a;
	*a = temp;
}
void Heapify(DataType *arr, int start, int end)
{
#if 0
	int i, temp;
	temp = arr[start];
	for (i = 2*start + 1; i < end; i = 2*i + 1) {// 左孩子 2*i + 1，右孩子 2*i + 2
		if (i + 1 < end && arr[i] < arr[i+1]) {// 如果左子结点小于右子结点，i 指向右子结点
			i++;
		}
		if (temp < arr[i]) {
			arr[start] = arr[i];// 将根节点设置为子节点的较大值
			start = i;// 继续往下
		} else
			break;// 已经满足大根堆
	}
	arr[start] = temp;// 将 temp 值放到最终的位置
#else
	// 建立父節點指標和子節點指標
	int dad = start;
	int son = dad * 2 + 1;
	while (son < end) { // 若子節點指標在範圍內才做比較
		if (son + 1 < end && arr[son] < arr[son + 1]) // 先比較兩個子節點大小，選擇最大的
			son++;
		if (arr[dad] >= arr[son]) // 如果父節點大於子節點代表調整完畢，直接跳出函數
			return;
		else { // 否則交換父子內容再繼續子節點和孫節點比較
			swap(&arr[dad], &arr[son]);
			dad = son;
			son = dad * 2 + 1;
		}
	}
#endif
}
void Heap_Sort(DataType *arr, int len)
{
	int i;
	// 先将数组构造成大顶堆
	for (i = len / 2 - 1; i >= 0; i--)
		Heapify(arr, i, len);// 从第一个非叶子结点从下至上，从右至左调整结构
	// 调整堆结构 + 交换堆顶元素与末尾元素
	for (i = len - 1; i > 0; i--) {
		swap(&arr[0], &arr[i]);// 将堆顶元素与末尾元素进行交换
		Heapify(arr, 0, i);// 重新对堆进行调整
	}
}
int Counting_Sort(DataType *arr, int len)
{
	DataType *counts,
	         *temp;
	int i;
	int max_val = arr[0];
	for(i = 1; i < len; i++)
		if(arr[i] > max_val)
			max_val = arr[i];
	/* 为计数器数组分配空间 */
	counts = (DataType *)malloc((max_val+1) * sizeof(DataType));
	/* 为已排序元素临时存放数组分配空间 */
	temp = (DataType *)malloc(len * sizeof(DataType));
	if(counts == NULL)
		return -1;
	if(temp == NULL)
		return -1;
	/* 初始化计数数组 */
	for(i = 0; i < max_val+1; i++)
		counts[i] = 0;
	/* 统计每个元素出现的次数（counts 的下标索引即是要统计的元素本身）*/
	for(i = 0; i < len; i++)
		counts[arr[i]]++;
	/* 将元素本身的次数加上它前一个元素的次数 (得到元素偏移量) */
	for(i = 1; i < max_val+1; i++)
		counts[i] += counts[i - 1];
	/* 关键代码：使用上面得到的计数数组去放置每个元素要排序的位置 */
	for(i = len - 1; i >= 0; i--) {
		temp[counts[arr[i]] -1] = arr[i];      /* counts 的值是元素要放置到 temp 中的偏移量 */
		counts[arr[i]]--;  /* counts 的计数减 1 */
//		temp[--counts[arr[i]]] = arr[i];
	}
	/* 将 Counting_Sort 已排序的元素从 temp 拷贝回 data */
	memcpy(arr, temp, len * sizeof(DataType));
	/* 释放前面分配的空间 */
	free(counts);
	free(temp);
	return 0;
}
int Bucket_Sort(DataType *arr, int len)
{
	int i, j, n;
	DataType *buckets;
	int max_val = arr[0];
	int min_val = arr[0];
	for(i = 1; i < len; i++) {
		if(arr[i] > max_val)
			max_val = arr[i];
		else if(arr[i] < min_val)
			min_val = arr[i];
	}
	n = max_val - min_val + 1;
	buckets = (DataType *)malloc((n) * sizeof(DataType));
	if(buckets == NULL)
		return -1;
	memset(buckets, 0, (n) * sizeof(DataType));
	for (i = 0; i < len; i++)
		buckets[arr[i] - min_val]++;
	for (i = 0, j = 0; i < n; i++)
		while((buckets[i]--) > 0)
			arr[j++] = i + min_val;
	return 0;
}
#define BASE            10
int Radix_Sort(DataType *arr, int len)
{
	DataType *temp,
	         *counts; // 计数器
	int i, j, k;
	int radix = 1;
	int max_val = arr[0];
	for(i = 1; i < len; i++)
		if(arr[i] > max_val)
			max_val = arr[i];
	/* 为计数器数组分配空间 */
	counts = (DataType *)malloc((BASE+1) * sizeof(DataType));
	/* 为已排序元素临时存放数组分配空间 */
	temp = (DataType *)malloc(len * sizeof(DataType));
	if(counts == NULL)
		return -1;
	if(temp == NULL)
		return -1;
	while (max_val / radix > 0) {
		for(j = 0; j < BASE+1; j++)
			counts[j] = 0; // 每次分配前清空计数器
		for(j = 0; j < len; j++) {
			k = (arr[j] / radix) % BASE; // 统计每个桶中的记录数
			counts[k]++;
		}
		for(j = 1; j < BASE+1; j++)
			counts[j] += counts[j - 1]; // 将 temp 中的位置依次分配给每个桶
		for(j = len - 1; j >= 0; j--) { // 将所有桶中记录依次收集到 temp 中
			k = (arr[j] / radix) % BASE;
			temp[counts[k] - 1] = arr[j];
			counts[k]--;
		}
		for(j = 0; j < len; j++) // 将临时数组的内容复制到 data 中
			arr[j] = temp[j];
		radix *= 10;
	}
	/* 释放前面分配的空间 */
	free(counts);
	free(temp);
	return 0;
}
int main(void)
{
	int i;
//	Bubble_Sort(buffer, LEN);
//	Selection_Sort(buffer, LEN);
//	Insertion_Sort(buffer, LEN);
//	Shell_Sort(buffer, LEN);
//	Merge_Sort(buffer, LEN);
//	Quick_Sort(buffer, 0, LEN-1);
//	Heap_Sort(buffer, LEN);
//	Counting_Sort(buffer, LEN);
//	Bucket_Sort(buffer, LEN);
//	Radix_Sort(buffer, LEN);
	for(i = 0; i < LEN; i++)
		printf("buffer[%d]=%3d\n", i, *(buffer+i));
	return 0;
}
/* -------------------- END OF FILE -------------------- */
点击并拖拽以移动
# 附录
参考来源：
https://zh.wikipedia.org/wiki/%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95
GitHub - hustcc/JS-Sorting-Algorithm: 一本关于排序算法的 GitBook 在线书籍 《十大经典排序算法》，多语言实现。
数据结构与算法 - 随笔分类 - 鹿呦呦 - 博客园
https://www.smslit.top/2018/11/07/algorithm-sort/
https://zoharyip.club/posts/Sort-Algorithms.html
图解排序算法 (三) 之堆排序 - dreamcatcher-cx - 博客园
堆排序 - Don'tYouSee - 博客园
模型建立：
数据结构和算法动态可视化 (Chinese) - VisuAlgo
GitHub - algorithm-visualizer/algorithm-visualizer: Interactive Online Platform that Visualizes Algorithms from Code
 
 更新于  阅读次数  次
请我喝[茶]~(￣▽￣)~*
夏沫の浅雨 微信支付
微信支付
夏沫の浅雨 支付宝
支付宝