十大排序算法——C语言实现

在这里插入图片描述

1.冒泡排序

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

作为最简单的排序算法之一，冒泡排序给我的感觉就像 Abandon 在单词书里出现的感觉一样，每次都在第一页第一位，所以最熟悉。冒泡排序还有一种优化算法，就是立一个 flag，当在一趟序列遍历中元素没有发生交换，则证明该序列已经有序。但这种改进对于提升性能来说并没有什么太大作用。

1.算法步骤

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

2.动画演示

在这里插入图片描述

3. 什么时候最快

当输入的数据已经是正序时（都已经是正序了，我还要你冒泡排序有何用啊）。

4. 什么时候最慢

当输入的数据是反序时（写一个 for 循环反序输出数据不就行了，干嘛要用你冒泡排序呢，我是闲的吗）。

5.C语言实现

include <stdio.h>
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;}
}
int main() {int arr[] = { 22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70 };int len = (int) sizeof(arr) / sizeof(*arr);bubble_sort(arr, len);int i;for (i = 0; i < len; i++)printf("%d ", arr[i]);return 0;
}

2.选择排序

选择排序是一种简单直观的排序算法，无论什么数据进去都是 O(n²) 的时间复杂度。所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。

1. 算法步骤

首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置
再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
重复第二步，直到所有元素均排序完毕。

2. 动图演示

在这里插入图片描述

3.代码实现

#include <stdio.h>
void swap(int *a,int *b) //交换两个数
{int temp = *a;*a = *b;*b = temp;
}
void selection_sort(int arr[], int len)
{int i,j;for (i = 0 ; i < len - 1 ; i++){int min = i;for (j = i + 1; j < len; j++)     //走访未排序的元素if (arr[j] < arr[min])    //找到目前最小值min = j;    //记录最小值swap(&arr[min], &arr[i]);    //做交换}
}
int main() {int arr[] = { 22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70 };int len = (int) sizeof(arr) / sizeof(*arr);selection_sort(arr, len);int i;for (i = 0; i < len; i++)printf("%d ", arr[i]);return 0;
}

3.插入排序

插入排序的代码实现虽然没有冒泡排序和选择排序那么简单粗暴，但它的原理应该是最容易理解的了，因为只要打过扑克牌的人都应该能够秒懂。插入排序是一种最简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

插入排序和冒泡排序一样，也有一种优化算法，叫做拆半插入。

1. 算法步骤

将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。
从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）

2. 动图演示

[ 动图演示

3.代码实现

#include <stdio.h>
void insertion_sort(int arr[], int len){int i,j,key;for (i=1;i<len;i++){key = arr[i];j=i-1;while((j>=0) && (arr[j]>key)) {arr[j+1] = arr[j];j--;}arr[j+1] = key;}
}
int main() {int arr[] = { 22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70 };int len = (int) sizeof(arr) / sizeof(*arr);insertion_sort(arr, len);int i;for (i = 0; i < len; i++)printf("%d ", arr[i]);return 0;
}

4.希尔排序

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

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

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

希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。

1. 算法步骤

选择一个增量序列 t1，t2，……，tk，其中 ti > tj, tk = 1；
按增量序列个数 k，对序列进行 k 趟排序；
每趟排序，根据对应的增量 ti，将待排序列分割成若干长度为 m 的子序列，分别对各子表进行直接插入排序。仅增量因子为 1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

2.动画演示

3. 代码实现

#include <stdio.h>
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;}
}
int main() {int arr[] = { 22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70 };int len = (int) sizeof(arr) / sizeof(*arr);shell_sort(arr, len);int i;for (i = 0; i < len; i++)printf("%d ", arr[i]);return 0;
}

5.归并排序

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

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

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

2. 算法步骤

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

3. 动图演示

动图演示

4. 代码实现迭代版

#include <stdio.h>
#include <stdlib.h>
int min(int x, int y) {return 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);
}
int main() {int arr[] = { 22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70 };int len = (int) sizeof(arr) / sizeof(*arr);merge_sort(arr, len);int i;for (i = 0; i < len; i++)printf("%d ", arr[i]);return 0;
}

4.1代码实现递归版

#include <stdio.h>
#include <stdlib.h>
void merge_sort_recursive(int arr[], int reg[], int start, int end) {if (start >= end)return;int len = end - start, mid = (len >> 1) + start;int start1 = start, end1 = mid;int start2 = mid + 1, end2 = end;merge_sort_recursive(arr, reg, start1, end1);merge_sort_recursive(arr, reg, start2, end2);int k = start;while (start1 <= end1 && start2 <= end2)reg[k++] = arr[start1] < arr[start2] ? arr[start1++] : arr[start2++];while (start1 <= end1)reg[k++] = arr[start1++];while (start2 <= end2)reg[k++] = arr[start2++];for (k = start; k <= end; k++)arr[k] = reg[k];
}void merge_sort(int arr[], const int len) {int reg[len];merge_sort_recursive(arr, reg, 0, len - 1);
}
int main() {int arr[] = { 22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70 };int len = (int) sizeof(arr) / sizeof(*arr);merge_sort(arr, len);int i;for (i = 0; i < len; i++)printf("%d ", arr[i]);return 0;
}

