排序算法大汇总-选择、插入、希尔、归并、快速、堆排
选择排序
这是排序算法是最简单的一种，过程是这样的：
首先找到数组中最小的那个元素，其次将它和数组的第一个元素交换位置（如果第一个元素就是最小元素那么他就和自己交换）。再次，在剩下的元素中找到最小的元素，将它与数组的第二个元素交换位置。如此往复，直到将整个数组排序
这种方法叫做选择排序，因为他在不断选择剩余元素中的最小者。
对于长度为N的数组，选择排序大概需要N^2/2次比较和N次交换。
特点：
- 运行时间和输入无关。
- 数据移动是最少的。
代码示例
package sort;
import java.util.Scanner;
public class Select {
public static void sort(Comparable[] a) {
int N=a.length;
for (int i = 0; i <N; i++) {
int min=i;
for (int j = i + 1; j < a.length; j++) {
if (less(a[j] ,a[min]))
{
System.out.println(less(a[j] ,a[min]));
min=j;
}
}
exch(a,i,min);
}
}
public static boolean less(Comparable v, Comparable w) {
return v.compareTo(w)<0;
}
public static void exch(Comparable[] a, int i, int j) {
Comparable t = a[i];
a[i] = a[j];
a[j]=t;
}
public static void show(Comparable[] a) {
for (int i = 0; i < a.length; i++) {
System.out.println(a[i]);
}
}
public static boolean isSorted(Comparable[] a) {
for (int i = 1; i < a.length; i++)
if (less(a[i], a[i - 1]))
return false;
return true;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
StringBuffer stringBuffer = new StringBuffer();
String[] a;
stringBuffer.append(scanner.nextLine());
a = stringBuffer.toString().split(",");
show(a);
System.out.println("********************");
sort(a);
assert isSorted(a);
show(a);
}
}
注意事项
上述中Comparable接口的对象进行排序，上述代码是对String类型的对象进行的排序。因此如果输入的是同样的位数的整数，上述代码可是正确实现排序。
例如 输入为：12，43，21，42，25
但是如果输入的整数的位数是不一致的，则得不到正确的结果
例如 输入为：12，43，211，42，25
出现上述问题的原因在于我们是对String类型进行的排序，String类型排序的依据是ASCii码表。
当然如果将上述的数组换成了int类型，那么在输入数值的时候就能够得到正确结果了
插入排序
我们在打扑克牌的时候用的插牌就可以看作是插入排序，将每一张摸到的牌插入到其他已经有序的牌中的适当位置。
计算机中为了给插入的元素腾出空间，需要将剩余所有元素在插入之前都向右移动一位。
插入排序所需要的时间取决于输入中元素的初始顺序。平均情况下插入排序需要~N^ 2/4次比较和~N^ 2/4次交换。最坏情况下需要~N^ 2/2次比较和~N^2/2次交换，最好情况下需要N-1次比较和0次交换。
代码示例
package sort;
import java.util.Scanner;
public class Insert {
public static void sort(Integer[] a) {
int N=a.length;
for (int i = 1; i < N; i++) {
for (int j = i; j > 0 && less(a[j], a[j - 1]); j--) {
exch(a,j,j-1);
}
}
}
public static boolean less(Integer v, Integer w) {
return v.compareTo(w)<0;
}
public static void exch(Integer[] a, int i, int j) {
Integer t = a[i];
a[i] = a[j];
a[j]=t;
}
public static void show(Integer[] a) {
for (int i = 0; i < a.length; i++) {
System.out.println(a[i]);
}
}
public static boolean isSorted(Integer[] a) {
for (int i = 1; i < a.length; i++)
if (less(a[i], a[i - 1]))
return false;
return true;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
StringBuffer stringBuffer = new StringBuffer();
String[] b;
stringBuffer.append(scanner.nextLine());
b = stringBuffer.toString().split(",");
Integer[] a=new Integer[b.length];
for (int i = 0; i < b.length; i++) {
a[i] = Integer.parseInt(b[i]);
}
show(a);
System.out.println("********************");
sort(a);
assert isSorted(a);
show(a);
}
}
注意
倒置：指的是数组中的两个顺序颠倒的元素。
如果数组中倒置的数量小于数组大小的某个倍数，则称这个数组是部分有序的。
以下几种典型的部分有序的数组：
- 数组中每个元素距离他的最终位置都不远
- 一个有序的大数组接一个小数组
- 数组中只有几个元素的位置不正确
插入排序对上述有序数组很有效
当倒置的数量很少时，插入排序很可能比本章中的其他任何算法都要快。
插入排序需要的交换操作和数组中倒置的数量相同，需要的比较次数大于等于倒置的数量，小于等于倒置的数量加上数组的大小再减一。
希尔排序
希尔排序为了加快速度简单的改进了插入排序，交换不相邻的元素以对数组的局部进行排序，并最终用插入排序将局部有序的数组排序。
思想：
使数组中任意间隔为h的元素都是有序的，这样的数组被称为h有序数组。换句话说，一个h有序数组就是h个互相独立的有序数组编织在一起组成的一个数组。
image.png
可以借助上图帮助理解一下。
代码示例
package sort;
import java.util.Scanner;
public class Shell {
public static void sort(Integer[] a) {
int N=a.length;
int h=1;
while (h < N / 3) {
h = 3 * h + 1;
}
while (h >= 1) {
for (int i = h; i < N; i++) {
for (int j = i; j >= h && less(a[j], a[j - h]); j -= h) {
exch(a,j,j-h);
}
}
h=h/3;
}
}
public static boolean less(Integer v, Integer w) {
return v.compareTo(w)<0;
}
public static void exch(Integer[] a, int i, int j) {
Integer t = a[i];
a[i] = a[j];
a[j]=t;
}
public static void show(Integer[] a) {
for (int i = 0; i < a.length; i++) {
System.out.println(a[i]);
}
}
public static boolean isSorted(Integer[] a) {
for (int i = 1; i < a.length; i++)
if (less(a[i], a[i - 1]))
return false;
return true;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
StringBuffer stringBuffer = new StringBuffer();
String[] b;
stringBuffer.append(scanner.nextLine());
b = stringBuffer.toString().split(",");
Integer[] a=new Integer[b.length];
for (int i = 0; i < b.length; i++) {
a[i] = Integer.parseInt(b[i]);
}
show(a);
System.out.println("********************");
sort(a);
assert isSorted(a);
show(a);
}
}
** 至今为止，世界上还没能透彻理解希尔排序的性能**
对于希尔排序，应该看更多的东西来加深理解，现在理解的还不是特别透彻，只是知道了他是如何进行的排序。
