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

(排序一)冒泡排序+选择排序+归并排序

程序员文章站 2022-05-12 16:38:02
...

冒泡排序:

从数组末尾开始依次与姓林的进行比较,如果a[i]<a[i+1] 交换位置,这样在第一轮比较后最大的冒在第0位置,然后再从末尾开始比较,然后次大的在第1的位置,依此类推

时间复杂度:O(n^2)

额外空间复杂度:O(1)

public static void popsort(int []arr) {
		if (arr == null || arr.length < 2) {
			return;
		}
		for(int i=0;i<arr.length-1;i++) {
			for(int j=arr.length-1;j>i;j--){
				if (arr[j-1] < arr[j]) 
					swap(arr, j, j - 1);
			}
		}
	}

选择排序:

从第0个位置开始,遍历一遍数组选择最大的放在第一个位置,然后遍历2~n位置,选最大的放在第二个位置。每次遍历一遍得到最大的放在第i位置

时间复杂度:O(n^2)

额外空间复杂度:O(1)

public static void choosort(int []arr) {
		if (arr == null || arr.length < 2) {
			return;
		}
		for(int i=0;i<arr.length-1;i++) {
			for(int j=i+1;j<arr.length;j++) {
				if(arr[i]<arr[j])
					swap(arr, i, j);
			}
		}
	}

代码2:


	public static void choosort2(int []arr) {
		if (arr == null || arr.length < 2) {
			return;
		}
		for(int i=0;i<arr.length-1;i++) {
			int maxIndex=i;
			for(int j=i+1;j<arr.length;j++) {
				if(arr[maxIndex]<arr[j])
					maxIndex=j;
			}
			swap(arr,maxIndex,i);
		}
	}

插入排序:

从第1位置开始,与前面的比较

第i次循环,第i位置的数与前面的依次比较,如果大于前面的,交换,继续比较,直到前面的数比自己大停止。

时间复杂度:O(n^2)

额外空间复杂度:O(1)

public static void insertsort(int []arr) {
		if (arr == null || arr.length < 2) {
			return;
		}
		for(int i=1;i<arr.length;i++) {
			for(int j=i;j>0;j--)
			{
				if(arr[j]>arr[j-1])
					swap(arr,j,j-1);
				if(arr[j]<=arr[j-1])
					break;
			}
		}
	}

swap函数:

private static void swap(int [] arr,int i, int j) {
		int t;
		t=arr[i];
		arr[i]=arr[j];
		arr[j]=t;	
	}

三个排序的稳定性分析:

插入排序和冒泡排序可以做到稳定性(相同大小的数保持原来位置)

选择排序不可以(在进行交换时,比如第2位置是一个较小的数数字0与后面的选择出来的最大的数交换时,可能会越过中间的数字0)