深入理解排序算法java版

发表于 | | 阅读次数:

简单插入排序

插入排序的基本思想是将整个排序序列划分成“有序区间”和“无序区间”，然后逐个将无序区间中的元素插入到前面有序区间了，逐步将这个区间变有序。其算法复杂度为O(n^2)
其算法描述如下：

1
2
3
4
5
6
7
8
9
10
11
12
描述：插入排序
输入：待排序数组array,数组最后一个元素位置lastIndex
输出：排序好的数组array
从i=2位置作为待插入元素，直至最后一个元素，循环如下操作
	设置array[0]为待待插入值array[i]作为哨兵
	取出待插入值tmp=array[i]
	从j=i位置开始循环
		如果tmp小于array[j-1],array[j]=array[j-1]
		否则，结束循环
		j减一
	j为最终的插入位置，array[j]=tmp

其java实现如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
 * 插入排序，数组从1开始存放
 * @param array
 * @param lastIndex 要排序的最后一个元素的位置
 */
public void insertSort(T[] array, int lastIndex) {
	for(int i=2;i<=lastIndex;i++) {
		array[0]=array[i];//标兵位
		int j;
		for(j=i;array[0].compareTo(array[j-1])<0;j--) {
			array[j]=array[j-1];
		}
		array[j]=array[0];
	}
}

希尔排序

希尔排序是插入排序的一个变种，它使用缩减的增量来进行插入排序，它的时间复杂度达到了O(n^3/2),也就是亚平方级别。
其算法描述如下：

1
2
3
4
5
6
7
8
9
10
描述：希尔排序算法
输入：待排序数组array,数组最后一个元素位置lastIndex
输出：排序好的数组array
从gap=lastIndex/2开始，在gap>0时，每次gap/2, 循环以下操作
	从i=gap+1位置开始，在i<=lastIndex时，i每次加1, 循环以下操作
		tmp=array[i],取出当前待排序元素
		从j=i开始，在j>=gap时，j每次减gap,循环以下操作
			如果tmp<array[j],array[j]=array[j-gap]
		array[j]=tmp

其java实现如下

1
2
3
4
5
6
7
8
9
10
11
public void shellSort(T[] array, int lastIndex) {
	for(int gap= lastIndex/2;gap>0; gap/=2) {//确定不同的增量过程
		for(int i=gap+1;i<=lastIndex;i++){//从第一个增量后的值开始到最后所有的值
			T tmp=array[i];
			int j;
			for(j=i; j>gap&&tmp.compareTo(array[j-gap])<0; j-=gap) 
				array[j]=array[j-gap];
			array[j]=tmp;
		}
	}
}

堆排序

如果我们想要从小到大排序，那么我们需要使用大根堆进行堆排序的过程，堆排序有两个主要过程：初始建堆过程和移除堆顶元素进行调整的过程，两个过程都用到了“下滤”的调整算法，整个堆排序的算法复杂度可以是O(N logN)，其实现思路如下。
首先是下滤的过程

1
2
3
4
5
6
7
8
9
10
11
描述：大根堆的下滤调整过程
输入：大根堆的数组array,数组的最后一个元素位置lastIndex,要调整的节点位置i
输出：下滤位置i元素后的数组
取出当前要挑战节点的值value=array[i]
如果i*2<=lastIndex,进行如下循环
	选取i节点值左右孩子节点（i*2和i*2+1）值较大的节点位置为child
	如果array[child]>value,令array[i]=array[child]
	否则，结束循环
	i=child
array[i]=value

初始建堆的过程很简单，就是从最后一个非叶子节点开始进行下滤，直至根节点，其java代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
private void buildHeap(T[] array, int lastIndex) {
	for(int i=lastIndex/2;i>0;i--)
		percDown(i,array,lastIndex);
}
private void percDown(int i, T[] array, int lastIndex) {
	T tmp=array[i];
	int child;
	while(i*2<=lastIndex) {
		child =i*2;
		if(child!=lastIndex&&array[child].compareTo(array[child+1])<0)
			child++;
		if(tmp.compareTo(array[child])<0)
			array[i]=array[child];
		else
			break;
		i=child;
	}
	array[i]=tmp;
	
}

写完了下滤过程，那么我们的堆排序过程就可以利用下滤调整的过程来进行描述

1
2
3
4
5
6
7
8
9
描述：堆排序
输入：待排序数组array,数组最后一个元素位置lastIndex
输出：排序好的数组array
堆数组array中1-lastIndex的元素进行初始建堆
从i=lastIndex开始，在i>1成立时，每次i-1,做如下循环
	交换1位置和i位置的值
	对从1位置的值在数组array中1到i-1进行下滤操作
结束

其java代码如下

1
2
3
4
5
6
7
8
9
10
public void heapSort(T[] array, int lastIndex) {
	buildHeap(array,lastIndex);//从小到大排序建立大根堆
	T tmp;
	for(int i=lastIndex;i>1;i--) {
		tmp=array[i];
		array[i]=array[1]; //将首节点移到1最后
		array[1]=tmp;//复制另一个节点
		percDown(1, array, i-1);
	}
}

