选择排序和插入排序
2018-06-13 本文已影响0人
世界是一个圆_
0.排序中离不开两个方法
排序中最常用的就是比较和互换两个方法，为了简便，在此处提取出来
//交换
public static void exch(int[] arr,int i,int j){
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
//比较
public static boolean less(int x, int y){
return x < y;
}
1.选择排序
1.1排序方式
1.找到数组中最小的元素，将它和数组的第一个元素交换位置。
2.在剩下的元素中找到最小的元素，将它与第二个元素交换位置
3.重复进行...
1.2实现
public static void selectionSort(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[min])) {
min = j;
}
}
exch(arr, i, min);
}
}
选择排序轨迹图.png
1.3复杂度
- 对于长度为N的数组，选择排序需要 N^2/2次比较和N次替换
1.4特点
- 优点：移动数据是最少的，只需要N次
- 缺点：花费时间与输入无关，一个升序的数组和一个倒序的数组所花费的时间是一样，因为此特点，下面来讲一下插入排序
2.插入排序
和选择排序不同的是，插入排序所需的时间取决于输入中元素的初始顺序。例如，对一个很大且其中已经有序（接近有序）的数组进行排序比对随机顺序或者逆序的数组进行排序要快的多。
2.1排序方式
索引 i 从1开始,依次比较i左侧相邻的元素(逆序)，如arr[i]与arr[i-1], arr[i-1]与arr[i -2]... 如果左侧的小于右侧的，就交换这两个元素，这样就保证了i左侧的元素都是有序的。
下一轮循环时，索引为i+1,由于上一次的排序导致i左侧的数据是有序的，所以只要找出i+1左侧需要交换的位置后，将元素插入此位置，就可以跳入到下一次循环了，即i+2
2.2实现
public static void insertSort(int[] arr){
int len = arr.length;
for(int i = 1; i < len; i++){
for(int j = i; j > 0 && less(arr[j],arr[j-1]); j--){
exch(arr,j,j-1);
}
}
}
2.3复杂度
- 平均情况：N^2 /4次比较和N^2/4次交换
- 最差情况，如逆序的数组，N^2 /2次比较和N^2/2次交换
- 最好情况，如顺序的数组，N-1次比较和0次交换
2.4用二分查找优化插入排序
由于插入排序索引左侧的数组是有序的，可以考虑采用二分查找法减少比较次数，代码如下
public static void sort(int[] a) {
int n = a.length;
for (int i = 1; i < n; i++) {
int v = a[i];
int lo = 0, hi = i;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (less(v, a[mid])) hi = mid;
else lo = mid + 1;
}
// insetion sort with "half exchanges"
// (insert a[i] at index j and shift a[j], ..., a[i-1] to right)
for (int j = i; j > lo; --j)
a[j] = a[j-1];
a[lo] = v;
}
}
4.对比
选择排序不会访问索引左侧的元素，插入排序不会访问索引右侧的元素，如下图所示：
对比.png
