排序算法的复杂度、稳定性与代码实现
程序员文章站
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