排序算法的复杂度、稳定性与代码实现

算法 复杂度与稳定性

相应Code

package SortTest;

import java.util.Arrays;
import java.util.PriorityQueue;

public class SortTest {

	static PriorityQueue<Integer> maxQueue;
	static PriorityQueue<Integer> minQueue;
	public static void main(String[] args) {
		int[] nums = {1,3,2,9,6,5,3,2};
		int N = nums.length;
		
		//直接插入排序
		int[] InsertNums = new int[N];
		System.arraycopy(nums, 0, InsertNums, 0, N);
		InsertSort(InsertNums, N);
		System.out.print("直接插入排序之前：" + Arrays.toString(nums));
		System.out.println("直接插入排序结果：" + Arrays.toString(InsertNums));
		
		//希尔排序
		int[] ShellNums = new int[N];
		System.arraycopy(nums,0,ShellNums,0,N);
		ShellSort(ShellNums,N);
		System.out.print("希尔排序之前：" + Arrays.toString(nums));
		System.out.println("希尔排序结果：" + Arrays.toString(ShellNums));
		
		//冒泡排序
		int[] BubbleNums = new int[N];
		System.arraycopy(nums,0,BubbleNums,0,N);
		BubbleSort(BubbleNums, N);
		System.out.print("冒泡排序之前：" + Arrays.toString(nums));
		System.out.println("冒泡排序结果：" + Arrays.toString(BubbleNums));
		
		//快速排序
		int[] QuickNums = new int[N];
		System.arraycopy(nums, 0, QuickNums, 0, N);
		QuickSort(QuickNums, 0, N-1);
		System.out.print("快速排序之前：" + Arrays.toString(nums));
		System.out.println("快速排序结果：" + Arrays.toString(QuickNums));
		
		//归并排序
		int[] MergeNums = new int[N];
		System.arraycopy(nums, 0, MergeNums, 0, N);
		int[] temp = new int[N];
		MergeSort(MergeNums, 0, N-1, temp);
		System.out.print("归并排序之前：" + Arrays.toString(nums));
		System.out.println("归并排序结果：" + Arrays.toString(MergeNums));
		
		//直接选择排序
		int[] SelectNums = new int[N];
		System.arraycopy(nums, 0, SelectNums, 0, N);
		SelectSort(SelectNums, N);
		System.out.print("直接选择排序之前：" + Arrays.toString(nums));
		System.out.println("直接选择排序结果：" + Arrays.toString(MergeNums));
		
		//堆排序
		int[] HeapNums = new int[N];
		System.arraycopy(nums, 0, HeapNums, 0, N);
		HeapSort(HeapNums, N);
		System.out.print("堆排序之前：" + Arrays.toString(nums));
		System.out.println("堆排序结果：" + maxQueue);
	}
	
	public static void InsertSort(int[] InsertNums,int N) {
		
		int i,j,k;
		for(i=1;i<N;i++) {
			for(j=i-1;j>=0;j--) {
				if(InsertNums[j] <= InsertNums[i])
					break;
			}
			if(j != i-1) {
				int temp = InsertNums[i];
				for(k=i-1;k>j;k--) {
					InsertNums[k+1] = InsertNums[k];
				}
				InsertNums[k+1] = temp;
			}
		}
	}
	
	public static void ShellSort(int[] ShellNums,int N) {
		
		int gap = N / 2,i,j;
		while(gap > 0) {
			for(i=gap;i<N;i++) {
				for(j=i-gap;j>=0;j-=gap) {
					if(ShellNums[j+gap] < ShellNums[j]) {
						int temp = ShellNums[j+gap];
						ShellNums[j+gap] = ShellNums[j];
						ShellNums[j] = temp;
					}
				}
			}
			gap /= 2;
		}
	}
	
	public static void BubbleSort(int[] BubbleNums,int N) {
		
		int i,j;
		for(i=0;i<N;i++) {
			for(j=1;j<N-i;j++) {
				if(BubbleNums[j-1] > BubbleNums[j]) {
					int temp = BubbleNums[j];
					BubbleNums[j] = BubbleNums[j-1];
					BubbleNums[j-1] = temp;
				}
			}
		}
	}
	
	public static void QuickSort(int[] QuickNums,int start,int end) {
		if(start > end)
			return;
		int ken = QuickNums[start];
		int i=start,j=end;
		while(i < j) {
			while(i < j && QuickNums[j] > ken) {
				j--;
			}
			if(i < j) {
				QuickNums[i] = QuickNums[j];
				i++;
			}
			while(i < j && QuickNums[i] < ken) {
				i++;
			}
			if(i < j) {
				QuickNums[j] = QuickNums[i];
				j--;
			}
		}
		QuickNums[i] = ken;
		QuickSort(QuickNums, start, i-1);
		QuickSort(QuickNums, i+1, end);
	}
	
	public static void MergeSort(int[] MergeNums,int start,int end,int [] temp) {
		if(start < end) {
			int mid = start + (end - start) / 2;
			MergeSort(MergeNums, start, mid, temp);
			MergeSort(MergeNums, mid+1, end, temp);
			MergeArray(MergeNums, start, mid, mid+1, end, temp);
		}
	}
	
	public static void MergeArray(int[] MergeNums,int left,int leftEnd,int right,int rightEnd,int[] temp) {
		int i = left,j = right;
		int k = 0;
		while(i <= leftEnd && j <= rightEnd) {
			if(MergeNums[i] <= MergeNums[j]) {
				temp[k++] = MergeNums[i++];
			}else {
				temp[k++] = MergeNums[j++];
			}
		}
		while(i <= leftEnd) temp[k++] = MergeNums[i++];
		while(j <= rightEnd) temp[k++] = MergeNums[j++];
		for(int m=0;m<k;m++) {
			MergeNums[left+m] = temp[m];
		}
	}
	
	public static void SelectSort(int[] SelectNums,int N) {
		int i,j;
		for(i=0;i<N;i++) {
			int minIndex = i;
			for(j=i+1;j<N;j++) {
				if(SelectNums[j] < SelectNums[minIndex])
					minIndex = j;
			}
			int temp = SelectNums[i];
			SelectNums[i] = SelectNums[minIndex];
			SelectNums[minIndex] = temp;
		}
	}
	
	public static void HeapSort(int[] HeapNums,int N) {
		//小根堆
//		minQueue = new PriorityQueue<Integer>();
//		for(int i=0;i<N;i++) {
//			minQueue.add(HeapNums[i]);
//		}
		//大根堆
		maxQueue = new PriorityQueue<Integer>((a,b)->(b-a));
		for(int i=0;i<N;i++) {
			maxQueue.add(HeapNums[i]);
		}
	}
}