十大排序算法与实现详解（C语言版）

十大排序算法与实现详解（C语言版）

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

0、总序

0.1 排序的概念

排序是计算机内经常进行的一种操作，其目的是将一组“无序”的记录序列调整为“有序”的记录序列。分内部排序和外部排序，若整个排序过程不需要访问外存便能完成，则称此类排序问题为内部排序。反之，若参加排序的记录数量很大，整个序列的排序过程不可能在内存中完成，则称此类排序问题为外部排序。内部排序的过程是一个逐步扩大记录的有序序列长度的过程。

0.2 稳定性概念

稳定排序：如果a原本在b前面，而a=b，排序之后a仍然在b的前面；
不稳定排序：如果a原本在b的前面，而a=b，排序之后a可能会出现在b的后面；

0.3 内部排序和外部排序

内部排序：排序不占用外存
外部排序：数据过大，排序占用外存

0.4 时空复杂度

时间复杂度：排序消耗的时间
空间复杂度：排序所需的内存

0.5 排序总结

1、冒泡排序

1.1 概念

冒泡排序（Bubble Sort）也是一种简单直观的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢"浮"到数列的顶端。
作为最简单的排序算法之一，冒泡排序给我的感觉就像 Abandon 在单词书里出现的感觉一样，每次都在第一页第一位，所以最熟悉。冒泡排序还有一种优化算法，就是立一个 flag，当在一趟序列遍历中元素没有发生交换，则证明该序列已经有序。但这种改进对于提升性能来
这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。

1.2 算法步骤

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

1.3 动画演示

1.4 算法实现

#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、选择排序

2.1 概念

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

2.2 算法步骤

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

2.3 动画演示

2.4 算法实现

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]);    	//做交换}
}

3、插入排序

3.1 概念

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

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

3.2 算法步骤

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

3.3 动画演示

3.4 算法实现

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;}
}

4、希尔排序

4.1 概念

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

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

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

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

4.2 算法步骤

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

4.3 动画演示

4.4 算法实现

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、归并排序

5.1 概念

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

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

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

和选择排序一样，归并排序的性能不受输入数据的影响，但表现比选择排序好的多，因为始终都是 O(nlogn) 的时间复杂度。代价是需要额外的内存空间。

5.2 算法步骤

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

5.3 动画演示

5.4 算法实现

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);
}

6、快速排序

6.1 概念

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

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

快速排序又是一种分而治之思想在排序算法上的典型应用。本质上来看，快速排序应该算是在冒泡排序基础上的递归分治法。

快速排序的名字起的是简单粗暴，因为一听到这个名字你就知道它存在的意义，就是快，而且效率高！它是处理大数据最快的排序算法之一了。虽然 Worst Case 的时间复杂度达到了 O(n²)，但是人家就是优秀，在大多数情况下都比平均时间复杂度为 O(nlogn)的排序算法表现要更好，可是这是为什么呢，我也不知道。好在我的强迫症又犯了，查了 N 多资料终于在《算法艺术与信息学竞赛》上找到了满意的答案：

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

6.2 算法步骤

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

6.3 动画演示

6.4 算法实现

void quickSort() {int arr[10] = {11, 7, 9, 3, 4, 6, 2, 8, 5, 3};quick_sort(arr, 0, 9);for (int i = 0; i < 10; i++)printf("%d\t", arr[i]);
}int partition(int arr[], int start, int end) {int temp = arr[start];int li = start, ri = end;while (li < ri) {while (li < ri && arr[ri] > temp)ri--;if (li < ri) {arr[li] = arr[ri];li++;}while (li < ri && arr[li] < temp)li++;if (li < ri) {arr[ri] = arr[li];ri--;}}arr[li] = temp;return li;
}void quick_sort(int arr[], int start, int end) {if (start < end) {int index = partition(arr, start, end);quick_sort(arr, start, index - 1);quick_sort(arr, index + 1, end);}
}

7、堆排序

7.1 概念

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

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

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

