初级排序算法

初级排序算法

约定

首先我们约定几个工具方法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
比较a是否小于b,如果a<b返回true
*/
public static boolean less(int a,int b){
if(a<b){
return true;
}
return false;
}

/**
交换数组中i,j的值的位置
*/
public static void exchange(int[] arr,int i,int j){
int temp = arr[i];
arr[i]=arr[j];
arr[j]=temp;
}

选择排序

选择排序的思想是在一堆无序数字中,首先找出最小的数字,然后与数组第一个元素交换,然后再在剩下的元素中找最小的数字,与第二个交换。这样以此类推,直到整个排序完成。这个就是选择排序。选择排序的思想就是一直选择最小的那个值。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
选择排序,在传入前请判断arr是否为null
*/
public static void selectSort(int[] arr){
int len = arr.length;
for(int i=0;i<len;i++){
int min = i;
for(int j=i+1;j<len;j++){
if(less(arr[j],arr[i])){
min=j;
}
}
exchange(arr,i,min);
}
}

选择排序的特点,我们可以看到,选择排序每次都是从开始位置,一直到最后的位置,而且每次都需要遍历。所以输入的值关系并没有影响它,比如你输入“1,2,3,4”和“4,1,3,2”所需要的时间是相等的,因为它每次都会起始位置开始比较。数据移动是固定的,跟待比较的值呈线性关系。输入N个值,移动N次。另外有一点,如果一次遍历下来最小值是它本身,那么它还是会和自己做一次交换。
选择排序的时间复杂度怎么计算了?我们可以看到比较次数为:(n-1)+(n-2)+(n-3)+(n-4)+…+3+2+1,也就是任意i的位置都需要进行一次交换和(n-i-1)次比较。可以由公式得出为 $ (n-1)+(n-2)+(n-3)+(n-4)+…+3+2+1 ~ N^2/2 $

插入排序

如果你喜欢打牌,那么你肯定就知道插入排序就是怎么样了。比如你抓牌的时候会将抓到的牌按照大小顺序来排列,当你手上的牌是一个已好的顺序时候,下次抓出的牌你会将它插入到相应的位置。这就是插入排序的原理了。在实际中,我们用数组的方式来表示的话,当插入的已有的顺序中间的时间,那么其它位置的牌将需要全部移动一个位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public void insertSort(int[] arr){
int len = arr.length;

//为什么从1开始?,第0个位置相当于抓的第一张牌,做基础对比的。
for(int i=1;i<len;i++){
// i之前的数据,可以看作是已经排好序了
for(int j=i;j>0;j--){
if(less(arr[j],arr[j-1])){
exchange(arr,i,j);
}
}

}
}

插入排序如果是以下集中情况将会很有效:

  1. 数组中每个元素的位置离他们最终元素的位置都不远;
  2. 数组中只有几个元素的位置不正确;
  3. 一个有序的大数组接一个小数组。
坚持原创技术分享,您的支持将鼓励我继续创作!