算法-排序（简单排序）

发表于 | 分类于

算法模板

Comparable接口 

Interface Comparable<T>

该接口对实现它的每个类的对象强加一个整体排序，这个排序被称为类的自然排序，类的compareTo方法被称为其自然比较方法 

**int compareTo(T o)** 将此对象与指定的对象进行比较以进行排序 
    返回一个负整数，零或正整数，因为该对象小于，等于或大于指定对象  

 compareTo() 必须实现一个完整的比较序列，即：
 自反性，对于所有的 v ， v=v ；
 反对称性，对于所有的 v<w 都有 v>w ，且 v=w 时 w=v ；
 传递性，对于所有的 v 、 w 和 x ，如果 v<=w 且 w<=x ，则 v<=x 。

算法模板：

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
28
29
public abstract class Sort<T extends Comparable<T>>{
	public static void sort(T[] a){			
	}
	//比较数据大小
	protected static boolean less (Tv,T w){
		return v.compareTo(w)<0;
	}
	//交换数据
	protected static void exch(T[] a,int i,int j){
		T temp=a[i];
		a[i]=a[j];
		a[j]=temp;
	}
	//输出显示排序好的数据	
	protected static void show(T[] a){
		for(int i=0;i<a.length;i++){
			System.out.println(a[i]+" ");
		}
		System.out.println();
	}
	//判断是否排序
	public static boolean isSorted(T[] a){
		for(int i=1;i<a.length;i++){
			if(less(a[i],a[i-1]))
					return false;
		}
		return true;
	}
}

注意：只要是实现了Comparable（自己定义的数据类型要重写compareTo方法）的数据类型都可以用次模板排序

选择排序