快速排序

正如起名，快速排序是使用最为广泛的一种排序算法，它采用了分治的策略，所以很容易用递归的方式来描述整个过程，快速排序的统计效率达到了O(N logN)，但是实际上快速排序的最坏情况可以达到O(N^2),算法的实际效率和选取的轴值有密切的关系。
简单的讲来，我们首先从待排序序列中选取一个轴值，根据这个轴值将整个序列划分成两部分，左边的部分所有的值小于轴值，而右边的部分所有的值大于轴值，然后我们再采用同样的方法对左右两部分进行排序，直到每部分只有一个值为止。详细的算法描述如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
描述：快速排序
输入：待排序数组array,待排序的第一个元素位置left,最后一个元素位置right
输出：排序好的array
如果left<right,进行如下操作
	令low=left，high=right
	零pivotValue=array[low]
	当low<high的时候循环执行如下操作
		当low<high并且array[high]>pivot值的时候，循环执行
			high--
		array[low]=array[high]
		当low<high并且array[low]<pivot值的时候，执行循环
			low++
		array[high]=array[low]
	array[low]=pivot的值
quickSort(array,left,low-1),对left到low-1位置的元素进行操作
quickSort(array,low+1,right)，堆low+1到right位置的元素进行操作

其代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public void quickSort(T[] array, int left, int right) {//元素从1开始存放
	if(left<right) {
		int low=left;
		int high=right;
		T pivot=array[low];
		while(low<high) {
			while(low<high&&array[high].compareTo(pivot)>0) 
				high--;//右指针左移
			array[low]=array[high];
			while(low<high&&array[low].compareTo(pivot)<0)
				low++;//左边的较小，左移
			array[high]=array[low];
		}
		array[low]=pivot;
		quickSort(array, left, low-1);
		quickSort(array, low+1, right);
	}
}

归并排序

归并排序也是一个O(N logN)的排序算法，但是归并排序需要额外O(N)的空间，归并排序的基本操作是将两个排序好的数组进行合并，而合并的过程不可避免的要使用临时数组。
合并的简述过程是这样的，对于A,B两个排序好的数组，合并到数组C。A，B各维护一个指针pa,pb指向当前扫描到的位置，如果A[pa]<B[pb]，就将A[pa]复制到C[pc]，并且pa和pc向前移动一个，否则就将B[pb]复制到C[pc]，并且pb和pc向前移动一个。如果A,B中有剩余的，就将剩余的全部赋值给C。
写好了合并的算法，那么归并排序的算法就可以在这个基础上得以搭建，其核心思想是将数组分成两部分，然后采用递归的方式排序连个部分，最后进行合并操作，详细如下

1
2
3
4
5
6
7
8
9
描述：归并排序
输入：待排序数组array,待排序最左边的元素位置left，最右边的元素位置right
输出：排序好的数组array
如果left<right，就可以进行如下操作
	center=(left+right)/2
	排序left到center位置的元素
	排序center+1到right位置的元素
	合并array[left到center]和array[center+1到right]

其算法实现如下

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
30
31
32
33
34
35
36
37
38
39
40
41
42
public void mergeSort(T[] array, int lastIndex) {
	T[] tmpArray=(T[]) new Comparable[lastIndex+1];
	mergeSort(array, tmpArray, 1, lastIndex);
}
void mergeSort(T[] array, T[] tmpArray, int left, int right) {
	if(left<right) {
		int center = (left+right)/2;
		mergeSort(array, tmpArray, left, center);
		mergeSort(array, tmpArray, center+1, right);
		merge(array,tmpArray,left,center+1,right);
	}
}
/**
 * 合并相邻的两部分排序好的数组
 * @param array 原数组
 * @param tmpArray 临时数组，不用每次递归就重新建立临时数组
 * @param leftPos 左边开始位置
 * @param rightPos 右边开始位置，左边结束位置为leftPos-1
 * @param rightEnd 右边结束位置
 */
public void merge(T[] array, T[] tmpArray, int leftPos, int rightPos, int rightEnd ) {
	int leftEnd=rightPos-1;
	int curPosition=leftPos;
	int numElements=rightEnd-leftPos+1;
	
	while(leftPos<=leftEnd && rightPos<=rightEnd) {
		if(array[leftPos].compareTo(array[rightPos])<=0)
			tmpArray[curPosition++]=array[leftPos++];
		else
			tmpArray[curPosition++]=array[rightPos++];
	}
	
	while(leftPos<=leftEnd)
		tmpArray[curPosition++]=array[leftPos++];
	while(rightPos<=rightEnd)
		tmpArray[curPosition++]=array[rightPos++];
	
	for(int i=0;i<numElements;i++,rightEnd--)
		array[rightEnd]=tmpArray[rightEnd];
}

全部源码

全部源码请点击这里，你同样可以在我的博客(点击这里)上看到这篇文章。

坚持原创技术分享，您的支持将鼓励我继续创作！