老实说

JAVA排序算法

2017/04/09 sort algorithm

Java排序算法

1.插入排序 稳定

原理：从有序序列中选择合适的位置进行插入

复杂度：最好 - 最坏 - 平均 O(n) - O(n^2) - O(n^2)

public void insertSort(int[] a) {
	if (null ==a || a.length < 2) {
		return;
	}
	for (int i = 1; i < a.length; i++) {
		int temp = a[i]; // 暂存
		int j = i - 1;
		while (j >= 0 && temp < a[j]) {
			a[j+1] = a[j];
			j--;
		}
		a[j+1] = temp;
	}
}

2.冒泡排序 稳定

原理：相邻两个元素比较大小进行交换，一趟冒泡后会有一个元素到达最终位置

复杂度：最好 - 最坏 - 平均 O(n) - O(n^2) - O(n^2)

public void bubbleSort(int[] a) {
	if (null == a || a.length < 2) {
		return;
	}
	boolean flag;
	for (int i = 0; i < a.length - 1; i++) {
		flag = false;
		for (int j = 0; j < a.length - 1 - i; j++) {
			if (a[j] > a[j+1]) {
				int temp = a[j];
				a[j] = a[j+1];
				a[j+1] = temp;
				flag = true;
			}
			if (flag == false) {
				return;
			}
		}
	}
}

3.希尔排序(缩小增量排序) 不稳定

按步长进行分组，组内直接插入，缩小增量再次进行此步骤，增量为1时相当于一次直接插入。

复杂度：最好O(n) - 最坏O(n^s 1<s<2) - 平均O(n^1.3)

public void shellSort(int[] a) {
	if (null == a || a.length < 2) {
		return;
	}
	for (int d = a.length/2; d > 0; d/=2) {
		for (int i = d; i < a.length; i++) {
		// 内部直接插入
			int temp = a[i];
			int j = i - d;
			while (j >= 0 && temp < a[j]) {
				a[j+d] = a[j];
				j -= d;
			}
			a[j+d] = temp;
		}	
	}
}

4.选择排序 不稳定

原理：每次从无序序列选择一个最小的

复杂度：最好O(n^2) - 最坏O(n^2) - 平均O(n^2)

public void selectSort(int[] a) {
	if (null == a || a.length < 2) {
		return;
	}

	for (int i = 0; i < a.length; i++) {
		int k = i;
		for (int j = i + 1; j < a.length; j++) {
			if (a[j] < a[k]) {
				k = j;
			}
		}
		if (k != i) {
			int temp = a[k];
			a[k] = a[i];
			a[i] = temp;
		}
	}
}

5.快速排序 不稳定

原理：分治+递归

复杂度：最好O(nlgn) - 最坏O(n^2) - 平均O(nlgn)

public void quickSort(int[] a, int low, int high) {

	if (low < high) {
		int mid = partition(a, low, high);
		quickSort(a, low, mid - 1);
		quickSort(a, mid + 1, high);
	}
}

private int partition(int[] a, int low, int high) {
	int pivot = a[low];

	while (low < high) {
		while (low < high && a[high] >= pivot) {
			high--;
		}
		a[low] = a[high];
		while (low < high && a[low] <= pivot) {
			low++;
		}
		a[high] = a[low];
	}
	a[low] = pivot;

	return low;
}

选取pivot的方式：固定基准元 随机基准 三数取中

快排的优化：针对随机数组+有序数组+重复数组

1.当待排序序列的长度分割到一定大小后，使用插入排序<三数取中+插入排序>：效率提高一些，但是都解决不了重复数组的问题。

2.在一次分割结束后，可以把与Key相等的元素聚在一起，继续下次分割时，不用再对与key相等元素分割 <三数取中+插排+聚集相同元素>

6.归并排序 稳定

原理：两个有序序列的合并，方法：分治 + 递归

复杂度：最好O(nlgn) - 最坏O(nlgn) - 平均O(nlgn)

public void mergeSort(int[] a, int low, int high) {
	int mid = (low + high) / 2;
	if (low < high) {
		//左边
		mergeSort(a, low, mid);
		//右边
		mergeSort(a, mid + 1, high);
		//有序序列归并
		merge(a, low, mid, high);
	}
}

private void merge(int[] a, int low, int mid, int high) {
	int[] temp = new int[high - low + 1];
	// 左指针
	int i = low;
	// 右指针
	int j = mid + 1;
	// 临时数组指针
	int k = 0;

	while (i <= mid && j <= high) {
		if (a[i] < a[j]) {
			temp[k++] = a[i++];
		} else {
			temp[k++] = a[j++];
		}
	}

	//左边剩余
	while (i <= mid) {
		temp[k++] = a[i++];
	}

	//右边剩余
	while (j <= high) {
		temp[k++] = a[j++];
	}

	// 倒出
	for (int t = 0; t < temp.length; t++) {
		a[t + low] = temp[t]; 
	}
}

7. 堆排序

原理：利用堆的特性

复杂度：O(nlogn) [平均 - 最好 - 最坏]

// 堆排序
public void heapSort(int[] a) {
	if (null == a || a.length < 2) {
		return;
	}
	buildMaxHeap(a);

	for (int i = a.length - 1; i >= 0; i--) {
		int temp = a[0];
		a[0] = a[i];
		a[i] = temp;
		adjustHeap(a, i, 0);
	}
}

// 建堆
private void buildMaxHeap(int[] a) {
	for (int i = a.length/2; i >= 0; i--) {
		adjustHeap(a, a.length, i);
	}
}

// 调整堆
private void adjustHeap(int[] a, int size, int parent) {
	int left = 2 * parent + 1;
	int right = 2 * parent + 2;
	int largest = parent;

	if (left < size && a[left] > a[largest]) {
		largest = left;
	}

	if (right < size && a[right] > a[largest]) {
		largest = right;
	}

	if (parent != largest) {
		int temp = a[parent];
		a[parent] = a[largest];
		a[largest] = temp;
		adjustHeap(a, size, largest);
	}
}

8.基数排序[稳定]

原理：分配加收集

复杂度： O(d(n+r)) r为基数d为位数 空间复杂度O(n+r)

// 基数排序
	public void radixSort(int[] a, int begin, int end, int digit) {
		// 基数
		final int radix = 10;
		// 桶中的数据统计
		int[] count = new int[radix];
		int[] bucket = new int[end-begin+1];
		
		// 按照从低位到高位的顺序执行排序过程
		for (int i = 1; i <= digit; i++) {
			// 清空桶中的数据统计
			for (int j = 0; j < radix; j++) {
				count[j] = 0;
			}
			
			// 统计各个桶将要装入的数据个数
			for (int j = begin; j <= end; j++) {
				int index = getDigit(a[j], i);
				count[index]++;
			}
			
			// count[i]表示第i个桶的右边界索引
			for (int j = 1; j < radix; j++) {
				count[j] = count[j] + count[j - 1]; 
			}
			
			// 将数据依次装入桶中
            // 这里要从右向左扫描，保证排序稳定性 
			for (int j = end; j >= begin; j--) {
				int index = getDigit(a[j], i);
				bucket[count[index] - 1] = a[j];
				count[index]--;
			}
			
			// 取出，此时已是对应当前位数有序的表
			for (int j = 0; j < bucket.length; j++) {
				a[j] = bucket[j];
			}
		}
	}
	
	// 获取x的第d位的数字，其中最低位d=1
	private int getDigit(int x, int d) {
		String div = "1";
		while (d >= 2) {
			div += "0";
			d--;
		}
		return x/Integer.parseInt(div) % 10;
	}
}

Search

    Table of Contents