Java—常见数组排序方法
文章目录
- 一、数组排序
- 1. 冒泡排序
- 2. 选择排序
- 3. 二分查找
- 4. 快速排序
- 5. 插入排序
- 6. 归并排序
一、数组排序
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];}}
}
先更这么多，缺的图示后面会补上，觉得有帮助的可以点赞关注一下哦！
发布评论