1
2
3
4
5
6
7
8
9
10
11
12
13
public class Selection<T extends Comparable<T>> extends Sort<T>{
	@Override
	public static void sort(T[] 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 /2 次比较和 N 次交换
    时间复杂度 T(N)=O(N*N);
  2. 运行时间和输入无关:已经有序的数组或是主键全部相等的数组和一个元素随机排列的数组所用的排序时间一样长
  3. 数据移动是最少的:选择排序用了 N 次交换,交换次数和数组的大小是线性关系

冒泡排序

冒泡排序：从左到右不断交换相邻逆序的元素，在一轮的循环之后，可以让未排序的最大元素上浮到右侧。在一轮循环中，如果没有发生交换，就说明数组已经是有序的，此时可以直接退出。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class Bubble<T extends Comparable<T>> extends Sort<T>{
	@Override
	public static void sort(T[] a){
		int N=a.length;
		boolean flag=false;
		for(int i=N-1;i>0 && !flag;i--){
			flag=true;
			for(int j=0;j<i;j++){
				if(less(a[j+1],a[j])){
					exch(a,j,j+1);
					flag=false;
				}
			}
		}
	}
}```

插入排序

1
2
3
4
5
6
7
8
9
10
public class Insertion<T extends Comparable<T>> extends Sort<T>{
	public static <T extends Comparable<T>> void sort(T[] 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);
			}
		}
	}
}

算法分析：

  1. 对于随机排列的长度为 N 且主键不重复的数组，平均情况下插入排序需要～ N 2 /4 次比
    较以及～ N 2 /4 次交换。最坏情况下需要～ N 2 /2 次比较和～ N 2 /2 次交换，最好情况下需要 N-1次比较和 0 次交换
    时间复杂度 T(N)=O(N*N)

  2. 插入排序所需的时间取决于输入中元素的初始顺序

  3. 插入排序需要的交换操作和数组中倒置的数量相同，需要的比较次数大于等于倒置的
    数量，小于等于倒置的数量加上数组的大小再减一

插入排序对于实际应用中常见的某些类型的非随机数组很有效
插入排序对于部分有序的数组十分高效，也很适合小规模数组

比较：对于随机排序的无重复主键的数组，插入排序和选择排序的运行时间是平方级别的，两者之比应该是一个较小的常数

希尔排序

希尔排序：对于大规模的数组，插入排序很慢，因为它只能交换相邻的元素，每次只能将逆序数量减少 1。希尔排序的出现就是为了改进插入排序的这种局限性，它通过交换不相邻的元素，每次可以将逆序数量减少大于 1。希尔排序使用插入排序对间隔 h 的序列进行排序。通过不断减小 h，最后令 h=1，就可以使得整个数组是有序的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class Shell<T extends Comparable<T>> extends Sort<T>{
	public static <T extends Comparable<T>> void sort(T[] a){ 
		int N=a.length;
		int h=1;
		while(h<N/3){
			h=h*3+1;
		}		
		while(h>=1){
			for(int i=h;i<N;i++){
				for(int j=i;j>0 && less(a[j],a[j-h]);j-=h){
					exch(a,j,j-h);
				}
			}
			h=h/3;
		}
	}
}
  • 算法的性能不仅取决于 h，还取决于 h 之间的数学性质
  • 目前最重要的结论是希尔排序的运行时间达不到平方级别
  • 希尔排序比插入排序和选择排序要快得多，并且数组越大，优势越大

MergeSort(归并排序)

In-place merge(原地归并)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class Merge<T extends Comparable<T>> extends Sort<T> {
	protected T[] aux;
	protected  void merge(T[] a,int lo,int mid,int hi){
		int i=lo;   //左边数组的起始位置
		int j=mid+1;  ////右边数组的起始位置
		for(int k=lo;k<=hi;k++){
			aux[k] =a[k];
		}
		for(int k=lo;k<=hi;k++){
			if(i>mid){
				a[k]=aux[j++];  //左边的子数组用尽
			}else if(j>hi){
				a[k]=aux[i++];   //右边的子数组用尽
			}else if(less(aux[j],aux[i])){
				a[k]=aux[j++];
			}else{
				a[k]=aux[i++];
			}
		}
	}

This method merges by first copying into the auxiliary array aux[] then merging back to a[].

In the merge (the second for loop), there are four conditions:

  1. left half exhausted (take from the right),
  2. right half exhausted (take from the left),
  3. current key on right less than current key on left (take from the right),
  4. current key on right greater than or equal to current key on left (take from the left).

Top-down mergesort(自顶向下的归并排序)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class UptoDpwnMergeSort<T extends Comparable<T>> extends Merge{
	public void sort(T[] a){
		aux=(T[]) new Comparable[a.length];
		sort(a,0,a.length-1);
	}
	private void sort(T[] a,int lo,int hi){
		if(hi<=lo){
			return;
		}
		int mid=lo+(hi-lo)/2;
		sort(a,0,mid);
		sort(a,mid+1,hi);
		merge(a,lo,mid,hi); 
	}
}

A: The code is a recursive(递归) mergesort implementation based on this abstract inplace merge.

B: It is one of the best-known examples of the utility of the divide-and-conquer(分而治之) paradigm for efficient algorithm design

C: the sort code simply provides an organized way to sequence the calls to the merge() method

算法分析：

A: Top-down mergesort uses between ½ N lg N and N lg N compares to sort any array of length N
时间复杂度：T(N)=O(N lg N)

B: Top-down mergesort uses at most 6N lg N array accesses to sort an array of length N

Bottom-up mergesort(自底向上的排序)

1
2
3
4
5
6
7
8
9
10
11
public class BottomtoUpMergeSort<T extends Comparable<T>> extends Merge<T> {
	public void sort(T[] a){
		int N=a.length;
		aux = (T[]) new Comparable[a.length];
		for(int sz=1;sz<N;sz=sz+sz){
			for(int lo=0;lo<N-sz;lo+=sz+sz){
				merge(a,lo,lo+sz-1,Math.min(lo+sz+sz-1, N-1));
			}
		}
	}
}

算法分析：
Bottom-up mergesort uses between ½ N lg N and N lg N compares and at most 6N lg N array accesses to sort an array of length N.

both the number of compares usedby mergesort in the worst case and the minimum number of compares that any compare-basedsorting algorithm can guarantee are ~N lg N

归并排序在最坏的情况下的比较次数和任意基于比较的排序算法所需的最少比较次数都是~ NlgN