本篇文章的排序讲解有:
冒泡排序
选择排序
直接插入排序
希尔排序
堆排序
快速排序
归并排序
讲解的大致的排序 就是这七种,讲解主要从思路,然后根据思路实现代码,然后进行计算优化,还有计算其时间复杂度,空间复杂度,稳定性
开篇:
那么,先从简单的开始:
冒泡排序
从c语言开始学到学完大致所有基本排序,第一个想必学的肯定是冒泡排序,冒泡排序,大致实现思路就是先经过一次的遍历将最大的(升序)放到最后一位,依次进行将倒数第二大的放在倒数第二位,反之降序相反。其实现过程大致同冒泡一样,排好一个数字就像冒出来一样,完成了一部分,故因此得名
大致运行动画如下:
那么代码实现思路就是,先将排好后该再最后一位的排好,对于升序,就像先比较,大的放在后面,代码就是:
if(arr[i]>arr[i+1])
swap(&arr[i],arr[i+1]);
然后遍历全部,就是加上循环,就可以遍历全部,这样就排好了一个//结束条件先不说
for (int j = 0; j < ; j++)
然后需要排号len-1个数就排好了全部
for (int i = 0; i < len - 1; i++)//趟数
所以代码全部即使:
void Bubble_sort(int* a, int len)
{
for (int i = 0; i < len - 1; i++)//趟数
{
for (int j = 0; j < len - i - 1; j++)
{
if (a[j] > a[j + 1])
{
swap(&a[j], &a[j + 1]);
count = 1;
}
}
}
}
但是,如果存在某一个数排好后,(但不是最后一个)再继续循环,就会空空浪费空间,所以优化:
void Bubble_sort(int* a, int len)
{
for (int i = 0; i < len - 1; i++)//趟数
{
//优化: int count = 0;
for (int j = 0; j < len - i - 1; j++)
{
if (a[j] > a[j + 1])
{
swap(&a[j], &a[j + 1]);
count = 1;
}
}
//优化:
if (count == 0)
{
break;
}
}
}
时间复杂度:0(n^2);
空间复杂度:0(1);
快速排序
然而有了冒泡排序,我们发现他的时间复杂度有点大,所有就有了与他同属于交换排序的——快速排序
快速排序是由东尼·霍尔所发展的一种排序算法,使用分治法(Divide and conquer)策略来把一个串行(list)分为两个子串行(sub-lists)。
快速排序又是一种分而治之思想在排序算法上的典型应用。本质上来看,快速排序应该算是在冒泡排序基础上的递归分治法。快速排序的名字起的是简单粗暴,因为一听到这个名字你就知道它存在的意义,就是快,而且效率高!它是处理大数据最快的排序算法之一了, 那么我们先讲解一下 霍尔 版的快速排序
其大致子路就为一个指针(left)从左开始,一个从右(right)开始,然后取left/right值为关键数
key,
left从左往右找到比key大的停止,
right从右往左找比key小的停止。 然后进行交换
结束条件就为left与right相遇,
最后在将key与相遇点的值交换(需要注意怎么确定相遇点是比key大还是比key小呢?)
对于这一点霍尔大佬也想到了解决方法:
如果开始选左边作为key,那么右边先走,保证了相遇点比key小/就为key的值。
反之右边作为key,那么在边先走,保证了相遇点比key大/就为key的值。
那么这时候相遇点左边全为比key小的值,右边全为比key大的值
然后在以相遇点为分界线分割 分为三个区间【left,相遇点-1】相遇点【相遇点+1,right】
然后依次循环直到left>right条件结束
运行效果动画:
实行起来还是比较容易的
int part(int* a, int left, int right)
{
//这里不采用指针,而是下标访问,如果感兴趣的话,可以尝试指针写法
int key = left;
while (left < right)
{
while (left < right && a[right] >= a[key])
{
right--;
}
while (left<right && a[left] <= a[key])//前一个是为了防止,在内存while已经不满足条件
{
left++;
}
swap(&a[left], &a[right]);
}
swap(&a[left], &a[key]);
return left;
}
void Hoare_sort(int* a, int left, int right)
{
if(left >= right)
{
return;
}
int key = part(a, left, right);
Hoare_sort(a, left, key - 1);
Hoare_sort(a, key + 1, right);
return ;
}
时间复杂度: O(nlogn)
空间复杂度:0(1);
虽然在最坏的情况下 的时间复杂度达到了 O(n²),但是人家就是优秀,在大多数情况下都比平均时间复杂度为 O(n logn) 的排序算法表现要更好,可是这是为什么呢,我也不知道。好在我的强迫症又犯了,查了 N 多资料终于在《算法艺术与信息学竞赛》上找到了满意的答案:
快速排序的最坏运行情况是 O(n²),比如说顺序数列的快排。但它的平摊期望时间是 O(nlogn),且 O(nlogn) 记号中隐含的常数因子很小,比复杂度稳定等于 O(nlogn) 的归并排序要小很多。所以,对绝大多数顺序性较弱的随机数列而言,快速排序总是优于归并排序。
本段取自菜鸟教程
针对优化就是key每次选择都为left与right与中间数的中间值,优化起来比较简单,不进行讲解,只展示代码,优化原理:防止了最坏情况0(n^2)的情况, 对应案例:(本来就有序);
int Get_key_Index(int* a, int left, int right)
{
int mid = (left + right) / 2;
if (a[left] < a[right])
{
if (a[left] > a[mid])
{
return left;
}
else if (a[right] < a[mid])
{
return right;
}
else
{
return mid;
}
}
else if(a[left]==a[right])
{
return left;
}
else
{
if (a[right] > a[mid])
{
return right;
}
else if (a[left] < a[mid])
{
return left;
}
else
{
return mid;
}
}
}
int part_1_sort(int* a, int left, int right)
{
int midi = Get_key_Index(a,left,right);
swap(&a[midi], &a[left]);
int keyi = left;
while (left < right)
{
while (left < right && a[keyi] <= a[right])
{
right--;
}
while (left<right && a[keyi] >= a[left])
{
left++;
}
swap(&a[left], &a[right]);
}
swap(&a[left], &a[keyi]);
return left;//返回此时keyi的下标数
}
void Quick_sort_Hoare(int* a,int begin,int end)
{
if (begin >= end)
{
return;
}
int keyi = part_1_sort(a, begin, end);
//三个区间 [begin,keyi-1] keyi [keyi+1,end]
Quick_sort_Hoare(a, begin, keyi - 1);
Quick_sort_Hoare(a, keyi + 1, end);
}
后人对于快排,有进行了别的版本1:挖坑版 2:双指针
挖坑版:
与霍尔版本不一样的就为key的位置想象为了坑,多了一个变量存储坑的下标,下面的实现原理跟霍尔相似了,只不过right与left找到对应的位置,将这个值补到这个坑,再将right/left的位置设置为坑
代码展示:
int part_2(int* a, int left, int right)
{
int key = a[left];
int hole = left;
while (left < right)
{
while (left < right && a[right] >= key)
{
right--;
}
a[hole] = a[right];
hole = right;
while (left < right && key >= a[left])
{
left++;
}
a[hole] = a[left];
hole = left;
}
a[hole] = key;
return left;//返回此时keyi的下标数
}
void Hole_sort(int* a, int left, int right)
{
if (left >= right)
{
return;
}
int key = part_2(a, left, right);
Hole_sort(a, left, key - 1);
Hole_sort(a, key + 1, right);
}
双指针法:
双指针法也是我认为快排最好实现的一种
其思路就为:
prev为头指针 cur为prev下一个的指针 key仍为最左边
1.然后cur找到比key小的
2.找到了先++prev,在swap(cur与prev)
3.在++cur
4.最后cur与prev之间全为比key大的,(当cur>right结束)
4.再进行swap(key与prev),key=prev return key;
最后递归结束条件:left>=right
代码实现比较简单:
void part_3_sort(int* a,int left,int right)
{
if (left >= right)
{
return;
}
int midi = Get_key_Index(a, left, right);
swap(&a[midi], &a[left]);
int keyi =left;
int cur = left+1;
int prev = left;
while (cur <= right)
{
if (a[cur] < a[keyi] && ++prev != cur)
{
swap(&a[cur], &a[prev]);
}
cur++;
}
swap(&a[keyi], &a[prev]);
keyi = prev;
part_3_sort(a, left, keyi - 1);
part_3_sort(a, keyi + 1, right);
}
void Quick_sort_Pointer_item(int* a, int begin, int end)
{
part_3_sort(a, begin, end);
}
利用栈去实现快排,这里就不讲解了,实现起来比较简单,需要注意的是栈是后进先出,然后入栈的时候入栈的为区间的边界值;
直接插入排序:
插入排序的代码实现虽然没有冒泡排序和选择排序那么简单粗暴,但它的原理应该是最容易理解的了,因为只要打过扑克牌的人都应该能够秒懂。插入排序是一种最简单直观的排序算法,它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。
插入排序和冒泡排序一样,也有一种优化算法,叫做拆半插入。
算法思路实现:
第一趟的情况下:将第一待排序序列第一个元素看做一个有序序列,把第二个元素当为最后一个进行,然后按照正常排序进行排序,
第二趟就将前2个待排序的元素看为一个有序序列,然后把第三个为最后一个,然后进行正常排序
动画演示如下:
代码实现如下:
void Insertion_sort(int* a,int len)
{
for (int i = 0; i < len-1; i++)
{
int end = i;
int tmp = a[i+1];
while (end >= 0)
{
if (a[end] > tmp)
{
a[end + 1] = a[end];
end--;
}
else
{
break;
}
a[end + 1] = tmp;
}
}
}
时间复杂度:0(n^2);
空间复杂度:0(1);
希尔排序:
希尔排序是由插入排序进行优化而来的
其原理很插入很相似,但是他是将间隔为gap(任意一个数,但不大于n),的为一组,然后总计gap个组
对每一组进行排序,这一整步骤为:预排序,达到的效果为:接近有序
然后再将gap的值缩小,在进行预排序,知道gap=1那一次排完后结束,
代码再实现的基础上就在插入上修改的一点地方
void shell_sort_1(int* a, int n)
{
int gap = n;
while (gap > 1)
{
gap = gap / 3 + 1;//分组,将间隔为gap分为一组,共gap个组
for (int i = 0; i < gap; i++)
{
for (int j = i; j < n - gap; j += gap)
{
int end = j;
int tmp = a[end+gap];
while (end >= 0)
{
if (tmp < a[end])
{
a[end + gap] = a[end];
end -= gap;
}
else
{
break;
}
}
a[end + gap] = tmp;
}
}
}
}
对比一下后 ,红笔为添加的,蓝色为修改的
然后我们还是可以优化的,将两个for循环转化为一个:
void shell_sort_2(int* a, int n)
{
int gap = n;
while (gap > 1)
{
//前gap个全不为一组
gap = gap / 3 + 1;//分组,将间隔为gap分为一组,共gap个组
for (int i = 0; i < n - gap; i++)
{
int end = i;
int tmp = a[end + gap];
while (end >= 0)
{
if (tmp < a[end])
{
a[end + gap] = a[end];
end -= gap;
}
else
{
break;
}
}
a[end + gap] = tmp;
}
}
}
时间复杂度:0(n^1.3~(logn)^2);//这个我是搜的,大概是这个,反之就是很快
空间复杂度:0(1);
选择排序:
选择排序是一种简单直观的排序算法,无论什么数据进去都是 O(n²) 的时间复杂度。所以用到它的时候,数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。
观看完动画我们也大概得知其实现原理,这里就不在多描述,
void Select_sort(int* a, int len)
{
int left = 0;
int right = len - 1;
while (left < right)
{
int min = left;
for (int i = left; i <= right; i++)
{
if (a[min] > a[i])
{
min = i;
}
}
//交换
swap(&a[min], &a[left]);
left++;
}
}
又或者两边同时走,这样写,进行优化。
void Select_sort(int* a, int len)
{
int left = 0;
int right = len - 1;
while (left < right)
{
int min = left;
int max = right;
for (int i = left; i <= right; i++)
{
if (a[min] > a[i])
{
min = i;
}
if (a[max] < a[i])
{
max = i;
}
}
//交换
if (max == left)
{
max = min;
}
swap(&a[min], &a[left]);
swap(&a[max], &a[right]);
left++;
right--;
}
}
时间复杂度:0(n ^2);
空间复杂度:0(1);
堆排序:
堆排序,就是利用了二叉树进行实现,其实先原理比较简单,但是代码用c实现比较多,这里不在展示,
提醒一点向下调整的整体效果是远远大于向上调整的。
时间复杂度:0(n logn);
空间复杂度:0(1);
归并排序:
归并排序
归并排序(Merge sort)是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。
作为一种典型的分而治之思想的算法应用,归并排序的实现由两种方法:
- 自上而下的递归(所有递归的方法都可以用迭代重写,所以就有了第 2 种方法);
- 自下而上的迭代;
在《数据结构与算法 JavaScript 描述》中,作者给出了自下而上的迭代方法。但是对于递归法,作者却认为:
However, it is not possible to do so in JavaScript, as the recursion goes too deep for the language to handle.
然而,在 JavaScript 中这种方式不太可行,因为这个算法的递归深度对它来讲太深了。
实现动画:
大致的实现图像:
再我首次学这个排序的时候,我都在想这个分的过程
在学玩后,就了解完了,无论任何情况,分的结果就为分为:每组只有一个数据,那么肯定这数据是有序的,然后再将相邻的两个组进行正常排序到另一个数组,这个过程就为治,就如图上所说:8 与 4这个两个组排好后就为4 ,8 这个是有序的,同理又有一组 5,7那么这两组在进行治,结果就如图:4,5,7,8
那么代码:(这个代码还是实现比较复杂的,首先要分,还要治)
分这很好解决,治是主要
这就为分:
int mid = (left + right) / 2;//(begin+end)>>1;
//[left,mid],[mid+1,right]
_MergeSort(a, left, mid, tmp);
_MergeSort(a, mid + 1, right, tmp);
归并排序还要另外开辟一个大小同样的数组,那么这个数组就是在治,的步骤使用
分完以后两个组,每组只有一个元素,然后进行排序拷贝到tmp数组,在将有序的再次拷回去
用语言表示很简单,但是对于递归理解还是有一定要求的,
还是需要练习:
代码:
void _MergeSort(int* a, int left, int right, int* tmp)
{
if (left >= right)
{
return;
}
int mid = (left + right) / 2;//(begin+end)>>1;
//[left,mid],[mid+1,right]
_MergeSort(a, left, mid, tmp);
_MergeSort(a, mid + 1, right, tmp);
//排完序了
int i = left;
//进行拷贝
int begin1 = left, begin2 = mid + 1;
int end1 = mid, end2 = right;
while (begin1 <= end1 && begin2 <= end2)
{
if (a[begin1] < a[begin2])//选1进
{
tmp[i++] = a[begin1++];
}
else
{
tmp[i++] = a[begin2++];
}
}
//不管谁先结束,再将剩下的拷贝进去
if (begin1 > end1)//1先结束 2没结束
{
while (begin2 <= end2)
{
tmp[i++] = a[begin2++];
}
}
else
{
while (begin1 <= end1)
{
tmp[i++] = a[begin1++];
}
}
//再最后拷贝回去
memcpy(a + left, tmp + left, sizeof(int) * (right - left + 1));
}
void MergeSort(int* a, int n)
{
int* tmp = malloc(sizeof(int) * n);
_MergeSort(a, 0, n - 1, tmp);
}
对于递归理解不了的,可以看一下非递归实现:
//归并排序--非递归实现
void _MergeSort_non(int* a, int left, int right, int* tmp)
{
int gap = 1;//每组的大小
int n = right + 1;
while (gap < n)
{
for (int i = 0; i <= right; i += gap * 2)
{
int j = i;
int begin1 = i,begin2= i + gap;
int end1 = i + gap - 1, end2 = i + 2 * gap - 1;
//printf("[%d,%d][%d,%d]\n", begin1, endl, begin2, end2);
//修正区间--防止越界
if (begin2 >= n)
{
break;
}
if (end2 >= n)
{
end2 = n - 1;
}
//进行区间排序--两个组合并排序,先排好序进去到tmp中,再拷贝回去
while (begin1 <= end1 && begin2 <= end2)
{
if (a[begin1] > a[begin2])//2进去
{
tmp[j++] = a[begin2++];
}
else
{
tmp[j++] = a[begin1++];
}
}
//不管谁先结束,再将剩下的拷贝进去
if (begin1 > end1)//1先结束 2没结束
{
while (begin2 <= end2)
{
tmp[j++] = a[begin2++];
}
}
else
{
while (begin1 <= end1)
{
tmp[j++] = a[begin1++];
}
}
//再从tmp拷回去
memcpy(a + i, tmp + i, sizeof(int) * (end2 - i + 1));
}
gap *= 2;
}
}
void MergeSort_non(int* a, int n)
{
int* tmp = malloc(sizeof(int) * n);
_MergeSort_non(a, 0, n - 1, tmp);
}