本文介绍6种常见的排序算法,以及他们的原理,性能分析和c语言实现:
为了能够条理清楚,本文所有的算法和解释全部按照升序排序进行
首先准备一个元素无序的数组arr[],数组的长度为length,一个交换函数swap,
在main函数中实现排序函数的调用,并输出排序结果:
void swap(int*x , int*y) {
int temp = *x;
*x = *y;
*y = temp;
}
int main() {
int arr[] = { 1,8,5,7,4,6,2,3};
int length = sizeof(arr) / sizeof(int);
sort(arr, length);
for (int i = 0;i < length;i++) {
printf("%d\n", arr[i]);
}
return 0;
}
插入排序
第一次循环:
第二次循环:
第三次循环:
外层循环每执行一次就从无序区向有序区中插入一个数据arr[i]
里层循环控制插入的数据arr[i]与其前一个数据比较,如果比前一个数据小,就让前一个数据后移1位
...不断重复上述步骤,直到找到不比arr[i]小的数据arr[j],因为arr[j]后面的数据都后移了1位,所以直接将arr[i]放在空闲的arr[j+1]位置
c程序实现:
void CRsort(int arr[], int length) {
int temp;
for (int i = 0;i < length;i++) {
temp = arr[i];
for (int j = i - 1;j >= 0;j--) {
if (arr[j] > temp) {
arr[j + 1] = arr[j];
}
else {
arr[j + 1] = temp;
break;
}
}
}
}
性能分析
稳定性 : 稳定
-->内层循环执行时,只有遇到大于arr[i]的才会后移,等于arr[i]的不会后移
时间复杂度 : (最坏n²,最好n,平均n²)
-->数据量为n的情况下,外层循环执行n次,内层循环最多执行n次,如果是数据是有序的内层循环只会执行1次
数据越有序,插入排序的执行效率就越高
空间复杂度: 1
-->程序没有用到递归,临时变量不占用存储资源,因此空间复杂度为1
希尔排序
希尔排序又叫"缩小增量排序",是插入排序的一种改进排本:
插入排序优点是适合处理接近有序的元素,缺点是每次只能比较一个元素,希尔排序利用了这两个特点:
区别于普通的插入排序,希尔排序有一个增量序列r,r的初始值一般取 int(length/2),也就是元素数量除以2向下取整
将所有相隔r个单位的元素组成一组,在组内完成排序
增量每次折半,直到最后一次排序时,增量为1,这时元素一定是有序的
最外层循环控制增量组,即每次循环的增量
里面的两层循环就是一个最基本的插入排序,只不过每次加入有序组的不是arr[i+1],而是arr[i+增量]
c程序实现:
void ShellSort(int arr[], int length) {
int r, temp, j;
for (r = length / ;r >= ;r = r / ) {
for (int i = r;i < length;i++) {
temp = arr[i];
j = i - r;
while (j >= && temp < arr[j]) {
arr[j + r] = arr[j];
j = j - r;
}
arr[j + r] = temp;
}
}
}
性能分析
稳定性 : 不稳定
-->每个元素都是在自己的排序组中排序,两个值相同的元素出于不同的排序组中他们总体的相对位置可能会发生变化
时间复杂度 : (最坏n²,最好n,平均n^1.3)
-->希尔排序的分析是一个复杂的问题，以为它的时间是所取“增量”序列的函数，这涉及到一些数学上尚未解决的难题,摘自网上.
最好和普通插入排序相同,如果是数据是有序的内层循环只会执行1次
同样拥有插入排序的特点:数据越有序,它的执行效率就越高
空间复杂度: 1
-->程序没有用到递归,临时变量不占用存储资源,因此空间复杂度为1
冒泡排序
冒泡排序
外层循环每次都将一个元素置入有序区
内层循环控制置入的元素:设置一个指针j,拿arr[j]的值与arr[j+1]进行比较:
如果arr[j]<arr[j+1],就将arr[j]的值与arr[j+1]交换,否则j++,直到无序区比较完毕
值得一提的是,冒泡排序可以进行这样的优化:
设置一个状态码change,当有数据交换发生时change置1
如果一整次排序都没有交换发生,那么这组数据就是有序的,可以直接结束循环
c程序实现:
int MPsort(int arr[], int length) {
int temp, change = 0;
for (int i = 0;i < length;i++) {
for (int j = 0;j < length - i - 1;j++) {
if (arr[j] > arr[j + 1]) {
swap(&arr[j],&arr[j+1]);
change = 1;
}
}
if (change == 0) {
return 0;
}
}
}
性能分析
稳定性 : 稳定
-->数据只有在大于或小于时才会交换,相等时不会交换,因此相同数据的相对位置不会发生改变
时间复杂度 : (最坏n²,最好n,平均n²)
-->在数据完全有序时,不会有数据交换,根据上面的优化处理,状态码change不会改变,外层循环执行一次就结束,时间复杂度为n+1,也就是n.
而如果是非常无序的数据,外层循环执行满n次,时间复杂度就是n²
空间复杂度: log(2)(N)
-->程序没有用到递归,临时变量不占用存储资源,因此空间复杂度为1
快速排序
快速排序是一种效率比较高的排序方法,这张图片我认为介绍的很清楚,搬运来用一下,出处在文章下面:
c程序实现:
void KSSort(int arr[], int left, int right) {
if (left < right) {
int key = arr[left];
int l = left;
int r = right;
while (l < r) {
while (l < r && arr[r] >= key) {
r--;
}
if (l < r) {
arr[l] = arr[r];
l++;
}
else {
break;
}
while (l < r && arr[l] <= key) {
l++;
}
if (l < r) {
arr[r] = arr[l];
r--;
}
else {
break;
}
}
arr[l] = key;
KSSort(arr, left, l - 1);
KSSort(arr, l + 1, right);
}
}
性能分析
稳定性 : 不稳定
--> 假设是稳定的,举个反例:
5 | 3 1 2 | 9 7 8 9 | 4 6 3
这时遍历unvisited部分 刚到了4 (array[8])
显然4<5 ，这是4应该从 unvisited 部分去到 lower 部分。 因此 higher部分第一个元素 9 (array[4]) 和 4互换。变成了这样：
5 | 3 1 2 4 | 7 8 9 9 | 6 3
时间复杂度 : (最坏n²,最好nlogn,平均nlogn)
-->快速排序最差的情况就是每次取到的基准数baes都是排序组的边界值(不是最小的就是最大的),这时外层循环要遍历n次才能将所有数据比较完,时间复杂度就是n²
这种情况多发生在排好序(或接近排好序)的数据中,要在这种数据中避免使用快速排序算法
最好的情况是基准数每次都能取到接近排序组的中位数,用最短的循环次数将程序完全分割,n个数据每次减半,也就是log(2)(N)次后数据被完全分割,算法的时间复杂度为
最差的情况不容易取到,平均时间复杂度取nlogn
空间复杂度: logn
-->在我这个程序里没有用到递归,空间复杂度为1,当然也可以使用递归实现,递归log(2)(N)次,空间复杂度为logn
最后附一张各种排序算法比较图
选择排序
选择排序是最简单的排序方式,也是比较低效的一种排序方式:
第一次循环 :
第二次循环:
第三次循环:
外层循环每执行一次向有序区添加一个元素
内层循环遍历到最大的元素,与刚刚填入有序区的元素交换
......直到数据全部加入有序区
c程序实现:
void XZsort(int arr[] , int length) {
int check;
for (int i = ;i < length - ;i++) {
check = i;
for (int j = i + ;j < length;j++) {
if (arr[j] < arr[check]) {
check = j;
}
}
if (i != check) {
swap(&arr[i],&arr[check]);
}
}
}
性能分析
稳定性 : 稳定
-->存在两个相同的元素时,肯定是下标小的元素先进入有序区,而且在值相等的情况下有序区元素不会被替换
时间复杂度 : (最坏n²,最好n²,平均n²)
-->外层循环要执行n次,才能将n个数据全部加入有序区
无论数据是否有序,内层循环都要将所有的数据比较一遍,找到最小的元素
空间复杂度: 1
-->程序没有用到递归,临时变量不占用存储资源,因此空间复杂度为1
堆排序
堆排序是选择排序的改进版本,它比堆排序的性能要高很多.
要实现堆排序,首先要了解这几个知识点:
大根堆:每个节点的值都大于他的左右子树(小根堆反之)
完全二叉树:除了最后一层之外的其他每一层都被完全填充，并且所有结点都保持向左对齐。
在n个节点的完全二叉树中,叶子节点有(n+1)/2个,非叶子节点有(n-1)/2个
在堆中,下标为n的数的左子树为2n+1,右子树为2n+2
首先要能够将一组无序的数排列成大根堆,大根堆的构造方法如下:
...
外层循环从最后一个非叶子节点( length/2-1 )向根节点遍历,每遍历到一个数据,就执行下面操作:
设置一个根指针i,指向当前要操作树的根节点
比较该树的左右子树的值,将biger指针指向较大的子树
如果该子树的值比根节点还大(arr[biger]>arr[i]),将该子树的值与根节点交换,并将i指针指向该子树,使之成为新的根节点
......递归执行上一步操作,直到有根节点不小于左右子树为止
构造出大根堆之后,每次取整个堆的根节点(也就是第一个元素)存入有序区,将堆的最后一个元素作为根节点
剩下的元素继续构造大根堆,直到数据完全存入有序区
c程序实现:
void MkHeap(int arr[], int i, int length) {
int bigger = * i + ;
int temp;
if (bigger<length){
if (arr[bigger] < arr[bigger + ]) {
bigger++;
}
if (arr[i]<arr[bigger]){//如果子树比爹树大:把子树的值与爹树值交换,并让该子树成为新的爹树
swap(&arr[i], &arr[bigger]);
MkHeap(arr,bigger,length);
}
}
}
void HeapSort(int arr[], int length) {
//从最后一个非叶子节点往根找
for (int i = length / - ;i >= ;i--) {
MkHeap(arr, i, length);
}
for (int j = length - ;j > ;j--) {
swap(&arr[j],&arr[]);
MkHeap(arr, , j-);
}
}
性能分析
稳定性 : 不稳定
-->先假设稳定,然后举个反例:
{6,7,7}这棵树左右子树的值都是7,本来左子树是应该是在前面的,但是6加入有序区之后右子树的7会被提到最上面,这样他们的顺序就被调换了
时间复杂度 : (最坏nlogn,最好nlogn,平均nlogn <底数可以写2也可以不写,根据时间复杂度的性质无论底数是几结果都是一样的> )
-->根据性质,外层循环会执行n次(n代表排序的元素个数),将所有数据全部加入有序区.
而内层递归函数指针从0到n,每次增长前一个的2n+1,忽略掉常数1,也就是执行log(2)(N)次
因此为Nlog(2)(N)次,忽略掉底数2,时间复杂度为nlogn
插入/希尔排序适合接近有序的数据,而堆排序适合非常无序的数据,因为无论数据多么杂乱,希尔排序的时间复杂度都是nlogn
(不放心再说一下 : log(2)(N)是log以2为底n的对数 , 不是log2乘n , 因为底数打不出来只能这样写)
空间复杂度: log(2)(N)
-->这里程序递归了log(2)(N)次,每次递归都占用内存,因此空间复杂度为log(2)(N)
当然也可以使用循环的方式实现,但是那样写出来结构略显混乱,不如递归方式清晰
不稳定算法口诀:快些选队
参考资料(文中的部分图片和思想来自以上材料):
1. 《新编数据结构习题与解析》
2. 文章
https://www.cnblogs.com/skywang12345/p/3603935.html
https://www.cnblogs.com/jingmoxukong/p/4302891.html
http://www.sohu.com/a/341037266_115128
https://www.toutiao.com/a6593273307280179715/?iid=6593273307280179715
3. 关于快速排序算法的稳定性？ - 知遥其实是德鲁伊的回答:https://www.zhihu.com/question/45929062/answer/262452296