6.快速排序

快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下，排序 n 个项目要 Ο(nlogn) 次比较。在最坏状况下则需要 Ο(n2) 次比较，但这种状况并不常见。事实上，快速排序通常明显比其他 Ο(nlogn) 算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实现出来。

快速排序的最坏运行情况是 O(n²)，比如说顺序数列的快排。但它的平摊期望时间是 O(nlogn)，且 O(nlogn) 记号中隐含的常数因子很小，比复杂度稳定等于 O(nlogn) 的归并排序要小很多。所以，对绝大多数顺序性较弱的随机数列而言，快速排序总是优于归并排序。

快速排序使用分治法（Divide and conquer）策略来把一个串行（list）分为两个子串行（sub-lists）

1. 算法步骤

从数列中挑出一个元素，称为 “基准”（pivot）;
重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序；

2. 动图演示

3.代码实现

#include <stdio.h>
#include <stdlib.h>
typedef struct _Range {int start, end;
} Range;Range new_Range(int s, int e) {Range r;r.start = s;r.end = e;return r;
}void swap(int *x, int *y) {int t = *x;*x = *y;*y = t;
}void quick_sort(int arr[], const int len) {if (len <= 0)return; // 避免len等於負值時引發段錯誤（Segment Fault）// r[]模擬列表,p為數量,r[p++]為push,r[--p]為pop且取得元素Range r[len];int p = 0;r[p++] = new_Range(0, len - 1);while (p) {Range range = r[--p];if (range.start >= range.end)continue;int mid = arr[(range.start + range.end) / 2]; // 選取中間點為基準點int left = range.start, right = range.end;do {while (arr[left] < mid) ++left;   // 檢測基準點左側是否符合要求while (arr[right] > mid) --right; //檢測基準點右側是否符合要求if (left <= right) {swap(&arr[left], &arr[right]);left++;right--;               // 移動指針以繼續}} while (left <= right);if (range.start < right) r[p++] = new_Range(range.start, right);if (range.end > left) r[p++] = new_Range(left, range.end);}
}
int main() {int arr[] = { 22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70 };int len = (int) sizeof(arr) / sizeof(*arr);quick_sort(arr, len);int i;for (i = 0; i < len; i++)printf("%d ", arr[i]);return 0;
}

4.代码实现递归版

#include <stdio.h>
#include <stdlib.h>
void swap(int *x, int *y) {int t = *x;*x = *y;*y = t;
}void quick_sort_recursive(int arr[], int start, int end) {if (start >= end)return;int mid = arr[end];int left = start, right = end - 1;while (left < right) {while (arr[left] < mid && left < right)left++;while (arr[right] >= mid && left < right)right--;swap(&arr[left], &arr[right]);}if (arr[left] >= arr[end])swap(&arr[left], &arr[end]);elseleft++;if (left)quick_sort_recursive(arr, start, left - 1);quick_sort_recursive(arr, left + 1, end);
}void quick_sort(int arr[], int len) {quick_sort_recursive(arr, 0, len - 1);
}
int main() {int arr[] = { 22, 34, 3, 32, 82,55, 89, 50, 37, 5, 64, 35, 9, 70 };int len = (int) sizeof(arr) / sizeof(*arr);quick_sort_recursive(arr, 0,len);int i;for (i = 0; i < 15; i++)printf("%d ", arr[i]);return 0;
}

7.堆排序、

堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。堆排序可以说是一种利用堆的概念来排序的选择排序。分为两种方法：

大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列；
小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列；

堆排序的平均时间复杂度为 Ο(nlogn)。

1. 算法步骤

将待排序序列构建成一个堆 H[0……n-1]，根据（升序降序需求）选择大顶堆或小顶堆；
把堆首（最大值）和堆尾互换；
把堆的尺寸缩小 1，并调用 shift_down(0)，目的是把新的数组顶端数据调整到相应位置；
重复步骤 2，直到堆的尺寸为 1。

2. 动图演示

动图演示

3. 代码实现

