欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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

程序员文章站 2024-01-20 16:09:28
算法复杂度与稳定性相应Codepackage SortTest;import java.util.Arrays;import java.util.PriorityQueue;public class SortTest {static PriorityQueue maxQueue;static PriorityQueue minQueue;public static void main(String[] args) {...

算法复杂度与稳定性

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

相应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]);
		}
	}
}

本文地址:https://blog.csdn.net/weixin_42166320/article/details/107364542