排序算法一般分为比较类算法和非比较类算法,这篇文章记录的是部分比较类算法。
在比较类算法中,我们通过比较来决定元素之间的相对位置,然后交换元素,使多个元素逐渐有序,所以我们首先介绍几种交换元素的方法(这里用来举例的数据结构是数组):
借助临时变量存储
int temp=arr[i]; arr[i]=arr[j]; arr[j]=temp;
加减法运算
arr[i]=arr[i]+arr[j]; arr[j]=arr[i]-arr[j]; arr[i]=arr[i]-arr[j];
异或运算
arr[i]=arr[i]^arr[j]; arr[j]=arr[i]^arr[j]; arr[i]=arr[i]^arr[j];
算法复杂度
上图中提到稳定性,那么解释一下排序算法稳定性的概念。
排序稳定性 : 假定在待排序的记录序列中,存在多个相同的元素,如果经过排序后, 这些记录的相对次序保持不变,即在原序列中,r[i]=r[j],且r[i]在r[j]之前,而在排序后的序列中,r[i]仍在r[j]之前,则称这种排序算法是稳定的;否则称为不稳定的。以上是比较官方的解释,事实上,稳定性主要还得看算法的具体情况,有时比较条件的改变(例如>改为>=),也会改变稳定性。
冒泡排序
(1)冒泡排序每一轮都比较出一个最大的数,如果数组有(arr.length)个元素,则只需比较(arr.length-1)轮,相当于第一轮把最大的数移到了数组的末位,第二轮把第二大的数移到了数组的倒数第二位......依此类推,最后一个元素自然就是最小的,也就是首位,这是外层循环,也就是总共需要排序的元素个数;
(2)在每一轮比较中,比较数组中相邻的元素,比较大的就往后移,而且数组尾部已排序的部分可以直接跳过,所以比较的次数=总次数-已进行比较的次数,这就是是内层循环,说白了也就是需要排序的元素个数=总共需要排序的元素个数-已进行比较的元素个数;
(3)优化:
- 如果内层循环时发现数组没有再交换,说明都已经按顺序排好了,可直接跳出外层循环;
for(int i=0;iarr[j+1]){
int temp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=temp;
flag=true;//发生交换则尚未排序完成
}
}
if(!flag) break;//若不需要交换,则证明后续数组元素皆已排序完成,直接跳出
}
- 记录下每轮最后一次交换的索引位置,每轮的最后一次交换的索引确定了该位置后的元素均已排序,则只需对该位置前的数进行比较,这就是下一轮的比较次数,免去了外层循环的运算,当索引位置为0时,则排序完成,跳出循环;
int n=arr.length-1;//记录每轮需要比较的次数
int last=0;//作为记录每轮最后一次交换的索引
while(true){
for(int j=0;jarr[j+1]){
int temp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=temp;
last=j;//发生交换则记录索引
}
}
n=last;
if(last==0) break;//索引为0,则证明后续数组元素皆已排序完成,直接跳出
}
选择排序
(1)顾名思义,选择排序就是每一轮遍历未排序的数组元素,选择最小的,将其添加到已排序的部分中,知道整个数组有序,同样也只需要排序(arr.length-1)轮,最后一个元素自然就是最大的;
(2)外层循环的下标表示每轮选择最小元素要交换的位置,通过内层循环将该位置之后的数组元素与外层下标对应的元素逐一比较,若找到更小的元素,则将新下标赋值给临时变量,内层循环结束后,将两下标对应的元素换位,总的来说,也就是将最小的、第二小的、第三小的元素......逐个换位到下标为0、为1、为2...的位置;
for(int i=0;i
(3)可以看出,冒泡排序和选择排序是有一些相似之处的,每一轮的目的都是找出一个最大或最小的元素,移动到已排序的部分中,不同的是,选择排序是通过遍历比较大小挑选出目标元素,而冒泡则是不停地比较相邻元素,将较大值往后移,一般来说选择快一些,毕竟交换次数少;
(4)优化:可考虑在每一次选择出最小元素的同时,选择出最大元素,确定两元素位置,这里懒得写了。
插入排序
(1)顾名思义,将待排序的数组元素插入到已排序数组元素的相对位置中去,从后往前依次与已排序的数组元素比较,该元素更小就往前移,其他的元素往后移;
(2 )执行步骤:
for(int i=1;i0&&temp
(3)优化:在需要将待排序的数组元素插入到已排序的数组序列中(即小于前一个元素)时,可选择二分插入,通过二分查找判断需要插入的位置,但即使是二分查找也需要将插入位置后的数组元素依次右移,懒得写了。
希尔排序
(1)当某个数组中大数比较靠前,而小数比较靠后,像[10,8,9,2,3,1]这样,此时如果使用插入排序的话,就必须将这些较大的数和较小的数一直移到数组两端,很影响效率,所以就有了希尔排序,也就是插入排序的改进算法;
(2)希尔排序的核心在于一个关键词——增量,通过增量进行分组,举例:就上面那个数组,长度为6,增量的初始值为长度除2(一般除2,有兴趣搜搜,这里不多解释),那么我们就将整个数组分成6/2=3组,即[10,2],[8,3],[9,1],对分出来的组分别进行插入排序,可以自己画个图,这能尽量地将大数往后移,小数往前移,然后缩小增量,即再除2,变成3/2=1组......
(3)执行步骤:
for(int gap=arr.length/2;gap>0;gap/=2){//表示增量在减少,分出来的组也越少,最后的组就最有序
for(int i=gap;i=gap&&arr[j-gap]>temp;j-=gap){//在每组间,如果比前面元素小,就执行插入排序,都是从后往前找,所以j-=gap
arr[j]=arr[j-gap];//前面的数往后移,腾一个位置出来
}
arr[j]=temp;//位置填充
}
}
(4)分析一波,我个人觉得增量的主要作用就是减少移动次数,增量大的时候,元素之间隔得远,这个时候交换是为了尽量让两端元素符合大的在后,小的在前,然后逐渐缩小增量,分出来的组就减少,每组的元素增多,相当于是让“邻里”元素变得有序,差不多就是这样。
快速排序
(1)首先,快速排序很快,它的核心在于每一轮排序选中左端元素作为基准点,将比基准点大的和小的元素分别移动到基准点两边,作为两个分区,接下来就是分治的思想,在子分区中重复以上操作,当子分区的元素个数<=1时,就排序完成了;
(2)快排的方式有好几种,接下来这一种我觉得好理解一些, 首先,在数组的右端通过索引j来寻找比基准点小的元素,在数组的左端通过索引i来寻找比基准点大的元素,交换对应元素的位置,直到两个索引相遇,证明左边都比基准点小,右边都比基准点大,然后将相遇的这个点和基准点交换位置,相当于隔了基准点这么一堵墙,接着就是在墙的两边递归以上操作,不停地建墙,等什么时候墙与墙之间的元素个数<=1时,那就证明有序了;
(3)执行代码:
public static void sort(int[] a,int l,int r){
if(l>=r){
return;
}
int i=l;
int j=r;
int key=a[i];//记录基准点
while(ikey){//寻找比基准点小的元素
j--;
}
while(i
(4)注意事项:往上看,代码中首先寻找比基准点小的元素,这是因为当两下标相遇后,在交换基准点和相遇点的时候,能保证相遇点一定比基准点小,移到左边才不会出错,然后都需要保证i
(文章用于个人记录和整理,欢迎提出意见)