7.2 算法步骤

• 创建一个堆 H[0……n-1]；
• 把堆首（最大值）和堆尾互换；
• 把堆的尺寸缩小 1，并调用 shift_down(0)，目的是把新的数组顶端数据调整到相应位置；
• 重复步骤 2，直到堆的尺寸为 1。

7.3 动画演示

7.4 算法实现

void heapSort() {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);for (int i = len; i > 1; i--)heap_Sort(arr, i); //建立堆 每次规模-1for (int i = 0; i < len; i++)printf("%d ", arr[i]);return 0;
}//构造一个大顶堆并将最大值换至最后一位
void heap_Sort(int arr[], int len) {int dad = len / 2 - 1; //最后一个父节点int son = 2 * dad + 1; //该父节点下的首个子节点while (dad >= 0) {//判断是否有两个子节点若有则在其中寻找最大子节点if (son + 1 <= len - 1 && arr[son] < arr[son + 1])son++;if (arr[dad] < arr[son]) //若父节点小于子节点则交换位置swap(&arr[dad], &arr[son]);dad--;             //回退到上一个父节点son = 2 * dad + 1; //上一个父节点的首个子节点}swap(&arr[0], &arr[len - 1]);
}void swap(int *a, int *b) {int temp = *a;*a = *b;*b = temp;
}

8、计数排序

8.1 概念

计数排序是一个非基于比较的排序算法，该算法于1954年由 Harold H. Seward 提出。它的优势在于在对一定范围内的整数排序时，它的复杂度为Ο(n+k)（其中k是整数的范围），快于任何比较排序算法。当然这是一种牺牲空间换取时间的做法，而且当O(k)>O(nlog(n))的时候其效率反而不如基于比较的排序（基于比较的排序的时间复杂度在理论上的下限是O(nlog(n)), 如归并排序，堆排序）

8.2 算法步骤

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

8.3 动画演示

8.4 算法实现

void countingSort() {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);counting_Sort(arr, len);for (int i = 0; i < len; i++)printf("%d   ", arr[i]);
}void counting_Sort(int arr[], int LEN) {//寻找最大最小值int max = arr[0], min = arr[0], i, j = 0;for (i = 0; i < LEN; i++) {if (arr[i] < min)min = arr[i];if (arr[i] > max)max = arr[i];}//建立计数数组int new_len = max - min + 1;printf("%d\n", new_len);int conunting_arr[new_len];//计数for (i = 0; i < new_len; i++) { //初始化conunting_arr[i] = 0;}for (i = 0; i < LEN; i++) {conunting_arr[arr[i] - min]++;}//根据计数结果进行排序for (i = 0; i < new_len; i++) {int index = conunting_arr[i];while (index != 0) {arr[j] = i + min;index--;j++;}}
}

9、桶排序

9.1 概念

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

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

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

9.2 算法步骤

• 人为设置一个BucketSize，作为每个桶所能放置多少个不同数值；
• 遍历输入数据，并且把数据一个一个放到对应的桶里去；
• 对每个不是空的桶进行排序，可以使用其它排序方法，也可以递归使用桶排序；
• 从不是空的桶里把排好序的数据拼接起来。

9.3 动画演示

9.4 算法实现

