1、概述：
这篇文章介绍几种常见的排序算法，分别从其方法，实现，性能三方面进行归纳,因为在下来的代码实现中要调用一些常见方法，故将这些方法封装到一个类Example中，方便调用，具体实现如下：
class Example{
//1、应用接口传参比较大小
private static boolean less(Comparable v,Comparable w){
return v.compareTo(w) < 0;
}
//2、应用接口传参实现位置交换
private static void exch(Comparable[] a, int i,int j){
Comparable t = a[i];a[i] = a[j]; a[j] = t;
}
//3、应用接口传参实现数据输出
private static void show(Comparable[] a){
for (int i = 0; i < a.length; i++) {
System.out.print(a[i]+””);
System.out.println();
}
}
//4、应用接口传参判断是否有序
private static boolean isSorted(Comparable [] a){
for (int i = 0; i < a.length; i++) {
if(less (a[i] ,a[i-1])) return false;
}
return true;
}
}
2、选择排序
- 方法：首先，找到数组中最小的元素，其次，将它和数组的第一个元素交换位置（如果第一个元素就是最小的元素，则进行交换），而后，依次寻找剩下元素中最小的元素，直到将整个数组排序（即不断地选择剩余元素中最小者，故称选择排序）
- 实现：
public class Selected {
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 < N; j++) {
if(less(a[j],a[min])){min = j;}
exch(a,i,min);
}
}
}
}
- 性能：1、对于长度为N的数组，选择排序需要大约N²/2次比较和N次交换；
2、运行时间和输入无关，即为了找到数组中最小的元素，每次都需要将数组扫描一遍，所以一个有序的数组和一个无序的数组所要进行比较的次数是相同的，故而该算法并没有对输入的初始状态进行考虑；
3、数据移动最少，选择排序数据交换N次，交换次数与数组大小线性关系，其他任何算法都不具备这个特征。
3、插入排序
- 方法：类似桥牌的整理方法，我们把牌一张张整理好，整理过程中，将每一张牌插入到其他已有序的牌中的任意位置，在计算机实现中，为了给要插入的元素腾出空间，我们需要将其余所有元素在插入之前都向右移动一位，即为插入排序。
- 实现：
public class Insertion{
public static void sort(Comparable[] a){
//将a[]按照升序排列；
int N = a.length;
for (int i = 0; i < N; i++) {
for (int j = i; j > 0 && less(a[j],a[j-1]); j–) {
exch(a,j,j-1);
}
}
}
}
- 性能：
1、对于随机排列的长度为N且主键不重复的数组，平均情况下插入排序需要N²/4次比较以及N²/4次交换，最坏情况需要N²/2次比较以及N²/2次交换，最好情况需要N-1次比较和次交换。
2、插入排序需要的交换操作和数组中倒置的数量相同，（倒置的数量+数组大小-1）=>需要的比较的次数>=（倒置的数量）
4、希尔排序
- 方法：希尔排序是基于插入排序的快速排序算法，对于大规模数组插入极为有效，它的方法是使数组中任意间隔为h的元素都是有序的，这样的数组被称为h有序数组，对于任意以1结尾的h序列，我们都能将数组排序，这就是希尔排序。
- 实现：
public class Shell{
public static void sort(Comparable[] a){
int N = a.length;
int h = 1;
while(h < N/3){h = 3*h + 1;}//1,4,13,40,……….
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;
}
}
}
Input:S H E L L S O R T E X A M P L E
Output: 13-sort: P H E L L S O R T E X A M S L E
4-sort: L E E A M H L E P S O L T S X R
1-sort: A E E E H L L L M O P R S S T X
- 性能：1、希尔排序可以用于大型数组，时间复杂度下降
2、使用递增序列1，4，13…….的希尔排序所需的比较次数不会超过N的若干倍乘以递增序列的长度。