一、数组排序
1. 冒泡排序
- 原理
- 从第一个元素开始,两两进行比较,将较大的数往后移,这样就将最大的数放在了最后。第二轮将第二大的数放在倒数第二个,以次类推,将元素按大小顺序排序
- 图示
- 代码实现
/**
* 利用冒泡排序法对数组进行排序
*/
public static int[] MaoPaoSequence(int[] arr) {
for (int j = 0; j < arr.length - 1; j++) {//控制多少轮
for (int i = 0; i < arr.length - 1 - j; i++) {//每执行一次就将一轮的最大值挪到最后
if (arr[i] > arr[i + 1]) {//将较大的数挪到后面
int mid = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = mid;
}
}
}
return arr;
}
2. 选择排序
- 原理
- 从0索引处开始,依次与后边的元素进行比较,小的放前面,这样子一趟下来就得到了最小值,然后从1索引处开始,得到第二个较小值,依次循环下去
- 图示
- 代码实现
public static int[] selectSequence(int[] arr) {
for (int i = 0; i < arr.length; i++) {
for (int j = i + 1; j < arr.length; j++) {
// 比较,若外层循环的数大于内层循环的数,则交换位置(将最小的数交换到最前面)
if (arr[i] > arr[j]) {
int mid = arr[i];
arr[i] = arr[j];
arr[j] = mid;
}
}
}
return arr;
}
3. 二分查找
- 原理
- 在有序数组中寻找一个元素x,先用数组的中间元素和x比较,如果相等则返回,x小于中间元素的话就在左半区寻找,大于中间元素就在右半区寻找,此时也可以用半区的中间元素进行比较,进一步缩小寻找范围,直到找到,可以采用递归的思想
- 图示
- 代码实现
/**
* 利用二分查找返回元素在有序数组中的索引,没找到则返回-1
*/
public static int getIndex(int[] arr, int num) {
int minIndex = 0;
int maxIndex = arr.length - 1;
int midIndex = (minIndex + maxIndex) / 2;
while (minIndex <= maxIndex) {
if (num == arr[midIndex]) {
return midIndex;
} else if (num > arr[midIndex]) {
minIndex = midIndex + 1;
} else {
maxIndex = midIndex - 1;
}
midIndex = (maxIndex + minIndex) / 2;
}
return -1;
}
4. 快速排序
- 原理
- 找一个基准点x,将数组中小于x的数放在x的左边,大于x的数放x的右边,这样就形成了两个分区;对两个分区执行同样的操作,一直到每个分区只有一个元素,此时数组元素就有序了,可以采用递归的方法
- 代码实现
/**
* @Description:对数组元素采用快速排序方法进行排序 .
* 1.得到左右分区的中间索引
* 2.对左边的分区再次分区
* 3.对右边的分区再次分区
* 4.重复3、4步,采用递归调用
*/
public static int[] quickSort(int[] arr, int start, int ends) {
if (start < ends) {
int index = getIndex(arr, start, ends);//得到左右分区的中间索引
quickSort(arr, start, index - 1);//对左边的区再次分区
quickSort(arr, index + 1, arr.length - 1);//对右边的区再次分区
}
return arr;
}
/**
* @Description:得到左右分区的中间索引 .
* 1.定义基准变量,默认为分区的第一个元素
* 2.从右往左遍历数组,比较数组元素
* 3.如果比基准元素小,就把这个元素填进上一个索引处
* 4.从左往右遍历数组,比较数组元素
* 5.如果比基准元素大,就把这个元素填进上一个索引处
* 6.重复2—5步骤,直到左右边界索引相遇
* 7.将开始的基准变量填入最后一个元素处,即中间索引处
* 8.返回分区的中间索引
*/
private static int getIndex(int[] arr, int start, int ends) {
int i = start;
int j = ends;
//定义基准变量
int x = arr[i];
//循环,当左右边界索引相遇时得到分区中间索引
while (i < j) {
//从右往左遍历,如果右边界的元素比基准数大,直接越过,右边界左移
while (i < j && arr[j] >= x) {
j--;
}
//如果右边界的元素比基准数小,且左边界小于右边界,将右边界的元素填入左边界对应元素中
if (i < j) {
arr[i] = arr[j];
//填完后将左边界右移一位
i++;
}
//从左往右遍历,如果左边界元素小于基准元素,则越过,左边界右移
while (i < j && arr[i] < x) {
i++;
}
//如果左边界元素比基准元素大,且左边界小于右边界,将左边界元素填入右边界对应元素中
if (i < j) {
arr[j] = arr[i];
//填完后右边界左移一位
j--;
}
}
//将基准元素填入中间索引处
arr[j] = x;
//返回中间索引
return i;
}
}
5. 插入排序
- 原理
- 将数组的第一个元素看作是一个有序数组,从第二个元素开始,将其与前面有序元素从左往右依次进行比较,当小于等于某一元素时将其插入,保证插入后也是有序的,依次将数组所有元素插入
- 代码实现
/**
* 插入排序法,对数组排序并返回
*/
public static int[] insertSort(int[] arr) {
for (int i = 1; i < arr.length; i++) {
for (int j = 0; j < i; j++) {
if (arr[i] < arr[j]) {
int mid = arr[i];
arr[i] = arr[j];
arr[j] = mid;
}
}
}
return arr;
}
}
6. 归并排序
- 原理
- 将一个右n个元素的数组拆成一个个单独的元素,这些单独的元素都可以认为是有序的,将这些单独的元素两个一组合并成n/2个有序数组,再将这n/2个有序数组合并成n/4个有序数组,最终得到长度为n的一个有序数组
- 代码实现
/**
* 归并排序方法
*/
public static void mergeSort(int[] a, int start, int end) {
if (start < end) { //递归结束条件,当子序列中只有一个元素时结束
int mid = (start + end) / 2; //划分子序列,得到中间索引
mergeSort(a, start, mid); //对左侧子序列进行递归排序
mergeSort(a, mid + 1, end); //对右侧子序列进行递归排序
merge(a, start, mid, end); //合并
}
}
/**
* 将两个子序列按顺序合并
*/
private static void merge(int[] a, int left, int mid, int right) {
int[] tmp = new int[a.length];//中间数组
int p1 = left, p2 = mid + 1, k = left;//p1、p2分别是左边界和中间边界,用来检测原数组元素的,k是给中间数组中填充元素
//当左边界小于中间边界,且中间边界小于右边界时
while (p1 <= mid && p2 <= right) {
//如果左边界处的元素小于等于中间边界处的元素(符合排序规则)
if (a[p1] <= a[p2])
//将原数组左边界的元素从左往右依次存入中间数组
//边界右移
tmp[k++] = a[p1++];
else if (a[p1] > a[p2])//如果左边界处元素大于中间边界处元素,则将中间边界处的元素依次存入中间数组
//边界右移
tmp[k++] = a[p2++];
}
while (p1 <= mid) tmp[k++] = a[p1++];//如果第一个序列未检测完,直接将后面所有元素加到合并的序列中
while (p2 <= right) tmp[k++] = a[p2++];//同上
//复制回原数组
for (int i = left; i <= right; i++) {
a[i] = tmp[i];
}
}
}
先更这么多,缺的图示后面会补上,觉得有帮助的可以点赞关注一下哦!
今天的文章java中数组排序方法都有哪些_java基础知识点整理分享到此就结束了,感谢您的阅读。
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/78058.html