首页 / 算法 / 算法笔记:归并排序 快速排序 计数排序
算法笔记:归并排序 快速排序 计数排序
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了算法笔记:归并排序 快速排序 计数排序,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含3730字,纯文字阅读大概需要6分钟。
内容图文
![算法笔记:归并排序 快速排序 计数排序](/upload/InfoBanner/zyjiaocheng/603/fa6639d7b0444dbeb0da174d27119128.jpg)
归并排序
public static void mergeSort(int[] a) {
mergeSort(a, 0, a.length - 1);
}
public static void mergeSort(int[] a, int start, int end) {
// 递归出口:数组长度为1时
if (start >= end) {
return;
}
// 取中点
int mid = start + (end - start) / 2;
// 递归排序左半部分
mergeSort(a, start, mid);
// 递归排序右半部分
mergeSort(a, mid + 1, end);
// 运行到这里时 [start, mid] [mid + 1, end]已经各自有序 将两个有序数组合并为一个
merge(a, start, mid, end);
}
public static void merge(int[] a, int start, int mid, int end) {
int i = start, j = mid + 1, k = 0;
// 需要创建临时数组存储数组 因为同一时间内只会创建一个数组(只有位于线程的栈的顶部的方法才会被运行) 所以空间复杂度为O(n)
int[] temp = new int[end - start + 1];
while (i <= mid && j <= end) {
if (a[i] <= a[j]) {
temp[k++] = a[i++];
} else {
temp[k++] = a[j++];
}
}
while (i <= mid) {
temp[k++] = a[i++];
}
while (j <= end) {
temp[k++] = a[j++];
}
k = 0; i = start;
while (i <= end) {
a[i++] = temp[k++];
}
}
快速排序
public static void quickSort(int[] a) {
quickSort(a, 0, a.length - 1);
}
public static void quickSort(int[] a, int start, int end) {
// 递归出口:数组长度为1
if (start >= end) {
return;
}
// 分区方法:将数组分为三个部分 前半部分的所有数均小于a[pivot] 后半部分的数均大于a[pivot]
int pivot = partition(a, start, end);
// 递归排序前半部分
quickSort(a, start, pivot - 1);
// 递归排序后半部分
quickSort(a, pivot + 1, end);
}
public static int partition(int[] a, int start, int end) {
// 取最后一个数为pivot
int pivot = a[end];
// 使得[start, i-1]中的所有数为小于pivot的
int i = start;
for (int j = start; j < end; j++) {
if (a[j] < pivot) {
swap(a, i, j);
i++;
}
}
// 将最后一个数放到分割的位置上
swap(a, i, end);
// 返回其索引
return i;
}
public static void swap(int[] a, int i, int j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
// 快速选择 找到无序数组中第k大的数
public static int findKthLargest(int[] a, int k) {
return quickSelect(a, 0, a.length - 1, a.length - k);
}
public static int quickSelect(int[] a, int start, int end, int k) {
if (start >= end) {
return start;
}
int pivot = partition(a, start, end);
if (pivot == k) {
return a[pivot];
} else if (pivot > k) {
return quickSelect(a, start, pivot - 1, k);
} else {
return quickSelect(a, pivot + 1, end, k);
}
}
public static int partition(int[] a, int start, int end) {
int pivot = a[end];
int i = start;
for (int j = start; j < end; j++) {
if (a[j] < pivot) {
swap(a, i, j);
i++;
}
}
swap(a, i, end);
return i;
}
计数排序
/**
* 要求数组中的元素为非负数 且范围不能太大
*/
public static void countingSort(int[] a) {
// 确定范围
int max = a[0];
int len = a.length;
for (int i = 1; i < len; i++) {
if (a[i] > max) {
max = a[i];
}
}
// 计算每个元素的个数
int[] count = new int[max + 1];
for (int num : a) {
count[num]++;
}
// 累加个数 count[i]中的值为 <=i的数个数
for (int i = 1; i <= max; i++) {
count[i] = count[i - 1] + count[i];
}
int[] temp = new int[len];
// 从后向前遍历 将元素插入到相应位置
for (int i = len - 1; i >= 0; i--) {
temp[--count[a[i]]] = a[i];
}
System.arraycopy(temp, 0, a, 0, len);
}
/**
* 假设我们现在需要对 D,a,F,B,c,A,z 这个字符串进行排序,
* 要求将其中所有小写字母都排在大写字母的前面,
* 但小写字母内部和大写字母内部不要求有序。
* 比如经过排序之后为 a,c,z,D,F,B,A,这个如何来实现呢?
* 如果字符串中存储的不仅有大小写字母,还有数字。
* 要将小写字母的放到前面,大写字母放在最后,数字放在中间,
* 不用排序算法,又该怎么解决呢?
*/
public static void sortChar(char[] c) {
// 双指针
int i = 0, j = c.length - 1;
while (i < j) {
while (Character.isLowerCase(c[i])) {
i++;
}
while (!Character.isLowerCase(c[j])) {
j--;
}
if (i >= j) {
break;
}
swap(c, i, j);
i++;
j--;
}
j = c.length - 1;
while (i < j) {
while (Character.isDigit(c[i])) {
i++;
}
while (Character.isUpperCase(c[j])) {
j--;
}
if (i >= j) {
break;
}
swap(c, i, j);
i++;
j--;
}
}
public static void swap(char[] c, int i, int j) {
char temp = c[i];
c[i] = c[j];
c[j] = temp;
}
内容总结
以上是互联网集市为您收集整理的算法笔记:归并排序 快速排序 计数排序全部内容,希望文章能够帮你解决算法笔记:归并排序 快速排序 计数排序所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。