算法导论——各种排序算法Java实现

一 插入排序

1.1 算法实现：

class InsertSort {
	public void sort(int[] arrToSort){
		int curIndex,insertIndex;
		int curNum;
		if(arrToSort.length<=1)
			return;
		for(curIndex=1;curIndex<arrToSort.length;curIndex++){
			curNum=arrToSort[curIndex];
			insertIndex=curIndex-1;
			while(insertIndex>=0 && arrToSort[insertIndex]>curNum){
				arrToSort[insertIndex+1]=arrToSort[insertIndex];
				insertIndex--;
			}
			insertIndex++;
			arrToSort[insertIndex]=curNum;
		}
	}
}

三个局部变量：curIndex，当前数字索引；curNum，当前索引所对应数字；insertIndex，当前数字应该放入的索引。

1.2 算法分析

稳定性：稳定

最坏时间复杂度：O(n*n)

平均时间复杂度：O(n*n)

空间复杂度：O(1)

二 归并排序

2.0 归并过程模拟

2.1 算法实现

class MergeSort {
	public void sort(int[] arrToSort, int beginIndex, int endIndex){
		if(beginIndex < endIndex){
			int midIndex=(beginIndex+endIndex)/2;
			sort(arrToSort, beginIndex, midIndex);
			sort(arrToSort, midIndex+1, endIndex);
			merge(arrToSort,beginIndex,midIndex,endIndex);
		}
	}

	void merge(int[] arrToSort, int beginIndex, int midIndex, int endIndex) {
		int indexLeft,indexRight;
		int lenLeft=midIndex-beginIndex+1;
		int lenRight=endIndex-midIndex;
		int[] arrLeft=new int[lenLeft+1];
		int[] arrRight=new int[lenRight+1];
		for(indexLeft=beginIndex;indexLeft<=midIndex;indexLeft++){
			arrLeft[indexLeft-beginIndex]=arrToSort[indexLeft];
		}
		for(indexRight=midIndex+1;indexRight<=endIndex;indexRight++){
			arrRight[indexRight-midIndex-1]=arrToSort[indexRight];
		}
		arrLeft[lenLeft]=Integer.MAX_VALUE;
		arrRight[lenRight]=Integer.MAX_VALUE;
		indexLeft=0;
		indexRight=0;
		for(int curIndex=beginIndex;curIndex<=endIndex;curIndex++){
			if(arrLeft[indexLeft]<=arrRight[indexRight]){//小于等于保证了算法的稳定性
				arrToSort[curIndex]=arrLeft[indexLeft];
				indexLeft++;
			}
			else{
				arrToSort[curIndex]=arrRight[indexRight];
				indexRight++;
			}
		}
	}
}

2.2 算法分析

稳定性：稳定

最好、最坏、平均时间复杂度都是：O(nlogn)

空间复杂度：O(n)

三 堆排序

（二叉）堆是一个顺序存储的完全二叉树。

3.1 算法实现

class HeapSort {
	public void sort(int[] arrToSort){    //arrToSort[0]不能存储有效数据
		Heap maxHeap=buildMaxHeap(arrToSort);                      //O(nlogn)
		for(int curIndex=maxHeap.length;curIndex>1;curIndex--){    //O(n)
			exchange(maxHeap.arrToSort, curIndex, 1);
			maxHeap.heapSize--;
			maxHeapify(maxHeap, 1);                            //O(nlogn)
		}
	}

	Heap buildMaxHeap(int[] arrToSort) {
		Heap heap=new Heap(arrToSort);
		for(int curIndex=heap.length/2;curIndex>=1;curIndex--){
			maxHeapify(heap,curIndex);
		}
		return heap;
	}

	void maxHeapify(Heap heap, int curIndex) {
		int largestIndex;
		int leftChildIndex=getLeftChileIndex(curIndex);
		int rightChildIndex=getRightChildIndex(curIndex);
		if(leftChildIndex<=heap.heapSize && heap.arrToSort[leftChildIndex]>heap.arrToSort[curIndex]){
			largestIndex=leftChildIndex;
		}
		else {
			largestIndex=curIndex;
		}
		if(rightChildIndex<=heap.heapSize && heap.arrToSort[rightChildIndex]>heap.arrToSort[largestIndex]){
			largestIndex=rightChildIndex;
		}
		if(largestIndex!=curIndex){
			exchange(heap.arrToSort, curIndex, largestIndex);
			maxHeapify(heap, largestIndex);
		}
	}
	
	void exchange(int[] arrToSort, int first, int second) {
    	int temp=arrToSort[first];
    	arrToSort[first]=arrToSort[second];
    	arrToSort[second]=temp;
	}
	public int getParentIndex(int childIndex){
		return childIndex/2;
	}
	public int getLeftChileIndex(int parentIndex){
		return 2*parentIndex;
	}
	public int getRightChildIndex(int parentIndex) {
		return 2*parentIndex+1;
	}
}

class Heap{
	public final int length;
	public int heapSize;
	public int[] arrToSort;
	
	public Heap(int[] arrToSort){
		length=arrToSort.length-1;
		heapSize=length;
		this.arrToSort=arrToSort;
	}
	public int getLength(){
		return length;
	}
}

3.2 算法分析

稳定性：不稳定，假设待排序数组所有数字相同，建大顶堆后，第一个数字放在堆顶，排序过程中，堆顶元素会被交换到最后、。

时间复杂度：O（nlogn）

空间复杂度：O（1）

四 快速排序

4.1 算法实现

class QuickSort {
	public void sort(int[] arrToSort, int beginIndex, int endIndex){
		if(beginIndex<endIndex){
			int partitionIndex=partition(arrToSort,beginIndex,endIndex);
			sort(arrToSort, beginIndex, partitionIndex-1);
			sort(arrToSort, partitionIndex+1, endIndex);
		}
	}

	int partition(int[] arrToSort, int beginIndex, int endIndex) {
		int key=arrToSort[endIndex];
		int finalSortedIndex=beginIndex-1;
		for(int curIndex=beginIndex;curIndex<endIndex;curIndex++){
			if(arrToSort[curIndex]<key){
				exchange(arrToSort, ++finalSortedIndex, curIndex);
			}
		}
		exchange(arrToSort, finalSortedIndex+1, endIndex);
		return finalSortedIndex+1;
	}
	void exchange(int[] arrToSort, int first, int second){
		int temp=arrToSort[first];
		arrToSort[first]=arrToSort[second];
		arrToSort[second]=temp;
	}
}

4.2 算法分析

partion实现思想：将数组划分为3段，第一段[beginIndex,i]<=pivot；第二段(i,j)>pivot；第三段[j,endIndex)未排序。pivot为枢轴。

稳定性：不稳定，在partition的过程中，相同的两个数可能会被交换位置，比如{2,3,3,2}，以末尾的2为枢轴，一次划分后，两个3会被交换。

平均时间复杂度：O（nlogn）

最坏时间复杂度：O（n*n）