Java列表排序

记录遇到过的所有排序实现, 持续更新.

 

1. 冒泡排序: 效率O（N*N），比较N*N/2，交换N*N/4

public void bubbleSort() {
	int[] arr = {1, 6, 3, 5, 10, 4};
	int arrLen = arr.length;

	// 内层循环变量
	int in;
		
	// 外层循环变量
	int out;

	// 外层循环次数 = 列表长度 - 1
	for (out = arrLen - 1; out > 0; out -- ) {

		// 内层循环总是从最前面开始
		// 依次与列表中每个元素比较
		// 排除已经比较过的值, out及其之后的值
		for (in = 0; in < out; in ++) {

			// 当前排序方式为升序排序
			// 即: arr[0] < arr[1] < ... < arr[arr.length - 1]
			if (arr[in] > arr[in + 1]) {
				// 每当遇到满足条件(当前值大于后一个值)时, 就交换值
				swap(arr, in, in + 1);
			}
		}
	}
}

2. 选择排序: 效率：O（N*N），比较N*N/2，交换<N

public void selectSort() {
	int[] a = {1, 6, 3, 5, 10, 4};
	int in;		// 内层循环控制
	int out;	// 外层循环次数
	int min;	// 最小值下标

	// 外层循环次数 = 列表长度 - 1
	for(out=0, len = a.length - 1; out<len; out++) {

		// 假设第一个总是最小值
		// 这一步相当于得到天平秤中其中一个盘中的砝码
		min=out;

		// in=out+1 : 当前值无需与当前值比较
		for(in=out+1; in<nElems; in++)

			// in下标所指定的值是天平秤中另一个砝码
			// 比较符号"<"就是称的规则
			// 当前需要的是较小的值放在左边, 即升序排序
			if(a[in]<a[min])
				min=in;

		// 自己与自己交换无任何意义
		if (out != min)
			swap(out,min);
	}
}

3. 插入排序, 序列中部分有序时效率较高, 逆序排序效率几乎与冒泡无异. 效率：O（N*N）, 比较N*N/4，复制N*N/4

Public void InsertionSort() {
	int[] a = {3, 5, 7, 6, 10, 4};

	// 外层循环次数 = 列表长度 - 1
	for(int out=1, len = a.length - 1; out<len; out++) {
		int temp=a[out]
		int in=out;

		// 从左到右依次比较, 
		// 其比较规则类似于冒泡,
		// 不同点在于每次排序列表长度都比上一次加1, 且结束条件是找到首个满足交换条件(a[in‐1]>temp)的值
		// 例如:
		//     当 out=3, tmp=6;时
		//     当前循环执行次数为2次
		while(in>0 && a[in‐1]<temp) {
			a[in]=a[in‐1];				
			‐‐in;
		}

		// 如果当前值(tmp)比所有已排序(下标out以前)的值都小时, 则插入到列表首个位置(in=0)
		a[in]=temp;
	}
}