logo头像
Snippet 博客主题

十大经典排序算法

总图


稳定性:当序列中存在两个或两个以上的关键字相等的时候,如果排序前序列中1领先于2,那么排序后1如果仍旧领先2的话,则是稳定的。(相等的元素排序后相对位置不变)

冒泡排序

1、把第一个元素与第二个元素比较,如果第一个比第二个大,则交换他们的位置。接着继续比较第二个与第三个元素,如果第二个比第三个大,则交换他们的位置….
2、我们对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对,这样一趟比较交换下来之后,排在最右的元素就会是最大的数。
3、除去最右的元素,我们对剩余的元素做同样的工作,如此重复下去,直到排序完成。

1
2
3
4
5
6
7
8
9
10
11
12
13
public static int[] BubbleSort(int [] a){
int len = a.length;
for(int i = 0; i< len; i++){
for(int j =1; j< len-i;j++){
if(a[j]<a[j-1]){
int temp = a[j];
a[j] = a[j-1];
a[j-1] = temp;
}
}
}
return a;
}

选择排序

1、首先,找到数组中最小的那个元素,其次,将它和数组的第一个元素交换位置(如果第一个元素就是最小元素那么它就和自己交换)。
2、其次,在剩下的元素中找到最小的元素,将它与数组的第二个元素交换位置。
3、如此往复,直到将整个数组排序。
selectSort

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public static int[] selectSort(int[] a) {
int len = a.length;
for(int i =0; i< len-1; i++){
//找出剩余的最小的那个坐标
int min = i;
for(int j =i+1; j<len;j++){
if(a[j]<a[min]){
min = j;
}
}
//交换
int temp = a[i];
a[i] = a[min];
a[min] = temp;
}
return a;
}

插入排序

1、从数组第2个元素开始抽取元素。
2、把它与左边第一个元素比较,如果左边第一个元素比它大,则继续与左边第二个元素比较下去,直到遇到不比它大的元素,然后插到这个元素的右边。
3、继续选取第3,4,….n个元素,重复步骤 2 ,选择适当的位置插入。
insertSort

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public static int[]  insertSort(int[] a){
int len = a.length;
for(int i=1; i< len; i++){
//从后往前找出最合适的位置,要交换位置,要倒着开始交换
for(int j = i; j>0; j--){
if(a[j]<a[j-1]){
int temp = a[j];
a[j] = a[j-1];
a[j-1] = temp;
}else{ //不用一直遍历到0,一旦不符合了,就说明换完了,就跳出内循环
break;
}
}
}
return a;
}

希尔排序(插入排序的变种)

希尔排序的思想是采用插入排序的方法
1、先让数组中任意间隔为 h 的元素有序
2、刚开始 h 的大小可以是 h = n / 2,接着让 h = n / 4,
3、让 h 一直缩小,当 h = 1 时,也就是此时数组中任意间隔为1的元素有序,此时的数组就是有序的了。

归并排序(重点,待补充代码)

1、将一个大的无序数组有序,我们可以把大的数组分成两个,然后对这两个数组分别进行排序,之后在把这两个数组合并成一个有序的数组。由于两个小的数组都是有序的,所以在合并的时候是很快的。
2、通过递归的方式将大的数组一直分割,直到数组的大小为 1,此时只有一个元素,那么该数组就是有序的了,之后再把两个数组大小为1的合并成一个大小为2的,再把两个大小为2的合并成4的 ….. 直到全部小的数组合并起来。

快速排序(重点)

挖坑填数进行总结
1.i =L; j = R; 将基准数挖出形成第一个坑a[i]。
2.j–由后向前找比它小的数,找到后挖出此数填前一个坑a[i]中。
3.i++由前向后找比它大的数,找到后也挖出此数填到前一个坑a[j]中。
4.再重复执行2,3二步,直到i==j,将基准数填入a[i]中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public static int[] quickSort(int s[], int l, int r) {
if (l < r)
{
int i = l, j = r, x = s[l];
while (i < j)
{
while(i < j && s[j] >= x){// 从右向左找第一个小于x的数
j--;
}

if(i < j){
s[i++] = s[j];
}

while(i < j && s[i] < x){ // 从左向右找第一个大于等于x的数
i++;
}
if(i < j){
s[j--] = s[i];
}
}
s[i] = x;
quickSort(s, l, i - 1); // 递归调用
quickSort(s, i + 1, r);
}
return s;
}

堆排序

1、根据初始数组去构造初始堆(构建一个完全二叉树,保证所有的父结点都比它的孩子结点数值大)。
2、每次交换第一个和最后一个元素,输出最后一个元素(最大值),然后把剩下元素重新调整为大根堆。

计数排序

计数排序是一种适合于最大值和最小值的差值不是不是很大的排序。
基本思想:就是把数组元素作为数组的下标,然后用一个临时数组统计该元素出现的次数,例如 temp[i] = m, 表示元素 i 一共出现了 m 次。最后再把临时数组统计的数据从小到大汇总起来,此时汇总起来是数据是有序的。

桶排序

1、桶排序就是把最大值和最小值之间的数进行瓜分,例如分成 10 个区间,10个区间对应10个桶,我们把各元素放到对应区间的桶中去
2、再对每个桶中的数进行排序,可以采用归并排序,也可以采用快速排序之类的。
之后每个桶里面的数据就是有序的了,我们在进行合并汇总。

基数排序

1、先以个位数的大小来对数据进行排序,接着以十位数的大小来对数进行排序,接着以百位数的大小……
2、排到最后,就是一组有序的元素了。不过,他在以某位数进行排序的时候,是用“桶”来排序的。
由于某位数(个位/十位….,不是一整个数)的大小范围为0-9,所以我们需要10个桶,然后把具有相同数值的数放进同一个桶里,之后再把桶里的数按照0号桶到9号桶的顺序取出来,这样一趟下来,按照某位数的排序就完成了

参考文献
必学十大经典排序算法,看这篇就够了
菜鸟网站排序算法总结
Jack Cui 堆排序