void bucketSort() {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);bucket_Sort(arr, len);for (int i = 0; i < len; i++)printf("%d   ", arr[i]);
}void bucket_sort(int arr[], int LEN) {int bucket[5][6] = {0}, i, j, k, temp; //初始化桶,每个桶存放6个数据//寻找最大最小值int min = arr[0], max = arr[0];for (i = 0; i < LEN; i++) {if (arr[i] < min)min = arr[i]; //0if (arr[i] > max)max = arr[i]; //9}//遍历数组,将元素放到对应桶中int index0 = 0, index1 = 0, index2 = 0, index3 = 0, index4 = 0;for (i = 0; i < LEN; i++) {if (arr[i] < min + (max - min + 1) / 5 * 1 && index0 < 7) {bucket[0][index0] = arr[i];index0++;} else if (arr[i] < min + (max - min + 1) / 5 * 2 && (index1 < 7 || index0 >= 7)) {bucket[1][index1] = arr[i];index1++;} else if (arr[i] < min + (max - min + 1) / 5 * 3 && (index2 < 7 || index1 >= 7)) {bucket[2][index2] = arr[i];index2++;} else if (arr[i] < min + (max - min + 1) / 5 * 4 && (index3 < 7 || index2 >= 7)) {bucket[3][index3] = arr[i];index3++;} else if (arr[i] < min + (max - min + 1) / 5 * 5 && (index4 < 7 || index3 >= 7)) {bucket[4][index4] = arr[i];index4++;}}//在每个桶中使用冒泡排序for (i = 0; i < 5; i++) {for (int j = 0; j < 5; j++) { //从小到大// 外循环为排序趟数，len个数进行len-1趟for (int k = 0; k < 5 - i; k++) {// 内循环为每趟比较的次数，第i趟比较len-i次,因为第一次已经将最大的元素冒泡到最后一个位置了if (bucket[i][k] > bucket[i][k + 1]) {//相邻元素比较,逆序则将交换位置temp = bucket[i][k];bucket[i][k] = bucket[i][k + 1];bucket[i][k + 1] = temp;}}}}//将桶中排序结果还原到原数组中for (i = 0; i < 5; i++) {for (j = 0; j < 6; j++) {arr[i * 6 + j] = bucket[i][j];}}
}

10、基数排序

10.1 概念

基数排序（radix sort）属于“分配式排序”（distribution sort），又称“桶子法”（bucket sort）或bin sort，顾名思义，它是透过键值的部份资讯，将要排序的元素分配至某些“桶”中，藉以达到排序的作用，基数排序法是属于稳定性的排序，其时间复杂度为O (nlogm)，其中r为所采取的基数，而m为堆数，在某些时候，基数排序法的效率高于其它的稳定性排序法。

10.2 算法步骤

• 取得数组中的最大数，并取得位数；
• arr为原始数组，从最低位开始取每个位组成radix数组；
• 对radix进行计数排序（利用计数排序适用于小范围数的特点）；

10.3 动画演示

10.4 算法实现

void radixSort() {int arr[] = {31, 25, 33, 40, 78, 26, 1, 52, 88, 63, 22, 44, 69, 42, 17, 10, 11, 28, 19, 47};int LEN = (int)sizeof(arr) / sizeof(*arr);int LEVEL = 0; //最大数的位数//寻找最大值以确定位数int max = arr[0], i;for (i = 0; i < LEN; i++) {if (arr[i] > max)max = arr[i];}for (i = max; i > 0; i /= 10) {LEVEL++;}// printf("%d",LEVEL);for (i = 0; i < LEVEL; i++) {radix_sort(arr, LEN, i);for (int i = 0; i < LEN; i++)printf("%d   ", arr[i]);printf("\n");}for (int i = 0; i < LEN; i++)printf("%d   ", arr[i]);return 0;
}void radix_sort(int arr[], int LEN, int level) {int bucket[10] = {0}, temp[LEN], i, j;int flag = pow(10, level); //用于确定当前比较的是什么位//获取个位并进行第一次基数排序//获取个位存储入桶for (i = 0; i < LEN; i++) {bucket[arr[i] / flag % 10]++;}bucket[0]--;for (i = 1; i < 10; i++) {bucket[i] += bucket[i - 1];}//根据桶结果将原数组进行第一次排序后复制到temp数组//注意这里必须要反向遍历for (i = LEN - 1; i >= 0; i--) {temp[bucket[arr[i] / flag % 10]] = arr[i];bucket[arr[i] / flag % 10]--;}//利用temp数组修改原数组for (i = 0; i < LEN; i++) {arr[i] = temp[i];}
}

部分算法动画转载自：十大经典排序算法 | 菜鸟教程