#include <stdio.h>
#include <stdlib.h>void swap(int *a, int *b) {int temp = *b;*b = *a;*a = temp;
}void max_heapify(int arr[], int start, int end) {// 建立父節點指標和子節點指標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;}}
}void heap_sort(int arr[], int len) {int i;// 初始化，i從最後一個父節點開始調整for (i = len / 2 - 1; i >= 0; i--)max_heapify(arr, i, len - 1);// 先將第一個元素和已排好元素前一位做交換，再重新調整，直到排序完畢for (i = len - 1; i > 0; i--) {swap(&arr[0], &arr[i]);max_heapify(arr, 0, i - 1);}
}int main() {int arr[] = { 3, 5, 3, 0, 8, 6, 1, 5, 8, 6, 2, 4, 9, 4, 7, 0, 1, 8, 9, 7, 3, 1, 2, 5, 9, 7, 4, 0, 2, 6 };int len = (int) sizeof(arr) / sizeof(*arr);heap_sort(arr, len);int i;for (i = 0; i < len; i++)printf("%d ", arr[i]);printf("\n");return 0;
}

8.计数排序

计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。

1.算法的步骤如下：

（1）找出待排序的数组中最大和最小的元素
（2）统计数组中每个值为i的元素出现的次数，存入数组C的第i项
（3）对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）
（4）反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1

2…动画演示

动图演示

2.代码实现

#include <stdio.h>
#include <stdlib.h>
#include <time.h>void print_arr(int *arr, int n) {int i;printf("%d", arr[0]);for (i = 1; i < n; i++)printf(" %d", arr[i]);printf("\n");
}void counting_sort(int *ini_arr, int *sorted_arr, int n) {int *count_arr = (int *) malloc(sizeof(int) * 100);int i, j, k;for (k = 0; k < 100; k++)count_arr[k] = 0;for (i = 0; i < n; i++)count_arr[ini_arr[i]]++;for (k = 1; k < 100; k++)count_arr[k] += count_arr[k - 1];for (j = n; j > 0; j--)sorted_arr[--count_arr[ini_arr[j - 1]]] = ini_arr[j - 1];free(count_arr);
}int main(int argc, char **argv) {int n = 10;int i;int *arr = (int *) malloc(sizeof(int) * n);int *sorted_arr = (int *) malloc(sizeof(int) * n);srand(time(0));for (i = 0; i < n; i++)arr[i] = rand() % 100;printf("ini_array: ");print_arr(arr, n);counting_sort(arr, sorted_arr, n);printf("sorted_array: ");print_arr(sorted_arr, n);free(arr);free(sorted_arr);return 0;
}

9.桶排序

桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。为了使桶排序更加高效，我们需要做到这两点：

在额外空间充足的情况下，尽量增大桶的数量
使用的映射函数能够将输入的 N 个数据均匀的分配到 K 个桶中

同时，对于桶中元素的排序，选择何种比较排序算法对于性能的影响至关重要。

1. 什么时候最快

当输入的数据可以均匀的分配到每一个桶中。

2. 什么时候最慢

当输入的数据被分配到了同一个桶中。

3. 示意图

元素分布在桶中：

然后，元素在每个桶中排序：

10.基数排序

基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。

1. 基数排序 vs 计数排序 vs 桶排序

基数排序有两种方法：

这三种排序算法都利用了桶的概念，但对桶的使用方法上有明显差异：

基数排序：根据键值的每位数字来分配桶；
计数排序：每个桶只存储单一键值；
桶排序：每个桶存储一定范围的数值；

2. LSD 基数排序动图演示

3.代码实现

#include<stdio.h>
#define MAX 20
//#define SHOWPASS
#define BASE 10void print(int *a, int n) {int i;for (i = 0; i < n; i++) {printf("%d\t", a[i]);}
}void radixsort(int *a, int n) {int i, b[MAX], m = a[0], exp = 1;for (i = 1; i < n; i++) {if (a[i] > m) {m = a[i];}}while (m / exp > 0) {int bucket[BASE] = { 0 };for (i = 0; i < n; i++) {bucket[(a[i] / exp) % BASE]++;}for (i = 1; i < BASE; i++) {bucket[i] += bucket[i - 1];}for (i = n - 1; i >= 0; i--) {b[--bucket[(a[i] / exp) % BASE]] = a[i];}for (i = 0; i < n; i++) {a[i] = b[i];}exp *= BASE;#ifdef SHOWPASSprintf("\nPASS   : ");print(a, n);
#endif}
}int main() {int arr[MAX];int i, n;printf("Enter total elements (n <= %d) : ", MAX);scanf("%d", &n);n = n < MAX ? n : MAX;printf("Enter %d Elements : ", n);for (i = 0; i < n; i++) {scanf("%d", &arr[i]);}printf("\nARRAY  : ");print(&arr[0], n);radixsort(&arr[0], n);printf("\nSORTED : ");print(&arr[0], n);printf("\n");return 0;
}