Connor算法每日三题 - 冒泡排序、归并排序、计数排序

Learn && Live

虚度年华浮萍于世，勤学善思至死不渝

Hey，欢迎来到Connor的算法练习室，这个系列记录了我的算法练习过程，欢迎各位大佬阅读斧正！原创不易，转载请注明出处：http://t.csdn.cn/RyeII，话不多说我们马上开始！

1.比较相邻的元素。如果第一个比第二个大（小），就交换他们两个。

2.对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是 最大（小）的数。

3.针对所有的元素重复以上的步骤，除了最后已经选出的元素（有序）。

4.持续每次对越来越少的元素（无序元素）重复上面的步骤，直到没有任何无序元素

public void bubbleSort(int[] arr) {
	int temp = 0;
	boolean flag;
	for (int i = arr.length - 1; i > 0; i--) {
		flag = false;
		for (int j = 0; j < i; j++) {
			if(arr[j] > arr[j + 1]) {
				temp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = temp;
				flag = true;
			}
		}
		if(!flag){
			break;
		}
	}
}

1.将待排序的数列分成若干个长度为1的子数列

2.然后将这些数列两两合并；得到若干个长度为2的有序数列

3.再将这些数列两两合并；得到若干个长度为4的有序数列

4.再将它们两两合并；直接合并成一个数列为止

/ 入口
public void mergeSort(int[] arr) {
	int[] temp = new int[arr.length];
	internalMergeSort(arr, temp, 0, arr.length - 1);
}

private void internalMergeSort(int[] arr, int[] temp, int left, int right) {
	// 当left == right时，不需要再划分
	if (left < right) {
		int mid = (left + right) / 2;
		// 左右往下拆分
		internalMergeSort(arr, temp, left, mid);
		internalMergeSort(arr, temp, mid + 1, right);
		// 拆分结束后返回结果进行合并
		mergeSortedArray(arr, temp, left, mid, right);
}

// 合并两个有序子序列
public void mergeSortedArray(int[] arr, int[] temp, int left, int mid, int right) {
	int i = left;
	int j = mid + 1;
	int k = 0;
	while (i <= mid && j <= right) {
		temp[k++] = arr[i] < arr[j] ? arr[i++] : arr[j++];
	}
	// 合并完，将非空的那列拼入
	while (i <= mid) {
		temp[k++] = arr[i++];
	}
	while (j <= right) {
		temp[k++] = arr[j++];
	}
	// 把temp数据复制回原数组
	for (i = 0; i < k; i++) {
		arr[left + i] = temp[i];
	}
}

1.建一个长度为K+1的的数组C，里面的每一个元素初始都置为0(Java里面默认就是0)。

2.遍历待排序的数组，计算其中的每一个元素出现的次数，比如一个key为i的元素出现了3次，那么C[i] = 3。

3.累加C数组，获得元素的排位，从0开始遍历C，C[i+1] = C[i] + C[i-1]

4.建一个临时数组T，长度与待排序数组一样。从数组末尾遍历待排序数组，把元素都安排到T里面，直接从C里面就可以得到元素的具体位置， 不过记得每处理过一个元素之后都要把C里面对应 位置的计数减1。

public void countSort(int[] arr) {
	// 找到最大值和最小值
	int max = Integer.MIN_VALUE;
	int min = Integer.MAX_VALUE;
	for(int i = 0; i < arr.length; i++){
		max = Math.max(max, arr[i]);
		min = Math.min(min, arr[i]);
	}
	int[] b = new int[arr.length]; // 存储数组
	int[] count = new int[max - min + 1]; // 计数数组
	for (int i = 0; i < arr.length; i++) {
		int num = arr[i];
		count[num - min]++; // 每出现一个值，计数数组对应元素的值+1
		// 此时count[i]表示数值等于i的元素的个数
	}
	for (int i = 1; i < count.length; i++) {
		count[i] += count[i-1];
	}
	for (int i = 0; i < arr.length; i++) {
		int num = arr[i]; // 原数组第i位的值
		int index = count[num - min] - 1; //加总数组中对应元素的下标
		b[index] = num; // 将该值存入存储数组对应下标中
		count[num - min]--; // 加总数组中，该值的总和减少1。
	}
	// 将存储数组的值替换给原数组
	for(int i=0; i < arr.length;i++){
		arr[i] = b[i];
	}
}